This class encapsulates both the generation of the maze and
its rendering as a Tkinter `Canvas`

widget.

mazeratty

# - - - - - c l a s s M a z e class Maze(object): '''Represents a maze. Exports: Maze(canvas): [ canvas is a Tkinter.Canvas widget -> return a new Maze that renders on that canvas ] .can: [ canvas argument passed to the constructor ] .generate(nRows, nCols, visible, seed): [ if visible -> self.can := self.can - (any previous drawing) + (a new maze of size nRows x nCols with the solution path shown) else -> self.can := self.can - (any previous drawing) + (a new maze of size nRows x nCols with the solution path not shown) In any case -> use seed as the random seed .pathDraw(): [ self.can := self.can with the solution path shown ] .pathErase(): [ self.can := self.can with the solution path not shown ] .postscript(outFileName): [ outFileName is a string -> if outFileName names a file can be opened for writing -> that file := self.can as PostScript else -> raise IOError ] .getWallCells(wallKey): [ wallKey is a wall-key in self -> return a list of the cells adjacent to that wall, one for outside walls, two for interior walls ] .getCell(cellKey): [ if cellKey is a cell-key in self -> return the corresponding Cell instance else -> raise KeyError ] .allWalls(): [ returns a list containing all the Wall instances in self ] .killWall(wallKey): [ wallKey is a wall-key in self -> self := self with that wall removed, and the adjacent cell(s) merged into the same cell set ]

Here are the internal attributes of the class. Cells and
walls are indexed using the keys defined in Section 9, “Specification functions: `cell-key`

and
`wall-key`

”. The principal data structures
are:

`.__cellMap`

, a dictionary relating all the possible`cell-key`

values to the cells as`Cell`

instances. See Section 14, “`class Cell`

: One cell in the maze”.`.__wallMap`

, a dictionary relating all the possible`wall-key`

values to the walls as`Wall`

instances. See Section 15, “`class Wall`

: One wall in the maze”.`.path`

, representing the solution path through the maze as an instance of Section 13, “`class Path`

: The solution path”.

mazeratty

