Monday, December 13, 2010

Coding - District Map Generation

How about a coding article? It's been quite a long time, so let's have one.
Let's start with some simple.
If "recursive quad splitting" tells you something you can skip the article alltogether, as the algorithm is really only doing that. It's nothing special really.

DISTRICT MAP...
If you look at the structure of district surface maps they basically all look the same : blocks of buildings cut by straight roads. It's no coincidence, there is one algorithm that generate all the districts.

...GENERATION : Generating Blocks
How can we get  this blocky district plan?
Let's start with the whole district rectangle and nothing in it.
Mister District.
We want blocks.
How about cutting this district along two lines?
Cut
The blue lines would split the district in the middle.
That would be not very interesting for the player.
So let's deviate a bit and cut along the red lines.
We obtain 4 smaller rectangles, call them quads a, b, c, d.
a is topleft, b topright, c bottomleft and d bottomright.
Nice.
But b is a bit too small, so let's merge it with a instead.
b merges with a
Let's continue splitting shall we?
We apply the same process we did on the big district rectangle on the smaller quads (recursion).

After Cut+Merge on a,c,d.
We try to split a in 4, but the smaller quads are too small, so we merge the smaller quads and get only two quads a1 and a2. Same with c.
We find d is already too small and decide to not split it further.
We decide that's enough as there has to be an end to this madness.
From these quads we make blocks and give them numbers.

Blocks

... GENERATION : Assigning Blocks.
Looks like your average district map, with the roads and all.
Only thing, the blocks are empty.
So next for each block we decide what to do with them and fill them.

Assigned blocks
h for housing block, p for park.
Different algorithms are used to fill different block types.
Different district types will have different distribution of block types.
That's it.

THE ALGORITHM
The block generation algorithms in pseudo code (image).

MakeBlocks : Making Blocks since 1887
Start the recursion with calling MakeBlocks on the district rectangle.
Block is a class that has a rectangle property and various other content properties that are filled later.

QuadSplit is even more simple, choosing the split lines semi-randomly and doesn't split quads that would be too small ("merge"), enlarging one of the quads and marking the merged one as empty.

End of post.

4 comments:

  1. Now i can put a name on the method i use (well it's kinda similar to what you're describing). On the matter of map generation, you could throw some L shaped buildings to give some variety to your maps.

    It's usually done by drawing a cross inside your building and removing the quarter you don't want. You can also use the same method to add a room in a square building. There is an article about that (and also about your district generator, used for dungeons) in a roguelike website but I am unable to find it atm.

    Speaking of code i'd be more interested in knowing what kind of AI you've implemented for your NPC. I'd guess a finite state machine, as your changelog hints toward that way.

    ReplyDelete
  2. @building shapes
    I'll add more floorplans one day or another.

    @ai
    Not really a FSM are there are no formalized states with transitions.
    I made post about it:
    http://roguesurvivor.blogspot.com/2010/06/ai.html
    It hasn't changed much since then.
    I guess you could classify it as a hard-coded behavior tree/rule system.

    ReplyDelete
  3. Wth? Serial Kicked comment disapeared.
    Here's what he said:

    SERIAL KICKED
    Now i can put a name on the method i use (well it's kinda similar to what you're describing). On the matter of map generation, you could throw some L shaped buildings to give some variety to your maps.

    It's usually done by drawing a cross inside your building and removing the quarter you don't want. You can also use the same method to add a room in a square building. There is an article about that (and also about your district generator, used for dungeons) in a roguelike website but I am unable to find it atm.

    Speaking of code i'd be more interested in knowing what kind of AI you've implemented for your NPC. I'd guess a finite state machine, as your changelog hints toward that way.

    ReplyDelete
  4. yeah i don't understand either, it disappeared for some reason, i thought it was my browser cache playing tricks on me, apparently not. weird.

    Anyway, thanks for the link to the article, I will give it a read tomorrow. It's probably not going to change my mind on rule based systems, but i like to understand what i'm up against :p

    ReplyDelete