How to convert a maze to a Graph?

Question

I am trying to convert a maze data structure into a graph. The maze is like a grid and some walls between cells.

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

I want to convert this maze to a graph how can I do it?

score 4 · Accepted Answer · answered May 19 '12 at 14:35

4

You can do it in two ways:

1.Create an adjacency matrix from your initial matrix. The adjacency matrix is of the form:

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.Create the neighbor list for each node: j is in the neighbor list of i if there is a direct link between i and j.

answered May 19 '12 at 14:35

Tudor

61,523
12
102
142

Keep in mind that if h[i][j] == h[j][i], you only need to store/calculate half of the matrix. – Gnosophilon May 19 '12 at 14:47
See [this](http://stackoverflow.com/questions/2218322/what-is-better-adjacency-lists-or-adjacency-matrix-for-graph-problems-in-c/5419933#5419933) for some info on what to choose when considering memory efficiency – keyser May 19 '12 at 14:54

Sayem Chaklader Gearspec · Answer 2 · 2017-01-24T07:31:34.637

Think of the input data as a Adjacency matrix. Think of the maze as a path, where each connecting segment creates vertices. And each corner is a node (including start and finish) If the connection exist, there is a value in the matrix. If it doesn't you can use INF or -1 to tell that there is no route. Anyway, you can solve this using Dijkstra's shortest math algorithm. There is a lot of info on the net about it.

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

score 1 · Answer 3 · answered May 19 '12 at 14:35

1

for every neighbor cells, if there is no wall between them, make them connected in the graph.

answered May 19 '12 at 14:35

Seçkin Savaşçı

3,446
2
23
39

score 1 · Answer 4 · edited May 13 '23 at 19:39

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)]}

I have added padding of size 1 to make the code more simle , actual size of maze will be (row-1,cols-1),

How to convert a maze to a Graph?

4 Answers4