java - 如何开始从 Java 中的迷宫矩阵制作最短路径迷宫求解器？

Question

所以我想创建一个解决迷宫的最短路径迷宫求解器。迷宫类似于这样:

我的迷宫周围总是有一堵墙。另外，如果你看不出的话，@s 就是墙。

@@@@@@@@
@   S@ @
@@@ @@E@
@   @  @
@@@   @@
@@@@@@@@

其中 S 是起点，E 是终点。

我想应用 Dijkstra 算法，但我不明白如何实际实现它。就像:

1. 检查当前位置(从头开始)。如果是 E，则返回“path” <-- 这是...？否则，将当前位置标记为已访问，并以某种方式标记它来自哪个位置...
2. 将所有当前位置的邻居(不是墙壁且尚未访问过)排入队列。
3. 对所有邻居重复 1，并将邻居的所有邻居放入队列。

...我很困惑，请帮忙。我有一个类，它保存开始和结束的 x 和 y 坐标，以及实际迷宫的 char[][] 。另外，我正在尝试打印迷宫的已解决版本。也就是说，用句点之类的东西替换最短路径位置。非常感谢任何帮助。

Answer 1

最广泛使用和最有效的寻路算法之一是 A* Pathfinding Algorithm虽然这可能超出您的需求，但它经常用于游戏和其他形式的计算机科学，并且可以根据您的需求进行扩展。