Computer Science 15-112, Fall 2011
Optional Lecture Notes:  Mazes

These notes were prepared by students attending the optional lecture on mazes.  As such, they may contain a small error here or there (standard disclaimer).  They are provided here as a service to those who may have missed the lecture.

First, here is the code that we wrote:  mazes.py

Also, here is a faster version that uses sets rather than island labels:  fasterMazes.py

Second, here is the header for the mazes.py file:

# mazes.py
# Code written during optional lecture on mazes.
# Given the group-based design and tight time constraints,
# there is a fine chance this code contains a bug here or there.
# Plus, there are a variety of ways to make this code much nicer
# (several of these were assigned as bonus for the lecture).
# Press "r" to reset to a new maze, and press "c" to switch
# to a circular view. 

Making Mazes

Q. How do you make a maze?

First, we’re going to define a maze:

·   Collection of points connected by edges/nodes/vertices

·   Contains special privileged start and end points

·   Can get from any point to any point

So, a maze is essentially a series of dots with things connecting them…

Q. How do we build this?

·   Start with a bunch of dots

·   Randomly pick one dot and a direction. Connect the chosen dot with the next dot in the specified direction

·   Repeat!

We’re going to connect things until everything is connected to everything else.

Here is an example that is valid but not optimal; you can remove any of the four edges of the box and still be fully connected.

So we’re going to place an extra constraint: We want the minimum amount of links possible. Every link connects two distinct nodes, so we want to add one fewer links than the number of nodes.

For now on, we’re going to refer to nodes as islands and links as bridges.

For identification purposes, every island will have a name, initially unique. When two islands are connected by a bridge, they become one island and share the same name. From this, we know that if two islands have the same name, then they’re connected. Every time you want to add another bridge, you’ll need to find an island whose neighbor is a different island. When the maze is done, we’ll have only one island

What will we have to store for every island?

·   Label

·   Two True/False values for whether or not there is a bridge in the given direction (East, South)

(Note that you don’t need West/North because other islands store that information already)

First, let’s try to represent the maze.

def makeEmptyMaze(rows, cols):

    maze = [([0]*cols) for row in xrange(rows)] #create 2d list of islands

    label = 0

    for row in xrange(rows):

        for col in xrange(cols):

            maze[row][col] = Island(label)

            label += 1 #every single island receives a unique label

    return maze

def Island(label): #there are cleaner ways to do this but this works for our purposes

    island = Struct() #remember to have class Struct: pass

    island.label = label #pass in a label

    island.hasEastBridge = False #initially the island has no bridges

    island.hasSouthBridge = False

    return island

Now, we need a way to display the maze! Try printing it.

def printMaze(maze): #0 False False means the 0^th node has no East and no South bridges

    rows = len(maze)

    cols = len(maze[0])

    for row in xrange(rows):

        for col in xrange(cols):

            island = maze[row][col]

            print "%2d" % island.label,

            print island.hasEastBridge, island.hasSouthBridge,

        print

Now we need to add our bridges. We will need rows*(cols-1) bridges…

def makeMaze(rows, cols):

    maze = makeEmptyMaze(rows, cols)

    for bridge in xrange(rows*cols-1):

        addRandomBridge(maze) # and we actually want to make them! see below…

    return maze

In order to add a bridge we need to first pick a random island and a random direction.

We know that if there is already a bridge, then the label on the target node will be the same as the label of the node we’re currently on. So, we just need to check if there’s a different island label on the node we’re trying to connect to.

