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

Question

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

我的迷宫周围永远有一堵墙。而且，@s是墙，如果你看不出来的话。

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

其中S为开始，E为结束。

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

1. 检查当前位置(即开始时)。如果是E，返回"path" <——哪个是…?否则，将当前位置标记为访问过的位置，并以某种方式标记它来自哪个位置…
2. 排队所有当前位置的邻居不是墙，还没有访问。
3. 对所有邻居重复1，并对邻居的所有邻居进行排队。

…我很困惑，请帮忙。我有一个类保存起始和结束的x和y坐标，以及实际迷宫的char[][]。同时，我正试图打印出迷宫的解决版本。也就是说，将最短路径位置替换为周期之类的东西。如有任何帮助，不胜感激。

Answer 1

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

Answer 2

大约7年前我在大学的时候用java和A-star算法做到了这一点。我记得，这篇文章在我的研究过程中派上了用场。您可以下载代码，看看是否有什么可以从中学到的东西。很抱歉我帮不上什么忙，我已经有一段时间没用java了

Answer 3

您可以从这个实现开始，它与您实际的问题定义非常相似。首先应该定义一个类来"解释"char[][]迷宫的信息。你应该实现(至少)的方法是:getStartPosition()， getGoalPosition()， getValidMovementsFrom(position)。这些方法允许你在地图上导航，从一个具体的位置获得所有空的邻居贴图。然后你可以使用任何合适的算法(BFS, DFS, Dijkstra, A*)来解决它，使用第三方库或你自己的实现。

您可能对这个使用A*和Java的Hipster库的问题的完整示例感兴趣。