Mar*_*ska 6 javascript performance a-star path-finding coffeescript
我正在建立一个在立方体表面上玩的蛇游戏.目前它使用Dijkstra的算法进行寻路.尽管使用set和priority队列数据结构进行了优化,但它仍然有点太慢.当蛇吃食物并开始寻找新食物时,你会注意到延迟.
我试图让它使用A*而不是我找不到一个好的启发式.在有4个运动方向的平面网格上,我会使用曼哈顿距离.我已经尝试过使用3D曼哈顿距离了abs(dx) + abs(dy) + abs(dz),这个距离并不合理:对于蛇来说,游戏世界实际上是6个网格(对应于立方体的面),具有不寻常的环绕特性.
在代码中,每个方块存储在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
什么是这个游戏世界的合适,简洁的启发式？
解决这个问题的一种方法是，不要在抓住一个食物后立即进行所有寻路，而是让蛇朝有下一个食物的一侧移动，然后当它位于该侧时，使用基本的二维网格 A* 算法获取食物。换句话说：
每当蛇抓住食物或移动到立方体的新一侧时，请执行以下操作：
这不能保证最短的整体路径，但它通常应该接近最短路径，并且应该更快，因为它将寻路分为多个阶段，并为每个阶段使用更有效的算法。
