next »

[Cthulhu32]

I've decided to write a quick tutorial on the Maze Generator/Solver I made a few days ago, and hopefully you will learn some of the beginnings of Python and Pygame through this little lecture. This tutorial expects you to have a moderate understanding of programming concepts and data structures, in particular arrays, ints, binary comparison, and loops.

The first thing you will need is Python 2.6.1 and Pygame 1.8.1 installed on your system. There are various ways to go about this for Windows, Mac, and Linux, but I'd suggest going to the following places:

Download Python 2.6.1 from here (install first!)
http://www.python.org/download/

Download Pygame 1.8.1 from here
http://www.pygame.org/download.shtml

Okay, now that we have Python and Pygame installed on our system, next we want to start out with a base py file. Create a new file called Maze.py, and open with either your favorite text editor, or the Python Idle Interpreter in Windows by right clicking, and selecting "Edit with IDLE." Now you should see a nice empty Maze.py file, and we shall begin our actual code.

Just to give a little background on Python if you are unfamiliar with it, typing is all automatic so you can declare anything as anything. For example, you can say "A = 5" "A = 'beeeeees'" and it will interpret that as "hey, A was an integer of 5, now A is a string with 'beeeeees'!" Also, Python is indent sensitive, so when you say something such as "if so and so", you will need to end your if statement with a :, and indent exactly 4 spaces to the next line to indicate its wrapped inside of that if.

C Syntax

Code:

if ( a == 5 ){
	b = 3;
}

Python Syntax

Code:

if a == 5:
	b = 3

First, we will want to make a quick skeleton to build on top of, and here is a very simple way to do it.

Code:

# import Pygame and Random
import pygame, random
# import all of the variables in pygame.locals to make our code easier
from pygame.locals import *

# Simple main function
def main():
	pygame.init() # initialize the pygame system

	return	# do nothing for now

# Python calls for __main__ in the __name__ so we tell it to call main() when that happens
if __name__ == '__main__': main()

Okay, now we have the base for our application, and we can begin adding some simple graphics code to start things up. We want to make a screen that is 640 x 480, with a heading of our choice, and we want to fill it in with lines representing a maze. So first, we need to declare a new screen representing our display area, and we also want to have a background that fills in the screen behind our maze.

Code:

	pygame.init()
	# Create a new screen from the pygame.display, and set the mode to 640x480
	screen = pygame.display.set_mode((640,480))
	pygame.display.set_caption('Tig Maze!')
	pygame.mouse.set_visibile(0)
	
	# Declare our background as a pygame surface, with the same size as the screen display
	background = pygame.Surface(screen.get_size())
	background = background.convert()
	background.fill((255,255,255))

Now we have started the pygame system, we have a screen to draw to, and we have a background to draw on, so we want to blit the background, flip the screen, and begin our while(1) main loop. We also want to create a clock used to keep track of our 60fps counter.

Code:

	screen.blit(background, (0,0))
	pygame.display.flip()
	clock = pygame.time.Clock()	
	while 1:
		clock.tick(60)
		screen.blit(background, (0,0))
		pygame.display.flip()

When we flip the display, we are drawing everything that is on the screen onto the actual surface we see, so after each flip, the screen is updated. If we wanted to hold off on drawing while physics are updated, we could remove the blits and flips, and use a fancy frame skipping technique, but that will come another day.

Next, we want to check for the user input in the while loop, to see if they have either closed the program, or pressed escape to exit. Without this, the program will lag and become unresponsive.

Code:

	while 1:
		clock.tick(60)
		for event in pygame.event.get(): # grab each event from the pygame event list
			if event.type == QUIT:
				return
			elif event.type == KEYDOWN:
				if event.key == K_ESCAPE:
					return
		screen.blit(background, (0,0))
		pygame.display.flip()

So now lets put this all together and look at what we have so far. We have the imports, main function, pygame initialization, screen and background creation code, a main while loop that returns when the user exits or presses escape, and a constant screen flipping to ensure our drawing works properly.

Code:

import pygame, random
from pygame.locals import *

def main():
	pygame.init()
	screen = pygame.display.set_mode((640,480))
	pygame.display.set_caption('Tig Maze!')
	pygame.mouse.set_visible(0)

	background = pygame.Surface(screen.get_size())
	background = background.convert()
	background.fill((255,255,255))

	screen.blit(background, (0,0))
	pygame.display.flip()
	clock = pygame.time.Clock()
	
	while 1:
		clock.tick(60)
		for event in pygame.event.get():
			if event.type == QUIT:
				return
			elif event.type == KEYDOWN:
				if event.key == K_ESCAPE:
					return
		screen.blit(background, (0,0))
		pygame.display.flip()

if __name__ == '__main__': main()

Now we are ready to create and draw a maze!

