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?
Answer
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.
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.
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.
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.
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.
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.
No comments:
Post a Comment