City-States

City-states rule the world. For the whole overworld, using my current projections, there will be a maximum of about 250 cities. For a 512x512 overworld, this would be very roughly a city per 32x32 grid.  Given that a grid cell would represent about 10 sq km, this mean a very sparsely populated overworld, which doesn't resemble the Middle Ages all that much. That's fine though, as the alternative/realistic version would be a city/town/hamlet per grid tile, and that would make a quarter of a million such towns.

Borders and growth

City-states have areas of influence, which define their territory and borders.  The area of influence is directly related to how difficult is to cross the terrain. In that sense, sea and high mountains are in general more difficult than other terrains, and the difficulty only increases in temperature/humidity/vegetation extremes. With that in mind, we can create an "influence cost map", which dictates how influence, generated by its sources (cities at the moment), is reduced while radiating outwards.

Borders between city states

Another interesting point is how to deal with borders between city-states. I found that the simple way of "whoever exerts greater influence on the tile, owns the tile" is unsatisfactory, as city-states with even slightly greater influence can quickly overcome the whole territory of another city state. For example, a city state gains 4% influence, and suddenly it wins over 60% of another city state's total territory. To deal with that, I still compare the influences, but they are scaled by a factor related to the inverse squared distance of the grid cell in question to the city states: tiles close to city-states (and owned by them)  are much more difficult to be won over by some other city state, especially if it's far away.

Algorithm

A couple of years ago I developed an algorithm for this, with "nations" in mind (a max of 16 of them). The algorithm was fast, a bit buggy and complicated. Also, code was messy. I tried to read and understand it, and realized I'd be better off writing something from scratch, and it had to be simple. As an attempt of documentation here's the algorithm in all its glory.

Data format

First things first. For each tile, we store the source ID and the influence decay so far, from the source location until the tile. The decay will be the accumulation of decays along the "shortest" 8-connected path starting from the source.

Initialization

Create the influence decay map, that stores for each tile how much influence is reduced on crossing the tile horizontally or vertically (for diagonal crossing, it's scaled by sqrt(2) )

Adding/Removing/Changing an influence source

All these cases are handled mostly in the same way, which important for simplicity.

-> Update local cache

We keep a very small per-source cache that stores the location and influence of each source -- that's it. We update the cache by adding/removing/modifying entries as needed

-> Calculate front

We calculate all the border tiles of a source in the following way. We start with the influence source location (the city), and we slowly expand outwards the 4 directions (left, right, top,bottom). We expand towards a direction if a point is within the influence of the source. Below is an image that represents this outwards expansion (the center of the concentric squares is the influence source). In the image, I mark the boundary points; these are the points that have at least one neighbour that is outside the source's influence (they could belong to a different city, or they might be neutral). So, we slowly grow this axis aligned bounding box of the source's points, while adding all the border points to a "to process" list.

 

-> Process queue

We have now a queue with a list of points to be processed. These are all the boundary points (For a newly created source, it's location is the one and single boundary point). The queue is a  priority queue: we add points accompanied by weights, where the weights represent how important it is to process the points first. The reason why a priority queue is important is because we want to avoid traversing tiles multiple times. Imagine the following scenario:

  • Tile (32,45) needs to be processed. We figure out that it should belong to source S0, and it will have an influence of 50
  • ...
  • Tile (32,45) needs to be processed again. Because we arrived here from a different path, we realize that it should actually belong to source S1, and it will have an influence of 62
  • ...
  • Tile (32,45) needs to be processed again. We arrived from a different path again, but from the same source ( so effectively used a shortcut, e.g. around the mountains that cost much to pass through). So, while it will still belong to source S1, it will now have an influence of 65.

So, a tile can be unnecessarily processed several times, while we can avoid that if we process the last one first (S1, 65 influence), as the others simply have lesser influence and will not cause the tile to get re-processed. The above also hints on how the processing is done: as a form of floodfill. While on a tile, we figure out who the owner is, how much influence is there at the tile (source influence - influence decay till point), and which neighbouring tiles do we need to process. The queue processing algorithm can be summarized as follows:

  • Get the top point in the queue
  • Check if it's obsolete. It would be obsolete if the stored weight is lower than the current weight (the weights are just the influence values). If it's obsolete, repeat from above
  • Check the 8 neighbours and calculate the scores as if the neighbours owned the tile. So, we pretty much calculate if they should own it
  • If our influence is negative and there's no better neighbour, the tile needs to be reclaimed by nature. If that's the case, add to the queue all neighbours that are of the same source
  • If our influence is positive and there's no better neighbour, we're ok and we need to see if we need to expand this source id to neighbouring tiles. By comparing influences, we add potential candidates to the queue.
  • If there's a better neighbour, we replace this tile. The new influence information can propagate further, so we check all neighbours to find out potential processing candidates and add them to the queue.

Video

Here's a video that demonstrates border growth for 256 city states.