[Cthulhu32]

The first thing we will want to do when creating the actual Maze logic is create a Maze class. Classes are extremely simple in Python, and the only necessary thing in a class is the constructor, declared as __init__. Lets create a maze that has the following three functions: init, update, and draw.

Code:

class Maze:
	def __init__(self):
		self.state = 'idle'

	def update(self):
		if self.state == 'idle':
			print "Idling"

	def draw(self, screen):
		pass # do some drawing here

And in our skeleton, we can now add a new instance of a Maze, and do update and draw code.

Code:

	......

	background = pygame.surface(screen.get_size())
	background = background.convert()
	background.fill((255,255,255))
	
	newMaze = Maze()

	......

		clock.tick(60)
		for event in pygame.event.get():
			if event.type == QUIT:
				return
			elif event.type == KEYDOWN:
				if event.key == K_ESCAPE:
					return
		newMaze.update()
		screen.blit(background, (0,0))
		newMaze.draw(screen)
		pygame.display.flip()

So we now have a maze class inside of our main loop, it updates, it draws, it slices, it dices! Now the maze will need to do the following things inside of its class: create an array representing every possible combination, update a drawing of the maze, keep track of this array after its completed and solve the maze. Its up to the programmer which parts of this process are seen and which are done before the next drawing loop. But I will write both a creator based on the frame counter, and a solver based on the counter.

Lets start making this maze class bigger by identifying what we need to create and solve a maze: first we should go check out http://www.mazeworks.com/mazegen/mazetut/index.htm and take a look at the Depth-First Search algorithm. It is pretty simple in psuedo code, and we will take advantage of the 16-bit schema used in their example

create a CellStack (LIFO) to hold a list of cell locations
set TotalCells = number of cells in grid
choose a cell at random and call it CurrentCell
set VisitedCells = 1
 
while VisitedCells < TotalCells

      find all neighbors of CurrentCell with all walls intact 
      if one or more found
            choose one at random
            knock down the wall between it and CurrentCell
            push CurrentCell location on the CellStack
            make the new cell CurrentCell
            add 1 to VisitedCells
      else
            pop the most recent cell entry off the CellStack
            make it CurrentCell
      endIf

endWhile

We will assume that each cell is 8x8, which gives us 80 cells by 60 cells on a 640x480 screen. So Total Cells = 80*60 or 4800. And we can draw this cell grid by drawing straight lines for each cell on the x and y axis, then drawing translucent lines on top of that when we want to break down a wall. We also want to draw the solution as boxes represnting each grid point, but we will get to that after we have a maze working.

So lets make a maze, give it a maze array represnting each square, a cell stack used in the DFS algorithm, a drawing layer, pass it into the Maze constructor (init), and start drawing some grid marks.

Code:

class Maze:
	def __init__(self, mazeLayer):
		self.mazeArray = []
		self.state = 'idle'
		self.mLayer = mazeLayer
		self.mLayer.fill((0, 0, 0, 0)) # fill it with black translucent
		for y in xrange(60):
			pygame.draw.line(self.mLayer, (0,0,0,255), (0, y*8), (640, y*8))
			for x in xrange(80):
				self.mazeArray.append(0x0000)
				if ( y == 0 ):
					pygame.draw.line(self.mLayer, (0, 0, 0, 255), (x*8, 0), (x*8, 480))
		self.totalCells = 4800
		self.cellStack = []

	def update(self):
		if self.state == 'idle':
			pass
		elif self.state == 'create':
			pass # start creating!
	
	def draw(self, screen):
		screen.blit(self.mLayer, (0, 0))

........

	
	background = pygame.surface(screen.get_size())
	background = background.convert()
	background.fill((255,255,255))

	mazeLayer = pygame.surface(screen.get_size())
	mazeLayer = mazeLayer.convert_alpha() # give it some alpha values
	mazeLayer.fill((0,0,0,0,))

	newMaze = Maze(mazeLayer)

Lets put this all together, and watch how we go from a blank screen to a screen full of grid!

Code:

import pygame, random
from pygame.locals import *

class Maze:
	def __init__(self, mazeLayer):
		self.mazeArray = []
		self.state = 'idle'
		self.mLayer = mazeLayer
		self.mLayer.fill((0, 0, 0, 0)) # fill it with black translucent
		for y in xrange(60):
			pygame.draw.line(self.mLayer, (0,0,0,255), (0, y*8), (640, y*8))
			for x in xrange(80):
				self.mazeArray.append(0x0000)
				if ( y == 0 ):
					pygame.draw.line(self.mLayer, (0, 0, 0, 255), (x*8, 0), (x*8, 480))
		self.totalCells = 4800
		self.cellStack = []

	def update(self):
		if self.state == 'idle':
			pass
		elif self.state == 'create':
			pass # start creating!
	
	def draw(self, screen):
		screen.blit(self.mLayer, (0, 0))

