我正在为我正在研究的某些AI找到正确的寻路算法 .
我有球员在球场上，自由移动（没有粘在网格上），但他们被限制在8个方向移动（N NE E等）
我正在努力使用A *和一个图表 . 但我意识到，图表上的每个节点都相距很远，并且所有边缘都具有相同的权重 - 因为节距是矩形的 . 并且节点的数量是巨大的（大间距，它们能够在1个像素和另一个像素之间移动）
我想必须有另一种算法，针对这种事情进行了优化？
我会把音调分成10x10像素网格 . 您的路由不必像系统的其他部分那样精细，它使算法占用的内存要少得多 .
正如克里斯所说，选择合适的启发式算法是让算法适合你的关键 .
如果玩家在网格上的点之间沿直线移动，则实际上不需要使用A * . Bresenham's line algorithm将非常快速地提供直线路径 .
您可以根据另一种启发式对方向进行加权 . 因此，与基于实际距离的路径加权相反，您可以根据另一个因素（例如“与其他玩家的亲密度”）来加权或缩放，这意味着玩家将偏向不会与其他玩家发生碰撞的路线 .
A *算法应该像这样工作得很好 .
我想你应该试试Jump Point Search . 它是一种非常快速的8-dire路径查找算法 .
这是一个描述Jump Point Search的blog .
而且，这是它的学术论文<Online Graph Pruning for Pathfinding on Grid Maps>
此外，Youtube上还有一些有趣的视频 .
我希望这有帮助 .
4 回答
我会把音调分成10x10像素网格 . 您的路由不必像系统的其他部分那样精细，它使算法占用的内存要少得多 .
正如克里斯所说，选择合适的启发式算法是让算法适合你的关键 .
如果玩家在网格上的点之间沿直线移动，则实际上不需要使用A * . Bresenham's line algorithm将非常快速地提供直线路径 .
您可以根据另一种启发式对方向进行加权 . 因此，与基于实际距离的路径加权相反，您可以根据另一个因素（例如“与其他玩家的亲密度”）来加权或缩放，这意味着玩家将偏向不会与其他玩家发生碰撞的路线 .
A *算法应该像这样工作得很好 .
我想你应该试试Jump Point Search . 它是一种非常快速的8-dire路径查找算法 .
这是一个描述Jump Point Search的blog .
而且，这是它的学术论文<Online Graph Pruning for Pathfinding on Grid Maps>
此外，Youtube上还有一些有趣的视频 .
我希望这有帮助 .