Archive for August, 2009

Procedural Road Generation

In the past weeks, I have approached the issue of generating procedural roads at runtime based on different maps generated by the Engine. The road generation is based on self-sensitive L-Systems.  This article will outline what L-Systems are and how I have started to use them to procedurally generate road networks.

This can be a pretty tricky subject depending on how authentic you want to make it; on the one hand you could generate random points on a terrain to represent towns and join them with lines, branch a few more lines off these and call it a road map. This would probably look okay, but inevitably you’re going to end up with roads which lead off to nowhere or two roads which illogically zigzag across one another, or which go up impossibly steep inclines or in water etc., all of these scenarios would seriouly affect the game play in a negative way.

However on the other hand, you could go all out and take into consideration the town positions, population density, altitude and slope information, culture and the time period and base the road generation on all of this. Obviously this would be ideal, but generating this at runtime would probably take a long time, depending at what resolution you generate the road maps. Because Britonia will be a trading and exploration game, the option for the player to follow a road to see where it leads should mean that the player is not simply left stranded in a forest, thinking “well who would have built a road here!?”.

I found an article by Pascal Müller on his site here. You can find the article in German at the bottom of the page, and there is also a shorter, less detailed version in English half way down the page. It is from the German version that I am basing the rules for generating the roads on.

L-Systems and making them self-sensitive:

I’m just going to paste the wikipedia definition of L-System first, because that pretty much sums up what L-Systems are:

“An L-system (Lindenmayer system) is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms. L-systems can also be used to generate self-similar fractals such as iterated function systems.”

What this means is, we can start out with a string of characters, such as “AB” and pass these into various functions, which are called productions. The productions have a set of variables which check the given string for any patterns called predecessors and if any are found, then it replaces those characters with a new set called successors (parallel rewriting system). Because this rewriting is based on a limited number of rules, and because we can iterate through our ‘string’ as often as we want, this produces the self-similar fractals mentioned above.

Let’s take Lindenmayer’s original L-System for modelling the growth of Algae as an example:

For this we start out with the string “AB” and we have two productions.  The first production replaces all instances of the character ‘A’ with ‘AB’.  The second production replaces all instances of the character ‘B’ with ‘A’.   We can run the string through this two productions <X> number of times, and each time the string will gradually grow with a specific pattern.  Consider the following code:

private void GenerateString()
{
    string Axiom = "AB"; // The initial string

    for(int i = 0; i < maxDepth; i++)
    {
        Axiom = Production1(Axiom); // Run the first production set.
        Axiom = Production2(Axiom); // Run the second production set.
    }
}

