javascript - 如何为六边形域实现 BFS(在 javascript 中)

Question

我从事基于六边形 map 的浏览器游戏。我有这个:http://www.dark-project.cz/wesnoth/map-view/1现在我有一个问题，我想标记单位可以去的领域(它的移动有限)。如果 movement 为 1，则没有任何问题，但如果它更高，则无法正常工作(尝试一下)。

我使用坐标系 http://www.dark-project.cz/wesnoth/coor.png

我的实际 js 在这里:http://www.dark-project.cz/wesnoth/js/map/base.js

在其他问题(Movement algorithm on a hexagon map)@unkulunkulu 推荐我使用 BFS 算法。但我没有像这样的算法的经验，也没有将其实现到 javascript 中，然后在六边形 map 上使用它的经验。他说 B​​FS 算法对此更好，因为我以后可以轻松扩展它(添加一些障碍等)。

如果你有关于这个或类似内容的 javascript 教程的一些链接，那将是惊人的。

Answer 1

建议的算法大致是这样的:

1. 取起始方 block 并将其标记为距离 0。将其添加到已处理的六边形列表中。

2. 找到所有有效的相邻六 Angular 形(即您可以进入的六 Angular 形)。

3. 将所有这些方 block 标记为距离 1。将它们添加到已处理的六边形列表中。

4. 查找与距离为 1 的六 Angular 形相邻但不在已处理的六 Angular 形列表中的所有有效六 Angular 形。

5. 将所有这些方 block 标记为距离 2。将它们添加到已处理的六边形列表中。

...

X。找到所有不在已处理的六 Angular 形列表中的与距离 N 六 Angular 形相邻的有效六 Angular 形。

X+1。将所有这些方 block 标记为距离 N+1。将它们添加到已处理的十六进制列表中。

广度优先搜索的思想是从内部迭代出所有可能性，这样您总能找到到每个六边形的最短距离。

在 Unkulunkulu 的评论之后，我重新考虑了对此的最佳实现(并且可能会在进一步输入后再次更改)。您应该有一个如上所述的已处理十六进制列表以及一个等待处理的十六进制队列。未处理的十六进制列表仅从距离为 0 的起始十六进制开始，您将遍历此列表直到它用完。当处理一个六 Angular 形时，所有新发现的未处理的六 Angular 形都被添加到这个列表中，并带有它们的距离。所以一旦你处理了距离为 0 的十六进制，你应该添加所有距离为 1 的六 Angular 形。它们得到处理，当它们完成时，您将拥有所有距离 2 个六 Angular 形...

就其值(value)而言，我认为我最初的递归建议从效率的 Angular 来看是失败的，并且取决于您想要解决潜在堆栈溢出问题的距离。 :)