java - 在图中寻找路径？（全球定位系统）？

Question

我游戏中的城市本质上是道路和十字路口的图表。

每条道路都有对起点和终点交叉口的引用。

每个交叉路口都有对顶部、左侧、底部、右侧道路的引用，如果它是 3 路、2 路路口等，则为 null。

道路是长方形的。

鉴于此，有没有办法生成从道路 A 到道路 B 的路径？（比说 A* 更简单的事情？

谢谢

Answer 1

由于该图未加权，您可以尝试BFS - 尽管它不知情并且可能会比 A* 算法慢（对 A* 具有合理的启发式函数）。

您可以通过执行双向 BFS来加快它的速度——这在未加权图中也是最佳的，并且应该比标准 BFS 快得多。
双向 BFS 的想法很简单：在“同一时间”（一个接一个）从头到尾执行一个 BFS 步骤（深度 1，深度 2，...），一旦你发现两个搜索的前沿相交 - 你有你的路径。
它要快得多，因为每个方向只搜索到中间，为您提供O(2 * B^(d/2)) = O(B^(d/2))要探索的总节点（d最佳解决方案的深度在哪里，并且B是分支因子 - 在您的情况下为 4），而常规 BFS 是O(B^d)

Answer 2

Dijkstra 的算法非常简单。

Answer 3

如果您不想自己实现所有路径查找算法，我强烈推荐JGraphT。它是满足您所有图形需求的优秀库。它可以通过返回边列表为您找到最短路径。

不过，它当然有一个学习曲线。我一开始想使用 WeightDirectedGraphs，后来在谷歌上搜索了一下才找到合适的使用方法。

编辑：我刚刚注意到您将您的帖子标记为 Java 和 C++，但 JGraphT 是一个 Java 库（正如名称中的 J 所暗示的那样）。