def main():
	pygame.init()
	screen = pygame.display.set_mode((640,480))
	pygame.display.set_caption('Tig Maze!')
	pygame.mouse.set_visible(0)

	background = pygame.surface(screen.get_size())
	background = background.convert()
	background.fill((255,255,255))

	mazeLayer = pygame.surface(screen.get_size())
	mazeLayer = mazeLayer.convert_alpha() # give it some alpha values
	mazeLayer.fill((0,0,0,0,))

	newMaze = Maze(mazeLayer)

	screen.blit(background, (0,0))
	pygame.display.flip()
	clock = pygame.time.Clock()
	
	while 1:
		clock.tick(60)
		for event in pygame.event.get():
			if event.type == QUIT:
				return
			elif event.type == KEYDOWN:
				if event.key == K_ESCAPE:
					return
		newMaze.update()

		screen.blit(background, (0,0))
		newMaze.draw(screen)
		pygame.display.flip()

if __name__ == '__main__': main()

Viola, we are now ready to start creating a maze using the Depth First Search seen on MazeWorks! So first we need to set our state to "create" so the update function knows that it needs to work on creating the maze, then we need to integrate from psuedo code to actual code. So lets fill in a few extra values we missed in the init function required, create a compass to help us in looking at neighbor squares, and start working on that update function!

Code:

class Maze:
	def __init__(self, mazeLayer):
		self.mazeArray = []
		self.state = 'create'
		self.mLayer = mazeLayer
		self.mLayer.fill((0, 0, 0, 0))
		for y in xrange(60): # 80 wide + 60 tall
			pygame.draw.line(self.mLayer, (0,0,0,255), (0, y*8), (640, y*8))
			for x in xrange(80):
				self.mazeArray.append(0)
				if ( y == 0 ):
					pygame.draw.line(self.mLayer, (0,0,0,255), (x*8,0), (x*8,480))
		self.totalCells = 4800 # 80 * 60
		self.currentCell = random.randint(0, self.totalCells-1)
		self.visitedCells = 1
		self.cellStack = []
		self.compass = [(-1,0),(0,1),(1,0),(0,-1)]

Notice how my currentcell is a random cell from 0, to total cells -1, that is because we created a mazeArray that has 4800 items inside of it, but at 4800 we error since we are going from 0-4799 (0 based!) Our compass is also backwards from the tutorial, but it is setup for [ West, South, East, North ]

Now we can make an update loop that uses the variables declared in __init__, and we can start really getting this thing working.

Code:

	def update(self):
		if self.state == 'create':
			#while VisitedCells < TotalCells 
			if self.visitedCells >= self.totalCells:
				self.currentCell = 0 # set current to top-left
				self.cellStack = []
				self.state = 'solve'
				return

			x = self.currentCell % 80
			y = self.currentCell / 80

			#find all neighbors of CurrentCell with all walls intact
			neighbors = []
			for i in xrange(4):
				nx = x + self.compass[i][0]
				ny = y + self.compass[i][1]
				
				# Check the borders
				if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):
					# Has it been visited?
					if (self.mazeArray[(ny*80+nx)] & 0x000F) == 0:
						nidx = ny*80+nx
						neighbors.append((nidx,1<<i))
      			#if one or more found
			if len(neighbors) > 0:
				
				#choose one at random
				idx = random.randint(0,len(neighbors)-1)
				nidx,direction = neighbors[idx]

				#knock down the wall between it and CurrentCell
				dx = x*8
				dy = y*8
				if direction & 1: # if direction is West
					self.mazeArray[nidx] |= (4) # knock down the East
					pygame.draw.line(self.mLayer, (0,0,0,0), (dx,dy+1),(dx,dy+7))
				elif direction & 2: # if the direction is South
					self.mazeArray[nidx] |= (8) # knock down the North
					pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy+8),(dx+7,dy+8))
				elif direction & 4: # if direction is east
					self.mazeArray[nidx] |= (1) # knock down the West
					pygame.draw.line(self.mLayer, (0,0,0,0), (dx+8,dy+1),(dx+8,dy+7))
				elif direction & 8: # if direction is North
					self.mazeArray[nidx] |= (2) # knock down the South
					pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy),(dx+7,dy))
				self.mazeArray[self.currentCell] |= direction

				#push CurrentCell location on the CellStack 
				self.cellStack.append(self.currentCell)

				#make the new cell CurrentCell 
				self.currentCell = nidx
				
				#add 1 to VisitedCells
				self.visitedCells = self.visitedCells + 1
			#else
			else:
				#pop the most recent cell entry off the CellStack 
				#make it CurrentCell
				self.currentCell = self.cellStack.pop()
			#endIf
		#endWhile

