6

我正在构建一个在立方体表面上玩的蛇游戏。目前它使用 Dijkstra 算法进行寻路。尽管对集合和优先级队列数据结构进行了优化，但它仍然有点太慢了。当蛇吃掉食物并开始寻找新食物时，您会注意到延迟。

我试图让它改用 A*，但我找不到一个好的启发式方法。在具有 4 个运动方向的平面网格上，我会使用曼哈顿距离。我尝试过使用 3D 曼哈顿距离abs(dx) + abs(dy) + abs(dz)，但没有充分的理由：对于蛇来说，游戏世界实际上是6 个网格（对应于立方体的面），具有不同寻常的环绕属性。

在代码中，每个正方形都存储在一个grid[15][15]二维数组中。有 6 个这样的数组来存储每个人脸。所以每个正方形都有一个(arrayX, arrayY, d)三元组来描述二维数组中的偏移量，并指定哪个数组。此外，每个正方形都有一个(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

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

4

1 回答 1

3

解决这个问题的一种方法是，不要在你抓住一个食物后立即进行所有寻路，而是让蛇向有下一个食物的一侧移动，然后，当它在该侧时，使用基本的获取食物的二维网格 A* 算法。换句话说：

每当蛇抓住食物或移动到立方体的新一侧时，请执行以下操作：

  • 如果食物在当前立方体的一边，使用带有 2D 曼哈顿距离启发式的 A* 算法找到它的路径
  • 如果食物在立方体的相邻边上，则使用相同的寻路算法找到一条到与当前边和目标边接壤的立方体边缘的路径。
  • 如果食物在立方体的另一边，用相同的寻路算法找到一条离开当前边的路径。

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

于 2012-12-07T07:40:39.597 回答