4 ms·

Building a Maze by Destroying Walls Efficiently

61 points by abyx 16y ago

acangiano 16y ago
And a simple example of how to solve them: http://thinkcode.tv/catalog/amazing-python/ http://thinkcode.tv/catalog/amazing-python/
xuhu 16y ago
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 http://homokaasu.org/gasgames/game.gas?27
Jach 16y ago
To build and run (I expected a build.xml file): 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 I like the output of this maze algo even more than the standard recursive backtracker, plus it's more efficient; from a few walkthroughs it seems to generate slightly more challenging mazes as well. (A solver line would help showing this and any bias.) 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,
dsgrethr 16y ago
Click on our website: == ( http://qr.net/nwn http://qr.net/nwn ) == Christan Audigier bikini $23 Ed Hardy Bikini $23 Smful short_t-shirt_woman $15 ed hardy short_tank_woman $16 Sandal $32 christian louboutin $80 Sunglass $15 COACH_Necklace $27 handbag $33 AF tank woman $17 puma slipper woman $30 == ( http://qr.net/nwn http://qr.net/nwn ) == ~ ¤ ╭⌒╮ ╭⌒╮ ╭⌒╭⌒╮╭⌒╮～╭⌒╮ ,））））,''）~~ ,''~） ╱◥█◣ ╱◥█◣ ｜田｜田｜｜田｜田｜ ╬╬╬╬╬╬╬╬╬╬╬╬╬╬
teraflop 16y ago
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.
kragen 16y ago
I wrote a maze-generation program [0] in 1999 that used disjoint-set forests with path compression to generate mazes. Wikipedia didn't exist yet, so I didn't know what they were called, but I'm pretty sure I'd heard of them somewhere before. [0]: http://lists.canonical.org/pipermail/kragen-hacks/1999-February/000161.html 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.
- reemrevnivek 16y ago
  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.
S714726 16y ago
For those interested in maze generation, Jamis Buck's maze series (http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...) covers the whole spectrum of algorithms and has recently started on weave mazes.
- Acorn 16y ago
  Wow, this is a fantastic link, thanks for sharing!

61 points by abyx 16y ago

And a simple example of how to solve them: http://thinkcode.tv/catalog/amazing-python/ http://thinkcode.tv/catalog/amazing-python/

xuhu 16y ago

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 http://homokaasu.org/gasgames/game.gas?27

Jach 16y ago

To build and run (I expected a build.xml file): 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 I like the output of this maze algo even more than the standard recursive backtracker, plus it's more efficient; from a few walkthroughs it seems to generate slightly more challenging mazes as well. (A solver line would help showing this and any bias.) 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,

dsgrethr 16y ago

Click on our website: == ( http://qr.net/nwn http://qr.net/nwn ) == Christan Audigier bikini $23 Ed Hardy Bikini $23 Smful short_t-shirt_woman $15 ed hardy short_tank_woman $16 Sandal $32 christian louboutin $80 Sunglass $15 COACH_Necklace $27 handbag $33 AF tank woman $17 puma slipper woman $30 == ( http://qr.net/nwn http://qr.net/nwn ) == ~ ¤ ╭⌒╮ ╭⌒╮ ╭⌒╭⌒╮╭⌒╮～╭⌒╮ ,））））,''）~~ ,''~） ╱◥█◣ ╱◥█◣ ｜田｜田｜｜田｜田｜ ╬╬╬╬╬╬╬╬╬╬╬╬╬╬

teraflop 16y ago

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.

kragen 16y ago

I wrote a maze-generation program [0] in 1999 that used disjoint-set forests with path compression to generate mazes. Wikipedia didn't exist yet, so I didn't know what they were called, but I'm pretty sure I'd heard of them somewhere before. [0]: http://lists.canonical.org/pipermail/kragen-hacks/1999-February/000161.html 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.

reemrevnivek 16y ago
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.

S714726 16y ago

For those interested in maze generation, Jamis Buck's maze series (http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...) covers the whole spectrum of algorithms and has recently started on weave mazes.

Acorn 16y ago
Wow, this is a fantastic link, thanks for sharing!