2D Procedural Terrain Generation - Guaranteeing connectedness?

I'm working on a 2D platformer in XNA. One of things I'd like to be a main design characteristic is procedural content generation. The first step of that is to procedurally generate the terrain. So, I've done loads of research on how to generate Perlin noise, smooth it out, play with parameters and all that jazz. I've also spent loads of time at pcg.wikidot.com. The problem I have is generating a level that is 100% connected. Meaning, it's possible for the character to get from the left part of the level all the way to the right part.

Right now, I use the perlin noise to generate a sprite when the noise value at that point is < 0.

Here is a video of the issue I'm having (please excuse the crazy background issues and the fact my character gets stuck when I generate a new level).

http://screencast.com/t/uWJsIGLoih

As you can see in the video, the terrain looks interesting enough, but you can't do a whole lot because the Perlin noise compartmentalizes the level into small, random chambers.

I attempted to perform a random walk and overlay the perlin noise on top of it, so I guarantee a path from left to right. The issue with that is illustrated below: http://screencast.com/t/ilLvxdp3

So my question is: What kinds of things can I do to ensure the player can get from the left part of the level to the right part of the level?

-

In using the word connectedness, you've come within a hair's breadth of the tool best suited to determining a solution: graph theory.

Connectedness is a property of graphs. Graphs can be either connected or disconnected (as you're experiencing, AKA a multigraph). Any game level, in any number of dimensions, can be represented as a graph, and logically, this is often the best way to manipulate them. Your game world is a graph in terms of the adjacency between the individual building blocks in your world; and also at the level of connectivity between your various areas. You can use the former to derive the latter.

There is a crucial point to consider when doing working with (2D) levels as graphs, and that is planarity. Depending on your requirements, planarity may or may not be a concern. Given your use of noise, I expect the latter, however I outline the options here so that you know what they are.

Planar graph - simplest example is a labyrinth. A labyrinth differs from a maze in that it contains no branchings -- it is unicursal. If you were to take a solid block of shrubbery(!), and generate a labyrith through it, then at no point could a turning that the labyrinth takes, run into an existing path. It's a bit like a game of Snake, really -- if the path is the snake's body, it cannot be allowed to bite/intersect itself. Further, you could have a planar maze; this would branch, but at no point could the branches be allowed to intersect existing parts of the maze already generated, just as with a labyrinth.

Non-planar graph - Simplest example is a city street map. A city is essentially a maze. However, it is a highly-connected maze in that there are many individual road routes to get from one place to another. Moreover, a non-planar graph embedding allows crossings, which is exactly what intersections are. And as we know, a city is not a city without intersections. They are integral to traffic flow. In games, this can be good or bad, depending on your goals. Good level flow allows AI to act more easily, and exploration to be freer; while on the other hand it also allows a player to get from startpoint to goal quickly -- potentially too quickly.

This brings us to your approach, which is to use noise. Depending on Perlin noise output is interpreted, it can have some level of connectedness as the macro scale, but it is not designed for 1-connectedness (a single graph). This leaves you a few options.

1. Drop the use of Perlin noise and instead generate a random, planar (non-crossing), connected graph. This provides maximum flow control. However this approach is non-trivial, because graph planarity requires the identification and removal of the Kuratowski subgraphs K3,3 and K5; as well as producing a subsequent planar embedding; both of which are NP-complete problems. This is without a doubt the hardest approach, but it had to be mentioned first to know where you stand. All other methods are a shortcut of some sort, around this method, which is the fundamental math behind maze generation.

2. Drop the use of Perlin noise and instead generate a random, non-planar graph embedded within a planar surface (AKA a planar embedding) -- this how games like Diablo and the roguelikes can be made to work easily, as they both use a grid structure to subdivide a planar space (in fact, the vast majority of levels in the roguelikes DO allow crossings, evident in the number of four way intersections). Algorithms producing the connectivity between cells or template rooms are often called "carvers" or "tunnellers", because they carve empty space out of a block of solid rock, incrementally.

3. Do as option (2), but avoid crossings. Thus both embedding (level geometry) is planar, and the topology (level flow) is also planar. You will have to be careful not to generate yourself into dead-ends, if you wish to avoid crossings.

4. Generate your map using noise. Then, using a flood fill algorithm on every cell in your unconnected level (which is a graph, albeit multipart and grid-based), you can deduce all unconnected, discrete subgraphs within that greater multigraph. Next, consider how you want to connect each individual subgraph. If you prefer to avoid crossings, I suggest a sequential connection of these. If not, you can connect them any way you wish. In order to do this organically, rather than producing hard, straight passages, I would use some sort of coherence function to meld the closest points of each pair of subgraphs (if linking sequentially). This will make the join more "liquid", which is in keeping with the typical Perlin output. The other way you could join areas would be to nudge them closer together, so there is some minimal overlap of the empty spaces.

5. Generate an excessively large map using noise. Isolate all subgraphs as described in option 3. Determine which is the most interesting, according to certain criteria (could be size, or something else, but size would be easiest). Pick out and use only that subgraph, which is already completely self-connected. The difficulty with this approach is that you may find it hard to control the size of your resultant graphs, unless you brute force generate a really large map, or many smaller ones, to pick your perfect subgraph. This is because the size of the subgraphs really depends on the Perlin parameters used, and how you interpret the result.

As an aside to the last two, something I'm sure you have already done, but just in case not: Create a minimal Perlin noise test case in Flash. Play around with parameters until you get a higher degree of connectivity between your "island" areas. I don't think this could ever solve your problem 100% across all generations, since Perlin noise has no inherent guarantee of connectedness. But it could improve connectedness.

Whatever you don't understand, ask and I will clarify.

-
This is an excellent answer. – tenpn Sep 5 '11 at 9:58
Then, you must cut down the mightiest tree in the forrest... with... a herring! – Jonathan Connell Sep 5 '11 at 11:53
Hahaha... yeah. – Arcane Engineer Sep 5 '11 at 15:52
I haven't implemented any of this solutions yet, but the information provided made me re-think some things and I think it answered my questions the best. So, I'm marking it as the answer. Thanks, all. – SpaDusA Sep 9 '11 at 3:23

General approaches to this problem:

1. Construct the map in a way that guarantees connectedness from the start. Many of the dungeon generators on PCG wiki work this way.
2. Generate a potentially disconnected map, and then write something (maybe a pathfinder) that checks for connectedness. Throw away the maps that don't work.
3. Generate a potentially disconnected map, and then fix it up whenever it's not connected. Whenever your checking algorithms find an area that's impassable, blast tunnels, build bridges, add teleporters, etc..
4. Generate a potentially disconnected map, and then give the player tools to connect things when needed. Turn the disconnected map bug into a feature. Terraria, Minecraft, etc. do this.
5. Generate a potentially disconnected map, and then make the player restart or move to a different level if the level can't be completed. I believe some roguelikes do this.

I agree with Kylotan that a noise function probably isn't ideal, but noise functions can do a lot and you might be able to fix it up in some way. See this article for some ideas.

-

A simple approach that's easy for you to adopt given your existing code is to keep generating random maps until one meets your connectedness constraint.

You can likely quickly check your connectedness constraint using a flood fill from the starting position. Does it fill all the way to a legal end-point?

You can likely do thousands of such checks per second, so its likely a perfectly acceptable hack.

-

That video's just confusing, and I can't work out what you're trying to show with it to be honest. But I would suggest Perlin noise is probably the wrong algorithm for the job. It's designed for smoothly undulating continuous entities, whereas you're trying to make scattered and discrete entities. What would probably work better is using random values to re-arrange and adjust hand-designed arrangements of platforms to ensure that the resulting area is playable.

There's some information on how Spelunky did this here: http://tinysubversions.com/2009/09/spelunkys-procedural-space/

-

Try modifying the perlin value based on height, i.e. at the bottom add 1 to the noise value, at the top subtract 1 from the noise value, and in between linearly interpolate between 1 and -1. This way, at the bottom you will almost be guaranteed to get a value >= 0 and at the top you will be almost guaranteed to get a value <= 0.

This is assuming values < 0 is supposed to be air. If I understand your description correct, you'll have to switch it around.

Cheers.

-
So I attempted you method and I got a result the following result: screencast.com/t/vxnc0LHbLGPQ I'm not really sure that helped out my problem. I still have to post-process to ensure connectedness. – SpaDusA Sep 4 '11 at 2:36