Subsystem: MapGeneration - Adam-Poppenheimer/Civ-Clone GitHub Wiki
- Overview
- Implementation
The MapGeneration subsystem handles the procedural generation of new, playable maps. It deals with the logical and game-mechanical aspects of this process rather than the rendering of its visual components, which is handled by MapRendering.
It's hard to tell how well Map Generation performs on a whole because its outcomes are difficult to analyze. Most of the other game mechanics of Civilization 5 have clear, well-defined parameters and sets of behavior: An aqueduct tells you exactly what it does, and a unit moves in a precise and determinable way. Not so with the procedural generation of maps. I was not able to find many specific, testable design goals for how, exactly, Civilization 5 generates its maps, likely because the information is proprietary. Thus I suspect this subsystem produces results that are the most divergent from how the inspiring product handles its design. My goal was to create something organized that produced sane results and did so quickly and efficiently, rather than to copy Civ 5's generation algorithms verbatim.
MapGeneration is also one of a handful of subsystems that aren't backed up by unit testing. There are a number of reasons why this decision was made. First is the reason outlined above: Without a clear idea of what a good result looks like, how could one build the tests that check for such a result? Another is the sheer complexity of testing. Map generation makes use of Unity's (non-multithreaded) Coroutine system, that it spreads generation across multiple frames. And far more substantially, MapGeneration makes very heavy use of IHexGrid, querying and subdividing and crawling across the grid of cells many times in its processing. Properly testing that behavior would, most likely, require a full implementation rather than a simple mock-up, which would make the testing integration rather than unit testing. For these reasons it was figured during development that manual testing, by running the map-generation system and taking a look at the results, would be sufficient.
That being said, the lack of testing in MapGeneration still represents a major flaw in the project. There are certainly processes (like the generation of players, or at least calls into the various steps of map generation) that could've been separated out and put under tests. And while it would've been a much more difficult task, creating a proper collection of integration tests would've helped me hammer out design goals, given certainty that the components were connected properly, and would've provided important experience for bigger-picture testing.
From a functional standpoint, the MapGeneration subsystem is basically a gigantic tree of helper classes whose root is the MapGenerator class. It implements IMapGenerator, whose only method is a GenerateMap() method that takes an IMapTemplate and an IMapGenerationVariables object as arguments. The first contains information for generating a specific type of map. Civ 5 allows players to start on a number of different types of worlds (ones filled with continents, ones filled with islands, ones dominated by a single gigantic continent, etc), and IMapTemplate provides the information for such world types. IMapGenerationVariables, on the other hand, contains configuration that can apply to all map types: How large the map is, how high the sea level is, the civilizations to place in the world, and what technologies will be discovered at the beginning of the game (which is used to set the starting era). IMapGenerationVariables implementations are supposed to be constructed from player input, while IMapTemplate implementations are selected from a list by the player.
The concrete class MapGenerator performs map generation within a Unity Coroutine primarily for the benefit of MapComposer (which is discussed in detail in MapManagement). The first thing it does is clear the existing "runtime" which is the nomenclature I used to describe the in-game objects and behaviors associated with a session of play. After everything's been cleared and destroyed, it rebuilds the IHexGrid at the correct size, generates players from the chosen civilizations, and performs other pre-generation initialization tasks.
At a very high level, map generation focuses first and foremost on creating a Homeland for each civilization. These homelands are created some minimum distance from each-other and are assigned a large chunk of the cells in the grid. All remaining cells are assigned as oceans. Once cells have been assigned to either a homeland or the oceans, MapGenerator picks a random template for each homeland and uses that to paint the cells of the map with appropriate terrain, shape, vegetation, and features, and also place Map Resources and rivers. After this process, map generation uses a number of balance strategies to either increase or decrease the total value of the land assigned to the civilization, in hopes of balancing the various homelands against each-other. That way, every civilization should start with a homeland about as good as all the others. After the map is painted and balanced, a civ's starting units are placed in the best part of their homeland, and every chunk in IHexGrid is told to refresh itself so that map rendering can begin its duties.
Player creation is a fairly straightforward process occurring in the private MapGenerator.GeneratePlayers() class. For each civilization template in the map generation variables, a new civ with the proper starting techs is instantiated. A player is then created around each of those civs and assigned the IPlayerBrain for a human player (i.e: It accepts UI inputs from the game and has no AI). It then creates a barbarian civ from a configured barbarian template, out of which it creates a barbarian player with a barbarian brain (one that actually has AI associated with it).
From there we move into MapGenerator.GenerateOceansAndContinents(), which exists to divide the cells in IHexGrid into civilization homelands for each non-barbarian civilization, and also ocean regions. To do this, the method first uses IGridPartitionLogic to break the map into a set of multi-cell MapSections that the rest of the map generation process will use. These regions are constructed to give landmasses a more realistic feel, that they're less snaky and more self-contained.
The standard implementation of IGridPartitionLogic (GridPartitionLogic) creates something a bit like a Voronoi Diagram out of IHexGrid's cells. It takes a set of random 2D points on the grid, creates a MapSection around those points, and then assigns each cell in the grid to the MapSection of its nearest point. Once every cell's been assigned to a MapSection, the centroid of each MapSection is calculated and a new round of MapSections are created, with the random points being substituted for the centroids of last cycle's sections. This process is repeated a configurable number of times as determined by the map template itself, after which a GridPartition with the last round of generated MapSections is returned.
Once a partition of the grid has been constructed, MapGenerator.GenerateOceansAndContinents() creates lists of MapSections for each homeland via ISectionSubdivisionLogic.DivideSectionsIntoChunks(). Each of these chunks is then assigned to a homeland for one and exactly one civilization. Added to that homeland are the coastal sections, i.e: all sections adjacent to the currently-assigned homeland but not currently assigned to anyone. A homeland template is pulled via ITemplateSelectionLogic.GetHomelandTemplateForCiv(), and then a HomelandData is created for the civ via IHomelandGenerator.GetHomelandData(), which constructs the homeland out of the land and water sections calculated above, plus the civ itself, the homeland template, and the map template.
ISectionSubdivisionLogic.DivideSectionsIntoChunks() takes a set of MapSections along with a number of configuration arguments and creates contiguous chunks of sections, returned as a List<List>, all of which connect to each-other.
The first thing it does is check whether its argued IMapTemplate has its SeparateContinents property set to true. If it does, it draws a line parallel to the Z axis of the grid down its height at some random X coordinate between a configured minimum and maximum. It then grabs every MapSection that contains a cell intersected by that vertical line, removes them from the list of unassigned sections, and adds them to the list of forbidden sections, so the rest of the subdivision process won't make use of those cells. This measure was taken for the sake of the Continents template, to help make sure at least two continents formed. The forbidden sections in that case get assigned to coastal water or the oceans, preventing that problem.
After the "Forbidden Line" is drawn, DivideSectionsIntoChunks() initializes each of the lists it'll return and adds a single section, called the Starting Section, to each one. These starting sections are chosen some configured distance away from the edge of the map and some configured distance away from the center of each previously-assigned Starting Section.
Once every chunk has a starting section in it, DivideSectionIntoChunks() iterates through the following loop until every chunk is finished or it runs out of unassigned sections. A random unfinished chunk is selected from the set. That chunk is then told to attempt expansion. While its total number of cells is beneath a desiredContiguousCells variable (calculated from configuration variables and the size of the map) it samples from the set of all unassigned MapSections adjacent to MapSections already in the chunk, adding one of those to the chunk. Otherwise it gets all unassigned sections within a certain distance, samples from those, and adds one of those to the chunk. In either case, the element is selected by weighted random selection through WeightedRandomSampler and a weight function passed into DivideSectionIntoChunks(). If a chunk's total cell count exceeds the desired maximum size of the chunk, or the attempt to add a new section to the chunk failed, it's declared as finished.
When every chunk's been finished, DivideSectionIntoChunks() returns them as a List<List>, having removed every section claimed by a chunk from the unassignedSections set passed to it.
Once DivideSectionIntoChunks() returns, MapGenerator.GenerateOceansAndContinents() takes each of these chunks and assigns them to some civilization. It generates a list of unassigned MapSections adjacent to the chunk, and grabs those, the homeland chunk, and the civ to create a HomelandData for each civ via IHomelandGenerator.GetHomelandData().
What is a HomelandData, though, and what is its purpose? Well, in Civilization 5, the map is divided into a number of different biomes: forests, grassland, jungles, deserts, tundra, and the like. Colder biomes are closer to the poles, warmer ones closer to the equator. Wetter and drier biomes exist in somewhat more complex fashion, but generally biomes fade somewhat gradually from wet to dry (jungles turn into grasslands, which turn into plains, and then into desert, for instance). This program, too, needs to have biomes that shift in such ways.
We handle this by dividing homelands into some number of regions, each of which has their own biome based on their temperature and their precipitation. Thus a homeland is made out of a number of MapRegions which exist independently from the MapSections of grid partitioning and continent formation. These regions are larger than MapSections to prevent patchwork biomes that flip frequently, but smaller than Homelands to add more natural diversity to the map. A similar thing is true of topologies: some areas are flat, others hilly, others mountainous, and their presence tends to follow a certain logic (mountains near hills, hills not near flood plains, etc).
In addition to biome requirements, one of the few things I managed to learn about Civilization 5's map generation algorithm is that it tended to create smaller starting regions around each civ with richer resources and very regular pattern compared to the rest of the land. Thus it was necessary to add some notion of a "starting region" to the homeland that could be populated with luxury and strategic resources differently than other parts of the homeland.
All of these tasks are given to IHomelandGenerator.GetHomelandData(). First, a starting region is constructed from the cells of all MapSections within some distance of the first land section assigned to the civ. From there, the unassigned MapSections are divided into some number of roughly rectangular chunks of land and/or water based on the provided homeland template. MapRegions are created from the cells of these chunks. Both these regions and the starting regions are then given an IRegionBiomeTemplate and an IRegionTopologyTemplate via ITemplateSelectionLogic. Or more accurately, HomelandData is given the regions and their corresponding RegionData, which contains the necessary biome and topology information. Why exactly these aren't added to the MapRegion itself is unclear, though it's most likely an architectural error.
ITemplateSelectionLogic and its standard implementation select appropriate biomes and topologies for a particular MapRegion on a particular IMapTemplate. For topologies a valid template is selected at random. For biomes, the temperature and precipitation is calculated for each cell in the region, their averages are taken, and then the biome whose min/max temperature and min/max precipitation most closely fits the MapRegion's properties is chosen (Biomes are created at design time as ScriptableObjects, for reference). Temperature and precipitation on a per-cell basis are calculated by ICellClimateLogic and its standard implementation. Cell temperature is based entirely on latitude, either making the equator warmer (if the configured map has two poles) or making the south warmer (if the configured map as only a north pole). Precipitation is currently queried from a noise texture, from which a bilinear sample is taken based on the cell's position in the grid.
Finally, once all that's been done, HomelandGenerator.GetHomelandData() creates the RegionData proper, adding to them a list of IBalanceStrategies that'll be explained in a dedicated section.
Once every chunk and its coastline has been assigned to appropriate homelands, GenerateOceansAndContinents() takes the remaining sections assigned to no homeland and turns them into OceanData via IOceanGenerator.GetOceanData() on some random IOceanTemplate provided by the IMapTemplate. The homelands and the oceans are then wrapped into an OceanAndContinentData object and returned.
Once the oceans, homelands, regions, and biomes have been determined, MapGenerator can proceed to paint the map with appropriate terrain features. This is handled by the private method PaintMap(), which accepts the OceanAndContinentData generated above and the IMapTemplate passed to GenerateMap(). It calls into a number of helper classes to give the broad outline of generating the first pass of the map proper. For each civilization, it grabs that civ's homeland, and passes it to IHomelandGenerator.GenerateTopologyAndEcology() (cell terrain, shape, and vegetation, as well as rivers). Afterwards, it takes the MapRegion's OceanData and passes that to IOceanGenerator.GenerateTopologyAndEcology(). Next it calls IWaterRationalizer.RationalizeWater() on every IHexCell in the game to make sure sufficiently small patches of ocean are turned into lakes. Then IHomelandGenerator.DistributeYieldAndResources() is called on each civ's homeland to add luxury and strategic resources to their territory and ensure it has a proper amount of yield across its terrain. A similar call is made to IOceanGenerator, but that method is currently a stub and doesn't do anything.
IHomelandGenerator.GenerateTopologyAndEcology() builds out the cell terrain, shape, vegetation, and rivers of a homeland in three stages. First, it takes each region (including the starting region) and builds their topologies and terrains via IRegionGenerator.GenerateTopology() and IRegionGenerator.PaintTerrain(). Then it determines how many cells should have access to rivers based on the biome's river percentage and passes that number into IRiverGenerator.CreateRivers() to create rivers for the entire homeland. After rivers are created, IRegionGenerator.AssignFloodPlains() is called to turn deserts adjacent to rivers into flood plains, per the design of Civilization 5. Lastly, each region is taken once again and given vegetation, this time by IVegetationPainter.PaintVegetation().
The standard implementation of IRegionGenerator.GenerateTopology() works as follows. The number of desired hills and mountains is calculated from the number of cells in the region and the topology's MountainsPercentage and HillsPercentage. Once this number's acquired, GenerateTopology() uses weighted random sampling to select "elevated" cells equal to the desired number of mountains and hills. Each of these is turned into a hill, and then another weighted sampling selects some of the elevated cells to be turned into mountains. HillWeight has a starting and a dynamic weight function. The starting weight function decreases the odds of being selected based on whether the cell is bordering water. The dynamic weight function increases the chance of being chosen if there are other hills nearby, improving more if there are a small number of hills and less if there are a large number. Mountains use only a starting weight, determined by the number of non-flat neighbors the cell has.
The standard implementation of IRegionGenerator.PaintTerrain() paints arctic terrain first. Unassigned cells are sorted by their distance to the poles (or pole, depending on the configuration). It then assigns snow cells up to the percentages required by IRegionBiomeTemplate, followed by tundra cells. In each case, it assigns the cells closest to the polar regions first.
After filling in the arctic regions (if any were present), PaintTerrain() fills in the rest with grassland, plains, and desert terrains, in that order. Unassigned cells (that is, cells not already given a territory) are selected one at a time by weighted random sampling. Higher priority is given for a terrain type to cells whose temperature and precipitation are close to that terrain type's ideal. Ideal temperature and precipitation, as well as the weight temperature and precipitation have on selection, is configured via fields in IMapGenerationConfig, along with a base weight at which all terrains begin.
The process described above can occasionally result in incomplete terrain coverage. For any unassigned land cell left after painting arctic and normal terrains, PaintTerrain() assigns it the terrain of some adjacent or nearby non-water cell.
After all land cells have been assigned terrain, each water cell is assigned the Shallow Water terrain type to represent the coastal waters most of these cells will represent. Freshwater lakes are handled in a different part of the codebase.
Back in HomelandGenerator.GenerateTopologyAndEcology(), once all regions have been given topology and painted with appropriate terrain, Homeland generator takes stock of all the land and water cells in all the regions and passes them into IRiverGenerator.CreateRivers(), which creates rivers for the entire homeland.
IRiverGenerator's standard implementation of CreateRivers() is very complex. Its goal is to create rivers that flow from some point inland to either the sea or another river, all in appropriate directions, such that a minimum number of land cells exist that are adjacent to a river. It does this by crawling across the terrain from some starting point, chosen for game design reasons, towards some ending point it's selected (usually a cell whose terrain is Shallow Water), maintaining proper flow and river segments along the way.
To find the starting point, CreateRivers() creates a list of candidates by filtering out any cell whose shape is Flatlands (rivers usually start in high places) and any cell whose neighbor is a water cell (otherwise it'd be a tiny river, not useful for the design). Then, while there are still candidates for starting points and the homeland still needs more rivered cells, CreateRivers() selects one of the candidates by weighted random sample (prioritizing for balance reasons nearby desert and arctic sells to try and improve these otherwise barren terrains) and attempts to make a river with them.
When attempting to make a river, RiverGenerator begins by finding a valid endpoint. A valid river endpoint is any cell that isn't the starting cell, isn't water, doesn't have a river, and isn't farther away from the river than its maximum river length (determined by the number of rivered cells CreateRivers() still needs to aim for). A river endpoint also needs to be adjacent to some water cell, determined either by its terrain or by the water cells passed to CreateRivers(). It then uses weighted random sampling to pick the endpoint with the same weighting calculations as the start point. If it fails to find such an endpoint, RiverGenerator aborts construction of the river.
If it does find an endpoint, however, RiverGenerator uses IHexPathfinder.GetShortestPathBetween() with a provided weight function to find the shortest path the river might take. That weight function makes water cells impassable, gives higher cost to cells adjacent to the water, and lower weight to inland cells. The current implementation lacks configuration for how avidly the pathfinder should avoid coastal cells before it reaches its endpoint. RiverGenerator then goes down this path, from the start point to the endpoint, cell by cell, adding rivers to the edges of the active cell necessary to bridge it from the previous cell to the next cell. RiverGenerator has private methods for constructing valid rivers for all 5 cases this can bring: if the previous and next cells are opposite each-other (CreateRiverAlongCell_StraightAcross()) are one edge clockwise or counterclockwise of that position (CreateRiverAlongCell_GentleCW- and GentleCCWTurn()) or if the previous and next cells are adjacent to each-other (CreateRiverAlongCell_SharpCW- and SharpCCWTurn()). These methods are used to handle river endpoints, as well, treating the valid ocean cell or rivered cell as the (N + 1)th point on the path. The rest of the class is handling all the many cases that arise from this, and on turning each link of the path into segments along the edges of cells.
CreateRivers() will run until it's met or exceeded the desired number of river cells, it runs out of candidates, or it goes a certain number of iterations (based on the number of land cells passed to it) without having achieved its target. When it does so it returns gracefully (or should return gracefully), throwing no errors.
Once the rivers have been built out, HomelandGenerator.GenerateTopologyAndEcology() then calls IRegionGenerator.AssignFloodPlains() to switch to Flood Plains are cells that have the terrain type Desert, are adjacent to a river, and can accept the terrain type Flood Plain (so not hills or mountains). This follows the design of Civilization 5, where rivers running through deserts almost always produce flood plains around their banks.
The last step to GenerateTopologyAndEcology() is to paint vegetation, done through IVegetationPainter.PaintVegetation() and its standard implementation. PaintVegetation() begins by adding marshes and flagging "open cells": cells which can accept whatever the standard tree type of their biome is (Forest or Jungle).
For marshes, a cell has a certain percentage chance of being turned into a marsh based on the number of adjacent water cells and adjacent rivers it has, with more of both increasing the odds. If the random number says so and the cell's a valid location for a marsh, it's immediately changed to one.
For Forests and Jungles (which are handled the same, just with a different vegetation being placed at the end), PaintVegetation() attempts to create some number of contiguous regions of forest, which crawl across the available cells via the IEnumerator returned by IGridTraversalLogic.GetCrawlingEnumerator(). The cost function the IEnumerator is built on excludes cells that are marshes, have a terrain feature on them, or which cannot be turned into the given tree type. It prefers cells closer to the "Seed" of the forest (where vegetation painting begins), and also changes costs based on the terrain and shape of the cell, as determined by the IRegionBiomeTemplate being used to paint the cells. Then, PaintVegetation() calculates the number of cells that ought to be trees and creates a for loop with that many iterations. That loop grabs a tree crawler and attempts to move to its next element. If that element exists, it declares that IHexCell a tree, removes it from the openCells set, and carries on. If it fails, the crawler is removed from the list and the loop tries again.
Once enough cells have been flagged for foliage, PaintVegetation() changes all their vegetation to the configured tree type and returns.
A similar process to the one described above for Homelands also applies to the oceans. OceanGenerator applies region generation to all archipelago regions to generate topology and paint terrain. However, it doesn't apply rivers or add vegetation because the islands are expected to be small. For the empty ocean regions it simply sets all those to the terrain type Deep Water. Ocean generation in general is underdeveloped and, if development were to continue, would need to be fleshed out, particularly to include vegetation and yield balancing.
The standard implementation of IWaterRationalizer.RationalizeWater() exists to add fresh water to the game. The process of generating continents can often cause regions of water to become landlocked, separated from the rest of the oceans, or else water can be added in Homeland generation. This water is added as Shallow Water, a type of seawater, by default. RationalizeWater() goes through all the water cells, divides them into individual bodies of water, and then checks the size of those bodies. If the number of cells is less than IMapConfiguration.MaxLakeSize, all the water in that body of water is switched to Fresh Water.
The standard implementation of IHomelandGenerator.DistributeYieldAndResources() is a fairly simple class that calls into three helper methods in three different interfaces: ILuxuryDistributor.DistributeLuxuriesAcrossHomeland(), IStrategicDistributor.DistributeStrategicsAcrossHomeland(), and IHomelandBalancer.BalanceHomelandYields(), all called in that order. OceanGenerator.DistributeYieldAndResources() is a stub left unimplemented because deep-ocean islands and their balance aren't a core part of Civilization 5: something nice to have, but less important than other issues. it exists to ease potential future development.
Luxury distribution informs its activities largely through a List of LuxuryResourceData objects attached to the argued HomelandData. It expects the terrain, topology, rivers, and vegetation of a Homeland to have been resolved already.
Distribution differentiates between a Homeland's starting region and its other regions. A LuxuryResourceData specifies a certain number of luxuries that ought to be in the starting region, and a certain number that should exist in other regions. To take the current build as an example: the Standard Homeland template wants some luxury to have 2 copies in the starting region, a second luxury to have 1 copy in the starting region and 3 in other regions, and a third to have 2 copies in the other regions. This could be satisfied by placing 2 Spices and 1 Ivory in the starting region alongside 3 Ivory and 2 Sugar in the other regions. The specific luxuries to add are left to LuxuryDistributor to figure out.
The first thing LuxuryDistributor does is figure out which IResourceDefinitions are valid for the homeland. It calls into a trio of private methods to find all luxuries valid for the starting region, all luxuries valid on one of the other regions, and all luxuries valid in the starting region and at least one other region. For each of these queries, a Dictionary is constructed with the summed weights of each valid luxury across the regions queried.
After the list of valid Luxuries along with their weights have been determined, LuxuryDistributor attempts to satisfy each of the requirements from HomelandData.LuxuryResources. It divides its attempts into three cases described below.
The first case is if the LuxuryResourceData requests placement of some Luxury only in the starting region. In that case, the resources and weights for the starting region, as well as the starting region itself and the desired number of IResourceNodes, are passed into DistributeLuxuryAcrossSingleRegion(). While there are any Luxuries valid for the starting region, this method selects one of them by weighted random sampling, ignoring it if this Luxury has already been placed in the homeland. Then it finds all cells on which that chosen resource is valid. If there are at least as many valid cells as nodes requested, the method selects as many cells as needed via weighted random sampling and constructs IResourceNodes on those cells of the IResourceDefinition deemed valid. It then makes note of the IResourceDefinition it just used so further distribution in the Homeland can avoid it.
The second case is if the LuxuryResourceData requests placement of some Luxury only outside the starting region. In that case, the valid resources, weights, and desired number of IResourceNodes are passed into DistributeLuxuryAcrossMultipleRegions(). This performs much the same process as described above, except it samples from the cells of a set of regions rather than a single region.
The third case is if the LuxuryResourceData requests some number of a Luxury in the starting region and some number outside it. In this case, LuxuryDistributor calls into TryDistributeLuxuryAcrossSingleAndMultipleRegions(). This functions much the same as the other two distribution methods, except it performs distribution separately on the one region and the many regions, and it won't perform any sort of distribution unless both the one region and the many regions can hold their share of the luxury in question. Since there's a not-insignificant chance of this failing, if TryDistributeLuxuryAcrossSingleAndMultipleRegions() doesn't work, LuxuryDistributor will instead satisfy the requirements of the given LuxuryResourceData with two resources instead of one, distributing one in the starting region and the other in the remainder of the Homeland.
LuxuryDistributor will, one rare occasions, fail to distribute the requested amount of luxuries in a Homeland. In this case it fails gracefully, producing a warning message into the log and returning control without throwing errors.
Strategic distribution, implemented via (I)StrategicDistributor, is much simpler than Luxury distribution. Rather than caring about specific types, StrategicDistributor seeks to place some number of nodes within a homeland, between which are some number of copies. Both of these numbers scale with the total number of cells in the Homeland. It doesn't differentiate between starting and non-starting regions.
StrategicDistributor continues running until either it's placed as many nodes with as many total copies as it needs, or for some number of iterations that scale with the number of regions. Each iteration it selects a random region and then selects some strategic resource valid on that region by weighted random sampling. It then searches for a valid cell for that Strategic resource, selecting one by weighted random sampling if it exists. It then creates a node of that type with a number of copies provided by IStrategicCopiesLogic.GetWeightedRandomCopies(). That region is then temporarily removed from the list of regions valid for Strategic placement. If, at the beginning of an iteration, there are no valid regions left, all the Homeland's regions are added to the list of valid regions.
StrategicCopiesLogic uses weighted random sampling to select some number of copies between IMapGenerationConfig.MinStrategicCopies and .MaxStrategicCopies. It's more likely to select values closer to the average of that range than those farther away, in much the same way the probability distribution of the sum of two six-sided dice works.
StrategicDistributor, like LuxuryDistributor, is designed to fail gracefully if it cannot add the desired nodes and copies to the homeland. It does not produce error messages when it does so.
The last step in generating a Homeland is to attempt to balance the total amount of yield all of its cells produce. Since each of these Homelands is supposed to support a single Civilization, it would be best if each Homeland was roughly as good for settlement as every other. Some variation is acceptable, but one Homeland shouldn't be several times richer (or poorer) than any of the other ones, or else the game wouldn't be fair.
The process of balancing the yield of Homelands is a very complex process often prone to error. While the current implementation does substantially reduce the variance between homelands, I'm not confident in its ability to normalize yields in all situations, particularly for zones heavy in low-quality cells like Ice, Tundra, and Desert. Even still, the basic architecture for this strategy seems reasonable and would require iteration rather than revamping.
Before yields can be balanced, they first must be estimated. That task belongs to (I)YieldEstimator, and there are a lot of things that complicate it. Getting the base yield of a particular cell is easy enough: Just sum the cell's inherent yield, add in yield from any IResourceNodes on it, and add 1 science to represent what the citizen working on it would generate just by existing. But cells can also have improvements on them, each of which provides different yields. And a cell's output, or an improvement's output, can be modified by the presence of buildings, as well, not to mention that an improvement might produce a different yield if it's an extractor for some IResourceNode. Estimating yield, then, requires finding all possible yields for that cell, comparing them, and returning the best yield, which means there also has to be some way of scoring yields to see which composition of factors is the most valuable.
And there's another yield: How do you reason about yields from improvements that aren't available from the start of a game, or on resources that aren't visible? Say the best improvement for a flat Grassland cell is a Mine on top of its Iron deposit, but that Iron won't be available (and that improvement won't be valid) for the first third of the game, since Iron requires the Classical-era tech Iron Working to gather. Most likely a higher yield gained later in the game should be worth less because it generates for fewer turns and produces less overall.
Yield estimation and yield scoring, then, is very complex. And it's also something that involves a lot of judgement on the part of the designer. How does the value of 10 Food compare to 10 Production? How about either of them to 10 Science? Is 3 food from the Ancient era better than 4 food starting in the Classical era? How valuable is a node with 5 Iron? How about 5 Horses? How about Spices? How do these things compare to each-other.
Ultimately this question felt like a matter of game design rather than game development: Something solved not with engineering, but with playtesting and a designer's intuition. Neither of these things were relevant to the goals of the project, since I was trying to prove technical abilities rather than design or artistic ones. Thus I opted to create a system that ideally could be used, by a savvy-enough game designer, to balance Homeland generation in a number of different ways, and could be extended with more complex considerations without much difficulty.
It's worth noting ahead of time that HomelandBalancer and its associated classes perform a pretty sizeable number of duplicate calculations. There is almost certainly a much faster version of this process that makes clever use of dynamic programming to cache calculated values, especially for commonly-occurring cell types (forested cells with no resource nodes, empty shallow water, empty grasslands beside rivers, etc). However, I was prioritizing functionality and clarity over performance, so I opted for a solution that, while inefficient, made clearer what was going on. Further development would likely improve upon the efficiency of this process.
Fundamental to this whole effort is calculating a cell's yield estimate for a given set of technologies (and all the improvements/buildings they provide). This is handled by (I)YieldEstimator, which provides an overloaded GetYieldEstimateForCell() accepting an IHexCell and either a set of techs or a CachedTechData that summarizes the various things technologies can do to modify cell yield. The former simply calls into the latter with a newly-instantiated CachedTechData.
GetYieldEstimateForCell() runs through every IImprovementTemplate available given the argued techs, creates a mock IImprovement (called HypotheticalImprovement), and then gets the estimate the yield of that cell with that IImprovement and the relevant factors from the given technology (visible resources, improvement modifications, and available buildings) and calls into IImprovementYieldLogic.GetYieldOfImprovementTemplate(). It adds in the yield from any IResourceNodes on the cell, accounting for the hypothetical improvement (whether it's an extractor or not). It incorporates the inherent yield of the cell, accounting for vegetation clearance if the improvement clears vegetation. And finally it adds the yield change from the building mods available given the argued techs on the cell (excluding the improvement). 1 Science is added to this yield and then the whole thing's returned.
This process happens for every improvement valid on the given cell. Once all yields have been calculated, it scores each yield via IMapScorer.GetScoreOfYield(), takes the yield with the highest score, and returns that as its estimate. If there were no improvements on the cell, the same process is run on a pregenerated NullImprovement that does not affect the cell's yield.
Yield scoring, handled by (I)MapScorer, is actually quite simple. There is a configurable property in IMapGenerationConfig called YieldScoringWeights, which is supposed to be an estimate for the relative value of each type of yield against the other. GetScoreOfYield() simply multiples the argued yield by YieldScoringWeights and returns the sum of the resulting YieldSummary's components. It's expected that configuring YieldScoringWeights properly would take an enormous amount of work on the part of the game designer. I set the weights to something that felt intuitively reasonable to me and left them alone.
Luxury and Strategic resources need to be taken into account more thoroughly, since they provide benefits beyond just yield. This is handled by (I)MapScorer.GetScoreofResourceNode(), which like its compatriots accepts a list of techs. If the IResourceDefinition within the argued node is visible and isn't a bonus resource, GetScoreOfResourceNode() returns its score (defined on the IResourceDefinition itself) times the number of copies it possesses.
Cell Scoring, handled by (I)CellScorer, makes heavy use of the previous three components. Its one method, GetScoreOfCell() creates three yield estimates for the argued cell, one in each era (Ancient, Classical, and Medieval). It adds to those the scores of any IResourceNodes on that cell at their corresponding tech levels. Then it returns the average of all the estimates across the tree eras.
The basic assumptions in CellScorer, that equivalent yields gained at different stages in the game are equivalent, is almost certainly false. Since Civilization 5 is a game about spending resources to gain more resources, early yields often have far more impact on the game than later ones. Most likely the weights should decline for later and later eras. But the precise balance of such things isn't relevant to the engineering, so it wasn't given much thought.
With yield estimation and scoring systems in place, we've got the tools for detecting yield deficits and score imbalances. But how does actually change them? There are numerous ways of changing a region's score, or the yield of a particular resource: adding or removing vegetation, changing shape, changing terrain, adding new resources, etc. Anticipating many different strategies by which regions could be tweaked, I created IBalanceStrategy. This interface has 3 methods: TryIncreaseYield() (for a specific YieldType), TryIncreaseScore(), and TryDecreaseScore().
This interface has many implementations, all of which are instantiated and installed in MapGenerationInstaller. They each manage a single type of modification that can be made to alter the map. Not all IBalanceStrategy implementations are capable of performing all three tasks, but all fail gracefully without throwing errors. The implementations are as follows:
ResourceBalanceStrategy can increase yield and score by adding new IResourceNodes to the region. In both cases it uses weighted random sampling to select a valid non-luxury resource and places a node containing it onto the map. This has a much greater effect on score than it does yield, but can improve both. It does not remove IResourceNodes, since this could violate the regular pattern of luxury distribution built out earlier in the process.
JungleBalanceStrategy can increase score by adding new Jungles to the region. It can also decrease score by removing them. It is not used to increase yield because it has the potential to drop available Food below accepted minimums after Food has already been balanced. Jungles are only added by this strategy to cells which have at least three neighboring Jungle cells, and are only removed from those with at least three neighboring cells with no vegetation.
LakeBalanceStrategy can increase yield and score by adding freshwater lakes to the region, which also adds access to fresh water to nearby cells. It is not used to decrease score, if for no other reason than that lakes are rare and their removal makes the map look worse. Since lakes only produce food, they only successfully increase yield or score based on the new food they produce. In both cases they need to consider the yield estimates of all neighboring cells. Cells adjacent to the sea or desert, cells with IResourceNodes, and cells with more than a configured number of nearby lakes are all invalid targets for LakeBalanceStratgy.
HillsBalanceStrategy can increase production yield and score by turning unvegetated flat land cells into Hills, particularly Desert, Snow, and Tundra cells. It does not decrease score because that might flatten hilly regions, making the map less visually interesting.
OasisBalanceStrategy can increase food yield and score by adding the Oasis feature to desert cells. In addition to providing food to themselves, Oases provide fresh water to adjacent cells, which makes them very powerful balancers in desert-heavy regions. This strategy tries to avoid placing Oases near non-deserts and other Oases to improve their efficacy. As with LakeBalanceStrategy, they need to incorporate changes to their adjacent cells into their yield and score improvements, as well.
MountainBalanceStrategy can decrease score by turning cells into unworkable, impassable Mountains. It can do this to hills that have IResourceNodes. Some configurations of MountainBalanceStrategy have overwhelmed hills in rich areas, turning almost all of them into mountains. It's not clear if that's an acceptable result or not.
ExpandOceanBalanceStrategy can decrease score by turning cells next to the coast into Shallow Water, substantially decreasing their value. This can only happen if there are no adjacent rivers, no IResourceNodes, and no neighboring freshwater lakes, and if the transition is valid.
There are many other possible balance strategies, a handful of which were implemented and deemed to be counterproductive. Future work on MapGeneration would most likely spend more time fleshing out balance strategies to provide more diversity, particularly for arctic regions, which tend to have severe score and yield shortages.
This is all brought together in HomelandBalancer, which works in the following way:
The total yield of all cells in the homeland, including coastal cells, is estimated. A minimum acceptable Food and Production yield is then calculated based on the number of cells in the Homeland. But it's not the full cell count per se. Homelands with a large percentage of water tended to become oversaturated, since water is generally resource-poor and HomelandBalancer tries to ensure a certain food, production, and score per cell. Thus a weightedCellCount is calculated that allows designers to modify how much land and water cells contribute to the food and score requirements for a Homeland.
Once min Food and Production yields have been calculated, HomelandBalancer checks to see if the current yield satisfies them. If it doesn't, it starts using its IBalanceStrategies to lift the yield up, resolving Food first, Production second. It does this in iterations, taking an IBalanceStrategy via weighted random sampling, with the weights determined by the HomelandData through a somewhat convoluted implementation. It then asks that strategy to attempt to increase the desired yield, keeping track of the yield added if it did. It repeats this cycle until the minimum yield has been achieved or it's undergone a certain number of iterations based on the number of regions in the Homeland.
Once Food and Production minimums have been achieved, HomelandBalancer calculates min and max scores from HomelandData and the same weightedCellCount as before. It then enters a very similar loop, except it continues while the current score is less than the minScore or greater than the maxScore. It asks the sampled IBalanceStrategy to increase its score in the former case, and decrease it in the latter.
This process, while it has merit, turns out to be very imprecise. It's possible for IBalanceStrategies to drop a Homeland below its food and production minimums, for instance, or to run out of iterations before it finishes its process. It might be better to contain these operations in a single, gigantic loop that only breaks when all four conditions have been met, or after some large number of iterations.
In theory, the islands and archipelagos generated in oceans outside of Homelands should also be balanced according to some principle. However, the current implementation of map generation doesn't produce islands very often, and mid-ocean islands aren't a particularly important part of the design. This feature has been left unimplemented, then, to be addressed if development continues.
Once all the oceans and homelands are done being created, MapGenerator assigns them to civilizations. It does this by calling into (I)StartingUnitPlacementLogic.PlaceStartingUnitsInRegion, with the starting region of the Homeland being passed in.
PlaceStartingUnitsIntoRegion() begins placement of units on the best possible location for a city. The best possible location is determined by calculating cell scores for a particular cell itself and all of the cells within the maximum border range of a city (defined in ICityConfig.MaxBorderRange). Once that cell's been found, StartingUnitPlacementLogic grabs the argued IMapTemplate's StartingUnits property and attempts to build those units, one at a time, in either the ideal cell or some valid cell within 2 hexes of that ideal cell.
Unlike other parts of the MapGeneration subsystem, PlaceStartingUnitsInRegion() doesn't fail gracefully when it fails to place a starting unit, instead throwing an InvalidOperationException. In theory this makes the system brittle, since it can't handle large numbers of starting units, or unusual cases like a homeland consisting entirely of mountains. It does occasionally place units in locations from which they cannot escape: holes in the middle of mountain ranges, for instance. The latter problem is a serious bug that should be addressed if development were to continue, but the former is considered of minor importance. The chances of increasing the starting unit count beyond 4 or 5 are very low, and it's much more likely to remain near the 2 it currently occupies.
With all that done, the map is ready to render. As its last act, MapGenerator tells all the chunks in the IHexGrid to perform a full refresh, at which point the long and complicated process of rendering the map begins.