Tuesday, October 5, 2010

Map Generation

I've been asked how I generate local map data.  Right now it's admittedly a complete mess, but hopefully I'll be cleaning it up and moving it to external lua scripts or the like.

First, a little background.  The game has two things called "maps," the overmap, and the map.  The overmap is what you see when you hit 'm'; it's a big, 180x180 grid of map types, like "house facing south" or "riverbank with ground to the east and south", etc.  The overmap is generated at the start of the game.  If you move off the edge of the overmap, a new overmap is generated that connects to the one you were originally on (roads connect, rivers, etc).

The map is what you see when you playing--it's a grid of terrain types, like
"locked door" or "pavement", etc.  The map is composed of a 3x3 grid of submaps, each of which holds data about memory, items, traps, etc.  Each submap is exactly as wide and tall as the player can see.  The player is *always* in the center submap.  If he attempts to move off it--say, to the north--the player will move to the BOTTOM of the center submap, and the submaps will shift around him.

+------+------+------+       +------+------+------+
|      |      |      |       |      |      |      |
|  A   |  D   |  G   |       | New  |  A   |  D   |
|      |      |      |       |      |      |      |
+------+------+------+       +------+------+------+
|      |      |      |       |      |      |      |
|  B  <-@ E   |  H   |   =>  | New  |  B  @|  E   |
|      |      |      |       |      |      |      |
+------+------+------+       +------+------+------+
|      |      |      |       |      |      |      |
|  C   |  F   |  I   |       | New  |  C   |  F   |
|      |      |      |       |      |      |      |
+------+------+------+       +------+------+------+

From the player's perspective, they have  just crossed from submap E into submap B.  The player can no longer see G, H or I, and they have been deleted from memory and written to the disk.  New submaps have been generated--either from a data file, if this area has been previously explored, or from scratch.

Each tile in the overmap corresponds to four (2x2) submaps.  This was done because one submap (12x12 tiles) is too small to generated a building in, which three (36x36 tiles) is too large.  When a new submap is to be generated, they are done in batches of 4, according to the instructions in mapgen.cpp.  First, the type of map to be generated is fetched from the overmap, as well as its neighbors to the north, south, east and west, plus the tile above it if we are underground. Then a new, temporary map is created.  Since tiles on the overmap correspond to 2x2 submaps, only the top left four (A D B and E in the diagram above, on the left) are touched, and only those are saved.

We use the adjacent terrain to determine things like terrain fade (e.g., forests will have less trees on a side facing a field, and more on a side facing more forest) and connections (subways and sewers generally have a short passage connecting them; sewers have a ladder going up to a manhole above them).

After the terrain is generated, items are placed.  The function place_items() takes several arguments.  First, a map items location; these can correspond 1:1 to the overmap tile (e.g., mi_forest is all the items found in a forest), or to specific areas with that tile (e.g., mi_kitchen, mi_fridge, mi_bedroom, mi_dresser, etc. are all used in houses).  It also takes a probability, in the range of 1 to 99.  A 100-sided die is rolled, and if the roll is less than or equal to the probability, an item gets placed, and the die is rolled again.  It also takes two points, which define the top left and bottom right corners of a rectangle inside which the items are place.  A boolean is accepted which, if true, allows items to be placed on dirt or grass; otherwise, such tiles are ignored.  This means that for, say, T-shaped road intersections, we can place items across the entire map, rather than using 2 calls to place_items(), and avoid any items being placed on the unpaved ground.  Finally, an integer is accepted which dictates on which turn the items were created.  Generally, this is 0, meaning the items have been there "forever," giving things like fruit a good chance of rotting.  However, for areas like the forest, we have FRESH fruit, so the items are told to have a creation date of the current turn.

We can also specify static monster spawns.  A location and monster type is specified, as well as a count.  Monsters will attempt to spawn at the given location, but if it is occupied, they'll spawn as close to it as possible.

Finally, the map may be rotated.  Since the generation algorithm for a house facing north is the same as one facing west, we can use the same code for both, and simply rotate a north-facing house 90 degrees counter-clockwise to turn it into a west-facing house.

That about covers it, I think.  As I said, it's extremely messy, and the code is rather opaque.  Please let me know if you have any follow-up questions.

No comments:

Post a Comment