Hi! I'm currently working on a classic RTS game (like Starcraft or Age of Empires) as a school project. Entities are currently stored in a simple list, but because of performance problems, I am going to change that to use two collections: a spatially optimized collection and a per-faction collection. One of the problems I'm facing is how these collections can be modified during the run loop, as those two collections are very likely to be iterated over while changes are made to the collection. Those changes can be triggered by a few events: - Entity movements (spatial collection must be updated) - Entity creation (entity must be added to the collections) - Entity death (entity must be removed from the collections) I can think of a few ways to handle the problem, but none of them seem great: - Allow iteration of the collections, but defer all modifications to the end of the frame. - Have all queries copying their results in a temporary buffer, so the master collection can be modified at all times without problems. - Allow iteration of the collections and their modification, and hope nothing bad happens How is this problem usually handled in games? Thanks for any help!

Are you multi-threading?

If not, you shouldn't have anything to worry about.

If you haven't, I would first make certain that the performance problem lies where you think it does, by profiling, before you embark on any major changes.

My first question would be - how are you generating the spatially optimized collection? Are you using spatial partitioning, like a quad-tree? If so, storing unit pointers or unique unit ID numbers in quad tree leaf nodes will likely be sufficient. If you want to be able to quickly move objects around in the quad tree, you could have a map of unit IDs (I don't recommend pointers in this case) to quad tree nodes. This map would need to be updated every time you add, remove, or move a unit to another quad-tree node. Basically, you'd just need a way to map a spatial node to a unit, and a unit to a spatial node.

Unless you're running multiple concurrent threads operating on these collections, I don't think keeping the two collections in sync will pose much of a problem. The only time you need to be certain to keep them synced is when you add/remove units (e.g. when you add a unit, add it to the faction collection and insert it into your spatial partition collection, and when you remove a unit, remove it from both collections). A unit moving in your spatial collection should have no impact on the faction collection.

To answer your last question, I think this problem is handled however the programmer feels it should be handled; there's no one-size-fits all solution. Again, a lot of this depends on what exactly your spatially optimized collection is.

@Michel_Carroll
I am not multithreading (not in the game logic anyways), but I still think problem can occur. Maybe I wasn't too clear, let me give you an example. To update the units in the game, do a simple loop like:



If one of the unit is being attacked and dies in this update step, the World.Units collection has to be updated to remove the reference to that unit. However that collection cannot be changed as the foreach loop is still iterating over it.

The same problem goes with code like:


@extralongpants
I have already profiled the code to find that a lot of time is spent iterating over my non-spatially optimized unit collection to find nearby units. A spatial collection will be needed and that's what I'm trying to plan ahead. The problem here is more a design problem than a performance problem.

The spatial partitionning I was planning to use, as it seems simple enough, is simply dividing the map into let's say 10x10 "zones", each of which containing a list of units in that area.

I don't think that keeping the two collections in sync will be a problem either. Good encapsulation should take care of it. The problem I'm trying to prevent is to have code that is iterating over a collection to update something which ultimately causes a modification of the collection that is being iterated over.


Thanks for your input on the problem, its food for thought for sure, but I'm still looking for a solution to my iteration/modification problem.

@Gage64
Interesting, I knew about the overwrite+pop way of removing elements from a list but hadn't thought it could be used as a way to safely remove elements from a list being iterated over. The only problem is that this technique is only valid for lists, it wouldn't work on a more complex spatial partitionning collection.

@b3rs3rk
This is the method I'm planning to use unless someone comes up with a better idea. As Gage64 noted, the Remove calls are far from ideal from a performance point of view (RemoveAll is not really better), but if I store the indices of the objects to be removed, and then remove them from the last one to the first one by overwrite+popping them, it should work well.

The approach can be used in spatial partitionning collections, deferring the changes until the end of the frame. The only thing I was worrying about is using outdated position data for the end of the frame, but I guess it's really not so much of a problem.

So that's the way I think I'll do it. Thanks for your help so far, any other tips are still appreciated if there's a better way to go.