javascript - 立方体曲面的寻星寻路算法

我正在构建一个在多维数据集的表面上播放的snake game。目前，它使用Dijkstra的算法进行寻路。尽管对集合和优先级队列数据结构进行了优化，但它仍然有些慢。您会注意到蛇进食某种食物并开始寻找新食物时的延迟。

我正在尝试使用A *代替它，但是我找不到很好的启发式方法。在具有4个运动方向的平面网格上，我将使用曼哈顿距离。我试过使用3D Manhattan距离abs(dx) + abs(dy) + abs(dz)，但这没有充分理由，这是有道理的:对于蛇来说，游戏世界真的是6 grids (corresponding to the faces of the cube)，具有异常的环绕属性。

在代码中，每个方块都存储在grid[15][15] 2D数组中。有6个这样的数组来存储每个面。因此，每个正方形都有一个(arrayX, arrayY, d)三元组，以描述2D数组中的偏移量并指定哪个数组。此外，每个方块都有一个(x, y, z)三元组，描述了空间位置。

这是寻路发生的游戏代码区域:

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

这是A *的库代码:

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

对于这个游戏世界，什么是合适的，简洁的启发式方法？

最佳答案

解决此问题的一种方法是，不要立即捕获一条食物就进行所有寻路，而是将蛇移到具有下一个食物的那一侧，然后在它位于那一侧时使用基本的2D网格A *算法可获取食品。换句话说:

每当蛇捕获食物或移动到立方体的新边时，请执行以下操作:

如果食品在当前多维数据集侧，请使用A *算法和2D Manhattan距离启发式

查找到该食品的路径

如果食品位于立方体的相邻侧，请使用相同的寻路算法找到与当前侧和目标侧接壤的立方体边缘的路径。

如果食品在立方体的另一侧，请使用相同的寻路算法在当前侧找到一条路径。

这不能保证总路径最短，但通常应接近最短路径，并且应该更快，因为它会将寻路分为多个阶段，并为每个阶段使用了更高效的算法。