考虑一个基于 2d 网格的回合制游戏，其中一个棋子可以移动到一个未占用的单元格，只要它只需要一定数量的步骤即可到达那里。当选择该 block 时，我想突出显示所有可能的目标单元格并显示它们 - 这是我使用洪水填充递归构建可用单元格 map ，然后将其覆盖在板上的地方。一旦选择了有效的方 block ，我就会使用 A* 来找到该棋子将遵循的方 block 的路径。
直观上，这种方法似乎浪费了工作 - 我费尽心思生成了一组可行走的方 block ，结果却需要做额外的工作来搜索它并实际行走它。
这似乎是许多游戏中的常见功能，是否已经有简化的方法？或者，考虑到洪水填埋产生的网格是不规则的，但保证可以步行，那么明显的过度工作可以忽略不计吗？
最佳答案
当然，只要记住你在洪水填充期间采取的路径即可(从概念上讲，它实际上更像是广度优先搜索)。
这通常是通过在探索过程中记住前驱单元来完成的。获得最终单元格(即用户单击它)后，按照前导链接遍历路径返回，直到找到起始节点。就像您在 A* 末尾所做的那样。唯一的区别是前向传球现在是通过 BFS 方法计算的。
关于algorithm - 淹没一个区域并 build 星形路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52753716/