Here I'm posting a maze generation and resolve class written in python. I wanted to learn python and generating and solving mazes is a good exercise to start with.
In addition to the maze class I've written another script using pygame to show the maze and its solution path in a window.
This is my first try with python, there is for sure a best way of doing things. Please feel free to comment and suggest!
The generation algorithm creates a "Perfect" maze. This means that, assuming I wrote it correctly, for every pair of cells chosen there is always exactly one path connecting them. No loops and no isolated regions.
There are many ways for solving mazes, I choose a "Shortest Path Finder" here.
This is a very good website with tons of information about maze-types, generation algorithms, solution algorithms, etc.
Maze Class: Crate, solve and display on terminal
mymazeclass.py
1 #=============================================================================#
2 # Name : mymazeclass.py #
3 # Autor : Adrian Antonana #
4 # Date : July, 20 2012 #
5 # Description : Maze class. Constructor generates random perfect maze. Maze #
6 # can also be solved. #
7 #=============================================================================#
8
9
10 # imports
11 import random
12 import sys
13
14
15 # constants and help for list access
16 BOTTOMWALL = 0
17 RIGHTWALL = 1
18 VISITED = 2
19 UP = 0
20 RIGHT = 1
21 DOWN = 2
22 LEFT = 3
23
24
25 # maze class definition
26 class Maze:
27
28 #object constructor
29 def __init__(self,rows,cols):
30
31 # set maze size, walls and visited values
32 self.rows = rows
33 self.cols = cols
34 self.maze = [[[True,True,False] for j in range(cols)] for i in range(rows)]
35
36 # set current position, start and end point
37 # start and end points are used to solve the maze
38 # currrow is used to generate the maze
39 self.startrow = random.randrange(rows)
40 self.startcol = random.randrange(cols)
41
42 self.endrow = random.randrange(rows)
43 self.endcol = random.randrange(cols)
44
45 currrow = self.startrow
46 currcol = self.startcol
47
48 # The searh can be quite deep
49 if rows*cols > sys.getrecursionlimit():
50 sys.setrecursionlimit(rows*cols+10)
51
52 # generate the maze with depth-first algorithm
53 self._gen_maze(currrow,currcol)
54
55 # number matrix for solving
56 self.numtable = [[-1 for j in range(cols)]for i in range(rows)]
57
58 #solution path
59 self.solutionpath = []
60
61 #-----------------------------------------------------------------------------
62
63 # returns the maze in ascii characters for printing on terminal
64 def __str__(self):
65
66 # the upper wall first
67 outtable = '.'+self.cols*'_.'+'\n'
68
69 for i in range(self.rows):
70 outtable += '|'
71
72 for j in range(self.cols):
73 if self.maze[i][j][BOTTOMWALL]:
74 outtable += '_'
75 else:
76 outtable += ' '
77 if self.maze[i][j][RIGHTWALL]:
78 outtable += '|'
79 else:
80 outtable += '.'
81
82 outtable += '\n'
83
84 outtable += 'Start Point : ('+str(self.startrow)+','+str(self.startcol)+')\n'
85 outtable += 'End Point : ('+str(self.endrow)+','+str(self.endcol)+')\n'
86
87 return outtable
88
89 #------------------------------------------------------------------------------
90
91 # get a list with posible directions from the current position
92 def _get_dirs(self,r,c):
93 dirlist = []
94
95 # check limits
96 if r-1 >= 0 : dirlist.append(UP)
97 if r+1 <= self.rows-1 : dirlist.append(DOWN)
98 if c-1 >= 0 : dirlist.append(LEFT)
99 if c+1 <= self.cols-1 : dirlist.append(RIGHT)
100
101 return dirlist
102
103 #------------------------------------------------------------------------------
104
105 # generates the maze with depth-first algorithm
106 def _gen_maze(self,r,c,d=None):
107 maze = self.maze
108
109 # knock down the wall between actual and previous position
110 maze[r][c][VISITED] = True
111 if d == UP : maze[r] [c] [BOTTOMWALL] = False
112 elif d == DOWN : maze[r-1][c] [BOTTOMWALL] = False
113 elif d == RIGHT : maze[r] [c-1] [RIGHTWALL] = False
114 elif d == LEFT : maze[r] [c] [RIGHTWALL] = False
115
116 # get the next no visited directions to move
117 dirs = self._get_dirs(r,c)
118
119 # random reorder directions
120 for i in range(len(dirs)):
121 j = random.randrange(len(dirs))
122 dirs[i],dirs[j] = dirs[j],dirs[i]
123
124 # make recursive call if the target cell is not visited
125 for d in dirs:
126 if d==UP:
127 if not maze[r-1][c][VISITED]:
128 self._gen_maze( r-1,c,UP )
129 elif d==DOWN:
130 if not maze[r+1][c][VISITED]:
131 self._gen_maze( r+1,c,DOWN )
132 elif d==RIGHT:
133 if not maze[r][c+1][VISITED]:
134 self._gen_maze( r,c+1,RIGHT )
135 elif d==LEFT:
136 if not maze[r][c-1][VISITED]:
137 self._gen_maze( r,c-1,LEFT )
138
139 #------------------------------------------------------------------------------
140
141 # solve the maze by filling it with numbers(algorithm name?)
142 def _solve_maze_aux(self,r,c,n):
143 maze = self.maze
144 numtable = self.numtable
145 numtable[r][c] = n
146
147 # check if the end has been reached
148 if (r,c) != (self.endrow,self.endcol):
149 directions = self._get_dirs(r,c)
150
151 # recursive calls only if there is no wall between cells and
152 # targel cell is not marked (=-1)
153 for d in directions:
154 if d==UP and not maze[r-1][c][BOTTOMWALL] and numtable[r-1][c] == -1:
155 self._solve_maze_aux(r-1,c,n+1)
156 elif d==DOWN and not maze[r][c][BOTTOMWALL] and numtable[r+1][c] == -1:
157 self._solve_maze_aux(r+1,c,n+1)
158 elif d==RIGHT and not maze[r][c][RIGHTWALL] and numtable[r][c+1] == -1:
159 self._solve_maze_aux(r,c+1,n+1)
160 elif d==LEFT and not maze[r][c-1][RIGHTWALL] and numtable[r][c-1] == -1:
161 self._solve_maze_aux(r,c-1,n+1)
162
163 #------------------------------------------------------------------------------
164
165 # get the solution path
166 def _get_solution_path(self):
167 actrow = self.endrow
168 actcol = self.endcol
169 startrow = self.startrow
170 startcol = self.startcol
171 path = []
172 numtable = self.numtable
173 path = self.solutionpath
174
175 while (actrow,actcol) != (startrow,startcol):
176 path.append((actrow,actcol))
177 directions = self._get_dirs(actrow,actcol)
178 for d in directions:
179 if d== UP:
180 if numtable[actrow][actcol]-1 == numtable[actrow-1][actcol]:
181 actrow -=1
182 break
183 elif d== DOWN:
184 if numtable[actrow][actcol]-1 == numtable[actrow+1][actcol]:
185 actrow += 1
186 break
187 elif d== LEFT:
188 if numtable[actrow][actcol]-1 == numtable[actrow][actcol-1]:
189 actcol -= 1
190 break
191 elif d== RIGHT:
192 if numtable[actrow][actcol]-1 == numtable[actrow][actcol+1]:
193 actcol += 1
194 break
195
196 path.append((actrow,actcol))
197 path.reverse()
198
199 #------------------------------------------------------------------------------
200
201 # solve the maze
202 def solve_maze(self):
203 self._solve_maze_aux(self.startrow,self.startcol,0)
204 self._get_solution_path()
Pygame: Show maze
It is possible to print the maze on the terminal with the above class but it doesn't look very good. So I defined a few functions using pygame to show mazes properly including the solution path.
mazeprogram.py
1 #!/usr/bin/python2
2
3
4 #=============================================================================#
5 # Name : mazeprogram.py #
6 # Autor : Adrian Antonana #
7 # Date : July, 20 2012 #
8 # Description : Function definitions for drawing a maze in a window using #
9 # pygame and the maze class (mymazeclass.py) I made. #
10 #=============================================================================#
11
12 # imports
13 from mymazeclass import *
14 from sys import *
15 import pygame
16
17
18 #-------------------------------------------------------------------------------------#
19 # function definitions for drawing the maze with pygame #
20 #-------------------------------------------------------------------------------------#
21
22 # generates a window with maze with all cells isolated from each other
23 def base_window(m):
24 winwidth = m.cols*CELLSIZE+(m.cols+1)*WALLSIZE
25 winheight = m.rows*CELLSIZE+(m.rows+1)*WALLSIZE
26 w = pygame.display.set_mode((winwidth,winheight))
27 w.fill(BLACK)
28
29 for i in range(m.rows):
30 for j in range(m.cols):
31 pygame.draw.rect(w,WHITE,(WALLSIZE+(j*CELLSIZE+j*WALLSIZE),WALLSIZE+(i*CELLSIZE+
32 i*WALLSIZE),CELLSIZE,CELLSIZE))
33
34 return w
35
36 #--------------------------------------------------------------------------------------
37
38 # knocks down walls from base_window to create the path
39 def maze_window(m):
40 w = base_window(m)
41
42 for i in range(m.rows):
43 for j in range(m.cols):
44 if not m.maze[i][j][BOTTOMWALL]:
45 pygame.draw.rect(w,WHITE,(j*CELLSIZE+(j+1)*WALLSIZE,(i+1)*CELLSIZE+(i+1)
46 *WALLSIZE,CELLSIZE,WALLSIZE))
47 if not m.maze[i][j][RIGHTWALL]:
48 pygame.draw.rect(w,WHITE,((j+1)*CELLSIZE+(j+1)*WALLSIZE,i*CELLSIZE+(i+1)
49 *WALLSIZE,WALLSIZE,CELLSIZE))
50
51 pygame.display.update()
52 return w
53
54 #--------------------------------------------------------------------------------------
55
56 # paints the solution path in the maze window
57 def maze_path_window(m,w):
58 path = m.solutionpath
59
60 # print every cell within the solution path
61 for index in range(len(path)-1):
62 actrow = path[index][0]
63 actcol = path[index][1]
64 nextrow = path[index+1][0]
65 nextcol = path[index+1][1]
66 pygame.draw.rect(w,RED,(actcol*CELLSIZE+(actcol+1)*WALLSIZE,actrow*CELLSIZE+(actrow+
67 1)*WALLSIZE,CELLSIZE,CELLSIZE))
68
69 # also paint the white spaces between the cells
70 if actrow == nextrow:
71 if actcol < nextcol:
72 pygame.draw.rect(w,RED,((actcol+1)*CELLSIZE+(actcol+1)*WALLSIZE,actrow*CELLSIZE+
73 (actrow+1)*WALLSIZE,WALLSIZE,CELLSIZE))
74 else:
75 pygame.draw.rect(w,RED,(actcol*CELLSIZE+actcol*WALLSIZE,actrow*CELLSIZE+(actrow+
76 1)*WALLSIZE,WALLSIZE,CELLSIZE))
77 elif actcol == nextcol:
78 if actrow < nextrow:
79 pygame.draw.rect(w,RED,(actcol*CELLSIZE+(actcol+1)*WALLSIZE,(actrow+1)*CELLSIZE+
80 (actrow+1)*WALLSIZE,CELLSIZE,WALLSIZE))
81 else:
82 pygame.draw.rect(w,RED,(actcol*CELLSIZE+(actcol+1)*WALLSIZE,actrow*CELLSIZE+
83 actrow*WALLSIZE,CELLSIZE,WALLSIZE))
84
85
86 # add a different color for start and end cells
87 startrow = path[0][0]
88 startcol = path[0][1]
89 endrow = path[-1][0]
90 endcol = path[-1][1]
91
92 pygame.draw.rect(w,BLUE,(startcol*CELLSIZE+(startcol+1)*WALLSIZE,startrow*CELLSIZE+(
93 startrow+1)*WALLSIZE,CELLSIZE,CELLSIZE))
94 pygame.draw.rect(w,GREEN,(endcol*CELLSIZE+(endcol+1)*WALLSIZE,endrow*CELLSIZE+(endrow+
95 1)*WALLSIZE,CELLSIZE,CELLSIZE))
96 pygame.display.update()
97
98
99 #================================================================================#
100 # Main Program #
101 #================================================================================#
102
103 # sizes and colors
104 CELLSIZE = 5
105 WALLSIZE = 2
106
107 WHITE = (255,255,255)
108 BLACK = (0,0,0)
109 RED = (255,0,0)
110 GREEN = (0,255,0)
111 BLUE = (0,0,255)
112
113 # get the maze size from program arguments
114 rows = int(argv[1])
115 cols = int(argv[2])
116
117 # generate random maze, solve it
118 maze = Maze(rows,cols)
119 print maze
120
121 maze.solve_maze()
122 #print maze
123 #print maze.solutionpath
124
125 # show the maze with the solution path
126 pygame.init()
127 window = maze_window(maze)
128 maze_path_window(maze,window)
129
130 while True:
131 for event in pygame.event.get():
132 if event.type == pygame.QUIT:
133 sys.exit()
Example Screenshot
Running "mazeprogram.py" an the shell as follows:
$ ./mazeprogram.py 40 40
Generate + Solve Time
A graphic comparing maze size with generation + resolution time.
Nice Vs Ugly Code
In my first try I wrote some code without really thinking about what data structures I needed and how exactly I wanted to solve the maze generation and solution problems. As a result the "ugly" code is extremely slow when maze size increases. Here is a comparison between both codes execution times.
Good Code Vs Bad Code comparison:
Take care of your code!!!
