Overworld Territories

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 512×512 overworld, this would be very roughly a city per 32×32 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.

 

Nations, Races and Cities

One thing that has been bugging me for a while is the administrative aspect of the world’s population. Several races coexist in the world, sometimes not so peacefully. One of the important questions is, how to divide the population groups? This can answer questions such as who lives where, who likes whom, how does the player interact with each group, etc. The context is always important: this is a game where the player controls a single character over the course of maybe several in-game decades, in a persistent and procedural world, where there are lots of self-sufficient cities with guilds, shops etc.

Nation-based

One way of dividing them is DnD/Forgotten Realms style using nations. Each nation has different government type (plutocracy, magocracy, autocracy) and has citizens of potentially many races. This is a nice, “realistic” division, but comes with a number of complications for a type of game where you’re an adventurer going around in the world and doing stuff. Just a few issues below:

  • Nation conflicts and diplomacy. When there are several nations, it’s only natural that over the course of time conflicts arise. If relations were all nice among them, there’s no reason not to be unified. Modeling nation-wide war in a game where the player controls a single or a few characters can be problematic. What happens if nation A wages war on nation B? What does that mean for the player? Can the player not safely visit several cities of nation A or B anymore?
  • Nation-wide AI, city-wide AI, unit AI. With nations, there’s more AI to develop. What responsibilities does a nation have? What can it do? Found cities, wage wars, etc? We’re getting heavily into 4x game territory, and that becomes a bit much for solo development.
  • Nation identity.  When creating a number of fictional nations, effort must be put so that the nations are unique, individual, interesting. I’m personally very averse to fiction where the differences are superficial. For example picking a name from a generator list, roll a dice for government, roll a dice for alignment, etc and that’s it. That’s not enough. Forgotten realms for example has quite good depth for each nation, but that’s over tons of books and game supplements. Solo development can not afford such depth.

Race-based

Another way to split nations is by race, where the race would also be the nation. You have dwarves, elves, humans, etc. That’s nice and simple and at least addresses the “identity” issue above. There are still potential conflicts and AI to be modeled though, but they are nothing compared to the effort in creating a striking identity for a nation. The identity of the races still needs to be developed to escape the confines of the generic high fantasy elf/dwarf and other races, but that would be done for the nation-based division anyway, as a separate task. ( Create identity for dwarves, humans, orcs, etc, also create identity for nation of Whatever and Etcetera). Issues with race-based division:

  • Not sensible. It just doesn’t make much sense that, at least “good” nations would prohibit citizenship from other intelligent species, as long as they could all co-exist peacefully. Of course dwarves could be reserved against other races, or elves be haughty and racist, but having that at 100% everywhere makes the races one-dimensional and not so believable.
  • Player interaction limitation. In the game, several guilds exist that the player can join. If the player is from race A, do you get excluded from guilds in cities of race B? Otherwise, why would they be the special cases of allowing members of different race? It would take quite a bit of writing effort to make that sensible and believable. The game would force you to be part of a big group, where inadvertently you’d have situations of “us vs them” at a nation/race scale.

Multicultural city-states

Another way to divide the world is to ignore the nation-wide scale using city states (Elder Scrolls cities feel sort-of like that). Cities are self-sufficient, can contain guilds and various other buildings and people that a player can interact, and have the following advantages:

  • No need for full-out warfare. A nation gathering army and ganging up to attack a city is much easier than a city gathering army to attack another city. So all-out warfare between city-states is not something that one can expect to naturally happen. Subterfuge on the other hand is much more likely, and can create very interesting scenarios: for example a guild hires you to steal a relic from a rival guild of another city-state, or the government hires you to sabotage a mine operation that belongs to another city-state.
  • Multicultural. A city-state can optionally be multi-race, or single-race, or anything in-between. A fully dwarven city in the mountain is as plausible than a hillside settlement with hill dwarves and hill orcs, as long as the races can coexist peacefully.
  • No nation-wide simulation layer. Easier to develop as there’s no need for nation AI. Nations don’t need to found new cities, as the time scale of the game is not centuries (which would take for a city to start, grow and have some sort of history). There’s no resource management layer between cities and nations (does a mine’s ore go into nation coffers? Does a nation have resources, or they are per-city?)
  • Emergent identity. The city-state types are used as a prototype several times, but the simulated and played history can affect the development of individual city-states. A dwarven city in the mountains can start as poor, if surrounded by not-so-resourceful environment, but its fate might change if they discover a rare mineral nearby and mine it. A different dwarven city could have a completely different fate, for example it could be eradicated by Unknown Destructive Forces or sabotaged to oblivion. The basic identity (how does a dwarven city look like, how does it function, etc) is written for a limited number of prototypes, while the emergent identity via history generation and playing is what will make it rich.

 

The above are just some thoughts; not final, but representative of my current development mindset. While originally I started with the race-based approach, I’ll be using the city-state paradigm unless I can think of a blocker.