So a quick breakdown, we removed the while loop so we could see whats going on :D Checked all of our neighbors, if a neighbor is found that has not been visited, choose one at random and knock the down the wall between it and the neighbor, and move the current cell to that neighbor. Otherwise, pop off the stack, and set the current cell to the last cell. This will create a perfect maze.

Taking out the comments, we can also add a quick check to see if we are backtracking and update again without drawing if this happens (check for the else pop)

Code:

class Maze:
	def __init__(self, mazeLayer):
		self.mazeArray = []
		self.state = 'create'
		self.mLayer = mazeLayer
		self.mLayer.fill((0, 0, 0, 0))
		for y in xrange(60): # 80 wide + 60 tall
			pygame.draw.line(self.mLayer, (0,0,0,255), (0, y*8), (640, y*8))
			for x in xrange(80):
				self.mazeArray.append(0)
				if ( y == 0 ):
					pygame.draw.line(self.mLayer, (0,0,0,255), (x*8,0), (x*8,480))
		self.totalCells = 4800 # 80 * 60
		self.currentCell = random.randint(0, self.totalCells-1)
		self.visitedCells = 1
		self.cellStack = []
		self.compass = [(-1,0),(0,1),(1,0),(0,-1)]

	def update(self):
		if self.state == 'create':
			if self.visitedCells >= self.totalCells:
				self.currentCell = 0
				self.cellStack = []
				self.state = 'solve'
				return
			moved = False
			while (moved == False):
				x = self.currentCell % 80
				y = self.currentCell / 80
				neighbors = []
				for i in xrange(4):
					nx = x + self.compass[i][0]
					ny = y + self.compass[i][1]
					if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):
						if (self.mazeArray[(ny*80+nx)] & 0x000F) == 0:
							nidx = ny*80+nx
							neighbors.append((nidx,1<<i))
				if len(neighbors) > 0:
					idx = random.randint(0,len(neighbors)-1)
					nidx,direction = neighbors[idx]
					dx = x*8
					dy = y*8
					if direction & 1: 
						self.mazeArray[nidx] |= (4) 
						pygame.draw.line(self.mLayer, (0,0,0,0), (dx,dy+1),(dx,dy+7))
					elif direction & 2: 
						self.mazeArray[nidx] |= (8) 
						pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy+8),(dx+7,dy+8))
					elif direction & 4: 
						self.mazeArray[nidx] |= (1) 
						pygame.draw.line(self.mLayer, (0,0,0,0), (dx+8,dy+1),(dx+8,dy+7))
					elif direction & 8:
						self.mazeArray[nidx] |= (2) 
						pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy),(dx+7,dy))
					self.cellStack.append(self.currentCell)
					self.currentCell = nidx
					self.visitedCells = self.visitedCells + 1
					moved = True
				else:
					self.currentCell = self.cellStack.pop()

	def draw(self, screen):
		screen.blit(self.mLayer, (0,0))

Now we have a pretty solid Maze generator that will generate while you watch! Its kind of hypnotizing, and we can make it even more so using a solver!

[Cthulhu32]

Looking at the mazeworks tutorial a bit more, we know we can use the top 8 bits of the 16-bit for our solver. So the top 4 bits will be the backtrack route, and the next 4 bits will be the solving route. We also use the cellstack, we know that the "solution" will be at the bottom right of the maze (you could change this), and we want to color as we work.

Code:

	elif self.state == 'solve':
		# have we reached the exit?      
		if self.currentCell == (self.totalCells-1):       
			self.state = 'reset'
			return

		# don't stop backtracking until we've moved forward once
		moved = False
		while(moved == False):
			x = self.currentCell % 80
			y = self.currentCell / 80
		
			# check all of our neighbors
			neighbors = []
			directions = self.mazeArray[self.currentCell] & 0xF
			for i in xrange(4):
				if (directions & (1<<i)) > 0:
					nx = x + self.compass[i][0]
					ny = y + self.compass[i][1]
					# Check to make sure we're not against a border
					if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):              
						nidx = ny*80+nx
						if ((self.mazeArray[nidx] & 0xFF00) == 0): # make sure there's no backtrack or solution
							neighbors.append((nidx,1<<i))
			# if we have a neighbor
			if len(neighbors) > 0:
				# Pick one at random
				idx = random.randint(0,len(neighbors)-1)
				nidx,direction = neighbors[idx]
				dx = x*8
				dy = y*8
				# set the opposite wall of the neighbor
				if direction & 1:
					self.mazeArray[nidx] |= (4 << 12)
				elif direction & 2:
					self.mazeArray[nidx] |= (8 << 12)
				elif direction & 4:
					self.mazeArray[nidx] |= (1 << 12)
				elif direction & 8:
					self.mazeArray[nidx] |= (2 << 12)
				# Draw a green solution block
				pygame.draw.rect(self.sLayer, (0,255,0,255), Rect(dx,dy,8,8))
				# Add a solution to our current cell of the direction we went
				self.mazeArray[self.currentCell] |= direction << 8
				# Push our current location to the stack
				self.cellStack.append(self.currentCell)
				# Set the current cell to our selected neighbor
				self.currentCell = nidx
				# Set moved to true
				moved = True
			else:
				# Draw a red solution block
				pygame.draw.rect(self.sLayer, (255,0,0,255), Rect((x*8),(y*8),8,8))

				# Not a solution, so AND the bit to take away the solution bit
				self.mazeArray[self.currentCell] &= 0xF0FF
				
				# Pop out the cell stack
				self.currentCell = self.cellStack.pop()

