Next / Previous / Contents / Shipman's homepage

Abstract

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

Sample maze illustrated

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

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

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