Clockwork Empires relies internally on a series of tags, as I think we’ve discussed on this blog far too many times. When you go to look for something like food, we check the game for every object with the “raw_food” tag, and then you go to eat it. Here is where the bad news happens: once you have a sufficiently long game, you can stockpile large quantities of food. Let us say that a player has 500 pieces of raw food. Let us also say you have 150 characters – so, to put it into perspective, the player has accumulated 3 days worth of food. (This isn’t even that large a number.) Every day, the 150 characters must go and eat 150 pieces of food out of the 500. The problem is – they want to eat the *closest* food. So now we have to check 500 pieces of food vs 150 players to see which piece is the closest, for a total of 150 * 500 = 75,000 distance queries. Well, that can be a bit slow, especially when our AI budget is very tight and we have a lot to do. However, we’re now seeing games where characters have huge amounts of food – 5,000 pieces of food, say – and the game slows to a crawl. Clearly, smarter programming is required.
A lovely sea-side desert colony sent in by a player as part of a bug report.
Clockwork Empires stores all information about object positions in a spatial dictionary. The handling of tags is done by a “tag index” class, which is essentially a giant array of information consisting of the following attributes: “position, object, previous item with this tag, next item with this tag”. When a tag is set, we grab a tag index from a giant statically allocated pool of tag indices, so that we don’t have a memory allocation, and attach it to the linked list of tags. The problem is… there’s no way to easily find the “closest” tag to your point. What is needed is a spatial acceleration structure of some kind – a way of dividing the world into regions so that we can start in our region, check it for the closest whatever, and then move on.
