Ensure house map maze with lifts can be solved?

Question

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:

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!

Answer 1

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.

Answer 2

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.