一个用于立方体表面的A星寻路算法启发式函数

Question

一个用于立方体表面的A星寻路算法启发式函数

javascriptperformancecoffeescriptpath-findinga-star

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

这个游戏世界适合什么简洁的启发式算法？

- Maros

你可以将你的图形想象成一个2D+形状的网格，它会环绕着。因此，你在A*算法中的启发式方法只需要取几个值的最小值即可（先试着想象一下如何在一个环绕的1D网格上实现）。然而，仅有1000个节点，即使在Javascript中，这真的不应该是必要的。你的代码的某些部分（或者你使用的数据结构）运行时间太长了。你需要进行一些分析，以确定哪些代码行导致了减速 - 你应该能够轻松地搜索超过1000个节点而没有明显的延迟。 - BlueRaja - Danny Pflughoeft

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- murgatroid99 · Accepted Answer

一种解决方法是，不要在一次抓取一个食物后就进行所有的寻路，而是让蛇移向下一个食物所在的一侧，当到达该侧时，使用基本的2D网格A*算法来获取食物。换句话说:

每当蛇抓取一个食物或移动到魔方的新一侧时，请执行以下操作:

如果食物在当前魔方侧面上，请使用带有2D曼哈顿距离启发式的A*算法找到到达它的路径。
如果食物在相邻的魔方侧面上，请使用相同的路径寻找算法找到边缘，该边缘与当前侧面和目标侧面相邻。
如果食物位于魔方相对面，则请使用相同的路径寻找算法找到该侧面外的路径。

这将不能保证最短的总路径，但通常会接近最短路径，而且速度更快，因为它将路径规划分成多个阶段，并为每个阶段使用更有效率的算法。