Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am working on a large scale real-time strategy game - ideally with thousands of units active at once - but I am having trouble managing all of the units at once without it becoming astonishingly slow. The problem is that it takes a while to update the positions and states of everything each time step. Do you know any design patterns/methodologies/tips for mitigating this?

share|improve this question
1  
although your question may seem alot different you can use the same algorithm as explained here. there is no need to use parralel processing in that algorithm, with only a single you'll get a high performance boost. –  Ali.S Jul 30 '11 at 21:44
    
Paralleling the update won't help if, say, you've got two cores and updating half of them already takes too long, but if you have multiple cores available and aren't already using them, it should help. Ideally you'll want a solution that doesn't require you to update every single unit every single time step, or a way to simplify the update so you can. How big is this time step? It's independent from draw frames, right? –  Blecki Jul 31 '11 at 0:43
4  
The first thing you can do is recognise that your speed has nothing to do with the quantity of independent actors. It has to do with what those actors are doing. I can have a hundred thousand independent actors update >60fps if all they're doing is if not dead position += 1 or one actor update <1fps if it's going into an infinite loop. Some of your algorithms - some parts of what these units are doing - are just too expensive the way you are doing them and that's all. There are probably a lot of different possible causes, and a lot of different possible strategies for each. –  Jonathan Hobbs Jul 31 '11 at 13:09

2 Answers 2

up vote 4 down vote accepted

There are two distinct things to consider when measuring and optimizing the performance of such a large-scale system of entities.

At the low level, you have the physical representation of your entities which tends to boil down to using efficient storage layouts like SoA (structs of arrays) to reduce the cost of iterating and updating all the active entities.

At the higher level, you have decision making logic, general game logic, AI and pathfinding. These are all tasks that have in common that they do not have to run at the same update rate as your rendering does.

As you would get an uneven frame time if you take the naive approach of just doing those tasks every N frames, it tends to be beneficial to amortize the cost over several frames.

If the task is incremental in nature, you could run part of the algorithm every frame and use partial results in your updates.

If the task is largely monolithic but separable per entity, you could perform that task for a subset of your game entities per frame, rotating among them in a round-robin fashion. This has the benefit of reducing the complexity of things like pathfinding and AI, as you don't have everyone trying to act at once.

In the large-scale tactical RTS I worked on, we focused on having robust data structures for querying the low-level representation in the high-level algorithms, for finding the neighbours of game entities. The low level update process acted on intents provided by the slow-updating high-level simulation, and in the end boiled down to a cheap particle simulation, scaling up well into the thousands.

share|improve this answer
    
+1. My thoughts exactly, particularly reducing logic down to managed groups that are only processed every few cycles, with all such groups potentially staggered for even processing. –  Nick Wiggill Jul 31 '11 at 21:29

as far as I can remember you'll always have less than 10,000 units a game. there is no game I can remember with more than that number, although empire earth could go up to 14000 trough a hack but no one will ever get to that point. so just having a static array of 10,000 objects seems to be more than needed.

as you know iterating over 10000 objects is no big deal but it may consume a lot of time if your algorithm run slower than O(n). for example if you try checking every two object for collision detection it will take O(n^2) time which means a lot of time. so you have to break your algorithms somehow. let's review a sample algorithm for every thing that I can think of right now:

  1. collision detection: for every collision detection algorithm you have to check every two objects but you can eliminate some checking starting the loops. as I suggested in the comments you can use same algorithm given for this question. there is no need to use multiple threads or anything, even with one thread and 4 regions you'll reduce your checkings from n*(n-1) to 4 * (n/4)*((n-1)/4), and by optimizing the number of regions you can get even better results. I think by using best number regions you can even get to O(n*log(n)).

  2. you have to generate path for each moving object. the usual system i've seen so far is a very simple thing: whenever player commands units to move somewhere computer calculates it's path, after that in every cycle if the object can move it moves if it can't it skips that cycle. there is nothing special. although you can also change the algorithms given here to reduce you path finding calls and have real time pathfinding for each group of units but that's really not needed.

  3. you have to check if some bullet or bomb or similar thing hits one of the units : you can use same regions you created for collision detection here.

  4. for selecting units you can also use same regions.

in general I would suggest using an static array (or a dynamic array with reserved size) of 10,000 or 20,000 at most. then use something around 10 or 15 loops each one iterating over all the units. that is a real big array containing all the units from all players. so each index have both data about unit owner and unit type. you cal also create some other arrays for each player. in each index of these secondary array you'll just have to store pointers to objects in main array.

if you have any other questions put comments to add them to my answer.

share|improve this answer
    
I remember having over 40,000 in Empires Dawn of the Modern World :). Shame the renderer could only keep around a 1000 on screen though before they started disappearing, but the rest of the game functioned well :). –  Daniel Aug 1 '11 at 5:15
    
@daniel :that't no big deal, generals didn't have any limitations on unit count. I was just giving some measure of good number of units to base my math calculations on. 40000 and 10000 are not very different from each other. –  Ali.S Aug 1 '11 at 17:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.