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

Abstract

Design and implementation of a Python program to generate satisfyingly challenging pencil mazes.

This publication is available in Web form and also as a PDF document. Please forward any comments to tcc-doc@nmt.edu.

Table of Contents

1. Why does the world need another maze generator?
2. Uploadable files
3. Design overview
3.1. Kruskal's algorithm
3.2. Improving the solution path
3.3. Generating the solution route
4. Operation of the script
5. Prologue
6. Imports
7. Manifest constants
7.1. Constants for the canvas
7.2. Colors
7.3. Fonts
8. Exceptions
9. Specification functions: cell-key and wall-key
10. main(): The main program
11. The App class: The application as a whole
11.1. App.__init__(): The constructor
11.2. App.__commandLine(): Process the command line arguments
11.3. App.__newSeed(): Randomize the random seed
11.4. App.__createWidgets(): Create all Tkinter widgets
11.5. App.__seedHandler(): Regenerate with a given random seed
11.6. App.__showHandler(): Turn display of the solution on or off
11.7. App.redoHandler(): Regenerate the maze
11.8. App.saveHandler(): Save the current image
12. class Maze: The maze and its rendering
12.1. Maze.__init__(): Constructor
12.2. Maze.generate(): Create a new maze
12.3. Maze.__buildMaps(): Construct cells and walls
12.4. Maze.__addWall(): Build one wall
12.5. Maze.__makePath(): Create the solution path
12.6. Maze.__extendPath(): Add one cell to the path
12.7. Maze.__genNeighbors(): Find the cells adjacent to a given cell
12.8. Maze.__exitCheck(): Is there an open route to the goal from this cell?
12.9. Maze.__addReachables(): Compute the transitive closure of the neighbor relation
12.10. Maze.__cutPath(): Remove walls along the solution route
12.11. Maze.__wallBetween(): What wall divides two adjacent cells?
12.12. Maze.killWall(): Remove one wall
12.13. Maze.getWallCells(): What cells adjoin this wall?
12.14. Maze.__kruskal(): Connect remaining cells to the solution
12.15. Maze.render(): Draw the maze on a canvas
12.16. Maze.__tkWall(): Draw a cell wall
12.17. Maze.__toDisplay(): Convert to display coordinates
12.18. Maze.__annotate(): Add descriptive text
12.19. Maze.pathDraw(): Show the solution path
12.20. Maze.__pathEdge(): Draw one segment of the solution path
12.21. Maze.__cellCenter(): Display coordinates of the center of a cell
12.22. Maze.blob(): Render one endpoint of the solution
12.23. Maze.pathErase(): Remove the solution path from the canvas
12.24. Maze.postscript(): Export the contents of the canvas as PostScript
13. class Path: The solution path
13.1. Path.__init__()
13.2. Path.add(): Add the next cell in sequence
13.3. Path.__iter__(): Return an iterator for the path
13.4. Path.__len__(): How many cells are in the path?
13.5. Path.__getitem__(): Get one cell in the path
13.6. Path.__contains__(): Test whether a cell is in the path
14. class Cell: One cell in the maze
15. class Wall: One wall in the maze
16. fatal(): Write a message and terminate
17. Epilogue

1. Why does the world need another maze generator?

Here is the rationale for this project.

  • Some people, including the author, find pencil mazes an amusing pastime.

  • The present program presents what may be a novel way to generate mazes that tend to be more challenging than mazes generate using algorithms in wide use.

  • This project is an example of lightweight literate programming: the program itself is contained in the documentation, rather than embedding documentation in the program or making it a separate entity.

  • This project is also an example of Cleanroom software engineering. In particular, comments [ within square brackets ] are Cleanroom intended functions, an informal mathematical notation used to verify the correctness of the implementation.

  • The project demonstrates the use of the Python language and two Python subsystems: the Tkinter graphical user interface and the pexpect module for running auxiliary processes.

Creative Commons attribution, share alike, non-commercial license. This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.