The algorithm starts at a random cell.
Mark the current cell as visited, and get a list of its neighbors.
Now, for each neighbor, starting with a randomly selected neighbor.
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor.
Use this recourse idea with that neighbor as the current cell.
Let's see the source code:
import os
import pygame
from pygame.locals import *
from random import choice
# create a maze cell with rect sized 6 pixels
class maze_cell(pygame.sprite.Sprite):
w, h = 6, 6
def __init__(self, x, y, maze):
pygame.sprite.Sprite.__init__(self)
self.image = pygame.Surface([self.w, self.h])
self.image.fill((0, 0, 255))
self.rect = self.image.get_rect()
self.rect.x = x * self.w
self.rect.y = y * self.h
self.x = x
self.y = y
self.maze = maze
self.nbs = [(x + nx, y + ny) for nx, ny in ((-2, 0), (0, -2), (2, 0), (0, 2))
if 0 <= x + nx < maze.w and 0 <= y + ny < maze.h]
# draw screen with pygame blit
def draw(self, screen):
screen.blit(self.image, self.rect)
# create the maze wall
class maze_wall(maze_cell):
def __init__(self, x, y, maze):
super(maze_wall, self).__init__(x, y, maze)
self.image.fill((0, 0, 0))
self.type = 0
# create the maze by generate into grid
class create_maze:
def __init__(self, size):
self.w, self.h = size[0] // maze_cell.w, size[1] // maze_cell.h
self.grid = [[maze_wall(x, y, self) for y in range(self.h)] for x in range(self.w)]
def get(self, x, y):
return self.grid[x][y]
def place_maze_wall(self, x, y):
self.grid[x][y] = maze_wall(x, y, self)
def draw(self, screen):
for row in self.grid:
for maze_cell in row:
maze_cell.draw(screen)
def generate(self, screen=None, animate=False):
unvisited = [c for r in self.grid for c in r if c.x % 2 and c.y % 2]
cur = unvisited.pop()
stack = []
while unvisited:
try:
n = choice([c for c in map(lambda x: self.get(*x), cur.nbs) if c in unvisited])
stack.append(cur)
nx, ny = cur.x - (cur.x - n.x) // 2, cur.y - (cur.y - n.y) // 2
self.grid[nx][ny] = maze_cell(nx, ny, self)
self.grid[cur.x][cur.y] = maze_cell(cur.x, cur.y, self)
cur = n
unvisited.remove(n)
if animate:
self.draw(screen)
pygame.display.update()
pygame.time.wait(10)
except IndexError:
if stack:
cur = stack.pop()
def draw_maze(screen):
maze = create_maze(WINSIZE)
maze.generate(screen, True)
WINSIZE = (maze_cell.w * 76, maze_cell.h * 76)
def main():
pygame.init()
screen = pygame.display.set_mode(WINSIZE)
pygame.display.set_caption('Generate maze')
screen.fill((0, 0, 0))
clock = pygame.time.Clock()
draw_maze(screen)
done = 0
while not done:
for e in pygame.event.get():
if e.type == QUIT or (e.type == KEYUP and e.key == K_ESCAPE):
done = 1
pygame.display.update()
clock.tick()
if __name__ == '__main__':
main()
