My maze-fu is strong

mangobrain on 2007/04/01 19:30 of Super Spelunker

Super Spelunker is born!

What you see below is a randomly generated maze. I started with the standard depth-first search algorithm, added the width limitation which gives it the upside-down-pyramid shape, then tweaked the algorithm slightly to give more pleasing results.

• A "weighted roulette wheel" technique was used to give a bias towards horizontal corridors, which is both a game design decision and a measure to counteract the natural bias towards long vertical corridors, which presumably results from the X-axis limitation (i.e. pyramid shape).
• The algorithm keeps an explicit stack rather than using recursion; there is a small random chance that at the top of each iteration, a random item shall be chosen from the stack (instead of the top item). This greatly increases the amount of branching in the maze, as otherwise the algorithm effectively creates a single path from the start point, and branches more than a few cells long aren't seen until quite a way along it.

I'm not sure if the pyramid shape will be kept yet, or if it will be kept but turned upside down. I'm also not yet going to release any details of gameplay in the sense of how you will actually get around the maze (other than what's already written in my entry description); partly because they aren't finalised, but mostly because it's mysteeeerious.