This is all that is really needed to make a solution. We reset it after we finished, and we can set a blue block for the start, and a purple block for the ending. We can wrap this up, fix up the creation so it happens automatically, and let it reset when it hits the end.

Code:

#/usr/bin/env python

import pygame, random
from pygame.locals import *

class Maze:
    def __init__(self, mazeLayer, solveLayer):
        self.mazeArray = []
        self.state = 'c'        # c = creating, s = solving, r = reset
        self.mLayer = mazeLayer # surface
        self.sLayer = solveLayer# surface
        self.mLayer.fill((0, 0, 0, 0))
        self.sLayer.fill((0, 0, 0, 0))
        for y in xrange(60): # 80 wide + 60 tall
            pygame.draw.line(self.mLayer, (0,0,0,255), (0, y*8), (640, y*8))
            for x in xrange(80):
                self.mazeArray.append(0)
                if ( y == 0 ):
                    pygame.draw.line(self.mLayer, (0,0,0,255), (x*8,0), (x*8,480))
        pygame.draw.rect(self.sLayer, (0,0,255,255), Rect(0,0,8,8))
        pygame.draw.rect(self.sLayer, (255,0,255,255), Rect((632),(472),8,8))
        # Maze Section
        self.totalCells = 4800 # 80 * 60
        self.currentCell = random.randint(0, self.totalCells-1)
        self.visitedCells = 1
        self.cellStack = []
        self.compass = [(-1,0),(0,1),(1,0),(0,-1)]

    def update(self):
        if self.state == 'c':
            if self.visitedCells >= self.totalCells:
                self.currentCell = 0 # set current to top-left
                self.cellStack = []
                self.state = 's'
                return
            moved = False
            while(self.visitedCells < self.totalCells):#moved == False):
                x = self.currentCell % 80
                y = self.currentCell / 80
                neighbors = []
                for i in xrange(4):
                    nx = x + self.compass[i][0]
                    ny = y + self.compass[i][1]
                    if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):
                        if (self.mazeArray[(ny*80+nx)] & 0x000F) == 0:
                            nidx = ny*80+nx
                            neighbors.append((nidx,1<<i))
                if len(neighbors) > 0:
                    idx = random.randint(0,len(neighbors)-1)
                    nidx,direction = neighbors[idx]
                    dx = x*8
                    dy = y*8
                    if direction & 1:
                        self.mazeArray[nidx] |= (4)
                        pygame.draw.line(self.mLayer, (0,0,0,0), (dx,dy+1),(dx,dy+7))
                    elif direction & 2:
                        self.mazeArray[nidx] |= (8)
                        pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy+8),(dx+7,dy+8))
                    elif direction & 4:
                        self.mazeArray[nidx] |= (1)
                        pygame.draw.line(self.mLayer, (0,0,0,0), (dx+8,dy+1),(dx+8,dy+7))
                    elif direction & 8:
                        self.mazeArray[nidx] |= (2)
                        pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy),(dx+7,dy))
                    self.mazeArray[self.currentCell] |= direction
                    self.cellStack.append(self.currentCell)
                    self.currentCell = nidx
                    self.visitedCells = self.visitedCells + 1
                    moved = True
                else:
                    self.currentCell = self.cellStack.pop()
        elif self.state == 's':
            if self.currentCell == (self.totalCells-1): # have we reached the exit?            
                self.state = 'r'
                return
            moved = False
            while(moved == False):
                x = self.currentCell % 80
                y = self.currentCell / 80
                neighbors = []
                directions = self.mazeArray[self.currentCell] & 0xF
                for i in xrange(4):
                    if (directions & (1<<i)) > 0:
                        nx = x + self.compass[i][0]
                        ny = y + self.compass[i][1]
                        if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):              
                            nidx = ny*80+nx
                            if ((self.mazeArray[nidx] & 0xFF00) == 0): # make sure there's no backtrack
                                neighbors.append((nidx,1<<i))
                if len(neighbors) > 0:
                    idx = random.randint(0,len(neighbors)-1)
                    nidx,direction = neighbors[idx]
                    dx = x*8
                    dy = y*8
                    if direction & 1:
                        self.mazeArray[nidx] |= (4 << 12)
                    elif direction & 2:
                        self.mazeArray[nidx] |= (8 << 12)
                    elif direction & 4:
                        self.mazeArray[nidx] |= (1 << 12)
                    elif direction & 8:
                        self.mazeArray[nidx] |= (2 << 12)
                    pygame.draw.rect(self.sLayer, (0,255,0,255), Rect(dx,dy,8,8))
                    self.mazeArray[self.currentCell] |= direction << 8
                    self.cellStack.append(self.currentCell)
                    self.currentCell = nidx
                    moved = True
                else:
                    pygame.draw.rect(self.sLayer, (255,0,0,255), Rect((x*8),(y*8),8,8))
                    self.mazeArray[self.currentCell] &= 0xF0FF # not a solution
                    self.currentCell = self.cellStack.pop()
        elif self.state == 'r':
            self.__init__(self.mLayer,self.sLayer)

    def draw(self, screen):
        screen.blit(self.sLayer, (0,0))
        screen.blit(self.mLayer, (0,0))

