In my game we see the floors of a house from the side, and the hero can take lifts -- a lift either goes up (to the next lift upwards), or down (to the next lift downwards), depending on the arrow as shown, and there's always a pair of exactly two lifts connected. That's the only way the hero can move vertically, though he can freely move horizontally. The house map is a randomized 11x5 grid with different items, and unpassable walls to the far left, far right, and sometimes in one of the two middle positions:

lifts example

My question: How can I ensure the map is always randomized yet always solvable and that the hero, starting at the left side of the bottom floor, can always leave it via any upwards-pointing lift at the top floor?

For what it's worth I'm using the Lua language for development. Thanks so much!


What you want to do is create a Graph such that every node is an elevator position, and the edges between them means you can walk/lift there. Once you made the graph you can use dfs/bfs to see if you can get from the start node to the end node.

Using you example above I made a picture of how the graph would look like. Green circles means there is an elevator there, and the green lines means you can travel from node to node.


  • \$\begingroup\$ Thanks, that's very useful! I should have emphasized more in my question that the map also needs to be generated in the first place. What I'm now pondering is if it might not be easier -- rather than generating fully randomized lift/ wall combinations over and over and checking their solvability -- to have the algorithm step through the house, like the hero would, and this way generate random lifts and doors (by taking random lift distances and left-right turns, as well as adding walls, for instance). As in "Walk right either 0, 4 or 8 turns; create an upward lift, go up from 1 to 4 floors..." \$\endgroup\$ – Philipp Lenssen Mar 4 '12 at 10:01
  • \$\begingroup\$ @PhilippLenssen That is essentially the "randomized depth-first search" approach to maze generation on a graph. \$\endgroup\$ – Kevin Reid Mar 4 '12 at 14:13

The difference between what you have and a normal maze is simply that it has non-adjacent connections vertically. I think that what you should be looking at are graph-based maze generation algorithms. You simply need to have a larger set of "adjacent rooms" or "possible walls" than an ordinary 2D maze does, in that every vertically aligned pair of floor-grid-cells which does not already have an intervening lift is adjacent. You could model this as a graph where adding definite lift edges incidentally deletes other possible lift edges; some algorithms might be confused by this, but not others.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.