c - 在 C 中找到穿过物理迷宫的路径

Question

所以我们有一个机器人穿过迷宫（我不需要担心），写下检测到的墙壁和路径并将其发送给另一个机器人，该机器人将直接穿过迷宫到达出口。
我已经编写了一个 zigbee 程序来发送迷宫（二维数组），我想它应该可以工作（还不能测试它，因为我家里只有一个机器人）。
所以我的机器人得到了二维数组。例如：

1 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 0 1
1 0 0 1 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 0 1

<1> 表示墙壁，<0> 表示方式（它必须是 2 并排，因为一个数字等于 10cm / 3,9 英寸）。现在我真的不知道如何让我的机器人走上正确的道路。

标签： carraysmaze

Answer 1

如果迷宫没有循环，那么它的所有墙壁在入口和出口之间形成两条平行（尽管扭曲）的线。只需始终遵循其中之一（例如始终向右走，然后沿着自由空间的边缘走）。当然，这不是最佳路径 - 但实现起来非常简单。

如果有周期，你就不会那么容易了。您可以在 Wikipedia上阅读一些解决迷宫的算法。@nneoneo 建议的一种选择是使用 Dijkstra 的算法，其中“图形”具有所有 n^2 迷宫正方形作为节点，以及两个相邻空 ( 0) 节点之间的边。它有点占内存，但它的性能还不错，也不是很复杂。

更有趣的阅读：在迷宫中查找忒修斯的希腊神话。他用一个毛线球来追踪他的路径。