def main():
    """Maze Main Function - Luke Arntson, Jan '09
        Written using - http://www.mazeworks.com/mazegen/mazetut/index.htm
    """
    pygame.init()
    screen = pygame.display.set_mode((640, 480))
    pygame.display.set_caption('Labyrinth')
    pygame.mouse.set_visible(0)
    background = pygame.Surface(screen.get_size())
    background = background.convert()
    background.fill((255, 255, 255))
    mazeLayer = pygame.Surface(screen.get_size())
    mazeLayer = mazeLayer.convert_alpha()
    mazeLayer.fill((0, 0, 0, 0))
    solveLayer = pygame.Surface(screen.get_size())
    solveLayer = solveLayer.convert_alpha()
    solveLayer.fill((0, 0, 0, 0))
    newMaze = Maze(mazeLayer,solveLayer)
    screen.blit(background, (0, 0))
    pygame.display.flip()
    clock = pygame.time.Clock()
    while 1:
        clock.tick(60)
        for event in pygame.event.get():
            if event.type == QUIT:
                return
            elif event.type == KEYDOWN and event.key == K_ESCAPE:
                return
        newMaze.update()
        screen.blit(background, (0, 0))
        newMaze.draw(screen)
        pygame.display.flip()

if __name__ == '__main__': main()

Hopefully this is helpful for people starting up some Pygame projects, if people enjoyed this I can write a quick tut on a Game of Life (Cellular Automata) application, or I can write a quick how to make a platformer engine in Pygame :D

[george]

hey this is great. And thanks for that Mazeworks reference, that's damn good.

[Cymon]

Uh, you rock.

[nayon]

This is awesome for beginners!

For a person like me, the platformer thing would be even awesomer, because when I try to code a platformer in pygame myself, I have miserably hilarious collision issues.

[Cthulhu32]

Sweet, alright I will set my sights next on making a tutorial for a platformer engine in Pygame. It is not the most efficient language in the world for something like a platformer, but I have managed to make a few cool platformers in Pygame running at 60fps. I will probably have to do it in a series though, as each component is kind of complicated. You start with a physics actor that can be inherited by other objects, then you build a physics manager on top of that, and integrate the levels as solid physics objects into there. You also want to minimize the amount of collisions you check for, so you turn the level into a grid and check collisions based on where your X/Y lay in the grid. Anywho, that will be next per request :D

[TheSpaceMan]

Implemented a simular algoritm for a game a while back, after the maze was generated it would remove X amount of random walls in the design as well as add a few coridors and more open rooms into it. Wish i had time to do more generation. Would like to make a game that use multi tile parts as well as multi doors. It could work with the same algoritm I guess.

[Cthulhu32]

Yeah there's a couple of ways to handle non-perfect mazes. You can start with a perfect maze, and pick away at it, or you can implement another algorithm such as Prim's Algorithm or Kruskal's Algorithm.

Wikipedia: http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm

Prim's Algorithm:
    Start with a grid full of walls.
    Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
    While there are walls in the list:
        Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:
            Make the wall a passage and mark the cell on the opposite side as part of the maze.
            Add the neighboring walls of the cell to the wall list.

