Difference between revisions of "Brain Maze"
m |
m |
||
Line 4: | Line 4: | ||
This is a fractal algorithm I created for generating mazes. I think it's pretty neat. The original was written in C for a computer science class I was taking at UCSC. This version is in Python. The original would print spaces and hashes (#) to display the maze. | This is a fractal algorithm I created for generating mazes. I think it's pretty neat. The original was written in C for a computer science class I was taking at UCSC. This version is in Python. The original would print spaces and hashes (#) to display the maze. | ||
− | In this version I also added HTML output. When I came up with the algorithm there were fewer than 1000 web sites | + | In this version I also added HTML output. When I came up with the algorithm there were fewer than 1000 web sites -- it wasn't popular yet. My original C source has this comment explaining the limit to the number of recursive iterations that could be done: |
<pre> | <pre> | ||
/* Six is the max value that seems to work on a 640K DOS machine */ | /* Six is the max value that seems to work on a 640K DOS machine */ | ||
</pre> | </pre> | ||
Nowadays, my Apple Mac Mini with a dual core 1 GHz CPU can run the interpreted Python version | Nowadays, my Apple Mac Mini with a dual core 1 GHz CPU can run the interpreted Python version | ||
− | in less than 400 ms when set for 6 iterations. | + | in less than 400 ms when set for 6 iterations. It can do 10 iterations in under 2 minutes. |
+ | |||
This generates a random maze with no loops. It is a [http://en.wikipedia.org/wiki/Spanning_tree_%28mathematics%29 spanning tree] -- ''a connected, undirected graph that uses all the vertices in a graph with no cycles''. | This generates a random maze with no loops. It is a [http://en.wikipedia.org/wiki/Spanning_tree_%28mathematics%29 spanning tree] -- ''a connected, undirected graph that uses all the vertices in a graph with no cycles''. |
Revision as of 04:16, 28 March 2010
This is a fractal algorithm I created for generating mazes. I think it's pretty neat. The original was written in C for a computer science class I was taking at UCSC. This version is in Python. The original would print spaces and hashes (#) to display the maze.
In this version I also added HTML output. When I came up with the algorithm there were fewer than 1000 web sites -- it wasn't popular yet. My original C source has this comment explaining the limit to the number of recursive iterations that could be done:
/* Six is the max value that seems to work on a 640K DOS machine */
Nowadays, my Apple Mac Mini with a dual core 1 GHz CPU can run the interpreted Python version in less than 400 ms when set for 6 iterations. It can do 10 iterations in under 2 minutes.
This generates a random maze with no loops. It is a spanning tree -- a connected, undirected graph that uses all the vertices in a graph with no cycles.
You can run the brain maze algorithm by clicking here: Generate a Brainmaze
The mazes generated by this algorithm are made up of the following maze atoms:
# # ### ### ### # # ### # # # # # # ### # ### # # ### ### # # ###
This can be simplified by removing rotated copies to these two mazeatoms:
### # # # # ### # # # #
Click here to download: brainmaze.py <include src="/home/noahspurrier/noah.org/engineering/src/python/brainmaze.py" highlight="python" />