13
\$\begingroup\$

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!

\$\endgroup\$
0
14
\$\begingroup\$

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.

nodes

\$\endgroup\$
2
  • \$\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\$ 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
5
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .