All posts tagged with "master blaster runs programmertown"

Acceleration Structures

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.

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.

{ read this article }

17 Comments

Technology Status Update

It’s been awhile since we checked in with the programming side of things. I put out a call this morning asking “what would people like me to talk about?” Interestingly, the main thing was the UI, and how we’d make it Not Awful. We’re not talking about the context-sensitive UI because we haven’t worked out all the details yet, but we’re working on it. Instead, let’s talk about the general state of programming.

So what have we been up to over in Programmer Town?

{ read this article }

26 Comments