Here is a small screencast showing some randomly generated mazes. I slightly modified the code I posted on my previous post to show the solution path step by step as it is created.
Monday, July 23, 2012
Friday, July 20, 2012
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.
mymazeclass.py
mazeprogram.py
$ ./mazeprogram.py 40 40
Good Code Vs Bad Code comparison:
Take care of your code!!!
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!!!
Subscribe to:
Posts (Atom)