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?

Moskow

Answer 1

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.

Ade

Keep in mind that if h[i][j] == h[j][i], you only need to store/calculate half of the matrix. – Inferior

See this for some info on what to choose when considering memory efficiency – Stepsister

Answer 2

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/

Hornblende

Answer 3

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

Vanguard

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

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

Olenolin