Goals

• Procedural generation of maps.
• A data-driven way of defining map templates, in the same way continent and region templates exist now.
• A small continents map generator, where players are scattered in pairs across some number of small continents.
• Procedural distribution of rivers and fresh water.
• Procedural distribution of strategic, luxury, and bonus resources.
• Statistical balancing of starting locations, so that every starting location has approximately equal amounts of resources and yields available to them.
• Procedural placement of the starting units of civilizations in ideal first-city locations.

Risks and Mitigation

1. Ensuring that starting regions have similar yields could end up taking a tremendous amount of time, which could make map generation impractically slow.
   • Ostensibly I can keep a running tally of gold, production, and food yields. I can then build some strategies for increasing any of these yields and then call into these strategies for the yield with the largest disparity. I'll need to come up with a strategy for estimating the yield of resources, hills, and terrain types. That might require knowledge of cell yield, improvements, and technologies, which could confuse things a bit. At the very least I can separate that logic into separate classes and keep it away from region generation and resource balancing. That should make things easier to work through.
2. Ensuring that starting locations have similar yields could make all starting locations feel samey, which would defeat the whole point of generating maps procedurally.
   • I'm not sure how big of a problem this'll be. Chances are good that it won't be, especially since there'll be many ways of addressing a particular resource abundance or shortage. If it turns out to be a problem, I can add a number of yield templates that a starting region can go for. For instance, there might be some starting locations with less food and gold but more production. Or there might be some starting regions with more yield but fewer specialty resources to trade. But I should defer that until starting location sameness becomes a problem, which it might never.
3. Map generation is currently in a somewhat messy and half-formed state. If I'm not careful, I could end up creating a rat's nest of code that's hard to extend or maintain.
   • I already have a pattern for region and continent generation that I can apply to map generation as a whole. I know I've had problems figuring out what my weight and filter functions should consider. I'll need to spend some time standardizing those. The most important thing will be spending some time early on cleaning things up. I'll need to attend to that continuously every time I add something new. I should try to add comments and unit tests wherever useful so I know how to work with these classes in the future.
4. I ran into many problems with river generation during my first attempt, many of which made it difficult to ensure the existence of sane rivers. I don't have a clear plan for resolving the problems I encountered.
   • One thing I might try is building the river backwards. If I start with its outflow aligned with the sea and then draw the river backwards until it reaches some valid starting location, I could probably prevent rivers from running into a bunch of hills and stopping. I might need to do something fancy to choose particular edges along which to run, or to split/combine rivers when that's a desirable thing to do. I might be able to repurpose some of my river code to make that work.
5. While I can imagine how to create a map template for small and large continents, it's not clear how I'll make a template that can handle things like archipelagos.
   • Right now, all of my sub-continental regions attempt to create a more or less solid block of land. For archipelagos, I could have my "continents" instead attempt to generate large amounts of water and scattered islands. I could then reduce the sizes of the larger, deeper oceans between my island clumps, or maybe eliminate them altogether. That's at least something I could attempt. I could probably make the islands snakier by having my weight function ignore distance from the seed and increase weight if the next neighbor is adjacent to land cells. There's stuff I can try, at least.
6. It's not clear to me how I'll detect good settler locations once I have a map region, which could make it difficult to ensure balanced starts.
   • The easiest way around this would be to simply choose a region where the settler starts and then build resources, rivers, and yields around it. That way I don't have to go searching for a good place and I can guarantee that the starting settler will always start somewhere good.

Review

I started by building a template-based system for generating maps. Maps are currently divided into continents, each of which is divided into some number of regions. There are templates for maps, continents, and regions, all of which allow for a considerable amount of configuration. It's now possible to substantially alter the way in which the map is generated without modifying the codebase itself. It remains to be seen whether this organizational hierarchy is useful for generating maps.

After reorganizing map generation, I reintroduced procedural generation of rivers. My current implementation often produces fairly decent results, though there are a number of problems. Rivers will occasionally not reach a valid endpoint, and will more rarely flow uphill (probably due to bugs in RiverCanon). The random assignment of river start and endpoints means that rivers will occasionally cluster together, producing results that are sensible but weird-looking. Very rarely a river will loop around to the body of water that supplied it.

