Multi-Threading In Turn Based Strategy AI
If you hit the end turn button too soon you will experience what Lovecraft merely dreamed of
Multi-Threading Introduction
Multi-threading is the holy grail in performance these days as CPUs stop gaining significant single core performance every generation. Turn based strategy games might not seem like an obvious area to benefit from this since they don’t need multi-threading or GPU acceleration for their low complexity graphics. Sure, dump the GUI/sound stuff on a thread but all the real bottlenecks are in main thread simulation computation. Luckily TBS games have a large advantage over their real time brethren including Paradox games. Stardock has had a professionally multi-threaded engine for a while now and while it doesn’t solve every problem it sure compresses turn times. That is the dream.
Designing For Multi-Threading
I don’t know how the Stardock multi-threading works but I suspect it is much more advanced than mine in various areas. Especially handling graphics and sound. Pretty much the only thing I am using it for is the NPC AI Planner.
In Axioms the AI for Characters has 2 phases. the high level Planner which gives them goals, and the low level code to execute suggested actions to help reach a goal. The goal generation code only writes to a class connected each character by a pointer and only from a given character. So there’s basically no chance of a problem. This part of the AI takes up most of the CPU power. So getting this off the main thread is quite useful.
I haven’t finished the AI and the current test map only has ~100k characters. Many of them wouldn’t naturally do anything because the code doesn’t have goals or actions for their unique Consciousness yet. And even Characters who would generate working goals don’t have to calculate the value of each goal for comparison. As a simplification I took the more performance intensive function available, moved it out of the checks and just had every Character run that to produce goals. 100 times each. For science.
While this doesn’t perfectly replicate a fully working AI or the potential for a million NPCs rather than 100k it does approximate having more characters doing more calculations. In any case with one threads coming off the main thread it takes ~97s for the runPlanner function to finish. At least according to VerySleepy.
With 4 threads aside from the main thread, that is one for each physical 4/8 core on my i7-4770k CPU(don’t judge me I’m poor okay). Well you also have the main thread with has the GUI and some other stuff plus the other programs running but close enough. This takes roughly 29 seconds.
That’s not quite a 75% reduction but is close enough given the limits of my CPU. Finally for 8 threads it takes 21s for all the threads to .join() the main thread. So essentially an 80% reduction.
Player Turn Multi-Threading
Having a 21 second turn is already relatively competitive, although I can’t be sure that would be comparable to the time with the full AI and character count. But we can do better. Much like Stardock I am taking advantage of all the time wasted by the human player. It is so unfair. The human gets to take as long as they want and they are the only person running on their hardware, well slimeware.
The Planner has no impact on the game state that the player interacts with. So it can run during their turn. Since the Planner is the most computation intensive part of the NPC AI this is very convenient. Especially since Axioms is relatively unique in that you really shouldn’t be mashing endTurn(). You get a constant amount of Attention Points each turn, although they do roll over. So you should probably always be at least socializing with family and close friends/vassals/allies/staffers.
In theory if we expected the player to spend a minimum of 120 seconds on their own turn we would always have more than enough time to finish the Planner. In the current test there is still some computation on the execution side of the AI that could be moved to the Planner if necessary. Regardless turns take ~2-4 seconds. If we only ran the test loop/function in the Planner 10x instead of 100x it would be under a single second. Remember that to some degree the test is supposed to mimic a game with worst case computation requirements. Not that this is necessarily a successful attempt.
Conclusion
With a multi-threading friendly design you can really annihilate turn times. Stardock has proven this in a released product, I think several by now actually. Civ6 sort of does multithreading but it is possible weird animation related slowdowns or a design not suited to heavy multi-threading are the reason it seems worse than it could be. Some consideration must also go to whether the Civ6 or Galciv AI actually does a lot of useful work. Just because they *can* doesn’t mean they *do*. The Civ6 Benchmark says my Civ6 turns should take about 8 seconds on average. I understand that Gathering Storm turns take much longer, roughly 4x as long.
Axioms should benefit quite a bit from any number of cores although I’ll need to run some tests on more modern CPUs. My multi-threading isn’t quite as fancy as Stardocks but it gets the job done. My goal is for games with the most complex game data to have 10s turns max but we’ll see.