State/Invariants: .nRows: [ current row count ] .nCols: [ current column count ] .seed: [ seed used to generate the most recent maze ] .lastRow: [ self.nRows-1 ] .lastCol: [ self.nCols-1 ] .start: [ wall-key of the start cell on the left side ] .goal: [ wall-key of the end cell on the right side ] .path: [ the solution path as a Path instance ] .__cellMap: [ a dictionary whose keys are all the possible (row,col) tuples of cells in self, and each related value is a Cell instance ] .__wallMap: [ a dictionary whose keys are wall-keys of the walls in self and each related value is a Wall instance with that wall-key ] .cellSize: [ length of a cell wall in pixels ] .halfCell: [ self.cellSize/2 ] '''

mazeratty

# - - - M a z e . _ _ i n i t _ _ def __init__(self, canvas): '''Constructor. ''' self.can = canvas

mazeratty

# - - - M a z e . g e n e r a t e def generate(self, nRows, nCols, visible, seed): '''Generate a new maze. ''' #-- 1 -- self.nRows = nRows self.nCols = nCols self.lastRow = self.nRows - 1 self.lastCol = self.nCols - 1 self.seed = seed random.seed(seed)

Now that we know the current row and column count,
generate the complete set of cells and walls; all walls
are initially solid. See Section 12.3, “`Maze.__buildMaps()`

: Construct cells
and walls”.

mazeratty

#-- 2 -- # [ self.__cellMap := a dictionary with all the cell-key # values for a maze of size self.nRows x self.nCols and # each corresponding value a Cell with that cell-key # and its set a singleton set containing itself # self.__wallMap := a dictionary with all the wall-key # values for a maze of size self.nRows x self.nCols and # each corresponding value a Wall with that wall-key ] self.__buildMaps()

Refer to Section 3, “Design overview” for an overview of the
maze construction process. The next step is to select
random start and goal locations on the left and right
side and then generate the solution path that connects
them. See Section 12.5, “`Maze.__makePath()`

: Create the
solution path”.

mazeratty

#-- 3 -- # [ self.start := cell-key of a random cell on the left side # self.goal := cell-key of a random cell on the right side # self.path := a Path instance representing a path # between those two cells, using self.seed as the random # seed self.__makePath()

Next, we remove all the walls that cross the solution
path. We don't actually destroy the `Wall`

instances; we just set their `.solid`

attribute to 0, so they will not be rendered. See Section 12.10, “`Maze.__cutPath()`

: Remove walls along
the solution route”. Note that we must also
breach the left- and right-hand walls to indicate the
entrance and exit.

mazeratty

#-- 4 -- # [ self.maze := self.maze - (the wall to the left of # self.path[0]) - (the wall to the right of # self.path[-1)) - (walls crossed by self.path) ] self.__cutPath()

All the cells that are not part of the solution path are
joined to the maze by running Kruskal's algorithm. Note
that the cells of the solution path are already all
merged into a single set. See Section 12.14, “`Maze.__kruskal()`

: Connect remaining
cells to the solution”.

mazeratty

#-- 5 -- # [ self.maze := self.maze with all cells connected using # Kruskal's algorithm ] self.__kruskal()

Finally, see Section 12.15, “`Maze.render()`

: Draw the maze on a
canvas” for the
actual drawing of the maze onto the canvas.

mazeratty

#-- 6 -- # [ self.can := self.can - (any existing elements) + # (rendering of self) ] self.render(visible)

This method sets up the `.__cellMap`

and
`.__wallMap`

data structures that enumerate
all the cell and wall locations.

mazeratty

# - - - M a z e . _ _ b u i l d M a p s def __buildMaps(self): '''Set up the maze with all walls initially solid. [ self.__cellMap := a dictionary with all the cell-key values for a maze of size self.nRows x self.nCols and each corresponding value a Cell with that cell-key and its set a singleton set containing itself self.__wallMap := a dictionary with all the wall-key values for a maze of size self.nRows x self.nCols and each corresponding value a Wall with that wall-key ] ''' #-- 1 -- self.__cellMap = {} self.__wallMap = {}

First we iterate over all the possible cell locations.
At each location, we create and store a `Cell`

instance and two `Wall`

instances
representing the walls above and to the left of the
cell.

mazeratty

#-- 2 -- # [ self.__cellMap := as invariant # self.__wallMap := as invariant, except for walls along # the bottom and right side of the maze ] for rowx in range(self.nRows): for colx in range(self.nCols): #-- 2 body -- # [ (rowx is a row index in self) and # (colx is a column index in self) -> # self := self with a new vertical wall to # the left of (rowx,colx) and a new horizontal # wall above (rowx, colx) ] cellKey = (rowx, colx) self.__cellMap[cellKey] = cell = Cell(cellKey) self.__addWall(cellKey, 0) self.__addWall(cellKey, 1)

All that remains is to build the exterior walls that are on the right and below the rest of the maze.

mazeratty

#-- 3 -- # [ self := self with solid horizontal walls along the bottom ] for colx in range(self.nCols): self.__addWall((self.nRows, colx), 0) #-- 4 -- # [ self := self with solid walls along the right side ] for rowx in range(self.nRows): self.__addWall((rowx, self.nCols), 1)

mazeratty

# - - - M a z e . _ _ a d d W a l l def __addWall(self, cellKey, isVert): '''Add a new, solid wall to self. [ (cellKey is a cell-key) and (isVert is 1 for vertical, 0 for horizontal) -> self := self with a new, solid wall added starting at cell-key and with orientation (isVert) ] '''

As defined in Section 9, “Specification functions: `cell-key`

and
`wall-key`

”, a `wall-key`

is a tuple `(`

that specifies
the starting row, the starting column, and the
orientation respectively. See Section 15, “* row*,

`col`

`isV`

`class Wall`

: One wall in the
maze”.
mazeratty

#-- 1 -- # [ wallKey := a wall-key with origin at (cellKey) and # orientation (isVert) ] wallKey = cellKey + (isVert,) #-- 2 -- # [ self.__wallMap +:= an entry with key (wallKey) and # related value a new Wall instance with key (wallKey) ] self.__wallMap[wallKey] = Wall(wallKey)

mazeratty

# - - - M a z e . _ _ m a k e P a t h def __makePath ( self ): '''Create a new solution. [ self.start := cell-key of a random cell on the left side self.goal := cell-key of a random cell on the right side self.path := a Path instance representing a path between those two cells, using self.seed as the random seed ] '''

First we pick a start cell and a goal cell, and set up a
new `Path`

instance with the start cell
added as its first element. Note that the `random.randrange(`

function returns
a value in the half-open range [* a*,

`b`

`a`

`b`

mazeratty

#-- 1 -- # [ self.start := cell-key of a random cell on the left side # self.goal := cell-key of a random cell on the right side # self.path := a new Path instance with self.start # added as its first element ] self.start = (random.randrange(0, self.nRows), 0) self.goal = (random.randrange(0, self.nRows), self.lastCol) self.path = Path() self.path.add(self.start)

So long as the path has not yet reached the goal, and
assuming that there is an open route from the end of the
path to the goal cell that does not use any cell that is
already in the path, the method Section 12.6, “`Maze.__extendPath()`

: Add one cell to
the path” is guaranteed to add one
cell to the path. This new cell will be either the goal
cell or a cell that has an open route to the goal.

mazeratty

#-- 2 -- # [ if self.path[-1] == self.goal -> # I # else -> # self.path := self.path + (cells that lead from # path[-1] to self.goal without using any cell twice) ] while self.path[-1] != self.goal: #-- 2 body -- # [ there is a route from path[-1] to self.goal that # does not use any element of path -> # self.path := self.path + (a cell adjacent to # path[-1] that has a route to self.goal that uses # no cells in self.path) ] self.__extendPath()

mazeratty

# - - - M a z e . _ _ e x t e n d P a t h def __extendPath ( self ): '''Add one new cell to the path. [ (self.path is nonempty) and (self.path does not include self.goal) and (there is a route from self.path[-1] to self.goal that does not use any element of path) -> path := path + (a cell adjacent to path[-1] that has a route to self.goal that does not use any element of path ] '''

First we generate a list of the `cell-key`

values for all the cells adjacent to the cell at the
growing end of the path. See Section 12.7, “`Maze.__genNeighbors()`

: Find the cells
adjacent to a given cell”. Then we randomly permute
that list using `random.shuffle()`

so that
the new route is a random choice among the available
neighbors.

mazeratty

#-- 1 -- # [ nabeList := list of cell-key values for cells adjacent to # path[-1] that are not in self.path, in random order ] nabeList = [ nabe for nabe in self.__genNeighbors( self.path[-1] ) ] random.shuffle(nabeList)

Next, we test each neighbor until we find one that has an
open route to the goal: see Section 12.8, “`Maze.__exitCheck()`

: Is there an open
route to the goal from this cell?”. The first qualifying cell
becomes the new addition to the solution path.

mazeratty

#-- 2 -- for nabe in nabeList: #-- 2 body -- # [ if there is a route from nabe to self.goal that # does not use any cell in (self.path+nabe) -> # self.path := self.path with nabe added at the end # return # else -> I ] if self.__exitCheck ( nabe ): self.path.add ( nabe ) return

The precondition that there is a route from the end of the path to the goal insures that the above loop always returns.

To automate the process of finding a cell's neighbors, we
declare a class variable `DELTAS`

that is a
list of (Δ* r*,
Δ

`c`

`r`

`c`

mazeratty

# [ DELTAS := a tuple of (dr, dc) tuples representing the # the delta row and delta column values for the # neighbors of a given cell ] DELTAS = ( (1,0), # Down: Add one row (0,1), # Right: Add one column (-1,0), # Up: Subtract one row (0,-1) ) # Left: Subtract one column def __genNeighbors ( self, cellKey ): '''Find neighbors that are in the maze and not in self.path. [ cellKey is a cell-key in the maze -> generate the neighbors of cell-key that are in the maze and not in self.path ] ''' #-- 1 -- row, col = cellKey #-- 2 -- # [ generate neighbors of the cell in row (row) and column (col) # that are in the maze and not in self.path ] for toCell in [ (row+dr, col+dc) for dr, dc in self.DELTAS ]: toRow, toCol = toCell if ( ( 0 <= toRow < self.nRows ) and ( 0 <= toCol < self.nCols ) and ( toCell not in self.path ) ): yield toCell #-- 3 -- raise StopIteration

mazeratty

# - - - M a z e . _ _ e x i t C h e c k def __exitCheck ( self, cellKey ): '''Is there a way to the goal from (cellKey) not crossing path? [ (cellKey is a cell-key in the maze) -> if there is a route from cellKey to self.goal that uses no cells in self.path -> return True else -> return False ] Algorithm: We build a set that initially includes cellKey. Then we recursively add neighbors of cellKey and their neighbors and so on until the set is complete. If at any time self.goal is a neighbor, we return True. If the set is completed without touching self.goal, return False. '''

First we must check the basis case: if `cellKey`

is the goal, then by definition it has
an open path to the goal. Otherwise, we create a Python
`set`

that includes `cellKey`

.

mazeratty

#-- 1 -- if cellKey == self.goal: return True else: canReach = set([cellKey])

To test whether there is an open path to the goal, we
compute the *transitive closure* of the neighbor
relation starting with `cellKey`

, excluding
cells already in the path. That is, we compute the set
of all the cells that can be reached from `cellKey`

, and test to see if the goal cell is
in that set.

Computationally, we start by creating set `canReach`

, initially containing `cellKey`

, and recursively evaluate the neighbors,
the neighbors of the neighbors, and so on, until one of
two conditions is met:

If we run out of neighbors, and no element of

`canReach`

is adjacent to the goal, we know that there is no open route to the goal from`cellKey`

; return`False`

.If at any time one of the elements of

`canReach`

is a neighbor of the goal, we know that there is at least one open route.To save time, as soon as this condition is met, we raise a

`GoalFound`

exception (see Section 8, “Exceptions”) to transfer control directly back here so we can return`True`

.

For the recursive function that adds neighbors not in the
path, see Section 12.9, “`Maze.__addReachables()`

: Compute the
transitive closure of the neighbor relation”.

mazeratty

#-- 2 -- # [ if cells reachable from cellKey that are not in self.path # or canReach include self.goal -> # return True # else -> # canReach := set of cells reachable from cellKey # that are not in self.path or canReach ] try: self.__addReachables ( canReach, cellKey ) except GoalFound: return True #-- 3 -- return False

mazeratty

# - - - M a z e . _ _ a d d R e a c h a b l e s def __addReachables ( self, canReach, cellKey ): '''Transitive closure of neighbor of cellKey. [ (canReach is a set containing cell-keys) and (cellKey is a cell-key) -> if there is a route from any cell in canReach to self.goal -> raise GoalFound else -> canReach := union ( canReach, all cell-keys that can be reached from cellKey without using any element of self.path ) ] '''

This function recursively evaluates the neighbors of
`cellKey`

, the neighbors of the neighbors,
and so on until one of two conditions is met.

If all neighbors have been recursively added, the method returns the set of all those neighbors.

If any neighbor is the goal cell, the method raises a

`GoalFound`

exception to skip any further evaluation. This optimization reduces execution time by a large multiple.

mazeratty

#-- 1 -- canReach.add ( cellKey )

For the function that generates the neighbors of a cell
that are not in `self.path`

, see Section 12.7, “`Maze.__genNeighbors()`

: Find the cells
adjacent to a given cell”.

mazeratty

#-- 2 -- for nabe in self.__genNeighbors ( cellKey ): if nabe == self.goal: raise GoalFound if nabe not in canReach: self.__addReachables ( canReach, nabe )

mazeratty

# - - - M a z e . _ _ c u t P a t h def __cutPath(self): '''Remove walls crossed by self.path. [ self.maze := self.maze - (the wall to the left of self.path[0]) - (the wall to the right of self.path[-1)) - (walls crossed by self.path) ] '''

First we cut a gap in the left wall for the entrance, and
another in the right wall for the exit. For the logic
that removes a wall, see Section 12.12, “`Maze.killWall()`

: Remove one
wall”.

mazeratty

#-- 1 -- # [ self := self - (wall to the left of # self.path[0]) ] r, c = self.path[0] self.killWall ( (r, c, 1) ) #-- 2 -- # [ self := self - (wall to the right of # self.path[-1]) ] r, c = self.path[-1] self.killWall ( (r, c+1, 1) )

For the internal walls, we walk the length of the path,
and use Section 12.11, “`Maze.__wallBetween()`

: What wall
divides two adjacent cells?” to find the
wall between each pair of adjacent cells.

mazeratty

#-- 3 -- # [ self := self - (walls within self.path) ] for i in range(len(self.path)-1): fromCell = self.path[i] toCell = self.path[i+1] target = self.__wallBetween ( fromCell, toCell ) self.killWall ( target )

mazeratty

# - - - M a z e . _ _ w a l l B e t w e e n def __wallBetween(self, fromCell, toCell): '''Find the endpoints of the wall between adjacent cells. [ fromCell and toCell are the cell-keys of adjacent cells within self -> return the wall-key of the wall between those cells ] ''' #-- 1 -- fromRow, fromCol = fromCell toRow, toCol = toCell

The caller guarantees that `fromCell`

and
`toCell`

are adjacent, but there is no
guarantee about their relative orientation. We need to
find the reference point X of the wall as shown in the
diagram.

For vertical walls, the cells are in the same row, and the column of point X is the greater of the column numbers of the two adjoining cells.

For horizontal walls, the cells are in the same column, and point X is the greater of the row numbers of the two adjoining cells.

mazeratty

#-- 2 -- # [ if fromRow == toRow -> # return the wall-key of the vertical wall between fromCell # and toCell # else -> # return the wall-key of the horizontal wall between fromCell # and toCell ] if fromRow == toRow: return ( (fromRow, max(fromCol, toCol), 1) ) # Vertical else: return ( (max(fromRow, toRow), fromCol, 0) ) # Horizontal

When we say a wall is “removed,” this does
not mean that the `Wall`

instance is
destroyed, only that its `.solid`

attribute
is set to `False`

so that it won't be drawn
on the canvas.

mazeratty

# - - - M a z e . k i l l W al l def killWall(self, wallKey): '''Remove (make not solid) the wall between p1 and p2. ''' #-- 1 -- # [ wallKey is a key in self.__wallMap -> # wall := the related value ] wall = self.__wallMap[wallKey] #-- 2 -- # [ wall := wall not solid ] wall.solid = False

Kruskal's algorithm requires that we maintain an invariant:
each cell's `.cellSet`

attribute is a set of
`Cell`

instances containing itself and all the
other cells that are reachable from there without going
through a solid wall. So, here we must check to see if the
removed wall divides cells of two different sets and, if
so, merge them. For the method that finds the cell(s)
adjacent to a given wall, see Section 12.13, “`Maze.getWallCells()`

: What cells
adjoin this wall?”.

mazeratty

#-- 3 -- # [ adjacents := list of Cell instances adjoining (wallKey) ] adjacents = self.getWallCells(wallKey)

If the wall does not separate two cells, we are done.

mazeratty

#-- 4 -- if len(adjacents) < 2: return else: fromCell, toCell = adjacents #-- 5 -- # [ if fromCell.cellSet is not identical to toCell.cellSet -> # fromCell.cellSet := union of fromCell.cellSet and # toCell.cellSet # cells in toCell.cellSet := those cells modified to # be in that union ] # else -> I ] if fromCell.cellSet is not toCell.cellSet: fromCell.cellSet |= toCell.cellSet for cell in toCell.cellSet: cell.cellSet = fromCell.cellSet

mazeratty

# - - - M a z e . g e t W a l l C e l l s def getWallCells(self, wallKey): '''Find the cell or cells adjacent to a given wall. '''

There are two cases, depending on whether the wall is
horizontal or vertical. The row and column from the
`wallKey`

are at the position marked
X in this diagram:

mazeratty

#-- 1 -- r, c, isVert = wallKey x = (r, c) result = []

Given that `(r,c)`

is the row and column of
the end of the wall closest to the origin, there are
two cases, each with up to two adjacent walls.

If the wall is vertical, the cell on the left is in the same row and the previous column, and the cell on the right is in the same row and column.

If the wall is horizontal, the cell above is in the previous row and the same column, and the cell below is in the same row and column.

However, because some walls are on the outside, each potential cell key is tested to see if it is within range before it is added to the resulting list.

mazeratty

#-- 2 -- # [ result +:= cells adjoining the wall from (r,c) with # orientation (isVert) ] if isVert: #-- 2.1 -- Wall is vertical leftCellKey = (r, c-1) if c > 0: result.append(self.__cellMap[leftCellKey]) if c < self.nCols: result.append(self.__cellMap[x]) else: #-- 2.2 -- Wall is horizontal aboveCellKey = (r-1, c) if r > 0: result.append(self.__cellMap[aboveCellKey]) if r < self.nRows: result.append(self.__cellMap[x]) #-- 3 -- return result

mazeratty

# - - - M a z e . _ _ k r u s k a l def __kruskal(self): '''Randomized Kruskal's algorithm for maze creation. [ self := self with all cells connected using Kruskal's algorithm ] '''

The first step is to build a list of all the walls in the maze, and then permute it randomly so that the walls between the cell sets are removed in a random order.

mazeratty

#-- 1 -- # [ wallList := wall-keys of all Wall instances in self, # shuffled into a random order ] wallList = [ wall.wallKey for wall in self.__wallMap.values() ] random.shuffle(wallList)

Each wall key in `wallList`

is considered in
turn.

If the wall is exterior, it will have only one adjacent cell; do nothing.

If the two adjacent cells are in different sets, we remove the wall and merge the adjacent cell sets.

mazeratty

#-- 2 -- # [ maze := maze with walls in wallList removed in order # so long as the adjacent cells are in different # cell sets ] for wallKey in wallList: #-- 2 body -- # [ if wall is between two cells with different cell sets -> # self := self with that wall removed and # the cell sets merged # else -> I ] #-- 2.1 -- # [ cellList := list of the cells adjacent to wall ] cellList = self.getWallCells(wallKey) #-- 2.2 -- # [ if (cellList has two elements) and (those elements # have different cell sets) -> # self := self with that wall removed and the # adjacent cell sets merged # else -> I ] if len(cellList) > 1: if cellList[0].cellSet is not cellList[1].cellSet: self.killWall(wallKey)

mazeratty

# - - - M a z e . r e n d e r def render(self, visible): '''Erase and redraw the maze onto the canvas. [ if visible -> self.can := self.can - (any existing elements) + (rendering of self with solution shown) ] else -> self.can := self.can - (any existing elements) + (rendering of self with solution not shown) ] '''

Because the canvas may be resized any time, we wait until rendering time to find its dimensions. We pick a cell size that is the largest that will allow square cells to fit on the canvas, minus twice the margin in both directions.

mazeratty

#-- 1 -- # [ self.canHigh := height of self.can # self.canWide := width of self.can ] self.canHigh = int(self.can['height']) self.canWide = int(self.can['width']) #-- 2 -- # [ self.cellSize := the largest cell interval that allows # self.nRows rows and self.nCols columns, with a margin # of size MARGIN all around # self.halfCell := half that value ] rowSize = (self.canHigh - WALL_THICK - 2*MARGIN) // self.nRows colSize = (self.canWide - WALL_THICK - 2*MARGIN) // self.nCols self.cellSize = min(rowSize, colSize) self.halfCell = self.cellSize / 2

Erase the canvas (using the `.find_all()`

method to enumerate all its elements). Draw all the
walls that are still solid: see Section 12.16, “`Maze.__tkWall()`

: Draw a cell
wall”. Then add a line of text
below the maze to allow its later regeneration; see Section 12.18, “`Maze.__annotate()`

: Add descriptive
text”.

mazeratty

#-- 3 -- # [ self.can := self.can, erased ] for oid in self.can.find_all(): self.can.delete(oid) #-- 4 -- # [ self.can := self.can + (all solid walls) ] for wall in self.__wallMap.values(): if wall.solid: self.__tkWall(wall.wallKey) #-- 5 -- # [ self.can := self.can with annotation added describing # the current maze ] self.__annotate()

Finally, draw the solution path if the caller wants it.
See Section 12.19, “`Maze.pathDraw()`

: Show the solution
path”.

mazeratty

#-- 6 -- # [ if visible -> # self.can := self.can + (self.path, rendered) # else -> I ] if visible: self.pathDraw()

mazeratty

# - - - M a z e . _ _ t k W a l l def __tkWall(self, wallKey): '''Draw one wall onto a canvas. ''' #-- 1 -- # [ (r1, c1) := vertex of wall closer to the origin # (r2, c2) := the opposite vertex ] r1, c1, isVert = wallKey r2, c2 = r1, c1 if isVert: r2 += 1 else: c2 += 1

For the function that converts row and column coordinates
to display coordinates, see Section 12.17, “`Maze.__toDisplay()`

: Convert to
display coordinates”.

mazeratty

#-- 2 -- # [ points := (display x coordinate of wall start, # display y coordinate of wall start, # display x coordinate of wall end, # display y coordinate of wall end) ] points = tuple ( [ self.__toDisplay(coord) for coord in (c1, r1, c2, r2) ] )

One subtle point about rendering walls: using `capstyle=PROJECTING`

makes walls slightly longer so
that they make a clean, sharp corner where two walls meet.

mazeratty

#-- 3 -- # [ self.can := can with a line added using (points) as the # vertices, with thickness WALL_THICK ] self.can.create_line(*tuple(points), capstyle=tk.PROJECTING, width=WALL_THICK, fill=WALL_COLOR, tags=WALL_TAG)

This method assumes that the upper left corner of
cell (0,0) is at display coordinate ```
(MARGIN,
MARGIN)
```

.

mazeratty

# - - - M a z e . _ _ t o D i s p l a y def __toDisplay(self, p): '''Convert p to display coordinates. [ p is a row or column number -> return the equivalent display coordinate ] ''' return MARGIN + p*self.cellSize

mazeratty

# - - - M a z e . _ _ a n n o t a t e def __annotate ( self ): '''Add annotation. [ self.can := self.can with annotation added describing the current maze ] ''' #-- 1 -- # [ xnw := x coordinate of the left side wall # ynw := y coordinate of a point just below the bottom wall ] xnw = self.__toDisplay ( 0 ) ynw = self.__toDisplay ( self.nRows ) + 3 #-- 2 -- totalCells = self.nRows * self.nCols percent = 100.0 * float(len(self.path)) / totalCells info = ( "%dR x %dC (%d cells); solution path %d (%.1f%%); " "seed %d" % (self.nRows, self.nCols, totalCells, len(self.path), percent, self.seed) )

The `anchor=tk.NW`

attribute orients the text
with its upper left (northwest) corner at the given point.

mazeratty

#-- 3 -- self.can.create_text(xnw, ynw, anchor=tk.NW, font=SMALL_FONT, tag=INFO_TAG, fill=INFO_COLOR, text=info )

mazeratty

# - - - M a z e . p a t h D r a w def pathDraw ( self ): '''Render the path in a contrasting color. '''

The path rendered as three elements: blobs (filled
circles) in color marking the start and goal cell, and
line segments joining the centers of the cells along the
solution path. See Section 12.20, “`Maze.__pathEdge()`

: Draw one segment
of the solution path” and
Section 12.22, “`Maze.blob()`

: Render one endpoint of
the solution”.

mazeratty

#-- 1 -- # [ self.can := self.can with internal arcs rendered ] for k in range(len(self.path)-1): #-- 1 body -- # [ self.can := self.can with a line of color PATH_COLOR # drawn between self.path[k] and self.path[k+1] ] self.__pathEdge(k) #-- 2 -- # [ self.can := self.can with starting cell set to # START_COLOR and goal cell set to GOAL_COLOR ] self.blob(self.start, START_COLOR) self.blob(self.goal, GOAL_COLOR)

mazeratty

# - - - M a z e . _ _ p a t h E d g e def __pathEdge ( self, k ): '''Draw one edge of the path. [ 0 <= k < len(self.path-1) -> self.can := self.can with a line of color PATH_COLOR drawn between self.path[k] and self.path[k+1] ] '''

See Section 12.21, “`Maze.__cellCenter()`

: Display
coordinates of the center of a cell”.

mazeratty

#-- 1 -- # [ p1 := center of cell self.path[k] # p2 := center of cell self.path[k+1] ] p1 = self.__cellCenter(self.path[k]) p2 = self.__cellCenter(self.path[k+1])

The constant defined in Section 7.1.5, “`PATH_THICK`

” is
only a maximum line thickness. For small cell sizes, we
adjust the line thickness down, but no smaller than one
pixel.

mazeratty

#-- 2 -- # [ if PATH_THICK is less than half self.cellSize -> # thickness := half of self.cellSize, or 1, # whichever is larger # else -> # thickness := PATH_THICK ] thickness = ( PATH_THICK if PATH_THICK < self.halfCell else max(1, self.halfCell-1) )

Tagging each line segment with `PATH_TAG`

is
necessary so that we can erase just the solution in
Section 12.23, “`Maze.pathErase()`

: Remove the solution
path from the canvas”. Using the projecting
cap style is necessary so that line segments that meet at
right angles will make a sharp corner.

mazeratty

#-- 3 -- # [ self.can := self.can with a line added ] self.can.create_line(*(p1+p2), #### capstyle=tk.PROJECTING, capstyle=tk.ROUND, width=thickness, fill=PATH_COLOR, tags=PATH_TAG)

mazeratty

# - - - M a z e . _ _ c e l l C e n t e r def __cellCenter ( self, cellKey ): '''Find the center of a given cell. [ cellKey is a cell-key -> return the display coordinates of the center of the cell with that cell-key as an (x,y) tuple '''

See Section 12.17, “`Maze.__toDisplay()`

: Convert to
display coordinates”.

mazeratty

#-- 1 -- # [ xnw := display x coordinate of the northwest corner of # cell with key (cellKey) # ynw := display y coordinate of the northwest corner of # cell with key (cellKey) ] r, c = cellKey xnw = self.__toDisplay ( c ) ynw = self.__toDisplay ( r ) #-- 2 -- return (xnw+self.halfCell, ynw+self.halfCell)

mazeratty

# - - - M a z e . b l o b def blob(self, cellKey, color): '''Draw a meatball of some color in a given cell. [ (cellKey is a cell-key in self) and (color is a Tkinter color) -> self.can := self.can + (a circle centered at the display coordinates of the center of cell (cellKey) and filled with color (color) ] '''

To draw a circle in Tkinter, one defines its bounding box
by two of its opposite corners. See Section 12.21, “`Maze.__cellCenter()`

: Display
coordinates of the center of a cell”.

mazeratty

cx, cy = self.__cellCenter(cellKey) radius = max(self.halfCell, 1) self.can.create_oval ( cx-radius, cy-radius, cx+radius, cy+radius, fill=color, width=0, tags=PATH_TAG )

Because each graphic element of the solution was tagged
with `PATH_TAG`

, we can ask the canvas to
find all the elements with that tag, and then delete
each.

mazeratty

# - - - M a z e . p a t h E r a s e def pathErase(self): '''Erase the solution path. ''' #-- 1 -- for oid in self.can.find_withtag ( PATH_TAG ): self.can.delete ( oid )

mazeratty

# - - - M a z e . p o s t s c r i p t def postscript(self, outFileName): '''Output the maze as PostScript. '''

Because the maze may not fill the entire canvas within the margins, we instruct the PostScript generation process to use only the part occupied by the maze, and to use landscape orientation if there are more columns than rows.

mazeratty

#-- 1 -- # [ xSize := width of area occupied by the maze plus margins # ySize := height of same area # landscape := True iff more columns than rows ] xSize = MARGIN*2 + self.cellSize*self.nCols ySize = MARGIN*2 + self.cellSize*self.nRows landscape = (self.nCols > self.nRows) #-- 2 -- # [ dest +:= PostScript rendering of self.can for width # (xSize), height (ySize), and orientation (landscape) ] self.can.postscript(file=outFileName, rotate=landscape, width=xSize, height=ySize)