Beyond the sanity of the rivers carved, starting regions have a hard time ensuring a consistent number of rivered cells. It seems as if some starting regions have a much higher concentration of cells with access to fresh water, which substantially modifies the balance of regions.

I then moved onto resource placement. I began by adding placement restrictions and weights to my various resource types to make sure that resources were placed on sensible cells. I then tried to get a reasonable distribution of luxury resources, since those are the most important. I eventually arrived at a solution similar to what Civ 5 seems to use. Regions can have up to 4 types of luxury resources in various quantities, which the generator tries to spread across the width and breadth of the region.

After figuring out luxuries, I decided to lump in statistical balancing of regions and the placement of bonus resources together and address them both at once. I spent the rest of the sprint trying out a number of solutions for creating balanced starting regions. This induced a change to the simulation code I used to calculate yields. I spent quite a bit of time figuring out what it meant to balance a region, of how I would detect imbalance, and of solutions for increasing or decreasing the value of a region.

During that time, I ran into lots of problems with resource saturation. I commonly found that my regions either had very few bonus resources or far, far too many. It seems that the configuration options I've created are very sensitive. Even small changes to things like score per cell can radically alter resource distribution. I slowly made my way towards something sensible, though the current implementation is not stellar.

Retrospective

What went well?

1. I managed to convert my river-carving solution from last sprint into my new map generation system without much difficulty. It turns out it was decoupled enough from that solution that I could move it around without trouble.
2. Luxury resource distribution is working very well. I've got a good way of ensuring resource diversity across the entire map, of creating good distributions across a particular region, and of controlling node numbers and resource types.
3. I finally resolved the SpecialtyResource/Resource naming problem. They're now called MapResources and Yield, which should help disambiguate those two distinct concepts.
4. My map generator is finally starting to produce results that look like Civ 5 maps, which means that all my work is finally starting to come together into something resembling a presentable project.
5. Map balancing went smoother than I'd feared. While I don't think I've a brilliant set of balancing strategies, the fact that I've gotten my starting regions to balance at all without destroying their appearance (most of the time) feels like an accomplishment.
6. I think the architecture of my map generation system is set up well for modification. I could completely rework how continental contours are generated and how regions are carved from the map without affecting any of my region generation code. Yield estimation and scoring, while both things that need work, are separated enough from the rest of the codebase that I can make improvements to them without interfering with anything else.
7. I have a much better idea of what map generation needs to do, of what problems I'm facing, of specific solutions that I need to implement and specific things I need to keep in mind. Off the top of my head I can think of about a dozen small, specific, self-contained improvements I could make to this system.
8. Addressing a specific need in the codebase, I've made the logic I use to calculate cell yield a lot less coupled and a lot more flexible. Figuring out yields through a collection of stateless classes has made current estimation of yields a lot easier. It's also made it much easier to change the system in the future.

What could be improved?

1. My map generation is almost completely uncovered by unit tests. Part of this stems from a lack of discipline, though mostly it's because I've not the slightest idea what unit tests would check for or what they would accomplish. I should do a bit of research to see how I might build test fixtures for procedural/pseudo-random generation, or whether such a thing is a fool's errand.
2. River generation has some problems. They sometimes don't drain into bodies of water. They still flow uphill occasionally. River generation doesn't produce a consistent number of rivered cells. And rivers will sometimes form too close to each-other, forming large doab-like regions that don't look very good. All of these problems will need to be resolved.
3. My current continent system feels too rigid to produce natural-looking maps without obvious and glaring structural patterns. I'll need to figure out some more organic way of generating continents than what I have now, especially if I'm looking to ape Civ 5's map generation.
4. I haven't incorporated strategic resources into map generation, mostly because I view neither horses nor iron to be particularly important to the game. Regardless, I need to start distributing strategic resources as if their placement were very important. In general they're a meaningful part of the game, so I need to incorporate them better.
5. Bonus resources still have a tendency to clutter regions. I need to keep working towards a better resource distribution system, preferably one I have more control over.
6. Map generation is getting complex enough that I'm starting to forget important implementation details. I need to start commenting this section of the codebase better so I don't need to remember how everything works.