Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...

enter image description here

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.

share|improve this question
11  
I'd add that it's not clear what is the end result you're looking for. The 'map' that you show is a top-down view of a region. You're developing a 2d side-scroller. How are the 2 related? – Alexandre Vaillancourt Mar 7 at 16:20
    
I removed the "best" phrasing from your question, as it's not really helpful. I also removed your three suggested approaches, which are all potentially valid answers. It's generally better if you don't include potential solutions in your question as comparing provided solutions is generally not a query we consider on-topic here (but asking how to solve the problem absent any existing solution bias usually is). I also cleaned up some of the comment chatter I feel is obviated by the edits. – Josh Petrie Mar 7 at 18:03
1  
That line looks almost exactly like what I got when I started with a straight line and added perlin (or simplex) noise to it (several octaves). Might be an area to explore (I was creating dynamic time varying lightening) – Richard Tingle Mar 7 at 22:02
up vote 14 down vote accepted

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:

enter image description here

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:

enter image description here

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:

enter image description here

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.

share|improve this answer
    
I made a map generator using Voronoi and Perlin Noise in Java, maybe it can be useful for you as an starting point: github.com/dragondgold/Map-Generator – Andres Mar 7 at 23:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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