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?
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.
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:
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(nlog(n)).
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.
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.
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.