A procedurally generated city (2d)-Part 1 : The nodes

I haven't really seen many examples on how to create a 2d procedurally generated city, most of the tutorials out there for procedural maps are focused to dungeons / caves.

I wanted to create a 2d top down city (not like...full of detail, but something that could pass for a city). I did try a couple cave-based approaches out there, but they did never look close to what a city (or neighborhood!) could look like.

After some investigation I came on with how L-Systems work...and since they give you full control on what you produce, they seemed promising! (see this)

Basically, an L-System is a ruleset through which you will pass some kind of input to transform it (strings are used frequently). Check the L-System wiki page

During these posts series, I will show how my L-System ended up being shaped.

In this first part, I will describe the L-nodes for my city generator:

  • A block
  • A road (or street, whatever you preffer)

With just these two, I can create a square-ish city, which, for a top down 2d game, I think is enough.

public abstract class CityNode{  
    public Rectangle bounds;
    public Color color = Color.WHITE;

    public CityNode(){
        this.bounds = new Rectangle();
    }

    /** Grows this node and stores the result into the passed array */
    public abstract void grow(Array<CityNode> nodes);

    @Override
    public String toString() {
        return bounds.toString();
    }
}

The bounds are what will delimit our square node, and the color is for drawing purposes (when we get to it!).

The important thing for our nodes is the implementation of that grow() method.
Let's see in detail our specific nodes (block and road).

public class CityBlock extends CityNode{  
    private boolean isHorizontalBlock;
    CityGenerator.CityGeneratorOptions opt;
    private Array<CityBuilding> buildings;

    private CityBlock(boolean isHorizontal, CityGenerator.CityGeneratorOptions options){
        super();
        color = new Color(0,1,0,1);
        this.isHorizontalBlock = isHorizontal;
        opt = options;
    }

    public CityBlock(int x, int y, int width, int height, CityGenerator.CityGeneratorOptions options, boolean isHorizontal){
        this(isHorizontal, options);
        bounds.set(x, y, width, height);
    }

    public CityBlock(int x, int y, int width, int height, CityGenerator.CityGeneratorOptions options){
        this(x, y, width, height, options, false);
    }

    @Override
    public void grow(Array<CityNode> output) {
        if (isHorizontalBlock)
            growHorizontalBlock(output);
        else
            growVerticalBlock(output);
    }

    private void growVerticalBlock(Array<CityNode> output){
        if (bounds.width <= opt.minBlockWidth)
        {
            output.add(this);
            return;
        }

        split(output);
    }

    private void growHorizontalBlock(Array<CityNode> output){
        if (bounds.height <= opt.minBlockHeight)
        {
            output.add(this);
            return;
        }

        split(output);
    }

    /** split the block into two more blocks, divided by a road */
    private void split(Array<CityNode> output){
        if (isHorizontalBlock){
            CityBlock top = new CityBlock(false, opt);
            Road road = new Road(true);
            CityBlock bottom = new CityBlock(false, opt);

            int minRoady = (int) (bounds.height * 0.35f + bounds.y);
            int maxRoady = (int) (bounds.height * 0.65f + bounds.y);

            int roadX = (int)bounds.x;
            int roadY = MathUtils.random( minRoady, maxRoady);

            road.bounds.set(roadX, roadY, bounds.width, MathUtils.random(opt.minRoadWidth, opt.maxRoadWidth));

            top.bounds.set(
                    bounds.x, 
                    road.bounds.y + road.bounds.height, 
                    bounds.width, 
                    (bounds.height + bounds.y) - road.bounds.y - road.bounds.height);

            bottom.bounds.set(
                    bounds.x, 
                    bounds.y, 
                    bounds.width, 
                    bounds.height - road.bounds.height - top.bounds.height);


            if (bottom.bounds.height < opt.minBlockHeight || top.bounds.height < opt.minBlockHeight)
                output.add(this);
            else
                output.addAll(top, road, bottom);
        }else{
            CityBlock left = new CityBlock(true, opt);
            Road road = new Road(false);
            CityBlock right = new CityBlock(true, opt);

            int minRoadX = (int) (bounds.width * 0.4f + bounds.x);
            int maxRoadX = (int) (bounds.width * 0.6f + bounds.x);

            int roadX = MathUtils.random( minRoadX, maxRoadX);
            int roadY = (int)bounds.y;

            road.bounds.set(roadX, roadY, MathUtils.random(opt.minRoadWidth, opt.maxRoadWidth), bounds.height);

            left.bounds.set(
                    bounds.x, 
                    bounds.y, 
                    road.bounds.x - bounds.x, 
                    bounds.height);

            right.bounds.set(
                    road.bounds.x + road.bounds.width, 
                    bounds.y, 
                    bounds.x + bounds.width - road.bounds.x - road.bounds.width, 
                    bounds.height);

            if (left.bounds.width < opt.minBlockWidth || right.bounds.width < opt.minBlockWidth)
                output.add(this);
            else
                output.addAll(left, road, right);
        }
    }

When we grow a block, we basically split it into two other blocks (not right at the middle of the block, just to not have a totally symetric city..). The split method does all the work, it takes coordinates within itself to determine where is the road going to be located, and how wide this road is going to be, because there are streets of different sizes in each city!.

The blocks are considered to be either horizontal or vertical, this type is only useful to know how we are going to split the block; this means where the splitting road will be located in within our block.
I guess it's way easier to see it graphically, so here's what above code is doing:

Vertical and Horizontal block difference

Notice how a road never "grows", it just stays the same:

public class Road extends CityNode{  
    @Override
    public void grow(Array<CityNode> output) {
        output.add(this);
    }
}

So, these are the rules for our city generator:

RD = RD  
VB = HB RD HB  
HB = VB RD VB

where:  
    RD = Road
    VB = Vertical Block
    HB = Horizontal block

It would have probably been better to first describe the L-System, and then show the code...but guess it's not that hard to understand the other way around.

A first test pass of our L-System (3-step iteration) with the input expression VB should give us this:

   map = VB
   map = HB RD HB                                            // 1st iteration
   map = VB RD VB RD VB RD VB                                // 2nd iteration
   map = HB RD HB RD HB RD HB RD HB RD HB RD HB RD HB        // 3rd iteration

Let's see how it should look:

Image for L-system example

That's just an approximation on how it should look...Next time we will actually create something which will allow us to see how our city layout looks.

comments powered by Disqus