Next / Previous / Contents / TCC Help System / NM Tech homepage

12. class Maze: The maze and its rendering

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:

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 ]
    '''

12.1. Maze.__init__(): Constructor

mazeratty
# - - -   M a z e . _ _ i n i t _ _

    def __init__(self, canvas):
        '''Constructor.
        '''
        self.can = canvas

12.2. Maze.generate(): Create a new maze

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)

12.3. Maze.__buildMaps(): Construct cells and walls

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)

12.4. Maze.__addWall(): Build one wall

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 (row, col, isV) that specifies the starting row, the starting column, and the orientation respectively. See Section 15, “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)

12.5. Maze.__makePath(): Create the solution path

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(a, b) function returns a value in the half-open range [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()

12.6. Maze.__extendPath(): Add one cell to the path

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.

12.7. Maze.__genNeighbors(): Find the cells adjacent to a given cell

To automate the process of finding a cell's neighbors, we declare a class variable DELTAS that is a list of (Δr, Δc) values such that Δr is a row offset and Δc is a column offset of one of the neighbors.

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

12.8. Maze.__exitCheck(): Is there an open route to the goal from this cell?

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

12.9. Maze.__addReachables(): Compute the transitive closure of the neighbor relation

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 )

12.10. Maze.__cutPath(): Remove walls along the solution route

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 )

12.11. Maze.__wallBetween(): What wall divides two adjacent cells?

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

12.12. Maze.killWall(): Remove one wall

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

12.13. Maze.getWallCells(): What cells adjoin this wall?

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

12.14. Maze.__kruskal(): Connect remaining cells to the solution

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)

12.15. Maze.render(): Draw the maze on a canvas

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()

12.16. Maze.__tkWall(): Draw a cell wall

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)

12.17. Maze.__toDisplay(): Convert to display coordinates

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

12.18. Maze.__annotate(): Add descriptive text

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 )

12.19. Maze.pathDraw(): Show the solution path

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)

12.20. Maze.__pathEdge(): Draw one segment of the solution path

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)

12.21. Maze.__cellCenter(): Display coordinates of the center of a cell

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)

12.22. Maze.blob(): Render one endpoint of the solution

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 )

12.23. Maze.pathErase(): Remove the solution path from the canvas

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 )

12.24. Maze.postscript(): Export the contents of the canvas as PostScript

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)