How can I generate a (relatively) linear dungeon path?

Question

We developing a concept for an action side-scroller. What we need is a way to generate a (relatively) straight map. By this I mean something like...

It's clear to see that this map follows one simple route, even if it deviates a bit. With that, we're also going to implement straying pathways -- shortcuts, or secret passages. So that, perhaps, to get from the third circled area to the fourth, you'd have the main path, and a secret passageway that's filled with stronger enemies, but is faster and has higher rewards.

Here we've reached an impasse. We're exploring a few options but haven't really made any progress. What approach could we use to generate this kind of path We're not bound by programming languages, as so far we've experimented with Java, C# and C++. Similarly, we don't have any current dependencies on specific game engines.

Answer 1

Requirements

1. You want multiple paths from A to B.
2. You want to work in grid space, presumably this is tile space for your side-scroller.
3. You don't want paths to cross, or it will spoil game progression.
4. You want the paths to look reasonably organic.

Voronoi Diagrams

Voronoi Diagrams are space-filling, planar graphs:

One nice thing about them is how you can use them to create organic paths. If you draw a straight line from centre to centre you will get quite an unpredictable (read: non-ortholinear) path.

How to create a Voronoi Diagram for use with a tile-based system

Create a map of some reasonable size, say 128x128. Generate n random grid coordinates (x,y) in the map and populate each with a unique id / colour. Create a list for that colour, and add that starting cell to it; do this for each colour.

Now you have these uniquely colour points floating in a void, but you need to create whole islands of colour around them, with end result looking so:

To do that we need to see which colour owns each cell in the map (cell = pixel in the image above). We run through every cell in the map, checking which of our n starting colour points is closest to it (via pythagoras). That cell goes into the list associated with that unique id / colour... hereafter referred to as islands AKA Voronoi cells (in above diagram, groups of pixels with same colour).

You should now have a quantised Voronoi diagram. The next step is to analyse the adjacency of each island to other islands. Set up a simple node and edge struct so you can store a graph (node is just the id, the list for that id, and an empty list of edges; edge is just the start and end node). For each uniquely id'ed island, create a node, and add edges to link it to each island it is adjacent to.

Once you have the complete diagram (graph), you get to the fun part - use the graph to find chains of islands, and by making all the cells in each island in the chain have the same ID, you're carving out one of your paths. Let's say an island with all cells having ID 503 is sitting next an island with id 657. You can replace all 503 cells with a 657 ID, thus creating one larger island of adjacent 657s.

For example - red is path 1, blue is path 2, magenta is both:

You can use any existing graph algorithms (A* included) to generate the paths from start to finish. Getting a meandering path is a case of not always using the optimal step toward the goal island.

Lastly, it is trivial to shrink the islands if you want narrower paths, or to use a larger map with many more islands in order to get finer resolution.

An optional, final step, for pathfinding

Either you can use the high-level graph you built in conjunction with the underlying cells / tiles to do runtime A*, OR you can do Hill climbing on the underlying cells / tiles for better motion:

At the centre (or any) coordinate of your goal island, you can place an influence cell. This influence can pump out "scent" as in Collaborative Diffusion. This scent will spread all the way down the path back to what was the start island, getting weaker and weaker as it goes. Now for an entity at the start, we simply climb from a lower-scented cell to higher-scented one, each time bringing you closer to the goal - the same way a dog operates. Each path being roughly linear, this allows you to avoid using A* at runtime. Or you can do the same with the graph of islands, but that way is a bit more complex because you'll probably want to navigate your entities at the tile level. So the first way is perhaps better. Either way will allow you to navigate to the goal at low processing cost.