Building a Maze by Destroying Walls Efficiently(codehowtos.blogspot.com)
codehowtos.blogspot.com
Building a Maze by Destroying Walls Efficiently
http://codehowtos.blogspot.com/2011/04/building-maze.html
7 comments
It's really more like 7 lines, with the bulk of the program logic in a single massive line that includes 3 comma-separated expressions and 6 conditional operators. It's called three lines because it's been mercilessly stripped to 79-character line widths.
That does however mean that it's a 237 character maze generator, which is still pretty cool.
That does however mean that it's a 237 character maze generator, which is still pretty cool.
This "efficient" algorithm takes O(n^2) time (where n is the number of grid squares) because it has to repeatedly remove elements from the middle of a list. It can easily be improved to O(n) by simply shuffling the list once and traversing it in order.
For those interested in maze generation, Jamis Buck's maze series (http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...) covers the whole spectrum of algorithms and has recently started on weave mazes.
Wow, this is a fantastic link, thanks for sharing!
To build and run (I expected a build.xml file):
Also to make more fun (Maze.java):
cd ai4u-read-only/com.ai4u.util/trunk/src
javac com/ai4u/util/*.java com/ai4u/util/disjointSet/*.java com/ai4u/util/games/maze/Maze.java
java com.ai4u.util.games.maze.Maze
Also to make more fun (Maze.java):
final int rows, cols;
if (args.length == 2) {
rows = Integer.parseInt(args[0]); cols = Integer.parseInt(args[1]);
} else {
rows = cols = 30;
}
final Maze m = createRandomMaze(rows, cols);
...
.addGap(0, 13 * cols,
...
.addGap(0, 13 * rows,I'm still puzzled how the Fulfillment[1] game builds a board by doing the opposite of this. Naively adding random walls clearly doesn't lead to a board filled with tetris pieces.
[1] http://homokaasu.org/gasgames/game.gas?27
[1] http://homokaasu.org/gasgames/game.gas?27
And a simple example of how to solve them: http://thinkcode.tv/catalog/amazing-python/
[0]: http://lists.canonical.org/pipermail/kragen-hacks/1999-Febru... "mazewiz in C (second iteration), posted to kragen-hacks 1999-02-16"
Joe Allen's three-lines-of-C maze generator (included in the post), however, blows the hell out of my program for coolness.