/// This production will search the current string for all instances of the character 'A' and
/// replace them with the characters 'AB'.  This will cause the string to expand each
/// time the production is applied to the current string.
private void Production1(string currString)
{
    string returnString = "";
    bool lbFound = false;
    foreach(char instr in currString)
    {
        if(instr == 'A'
        {
            returnString += 'A';
            returnString += 'B';
            lbFound = true;
        }
    }

    // If this production was not applied to any characters in
    // the current string, then pass out the unmodified string.
    if(!lbFound) returnString = currString;
}

/// This production will search the current string for all instances of the character 'B' and
/// replace them with the characters 'A'.
private void Production2(string currString)
{
    string returnString = "";
    bool lbFound = false;
    foreach(char instr in currString)
    {
        if(instr == 'B'
        {
            returnString += 'A';
            lbFound = true;
        }
    }

    // If this production was not applied to any characters in
    // the current string, then pass out the unmodified string.
    if(!lbFound) returnString = currString;
}

Running this system 5 times will yield the following results:

Photobucket

While this may not look very useful, imagine now that we also assign a drawing command to each of the characters in the resulting string after 5 iterations.  This would enable us to draw some pretty complex patterns with a relatively small and easy piece of code.

As another quick and slightly more interesting example, take the following instruction set:

start : X
Production : (X → F-[[X]+X]+F[+FX]-X), (F → FF)
angle : 25°

In this example, ‘F’ means “draw forwards”, a ‘-‘ will be interpreted as “rotate angle -25°”, a ‘+’ will increment the angle 25°. the ‘[‘ and ‘]’ push and pop the current position and angle on a stack, so we can branch different instructions. Using the above simple L-System, we can produce images like this:

Photobucket

Again, while this may not seem all that graphically realistic, it is possible for us to assign our own graphics to each instruction, therefore we could use real textures for the stem and leaves etc. This was done to great effect in Asger Klasker’s Ltree project (http://ltrees.codeplex.com/ ).

Input Maps:

There is a problem emerging here though as we cover the basics of L-Systems.  How can we use input (i.g. the environment) to direct the growth of the patterns?  To do this we can assign functions to different instructions which are run in the correct sequence and can be use to make sure certain conditions are met.  Such instructions are used in road generation to check the height under the current position and end position to make sure the gradient is not too high etc.  These are some of the input maps which I am using to generate the road maps at the minute:

Water and Parks Map:

parks and water map

The idea of this map is to define which areas are out-of-bounds for road generation. We can use this map to also model bridges and fords by using the full range of colours in each pixel. Fords are achieved by allowing the roads to cross only at places where the water level is shallow enough, say:

waterLevel-20 <= roadLevel <= waterLevel.

Because roads cannot be built in (deep) water, we can check the end coordinates of a road’s position, and if water occurs between these two points, then we could place a bridge to allow the player to cross the river. We can also limit this action to only allow main roads to have bridges, that way there is only a limited number of bridges built in any one city.

Altitude (height) Map:

Photobucket

Again we can use this map to define where roads can and cannot be built. Using the height map we can also check the gradient of the planned road and ensure that roads are not built steeper than what the player is able to climb. It is also possible for us to define that the main roads should try and follow the contour of the hills, so we get roads which spiral upwards instead of just going straight from the bottom to the top.

Population Density Map:

pop density map

The population density map is used to steer the roads and motorways in meaningful directions. Areas with a higher population density will usually have a higher density of roads.

Profiles:

There are two major profiles that I’ve been looking at for generating the road maps. The first is a ‘New York’/urban style road generation, which creates dense grid like road networks. While this will not be used in Britonia, I would like to add this capability to the Galaxis Engine so that in the future, any space games made with the Engine can generate modern cities on the surface. The second profile is a medieval/rural profile which looks a lot more organic, with long curving streets branching out from each other. This will be more suited to medieval street maps, whereby the land shapes the streets more than functionality.

New York / Urban:

Photobucket

This is one outcome for procedurally generating a street plan based on New York. The streets are basically created with a vary small chance of the heading changing for forward facing road sections. Then, every <x> pixels/meters I can define a branch in the road in three seperate directions at 90° from each other (fwd, left and right). This helps to produce the block effect.

Rural:

rural street plan

This is my attempt at generating a street plan for a rural, high mountain area. To achieve this, I set the size of the main road sections much smaller than in the urban map, and also increased the chance that the heading (angle) changes with each section, resulting in streets which are curve instead of straight. so there shouldn’t be as many well defined ‘blocks’ as you might find in New York city etc. I also cut down on the number of branches in the roads, from 3 to 2. This effect doesn’t look to bad and it is possible to tweak the parameters further still to create larger or smaller settlements.

Improvements:

I am still working on the road generation instructions, and there are several things which I hope to finish soon.  At the minute the population density map doesn’t have such a big influence on the generation of the roads.  I am thinking to leave the road generation as it is and just us the population map to determine the actual buildings which will be placed on the land.

Source Code:

The source code will be made available as soon as I have made it friendlier to use.  I will create a download link on the left,  but if anyone wants to see the source before hand then just send me a mail and I’ll forward it to you.  The solution has been created with XNA 3.1, so make sure you have that before running it. The project generates a lot of garbage as everything uses large amounts of strings, so it most definately shouldn’t be used as is in your game. I haven’t done this, but perhaps using StringBuilder would be a better solution and would cut down garbage.

If you have any comments or criticism, then feel free to post on the forums here, but please remember that this was a proof of concept application, and as such I made it with readability in mind, not speed, so there are a great many optimisations which could and should be implemented before you use this in your own projects.

You can get the source code here

Advertisements

4 Comments