Alright, I modified my maze to be a Prim's maze.
If you want to see the Prim in action, uncomment line 46 so it checks to see if moved = true (this will make it update once a frame

Code:

#/usr/bin/env python

import pygame, random
from pygame.locals import *

class Maze:
	def __init__(self, mazeLayer, solveLayer):
		self.mazeArray = []
		self.state = 'c'		# c = creating, s = solving, r = reset
		self.mLayer = mazeLayer # surface
		self.sLayer = solveLayer# surface
		self.mLayer.fill((0, 0, 0, 0))
		self.sLayer.fill((0, 0, 0, 0))
		for y in xrange(60): # 80 wide + 60 tall
			pygame.draw.line(self.mLayer, (0,0,0,255), (0, y*8), (640, y*8))
			for x in xrange(80):
				self.mazeArray.append(0x0)
				if ( y == 0 ):
					pygame.draw.line(self.mLayer, (0,0,0,255), (x*8,0), (x*8,480))
		pygame.draw.rect(self.sLayer, (0,0,255,255), Rect(0,0,8,8))
		pygame.draw.rect(self.sLayer, (255,0,255,255), Rect((632),(472),8,8))
		# Maze Section
		self.totalCells = 4800 # 80 * 60
		self.wallList = []
		self.currentCell = random.randint(0, self.totalCells-1)
		c = self.currentCell
		mz = self.mazeArray[c]
		self.mazeArray[c] |= 0x00F0 # now its part of the maze
		self.wallList.append((c,0))
		self.wallList.append((c,1))
		self.wallList.append((c,2))
		self.wallList.append((c,3)) # fill the walls
		self.visitedCells = 1
		self.cellStack = []
		self.compass = [(-1,0),(0,1),(1,0),(0,-1)]

	def update(self):
		if self.state == 'c':
			#if self.visitedCells >= self.totalCells:
			if len(self.wallList) <= 0:
				self.currentCell = 0 # set current to top-left
				self.cellStack = []
				self.state = 's'
				return
			moved = False
			while(len(self.wallList) > 0):# and moved == False):
				# pick a random wall
				wi = random.randint(0, len(self.wallList)-1)
				self.currentCell = self.wallList[wi][0]
				x = self.currentCell % 80
				y = self.currentCell / 80
				dir = self.wallList[wi][1]
				nx = x + self.compass[dir][0]
				ny = y + self.compass[dir][1]
				nidx = ny*80+nx
				dx = x*8
				dy = y*8
				direction = 1 << dir # make it perty
				if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):
					if (self.mazeArray[nidx] & 0x00F0) == 0:		
						if direction & 1:
							self.mazeArray[nidx] |= (4)
							pygame.draw.line(self.mLayer, (0,0,0,0), (dx,dy+1),(dx,dy+7))
						elif direction & 2:
							self.mazeArray[nidx] |= (8)
							pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy+8),(dx+7,dy+8))
						elif direction & 4:
							self.mazeArray[nidx] |= (1)
							pygame.draw.line(self.mLayer, (0,0,0,0), (dx+8,dy+1),(dx+8,dy+7))
						elif direction & 8:
							self.mazeArray[nidx] |= (2)
							pygame.draw.line(self.mLayer, (0,0,0,0), (dx+1,dy),(dx+7,dy))
						self.mazeArray[self.currentCell] |= direction
						self.mazeArray[(ny*80+nx)] |= 0x00F0 # mark it as part of the maze
						# add its walls to the list
						self.wallList.append((ny*80+nx,0))
						self.wallList.append((ny*80+nx,1))
						self.wallList.append((ny*80+nx,2))
						self.wallList.append((ny*80+nx,3))
						moved = True
				self.wallList.remove(self.wallList[wi])
		elif self.state == 's':
			if self.currentCell == (self.totalCells-1): # have we reached the exit?			
				self.state = 'r'
				return
			moved = False
			while(moved == False):
				x = self.currentCell % 80
				y = self.currentCell / 80
				neighbors = []
				directions = self.mazeArray[self.currentCell] & 0xF
				for i in xrange(4):
					if (directions & (1<<i)) > 0:
						nx = x + self.compass[i][0]
						ny = y + self.compass[i][1]
						if ((nx >= 0) and (ny >= 0) and (nx < 80) and (ny < 60)):			  
							nidx = ny*80+nx
							if ((self.mazeArray[nidx] & 0xFF00) == 0): # make sure there's no backtrack
								neighbors.append((nidx,1<<i))
				if len(neighbors) > 0:
					idx = random.randint(0,len(neighbors)-1)
					nidx,direction = neighbors[idx]
					dx = x*8
					dy = y*8
					if direction & 1:
						self.mazeArray[nidx] |= (4 << 12)
					elif direction & 2:
						self.mazeArray[nidx] |= (8 << 12)
					elif direction & 4:
						self.mazeArray[nidx] |= (1 << 12)
					elif direction & 8:
						self.mazeArray[nidx] |= (2 << 12)
					pygame.draw.rect(self.sLayer, (0,255,0,255), Rect(dx,dy,8,8))
					self.mazeArray[self.currentCell] |= direction << 8
					self.cellStack.append(self.currentCell)
					self.currentCell = nidx
					moved = True
				else:
					pygame.draw.rect(self.sLayer, (255,0,0,255), Rect((x*8),(y*8),8,8))
					self.mazeArray[self.currentCell] &= 0xF0FF # not a solution
					self.currentCell = self.cellStack.pop()
		elif self.state == 'r':
			self.__init__(self.mLayer,self.sLayer)

	def draw(self, screen):
		screen.blit(self.sLayer, (0,0))
		screen.blit(self.mLayer, (0,0))