def addRandomBridge(maze):

    rows = len(maze)

    cols = len(maze[0])

    while True:

        # keep trying to find a random island and random direction that

        # works (so we can add a bridge and keep the maze property)

        # and repeat infinitely until we get "lucky"

        islandRow = random.randint(0, rows-1) #random.randint() is inclusive

        islandCol = random.randint(0, cols-1)

        dir = random.randint(0, 3) #we will assign 0-3 to the directions North, South, East and West as global variables

        #note on global direction: if I refer to a variable that’s unbound to a function, it looks for a global variable

        #it’s usually not good to use these, but in this case it’s good to lock down the variables for consistency

        (targetRow, targetCol) = findTarget(islandRow, islandCol, dir)

        if ((targetRow >= 0) and (targetRow < rows) and

            (targetCol >= 0) and (targetCol < cols)): #we're on the board!

            if (maze[islandRow][islandCol].label != maze[targetRow][targetCol].label): #make sure target is different!

                addBridge(maze, islandRow, islandCol, dir, targetRow, targetCol) #establish a bridge

                break

A better way to do the above would be to create a LIST of all the bridges and pull out every bridge we’ve found. We’d then be able to choose from the shrinking list. However, our current strategy is good enough for our purposes.

Now we create our helper functions…

def findTarget(row, col, dir): #note that this is inferior to wordsearch’s drow and dcol

    if (dir == EAST): return (row, col+1) #nothing happens to the row when going East!

    elif (dir == WEST): return (row, col-1)

    elif (dir == NORTH): return (row-1, col)

    elif (dir == SOUTH): return (row+1, col)

    assert(False) # should never happen

def addBridge(maze, islandRow, islandCol, dir, targetRow, targetCol):

    # assume the bridge (and all parameters) are legal

    rows = len(maze)

    cols = len(maze[0])

    # 1. add the bridge itself by changing the hasFooBridge to True

    if (dir == EAST): maze[islandRow][islandCol].hasEastBridge = True

    elif (dir == SOUTH): maze[islandRow][islandCol].hasSouthBridge = True

Q. What if we’re moving West?

Every node is keeping track of East and South bridges. If we’re moving west, go to the target! West from the source = East from the target

    elif (dir == WEST): maze[targetRow][targetCol].hasEastBridge = True #west from the source = east from the target

    elif (dir == NORTH): maze[targetRow][targetCol].hasSouthBridge = True

    # 2. update all the labels replacing the larger label with the smaller label

    islandLabel = maze[islandRow][islandCol].label

    targetLabel = maze[targetRow][targetCol].label

    largerLabel = max(islandLabel, targetLabel)

    smallerLabel = min(islandLabel, targetLabel)

    for row in xrange(rows):

        for col in xrange(cols):

            if (maze[row][col].label == largerLabel):

                maze[row][col].label = smallerLabel

Now we need to display our islands and bridges!

We want to make our maze in init() so we only make one maze. In redrawAll, we need to display it. In order to display our maze, we need to at least display our islands!

We should represent islands as rectangles in the center of each square.

def drawMaze(maze):

    (rows, cols) = (len(maze), len(maze[0]))

    (width, height) = (canvas.data.width, canvas.data.height)

    r = 0.1*min(width/cols, height/rows)

    for row in xrange(rows):

        for col in xrange(cols):

            (cx, cy) = islandCenter(row, col) #we put this into a helper function because we’ll need the island center for bridges too

            # paint the island

            canvas.create_rectangle(cx-r, cy-r, cx+r, cy+r, fill="blue")

Now, we want to paint the bridges!

         # paint the bridges

            if (maze[row][col].hasEastBridge): #if there is an East bridge, we need to draw it

                (tx, ty) = islandCenter(row, col+1) #get the other island center

                canvas.create_line(cx, cy, tx, ty, width=2, fill="blue") #connect the two island centers with a line!

            if (maze[row][col].hasSouthBridge):

                (tx, ty) = islandCenter(row+1, col)

                canvas.create_line(cx, cy, tx, ty, width=2, fill="blue")           

And now onto our helper function for finding the center of each square... we’ll just look at the horizontal (meaning width and cols). The width of one cell will be width/cols. The center of col 0 is one half column over, so it can be represented as (col + 0.5)*(width/col). The symmetric formula can be used to find cy.

