Monster Spawning

A little insight into my monster spawning routines.

The overmap, which holds macro map data with tiles like "a house" and "a subway station," as well as "forest" and "river bank facing east," also holds a number of monster groups.  These groups have a type, an origin (x, y), a population, and a radius.  The type is a moncat_id enum, which includes things like mcat_forest (woodland animals), mcat_zombie (typical zombies), mcat_bee, and many others.
It is assumed that monsters occupy a circular region (trig circular, not roguelike circular), with the greatest population density concentrated at the origin, (x, y).  The population density at any given square is determined by the equation (3.8 - (dist / rad)) * pop; where distance is the trigometric distance from the origin, rad is the group's radius, and pop is the group's population.  This is one of those cases where I wish I'd documented my code better; I'm not sure where the 3.8 value came from, but it's been heavily influenced by game-balancing.

The game holds a value next_spawn, which is a turn number.  When the player moves forward into new territory, the game checks to see if next_spawn is less than or equal to the current turn.  If it is, monsters get spawned, and next_spawn is increased.
The amount that next_spawn is increased by has changed several times, and is one of the single most important calculations for game balance.  Too low, and monsters are a constant worry; the player never gets a chance to breathe.  Too high, and monsters are only sporadic, and the game loses those moments of exiciting pursuit or intense combat.
Right now, next_spawn increases by a random amount from $low to $high.  $low is equal to the number of monsters spawned times three, plus the number in play before the spawn; $high is equal to the number spawned times eight, plus the number in play before the spawn times 10.  So, if there are 5 monsters in play, and 5 more get spawned, next_spawn will increase by an amount between 20 and 90 turns.  Or, if there are 20 monsters in play, and 1 gets spawned, next_spawn will increase by 23 to 208 turns.  And if  there are no monsters in play, and 10 get spawned, next_spawn will increase by 30 to 80 turns.
The idea here is that when there are lots of monsters in play, next_spawn will increase by a lot.  A large spawn on its own won't cause a big increase, but several large spawns in a row--basically, a rush or hoarde of monsters--will cause a very large increase.  This provides for a "cool down" period to reward the player after a big rush, allowing them to reload, heal, collect items, etc.
Note that next_spawn is generally only checked if the player is moving from one overmap square to the next.  This means that a player who is staying in the same place for a long period of time will not see any spawns.  This is good; if a player isn't moving, they're probably trying to heal up, and should be rewarded for their defensive tactics.  However, we do want SOME monsters to show up and disturb sleep occasionally--making traps and constructed defenses necessary.  With this in mind, the game will also check if next_spawn is 400 turns, or 40 minutes, overdue, and will spawn monsters in that event, generally at the very edge of the map (if the player has the Inconspicuous trait, this is changed to 2400 turns, or four hours).  Note that these monsters probably won't find the player right away--they'll spawn outside of the scent cloud, and if the player's smart and is indoors, out of sight of the player.
A few other things affect next_spawn, most importantly noise.  A player firing a gun will produce a sound equal to (20 + (ammo damage * .8))--with 00 shot, this will be 60.  Any sound of volume > 20 will reduce next_spawn by $min to $max; $max is the volume, minus 20 (capped at 50), and $min is $max / 6.  It is not only player-created sounds that cause this decrease; shrieker zombies are an important target because their shrieks are of volume 80.  This means that a 00 shot will, on average, cause next_spawn to decrease by around 25, making shotguns dangerous to use, except in emergencies, or when the player can handle (or desires?) a continuous onslaught.

I'd appreciate any feedback on the spawn system in Cataclysm.  Do monsters spawn too often, not often enough?  Do you feel as though you get a "breather" in between huge hoardes of monsters?  Does the increased spawn penalty for using noisy weapons feel fair?

Cataclysm has an undocument key, 'M', which will display the current turn number and the value of next_spawn.

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.

Segfault caused by std::vector copying?

Since the early days of cataclysm, I've been getting this annoying segfault that I just couldn't figure out.  The backtrace didn't end, like most segfaults do, with me trying to access an out-of-bounds address; rather, it descended through 10 calls in stl_vector.h and ended with a few in cmov.  Today it finally dawned on me that they all had the same thing in common; copying a vector.  Something along the lines of
std::vector<point> plans2 = plans;

would always be at the root of the problem (the backtrace also produced erroneous line numbers, for some reason, making it hard to debug).  Having replaced these lines with stuff like

std::vector<point> plans2; 
for (int i = 0; i < plans.size(); i++)
    plans2.push_back(plans[i])
I hope I've solved the issue for good, and eradicated my  last known segfault.  This should reduce crashes to 1% of what they used to be!