Galaxy108
Back

Path finding improvements2 min read

path finding improvements feature image

Development Log: Pathfinding Algorithm Improvements

Over the past month, I have dedicated significant effort to refining and improving various details in Galaxy108, with a particular focus on the pathfinding algorithm. As a seamless, ultra-large-scale sandbox game, traditional grid-based A-star algorithms are not suitable for our needs. Here's an overview of the improvements I've made:

Map Data Structure: Dual-Mesh System

Galaxy108's map data is based on a nested dual-mesh system:

  1. First Layer (Region Level):
    • The polygons of the first dual-mesh form the region blocks of the world map.
  2. Second Layer (Property Level):
    • Each region's polygon edges generate a second dual-mesh.
    • The polygons in this layer serve as property blocks, where random elements like plants, resources, furniture, and farmland are generated.

Pathfinding Algorithm: Quad-Grid Approach

To support pathfinding in this complex structure, I implemented a quad-grid system for each region:

  • Grid Resolution: Each region is divided into a quad-grid with a minimum resolution of 0.5 meters, serving as the basic nodes for the pathfinding algorithm.
  • Advantages:
    • Minimizes the number of nodes for random or regular placement of rigid bodies within limited areas.
    • Reduces computational cost while maintaining high precision.
    • Supports pathfinding for objects as small as 0.5 meters.

For those interested in the technical details, I've open-sourced the algorithm (including a demo) on GitHub:
Quad-Grid Pathfinding Algorithm

Seamless Cross-Region Pathfinding

  • NPCs can now navigate seamlessly between regions (A to B) without interruption, thanks to overlapping spaces between adjacent regions.
  • Limitation: Pathfinding continuity may be blocked if there are long rigid walls spanning multiple regions.

These improvements ensure that Galaxy108's pathfinding system is both efficient and precise, providing a smooth and immersive experience for players. Stay tuned for more updates as I continue to refine the game!

开发日志：路径算法改进

在过去的一个月里，我投入了大量精力来完善和改进 Galaxy108 的细节，特别是 路径算法。作为一款无缝的超大地图沙盒游戏，传统的基于网格的 A-star 算法并不适合我们的需求。以下是我们的改进概述：

地图数据结构：双网格系统

Galaxy108 的地图数据基于 嵌套的双网格系统：

  1. 第一层（区域层级）：
    • 第一层双网格的多边形组成了世界地图的 区域区块。
  2. 第二层（场景层级）：
    • 每个区域的多边形边缘生成第二层双网格。
    • 该层的多边形作为 场景块，随机生成植物、资源、家具和耕地等元素。

路径算法：四叉网格方法

为了在这种复杂结构中支持路径查找，我为每个区域实现了 四叉网格系统：

  • 网格分辨率：每个区域被划分为最小分辨率为 0.5 米 的四叉网格，作为路径算法的基本节点。
  • 优点：
    • 在有限区域内随机或规律放置刚体时，最小化节点数量。
    • 降低计算成本，同时保持高精度。
    • 支持最小 0.5 米 物体的路径查找。

对技术细节感兴趣的朋友，我已将算法（包括演示）开源在 GitHub 上：
四叉网格路径查找算法

无缝跨区域路径查找

  • 由于相邻区域之间的重叠空间，NPC 现在可以在区域之间（从 A 到 B）无缝导航而不会中断。
  • 限制：如果有 跨越多个区域的超长刚体墙，可能会阻挡路径查找的连贯性。

这些改进确保了 Galaxy108 的路径查找系统既高效又精确，为玩家提供了流畅且沉浸式的体验。敬请期待更多更新，我将继续优化游戏！