python: maze generation and solution

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

  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.

  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!!!