def islandCenter(row, col):

    maze = canvas.data.maze

    (rows, cols) = (len(maze), len(maze[0]))

    (width, height) = (canvas.data.width, canvas.data.height)

    return ((col+0.5)*width/cols, (row+0.5)*height/rows)

Now define reset in keyPressed() so it resets a new maze each time the user presses “r”. This simply calls init().

def keyPressed(event):

    if (event.char == "r"):

        init()

    redrawAll()

At this point we have a functioning maze creator. Now, what if we wanted to construct a polar maze? We will build the exact same maze, and display it circularly instead. Each row of our maze will be one of the concentric rings, and each column will be a spoke radiating out from the center.

First, we define “c” in keyPressed for circular mazes and add drawCMaze in redrawAll()

def keyPressed(event):

    if (event.char == "r"):

        init()

    elif (event.char == "c"):

        canvas.data.isCircular = not canvas.data.isCircular

    redrawAll()

def redrawAll():

    canvas.delete(ALL)

    maze = canvas.data.maze

    if (canvas.data.isCircular):

        drawCircularMaze(maze)

    else:

        drawMaze(maze)

So, how do we draw a circular maze? If it’s 4x4, we’ll have 4 rings and 4 spokes…

·         Rows, cols = rings, spokes

·         South bridges point towards the middle

·         East bridges are the arcs

We didn’t reconstruct our maze generator to generate a truly radial maze. So we’ll have guaranteed missing edges from trying to take a radial projection from a maze that’s on a rectilinear grid. #Bonus! Add the missing edges to make it truly circular!

Now, we need to find the x and y values for a ring and spoke.

Q. How do I figure out the r for any given ring?

My outermost ring (largest r) should equal the minimum of (bx, by)

The innermost ring is 0. r = (ring+1)/rings * min(bx,by)

Here, you need to add one because otherwise ring 0 = 0!

Q. How do I find theta for spokes?

When the spoke is 0, theta should be 0. When the spoke is the max number of spokes, theta should be 2 pi.

Here, you don’t need to add one because you don’t want to go all the way around

Let’s also look at a little trig:

In order to get the coordinates we want, we’ll need to add bx to rcos(theta) and subtract rsin(theta) from by. In this case, we’re subtracting because up is down!

We discard the idea of drawing arcs for now, so the only code we need to change AT ALL is islandCenter().

def circularIslandCenter(row, col):

    maze = canvas.data.maze

    (rows, cols) = (len(maze), len(maze[0]))

    (width, height) = (canvas.data.width, canvas.data.height)

    (bx, by) = (width/2, height/2)

    (ring, spoke) = (row, col) #renaming convention for self-documenting code

    (rings, spokes) = (rows, cols)

    maxRadius = 0.8*min(bx, by) #multiplying by 0.8 creates a buffer so no islands are clipped by the canvas

    r = float(maxRadius)*(ring+1)/rings #make sure you multiply first! Otherwise this amplifies the size of the roundoff

    theta = math.radians(360*spoke/spokes)

    return (bx+r*math.cos(theta), by-r*math.sin(theta)) #derived above

Look up how to create arcs with tkInter: http://www.pythonware.com/library/tkinter/introduction/canvas-arc.htm

We should change the East bridges to arcs since they’re the ones that are going from spoke to spoke. In order to do so, you need to specify a bounding box with some width, a fill of None, the center and radius that’s dependent on the ring, and the start and end angles. The radius will be the distance between x and y; however, the start and end angles will be more difficult. Our code that computed r theta should be returning the value instead of directly computing – change this and you should be able to draw actual arcs in your circular mazes!
 

Summary:

To make a maze…

We had a large list of islands and labeled them. We chose a random island and checked a random direction. If those two islands didn’t have the same label, we added a bridge and relabeled all the islands to the smaller of the two numbers. We repeated until everything was 0 (or repeat for rows*(cols-1) times). If we have really bad luck, we’ll keep guessing randomly forever -> this is a bad idea in principle. This works fine for the types of mazes we’re seeing but we can do better.