3

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?

false
  • 10,533
  • 12
  • 98
  • 192
Salih Erikci
  • 4,976
  • 11
  • 36
  • 68

4 Answers4

3

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.

Tudor
  • 60,450
  • 12
  • 98
  • 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
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/

Sayem Chaklader Gearspec
  • 131
  • 5
1

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

Seçkin Savaşçı
  • 3,326
  • 2
  • 22
  • 38
0
    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 i 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),

dar ali
  • 1