如何将迷宫转换为图形

Question

我正在尝试将迷宫数据结构转换为图形。迷宫就像一个网格和牢房之间的一些墙壁。

maze[8][8][4] is how the maze is represented.
If maze[i][j][0] = 1 it means you can't go up from (i,j)
if maze[i][j][1] = 1 it means you can't go down from (i,j)
// and so on

我想将这个迷宫转换为图形，我该怎么做？

Answer 1

您可以通过两种方式执行此操作：

1.从初始矩阵创建邻接矩阵。邻接矩阵的形式为：

h[i][j] = 0, if there is no direct link from i to j 
(i and j are not neighbors in the maze)
h[i][j] = 1, if there is a direct link from i to j 
(i and j are neighbors in the maze)

2.为每个节点创建邻居列表：如果i和j之间存在直接链接，则j位于i的邻居列表中。

Answer 2

将

输入数据视为邻接矩阵。将迷宫视为一条路径，其中每个连接段创建顶点。并且每个角都是一个节点(包括开始和结束( 如果连接存在，则矩阵中有一个值。如果没有，可以使用 INF 或 -1 来告知没有路由。无论如何，您可以使用Dijkstra最短的数学算法来解决这个问题。网上有很多关于它的信息。

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

Answer 3

对于每个相邻单元格，如果它们之间没有墙，则使它们在图形中连接。

Answer 4

game = [[1, 1, 1, 1, 1, 1, 1],
        [1, 'A', 1, 1, 0, 0, 1],
        [1, 0, 0, 0, 0, 1, 1],
        [1, 0, 0, 1, 1, 1, 1],
        [1, 1, 0, 0, 0, 'B', 1],
        [1, 1, 1, 1, 1, 1, 1]]
rows = len(game)
cols = len(game[0])
graph = {}
for i in range(1, rows - 1):
    for j in range(1, rows - 1):
        if game[i][j] != 1:
            adj = []
            for ele in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if game[ele[0]][ele[1]] == 0 or game[ele[0]][ele[1]] == 'B':
                    adj.append((ele[0], ele[1]))
            graph[(i, j)] = adj
print(graph)
    {(1, 1): [(2, 1)],
    (1, 4): [(2, 4), (1, 5)],
    (1, 5): [(1, 4)],
    (2, 1): [(3, 1), (2, 2)],
    (2, 2): [(3, 2), (2, 1), (2, 3)],
    (2, 3): [(2, 2), (2, 4)],
    (2, 4): [(1, 4), (2, 3)],
    (3, 1): [(2, 1), (3, 2)],
    (3, 2): [(2, 2), (4, 2), (3, 1)],
    (4, 2): [(3, 2), (4, 3)],
    (4, 3): [(4, 2), (4, 4)],
    (4, 4): [(4, 3), (4, 5)],
    (4, 5): [(4, 4)]}

我添加了大小为 1 的填充以使代码更加简单，迷宫的实际大小将是(行-1，cols-1(，