Difference between revisions of "Brain Maze"

From Noah.org
Jump to navigationJump to search
m
m
Line 8: Line 8:
 
/* 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 in less than 400 ms when set for 6 iterations. It can do 10 iterations in under 2 minutes producing an output of 2047 columns by 2047 rows, taking 4 MB of ASCII text (XPM format). This is easily converted to PNG. You may click on the following link to view the maze: [[file:big_maze.png]]  
+
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 producing an output of 2047 columns by 2047 rows, taking 4 MB of ASCII text (XPM format). This is easily converted to PNG. You may click on the following link to view the maze: [[Media:big_maze.png]]
  
 
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 18:29, 9 May 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 producing an output of 2047 columns by 2047 rows, taking 4 MB of ASCII text (XPM format). This is easily converted to PNG. You may click on the following link to view the maze: Media:big_maze.png

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" />