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.
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.
The solution I came up with after some hacking is very similar to what we already do for raycasting to pick items for selection in-game: an object grid. The world map (256×256) is divided into cells (currently 16×16), and we keep a list of what tags are in each cell as part of the same tag index. A tag can only be in one cell by definition, so we can use the same data structure and make the cell logic part of the existing tag registration/deregistration process. When doing a distance query, we check our cell first for tags – and then we find the closest one in that cell, and we’re good, right? Wrong. You can have this behaviour:
In this lovingly rendered piece of programmer art, the yellow sphere is the player, and the red spheres are two food items. You can have a case where the closest object is in a neighbouring cell, which means we need to find it. So the obvious solution is to check the neighbouring cells. The problem is now that you need some sort of way to stop the algorithm – when do you decide not to check a neighbouring cell? Well, you shouldn’t check a neighbouring cell if you *know* that it’s going to be further away than your most recently seen best object – a problem which is equivalent to asking “what is the closest point in the cell to the current location”? We need to find this quickly, which… well, that seems like math.
Fortunately, cells are axis-aligned bounding boxes. Here is some more hastily drawn programmer art:
We can see that the area around a cell is divided into eight sub-regions. In the upper left subregion, any point up here is closest to the top left corner of the cell. In the upper right subregion, any point is closest to the top right corner of the cell, et cetera. So all we need to do to find the closest point on an axis-aligned bounding box to a given point is to check, for each of the x and y components, whether it is to the left of, to the right of, or in the space defined by the axis-aligned bounding box; this means that we can find the closest point in a neighbouring cell with something like four if statements. We then only check those cells that *might* have an object closer to the player than our current cells, and everything else is a recursive algorithm.
This is a pretty good example of a good technical interview question for an entry level AI programmer, now that I think about it. Anyhow, people should be able to have better performance on larger colonies now.