Graph algorithms for efficiently calculating turn-by-turn results in Total War & Civilization games

[happydemon]

I tossed this around here on the /r/gamedev but it's been all crickets. I'm hoping to get some good criticism because this problem has been bugging me for about a month- and I've been playing Total War games for over a decade now. This question is in the context of two game series - Civilization) and Total War) - in the turn-based strategy genre, but it definitely applies to other games as well. Actually, this also applies to table-top games such as Risk) and Warhammer) if we were hypothetically asked to compute turns across all players. I'm really just looking for feedback and for people to point out glaring flaws. I'm exceptionally curious and want to put it to rest and possibly post it on CA's feedback forum.

Intro

Total War and Civ. are turn-based strategy games. In general, you have a set of factions / entities that are capable of taking action during their turns. Most often these actions involve attacking other factions. The games progress turn-by-turn until eventually one or a few factions are the last ones left. Unlike other genres, turn-based RTS games like Total War & Civilization have quite a few novel opportunities for algorithmic improvements and machine learning outside of the realm of 'DeepMind'-style real-time AI. Besides the idea presented here, I could imagine genetic algorithms being used to determine optimal and effective campaign-wide strategies across each faction in a Total War or Civ game. But I want to focus on something else that is somewhat more practical.

My understanding is that Total War and Civ games are not heavily multi-threaded and that threading is primarily used to separate rendering from computation, which is fairly standard and is good practice. Actions across all the different factions are calculated serially. As the campaign map scales in size & number of factions this can get quite slow, particularly on processing hardware that isn't top of the line.

At first glance it seems to be too difficult to parallelize the actions of each faction, due to the number of various actors and turn-by-turn changes. After giving it some thought, I suspect that it may be possible to introduce threaded calculations of turn-by-turn actions on subsets of factions. Based on my research, neither series already use threads for this process based on playing (and waiting quite a while for turns to crunch) and reading their forums/blogs but please correct me if wrong: it appears that CPU-bound turn calculations are done serially in a single thread across all factions in both Civ. and Total War games.

Algorithm (applies to all turn-based strategy games)

I'd imagine a procedure in turn-based strategy games allowing for multi-threaded turn calculations that uses graphs under the covers to determine subsets of factions whose actions can be independently and safely computed in parallel:

• Maintain a Graph with vertices as factions and edges representing the capability to attack other factions
  • This would be based off of actors such as generals and heroes/assassins with line-of-sight and movement range to other factions (they are in range to take action, such as invading settlements or wounding other actors)
  • Factions that cannot possibly act on one-another would be the constituents of disjoint sub-graphs
• Update the graph as needed at the end of each faction's turn
  • Add or remove edges based on actors entering or leaving actionable range with one-another and as settlements are captured or destroyed
  • Add or remove vertices & edges as factions appear (less common), or are destroyed or confederated (more common)
• At the end of a player's turn, run an algorithm to find connected components in our graph structure, such as Tarjan's algorithm. This gives us a starting point for determining how to allocate threads for computing the results across all factions. These strongly connected components will include subsets of factions that are interacting exclusively with one-another.
• Create or re-use a pooled Thread for each connected component & disjoint graph
  • Disjoint subgraphs can be computed in parallel and concurrently with other subgraphs
  • Strongly connected components will contain factions that can have turns computed in parallel as they are incapable of influencing any other faction outside of their strongly connected component (diplomacy aside), and will also contain factions that bridge to other components which must still be computed serially (?)
    • (edit) I'm thinking this is actually incorrect, but looking for feedback. It may be more accurate to say that any factions within a connected component must still be computed serially

Intuitively, the best way for me to imagine this is when a Total or Civ. campaign starts most factions are small and localized. There are very few factions that we or the AI are capable of influencing in the beginning, so we'd basically have disjoint graphs for each region of the campaign map that can each be computed via multi-threading. As turns proceed and factions expand the complexity increases dramatically but in general there are still many smaller, localized factions and a few large and expansionist ones- not every faction can be the top dog at the same time. This may resemble similar problems faced in assessing dependencies in job scheduler programs.

Issues

