How to convert a maze to a Graph?
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?
Answer
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.