def main():
	"""Maze Main Function - Luke Arntson, Jan '09
		Written using - http://www.mazeworks.com/mazegen/mazetut/index.htm
	"""
	pygame.init()
	screen = pygame.display.set_mode((640, 480))
	pygame.display.set_caption('Labyrinth')
	pygame.mouse.set_visible(0)
	background = pygame.Surface(screen.get_size())
	background = background.convert()
	background.fill((255, 255, 255))
	mazeLayer = pygame.Surface(screen.get_size())
	mazeLayer = mazeLayer.convert_alpha()
	mazeLayer.fill((0, 0, 0, 0))
	solveLayer = pygame.Surface(screen.get_size())
	solveLayer = solveLayer.convert_alpha()
	solveLayer.fill((0, 0, 0, 0))
	newMaze = Maze(mazeLayer,solveLayer)
	screen.blit(background, (0, 0))
	pygame.display.flip()
	clock = pygame.time.Clock()
	while 1:
		clock.tick(60)
		for event in pygame.event.get():
			if event.type == QUIT:
				return
			elif event.type == KEYDOWN and event.key == K_ESCAPE:
				return
		newMaze.update()
		screen.blit(background, (0, 0))
		newMaze.draw(screen)
		pygame.display.flip()

if __name__ == '__main__': main()

[agj]

This looks amazing, thank you so much! Now I have something to get started with Python when I get the chance to sit down and learn it. Hope that time comes soon enough.

[Cranktrain]

Very interesting tutorial. I shall be exploring this more later today.

[Johhny]

Can't wait to start working on this. I've been working on learning Python, and at this point I'm still trying to master the basics before I move onto anything graphical. This looks like a great stepping stone into pygame for when I finally get there. 

[Cthulhu32]

Can't wait to start working on this. I've been working on learning Python, and at this point I'm still trying to master the basics before I move onto anything graphical. This looks like a great stepping stone into pygame for when I finally get there. 

Yeah I haven't touched any of the cool built in pygame goodness like sprites or how to implement cool state engines, but I figure this would be a nice way for people to step into python and pygame, and get a better feeling on how to program in Python vs. C or C++ or something like that.

My next plan is to do a quick platformer tutorial, showing how to make a simple one screen tile engine, have actors with a common physics back-end moving around, and how to do a sleek little animation system.

[hagel]

...
My next plan is to do a quick platformer tutorial, showing how to make a simple one screen tile engine, have actors with a common physics back-end moving around, and how to do a sleek little animation system.

My tip would be to include some kind of scrolling.

Also, thanks for this, I recently started programming in Python with pyGame.
 I didn't even know all code was open-source.

[wire]

How very nice, thanks for the tutorial! :D I find that the Pyglet and Chipmunk modules an do wonders too

[desdinova]

Sweet! looks like a good tutorial.  I've been learning Python the past week, just emulating some arcade games so far so this will be a good stepping stone

[Cthulhu32]

Thanks for all the nice words, yeah Python/Pygame is a really cool prototyping language. I've been coming up with a few project ideas I'd like to get done including a little RPG battle system that uses various spells involving user-input (like Xenogears.) Also when I do get the platform tutorial together, it will definitely start small with single-screen physics and tile-loaders, then expand to scrolling platforms. And I'll try to code it in a non-python specific way, so people who want to extend their games to C++/Java/whatever can pick up the tutorial and just go.

Also Pyglet and Chipmunk are both very cool, Pyglet is maintained by Richard, the founder of Pyweek which is very cool. I've heard really good things about the performance of Pyglet because it uses OpenGL vs. Pygame which uses SDL. If I get more into Pyglet I'll see if I can put together a little tutorial for that as well I'm just glad people are learning and having fun with this stuff!

[SkyBox]

This is a very clever program, thanks for putting this up, although it's way beyond me right now!

In the future can you put your code segments up in a less...stream-of-consciousness way? I appreciate seeing the evolution of the program but maybe just segment the whole program and explain each bit in turn? I found it hard to follow at points because I didn't know where the new code was being inserted, or what had changed in cases where only a few lines had been added into a big block.

[Jrsquee]

HEY this looks awesome
I think...
I think I will try this!