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.
What’s New In Programmertown?
The best part of game development, for me at least, is when everything suddenly starts working. Quite often, there is a critical mass of code that you end up writing for a game, and then – in the span of a week, or even days – you go from “everything is hideously broken and we’re going to die” to “Oh, this might be fun.” We’re right on the cusp of that right now; programming has seen some setbacks this week, mainly due to an outbreak of flu that has consumed the office. Nonetheless, we’ve been hard at work here in Programmertown, trying to get all the excellent artwork and ridiculous designs that people have come up with integrated into the game as quickly and efficiently as possible. Once again, let us take a tour through my folder of wonderful work-in-progress screenshots.
{ read this article }
8 Comments