我正在构建一个在立方体表面上播放的snake game . 目前它使用Dijkstra的算法进行寻路 . 尽管使用set和priority队列数据结构进行了优化，但它仍然有点太慢 . 当蛇吃食物并开始寻找新食物时，你会注意到延迟 .
我找到了一个很好的启发式方法 . 在有4个运动方向的平面网格上，我会使用曼哈顿距离 . 我已经尝试过使用3D曼哈顿距离 abs(dx) + abs(dy) + abs(dz) 这种情况并不合理：对于蛇来说，游戏世界真的是6 grids (corresponding to the faces of the cube)具有不寻常的环绕特性 .
在代码中，每个方块存储在 grid[15][15] 2D数组中 . 每个面都有6个这样的数组 . 因此每个方块都有一个 (arrayX, arrayY, d) 三元组来描述2D数组中的偏移并指定哪个数组 . 此外，每个方块都有一个描述空间位置的三元组 .
这是寻路发生的游戏代码区域：
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
什么是这个游戏世界的合适，简洁的启发式？
1 回答
解决这个问题的一种方法是，一旦你 grab 一个食品项目，而不是做所有的寻路，让蛇朝着有下一个食品的一侧移动，然后，当它在那边时，使用一个基本的2D网格A *算法来获取食物项目 . 换一种说法：
每当蛇 grab 食物或移动到立方体的新侧时，请执行以下操作：
如果食物项位于当前立方体侧，请使用带有2D曼哈顿距离启发式的A *算法找到它的路径
如果食物项位于立方体的相邻侧，请使用相同的寻路算法找到与当前侧和目标侧接壤的立方体边缘的路径 .
如果食物项位于立方体的另一侧，请使用相同的寻路算法找到当前侧的路径 .
这不能保证最短的整体路径，但通常应该接近最短路径，并且它应该更快，因为它将路径寻找分成多个阶段，并为每个阶段使用更有效的算法 .