I needed some sample code for a job application, and it was a little challenging coming up with a fun problem that could be solved in a couple hundred lines of code. I hope this fits the bill!
''' Jon Beckham <beckham@leftorium.net>, code sample Generates a minimally spanning maze, thickening the walls to match an input image. Samples available at http://strok.in/mazer Requires the Python Imaging Library. http://www.pythonware.com/library/pil/handbook/index.htm '''
Script: mazer.py
$ ./mazer.py
--input required.
usage: mazer.py [options]
options:
-h, --help show this help message and exit
-s SIZE, --size=SIZE set grid size of resultant maze [default: 30x30]
-c CELLSIZE, --cellsize=CELLSIZE
set size of maze cells [default: 10]
-i INPUT, --input=INPUT
image used for wall weighting
-o OUTPUT, --output=OUTPUT
resultant image file
The maze generation is performed using Prim's algorithm, which when given a large input space explodes the resources required for completion. A simple optimization would be to partition the cells into smaller squares, run Prim's on each partition, and destroy one wall between each resultant partition to minimally span the entire set of cells. This speed improvement obviously sacrifices the random appearance of the maze, though I'm sure it'd still be next to impossible to navigate.
