Generates a maze on the fly after entering the desired height of the maze. This compiled fine back in 1988 when I submitted it to the IOCCC (having rediscovered Eller's algorithm). Modern C compilers don't allow constant strings to be overwritten, which can be avoided by changing the first line to
Sadly neither version works here with an older clang on OS X. Both variants build fine with 9 warnings each. But the old variant dies with a "Bus Error: 10", and the new variant with "Segmentation fault: 11". Same with gcc (albeit only 8 warnings.)
/edit
OK, just wrong user input. You gotta feed it a number, and not a "foobar" or another random string.
For anyone interested in this, Jamis Buck's book 'Mazes for Programmers' is a masterpiece of the genre.
My personal favorite distinction is between the Recursive Backtracker (which creates long, winding corridors with few dead ends which is great for tower defense games) vs. Prim's Algorithm (which creates lots of short cul-de-sacs which is better for roguelikes). The bias of the algorithm dictates the feel of the game more than the graphics do.
My favorite maze algorithm is a variant of the growing tree algorithm - each time you carve a cell, add it to a random one of N lists. When choosing a cell to visit, pop the last cell off the first non-empty list. It's considerably faster than the standard tree algorithm, but more importantly, changing N has a dramatic impact on the texture of the maze (compare 1 2 4 8 etc on a decently large maze).
The main difference between the above tool and most custom shaped maze generators out there is breaking the assumption that the maze's outer shape must be defined by adding or removing regularly-shaped cells along the edge.
To have mazes look more human drawn, cells need to be irregular and the inner walls need naturally follow the contours of the outer shape.
I've always known about algorithms that solve mazes, but never about actually making them. It's interesting seeing all these algorithms and how the mazes they generate look different.
That's not a good link for a list of past threads since the idea for the latter is to include only the ones with interesting comments.
However, it looks like a good article that could use a repost! Just not soon, since we want to give enough time for the hivemind caches to clear :) - if you want to repost it in (say) a month or two, email us at [email protected] and we'll put it in the SCP (https://news.ycombinator.com/item?id=26998308).
Is it known which algorithms produce 'difficult' mazes? I'm imagining you could run all the maze solving algorithms against all the maze generating algorithms many times, and then calculate what the Nash equilibrium would be if the solver is trying to minimise expected time and the generator is trying to maximise it.
There is another old site ("since September 23, 1996"), my second favorite maze site, that has some articles about things like that. Like on the page below ("Tips on how to create difficult and fun Mazes, and how to solve and analyze them").
I think there is a difference if you want to make it only expensive to solve using popular maze solver algorithms, vs to make it difficult for a human to solve. Many of the recommendations on that page are for how to do things that can make a maze more difficult for humans to solve, but will not always matter to an algorithm that just mechanically tries solutions in some order.
seconding the jamis buck book, its one of the few programming books i actually finished. the way he explains each algorithm with visualizations makes it stick
It feels like many of the more complicated algorithms produce worse mazes (long horizontal/vertical walls, many 1-2 square dead ends next to another) than basic recursive backtracking.
reply