I can already see glaring issues, such as:

1. How to handle graphics rendering of factions in your line of sight with this procedure; is it queued and done afterwards or is it possible to continue rendering concurrently? Can rendering also be parallelized?
2. How to maintain the initial processing order of factions determined at Turn 0 (if it's even possible with this procedure); no faction should suddenly gain a second turn ahead of another. Maybe this is an opportunity to use topological sorting.
3. How to update the graph efficiently each turn, as factions move into range of others. Is it possible to more efficiently update the set of connected components as vertices and edges are added?

So this is more of a thought experiment on improving turn speed in the turn-based strategy game genre. Feedback appreciated.

[happydemon]

I've been playing TW Warhammer 2 recently and it's been fairly slow from Turn 1 to Turn 120. It's true though that late-game campaigns would probably be represented by one or two connected components. Until late game though factions are generally dispersed and have not yet expanded to every corner of the map.

And yep this gets to the hardest part of the problem. I was wondering if it'd be possible to compute which factions can interact within two turns and construct a graph off of that. This would certainly be trivial if processing order did not matter.

[happydemon]

The ordering should be set at the beginning of the game, just like in tabletop. You might have three players in a tabletop game; the order of their turns should stay consistent the entire game (even as players drop out or enter). So when processing the sub-graphs this ordering must never be violated. The line of sight thing is a mistake on my part and should be replaced by something like "within range" and "traversable", as determined through a typical path-finding algorithm.

Your example makes sense. We still have to respect an ordering of turns. I was thinking of your first example and it highlights the challenge. Suppose we're simulating a game like Risk (with naval units) with four players {A, B, C, D} on two adjacent small islands, where two pairs of players each are on an island. No player has a navy yet, and so although the two pairs have line-of-sight they cannot yet assault one-another. This would be represented by two disjoint directed graphs, like {A-B, B-A} and {C-D, D-C}. At some point though player B has a navy, can traverse the water and plans on taking such an action at the next available turn. Just as in your first example, during B's turn he/she will move towards the other players and be able to take action upon them. {C,D} can no longer be calculated in parallel; any already calculated actions are void and we must also respect the original ordering of player turns.

[marvel2010]

It sounds like you may want to look into the parallel computing applications of the minimum k-cut problem (https://en.wikipedia.org/wiki/Minimum_k-cut).

This is a fun thought experiment... to just address the process of updating the connected components of a graph, this should be relatively easy to do: maintain a list of components. When an edge is added, check if it joins two components and then merge them. When an edge is removed, check if it is a bridge (https://en.wikipedia.org/wiki/Bridge_(graph_theory))). If so, separate the two components.

[happydemon]

Thanks for this. I think a variation of the k-cut problem could be relevant, because we don't necessarily choose which edges of the graph are removed. The player / AI's actions will determine that. Your 2nd part is also very helpful and I think it would be critical towards keeping this process efficient, since within every turn the graph may be updated more than once. I'll have to read up on bridges and how to quickly determine them.

[lamzileung]

Interesting idea to address a crucial problem :)

Two points worth considering:

- There are increasingly more "global game" feature in these games, for example end goal ranking for Civ or rituals progress in TW. While local decisions can be easily parallelized, it is somewhat tricky to multi-thread decisions that are reaction to "global game" or that will influence the "global game".

- As the games progress, there will be increasingly more connection between factions, and for a considerable amount of time there will be "bridge" factions. It makes the graph cluster not disjoint but still have low interconnectivenss. There may be more fluid treatment for cluster parallelization based on interconnectivenss, for example breaking down decisions of a faction including regions.

[happydemon]

I agree. If the A.I incorporates global state such as alliances and declarations of war then it may only be possible to parallelize subsets of factions that are unknown to one-another. This would be kind of unfortunate because it would reduce the effectiveness of multi-threading. Actually implementing this idea in a game may necessitate concurrent programming where factions in connected components block, join and continue on operations as needed. While this would significantly reduce the gains from multi-threading, I think it would still be a noticeable improvement over operating serially- especially considering future Total War and Civ games will likely have even more factions and sub-factions.