algorithm - 建筑物的寻路(具有多个坐标的 A*)？

1) 我在想一个游戏，我们可以 build 需要很多方 block 的建筑物，例如 3x3。

所以在开始构建之前，我需要将角色移动到相邻的图 block 。那么有一种算法可以找到到建筑物区域的最短路径吗？

我们是否必须在区域建筑物的每个地 block 上使用 A * 并选择最短的？

编辑，例如:

map :

对于这个例子，(0;0) 坐标位于具有此地标的图像的左上角: 想象你的角色在 (0;0)

我正在寻找算法来将角色移动到最靠近图像左侧的建筑物。 [ 坐标:(1;2), (8,2), (1,10), (8, 10) ]

目标不是像“正常”情况那样的单个坐标，而是一个区域(有 4 个点)。

那么找到从单个起始坐标 [此处，(0,0)] 到区域 [此处 : (1;2), (8,2), ( 1,10), (8, 10) ] ?

我想要算法返回解决方案数组，所以如果像这个例子中的多种方式:[ (0,2), (1,1) ] ，不选择解决方案，只需给我所有等效的解决方案。

2) 与没有图 block 但只有坐标的 map 系统有同样的问题？

最佳答案

嗯array/grid version of A*可以在目标区域中的任何命中停止，所以只需从起点开始增长，直到命中任何目标坐标，然后 backtrack .

是的，您也可以使用图形/矢量版本来执行此操作，您只需将任何障碍设置为节点即可。

如果您的瓷砖是(半)可步行的，那么 A* 的网格版本会更好，因为您可以利用它。您只需为每个瓷砖标记可步行区域和墙壁区域制作 2D 表示。像这样:

这也将允许您在您的建筑物中导航……但是我看不到您建筑物的内部，所以我敢打赌您直到现在才想到这一点。看看:

我正在使用 3D 网格，所以我得到了 3D 地形和建筑物也可以有等级......你只需要调整 View 以选择性地削减玩家上方的等级像这样:

关于algorithm - 建筑物的寻路(具有多个坐标的 A*)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46037819/