Optimizing Colonist AI

We are definitely moving into the part of the dev cycle where we can craft the  “mid game” experience of Clockwork Empires effectively. One of the issues we are currently facing with the middle game is one of performance. We have a requirement that the game perform 10 simulation ticks per second, as mandated by our AI. This means that every update to the game state needs to take place in approximately 100 msec to avoid stuttering between frames – the renderer will keep rendering, if necessary, while it waits for the game AI to catch up. If you have 100 characters to be simulated, this gives you a budget of slightly under 1 msec per character. With Revision 36, we started to see people sending us save games with functioning colonies of 70 or so colonists, where stuttering was frequently occurring, and where in general the frame took more than 100 msec to run on my PC at the office. What can be done?

A busy town bustles. What is to be done!

A town bustling busily. What is to be done!

Optimization for game AI is, not surprisingly, basically the same as optimizing a renderer. The goal is to eliminate unnecessary work. You can do this in a number of ways: for instance, pathfinding can (and should!) use a hierarchical structure to accelerate A* queries. We have a connected component system in place which stops people from spending a lot of time trying to path from one area to another area if they can’t reach them, but pathfinding still takes a certain amount of our budget and needs more optimization. In the mean time, however, it is interesting to look at what our actual hotspots were, thanks (as always) to the miracle of RAD Game Tools’ Telemetry. Here’s an itemized list of problems and how they were fixed:

  • “Unnecessary dependency checking.” Our job requirement system can check to see if a job dependency can be filled by doing another job, and if that job has a dependency that can be filled by doing another job. Very often, a job requires empty hands; if you have a tool, this requires you to stow the tool. This requires you to be wielding a tool; if you weren’t wielding a tool (for instance, if you are holding a Crate of Pickled Black Fungus) the game would then try to fill the stowing a tool dependency by seeing if you could wield some tool somewhere, which in turn would try to see if it could get you to drop the Crate of Pickled Black Fungus to wield the tool to stow the tool to get your hands emptied. We cleaned this up by adding a flag saying “don’t evaluate dependencies for this requirement.” We also do this in a few other places: most notably, if we don’t have an enemy, we see if there is a job we can perform to create one. All this got cleaned up.
  • “Unnecessary round trips to and from Lua.” This shows up in the stockpile code, amongst other things. Everybody hates how stockpiles currently work (which is to say not at all), so I’m just moving the entire mess to C++ space and rewriting them! Yay!
  • “Getting all the objects in a region with a certain tag, and then ignoring the tag.” This shows up a bunch of times and is related to “Unneccessary Round Trips To And From Lua.” If you ask the engine from the script system for “all the objects in this radius with this tag”, it has to search for them (slow), put them in an array (allocation of memory!), send the array back to Lua, and then delete it once Lua is done with it (Garbage Collection!) This adds up a lot, especially when you consider the amount of round trips that the engine actually requires us to take. The solution is two-fold: first, just ask the engine “Are there any entities with this tag in this radius” and have it return a Yes or No answer. (In fairness, this code didn’t exist.) Second, for a sufficiently large radius and a sufficiently sparse object quantity (for instance, all alarm waypoints in a 50 tile radius), it is better to just reverse the lookup and check all alarm waypoints in the game, rather than searching 10,000 squares by hand for the alarm waypoints.
  • “Unnecessary string access.” Tags are designated as strings because, well, scripters like strings. For fast comparison, we hash the string; for elimination of programming bugs, we convert the string to lower case first. In a handful of places, however, we would hash the string and lower case it every time we did a comparison, without re-using it. Fixed!
The only thing Mr. Fox is going to catch on the way to that raw dodo is a landmine.

The only thing Mr. Fox is going to catch on the way to that raw dodo is a landmine.

With these changes, people should be able to have a lot more colonists running around in the simulation without the game side lagging. Have fun!

Posted in Clockwork Empires | Tagged , , , , , ,

12 Responses to “Optimizing Colonist AI”

  1. Skyler Donahue says:

    Cool Stuff. Are you guys putting out a 36B today?

    { reply }
  2. Alejandro Moreno says:

    The Brazen-x forefather must have had quite the clan!

    My favourite branch of the Brazen family: Brazenwhistlesly.

    { reply }
  3. Alephred says:

    When you Google ‘Harvard Compact’, the very first link goes to Deep Blue Sea. You made me remember Deep Blue Sea.

    { reply }
  4. Sapphire Crook says:

    The fact that ‘have empty hands’ equates to ‘has tool in hands’ is a problem I can’t fully understand.
    Shouldn’t the solution to an ’empty hands’ job be… well… ‘drop everything in hands’ instead of ‘acquire object normally expected in hands, then drop that, oh, but first find a way to drop what you were holding that wasn’t normally expected in your hands in the first place’.
    I dunno, that’s just me. And programming is half-art, half-structure, so it’s not surprising to see things clash. Or perhaps there’s a super smart reason why it’s done like that that I have yet to learn! Exciting either way!

    I love that ‘we have no enemies, so make one’ is a logical conclusion. If you EVER want to display how to-the-point computers are, just tell them how they’re happy to do something bad as long as it fulfils the arbitrary requirements they were given.
    Also, I wonder what it takes to make an enemy. “To make one Fishman, put one Colonist and one Fish on an altar, pray to the Fish Lords and douse in salt water until evolution happens”.

    { reply }
  5. Mike says:

    Are Kitchen improvements on the horizon? I’d like the colonists to just make food as the queue system is a nightmare. I’d also like a need for food diversity, and perhaps to replace the queue some way to gain new recipes instead of starting with all of them.

    { reply }
    • One of our ongoing tasks involves looking at the entirety of the production tree to identify places where an item isn’t worth creating or isn’t worth the cost. Kitchens definitely suffer from the former problem, but since they’re functional (just not super interesting) they’re a bit further down the to-do list than some others. We will definitely be looking at ways to make food variation valuable.

      As for the queue system issues with kitchens, I’m assuming you’re referring to the issue where the raw goods get consumed before the cooks can make them into cooked food. We have plans to improve this as well, which should actually improve all of the systems with useful intermediary commodities. I can’t say when these will be in the game as the solutions might need more work than we think, but hopefully it’s nice to know at least that we are working on it 🙂

      { reply }
  6. Benevolent Overlord says:

    Was able to get to over 100 colonist before a save game attempt caused a crash. After about 80 colonist, things really started bogging down, and at 100+ it became too painful to watch. I was also having trouble with my mine eating colonists even when they were unassigned. I look forward to testing your fixes when you release 36b.

    { reply }
  7. Velvet Apocalypse says:

    Something feels very “Dogs must be carried” about the dependency checker!

    { reply }

Leave a Reply

Your email address will not be published. Required fields are marked *