# Optimizing updating thousands of enemies? (Or break up the enemies that need updated?)

Thanks in advance for wanting to help.

I have an array of (right now) ~1000 enemies that I need to update every frame. The issue, I believe, is mainly brute-force checks. I've profiled my application with dotTrace, and there are no lines of code that are inherently slow (the method itself is slow, though). This leads me to believe that it's simply the number of operations performed that's my bottleneck.

I can already picture the comments of "why do you need to update that many objects!", so I'll answer that first.

I'm using GLEED2D (amazing level editor, by the way) to create my "maze" of enemies. This is a top-down shooter level, so these enemies are then loaded into my game, and I move them downward each frame. Picture a giant sheet that I move downward every frame, and you have the basic idea.

Now, I have to (currently) update every enemy with it's velocity, to keep it in sync with all of the other enemies.

This takes a long time, even on the PC, eventually starting to lag.

I'm asking for some help in thinking this problem through, or in designing a solution if you're generous. I thought I could possibly do a chunk-based solution, where I throw enemies into arrays that contain bite-sized chunks, but then I'm back to trying to update them correctly. This would mean I'd have to move the chunk, or keep track of the chunk's offset (if it were moving) and apply them later.

I can't see that as the best solution. Not to mention that this is a seamless level, so the chunk calculations would have to match perfectly. However, if it sounds good, I would still require some help in figuring out how to split up and update chunks.

I've thought about this problem for days now, and nothing I've tried has worked. Ideally, this will be a solution that can handle more than my current amount of enemies (which was why I thought the chunk-based solution might work).

Any suggestions or ideas?

Thanks!

The enemies are mainly just having a velocity applied to them. Strictly Vector2 += Vector2.

• What are they being updated for? Movement? Animation? Path-finding? Would it make sense to only update those enemies around the player? – MichaelHouse Apr 20 '12 at 23:39
• Sorry, I neglected to say what I was updating. I edited my original question. And, no, just around the player won't work. I don't actually have a camera or anything, I just fake it by moving the enemies (that are offscreen) downward towards the player. – electroflame Apr 20 '12 at 23:44
• Do you have any kind of scripting system, with timers or something like that? Then you could just script your way out of it, this way you only need to have each "wave" of enemies in memory, and then spawn them as each "wave" is cleared. – William Mariager Apr 21 '12 at 2:59
• @William Not truly scripting for these enemies, no. That's why I'm using a visual level editor. I had thought about that, too, but for my purposes (creating a maze the user has to navigate through) I could only spawn the next line, which would probably not help my performance enough. (And the work required to do so would be about the same as creating the chunk method) Thanks, though! – electroflame Apr 21 '12 at 3:29
• Re your meta-question: Yes, you should post your answer as an answer. You can always give credit, and accept a different answer. – Kevin Reid Apr 23 '12 at 12:56

You mention this is a "top-down shooter" and that the enemies are all moving downward simultaneously. If you mean the kind of game where the player flies past/shoots down lots of enemies as they scroll by, then...

Don't move the enemies! Instead, move the player and the camera. (You mention in comments you don't have a camera — so fix that problem. It will be far more efficient than updating many enemies, and simpler than a scene graph.) Then, there is no need to update every enemy every frame, unless it's on-screen and therefore having visible behavior.

An even more refined method which you can use if this is a strictly fixed-scrolling game is to not actually have all the enemy objects instantiated at once — create them at the top of the visible screen at designated time points. Keep a data structure that's basically a script for creating enemies at designated times. Given fixed scrolling, this works out to be exactly the same thing as having the enemies at designated not-yet-on-screen positions (kind of like how a waveform can be seen in either space or time). The advantage of this method is that you do not need to keep around all the information about idle offscreen enemies — just when they go onscreen.

• That is the ideal method, yes, but I didn't want to rewrite my code, as I have a pretty strict time-limit. Most of the level is created this way (and I know better now) but it's too far along to switch to an entirely new method. This isn't for a whole game, or else I would change it. It's for a one-off special level. Thanks anyway, though. – electroflame Apr 21 '12 at 1:11
• This is obviously correct. When you scroll the world, you don't change the world-coordinates, you change the view! – MarkR Apr 22 '12 at 7:50
• @MarkR As I said, this is the correct way. However, I hadn't created a camera when I started this one-off level (totally different than the game) so I was too far along to change it. I apologize for the confusion, and I should have clarified in my question that this was more of a matter of retrofitting a solution to fit my existing codebase for the level. – electroflame Apr 23 '12 at 1:13

If you can organize the enemies into chunks then what you may be looking for is a scene graph.

You would make each enemy in your chunk a child of that chunk which would also have a position, orientation and scale. Each enemy would then, in turn, inherit the values of the parent, but can still be moved separately when necessary.

I would tend to make a SceneNode interface. Then anything can be a SceneNode, even the enemies themselves.

I might use an interface for scene nodes like the following;

public interface SceneNode
{
Vector3 Position, Orientation, Scale;
Vector3 finalPosition, finalOrientation, finalScale;
void Update(float ElapsedTimeInMilliseconds);
SceneNode Parent;
List<SceneNode> Children;
}


The final... values are the values after adding on the values for the parent final... So these values would propagate down the tree, although you'd make them read only. So the get for finalPosition might be; return Parent.finalPosition + Position;

Then you simply have to change the parent object and all of it's children will be changed as well.

• I haven't worked with a scene graph before, but I will do some research. I don't currently know (a) what it is or (b) how to make one, but I'll look into it. – electroflame Apr 20 '12 at 23:56
• The example code you provided helped me understand it a bit better; thank you. However, my question now is how do I successfully update each enemy in the chunk, without the same overhead I have now? Is there some way to update all the enemies without a loop, or am I missing something obvious? – electroflame Apr 21 '12 at 0:04
• I added some sample code to make it a bit clearer. You could try making your enemies implement it and play around with it a bit. If you are planning to make this usable by the outside world then you will want to change the access modifiers on the properties to make it safer. – OriginalDaemon Apr 21 '12 at 0:06
• When your using the scene graph you only need to update the parent object. So say five enemies are part of an object called platoon, you only need to update the platoon. Your enemies will be a fixed offset to the platoon. When you need their individual positions, for rendering for example, you just need to get the finalPosition. – OriginalDaemon Apr 21 '12 at 0:09
• Alright, that makes more sense. So then, when the parent moves, I just need to recalculate the offset of each object from the parent position? – electroflame Apr 21 '12 at 0:11

## (My final chunk-based approach)

I used a combination of things. Much like the Scene-Graph suggested by OriginalDaemon, I divide my enemy array into "Chunks". I created rectangles in the editor, and imported them as a pre-defined array of "Chunk Boundaries".

From this, I take my giant array of enemies, and run through it at build time to place the enemies into the "Chunks" in which they fit (Checking if their position is a point in the "Chunk Boundary" rectangle).

Then, at runtime, I only update each "Chunk Boundary"'s position. Then, when the last "active" chunk that's having it's enemies updated passes a certain point, I activate the next chunk "behind" it, thus letting the enemies in that chunk be drawn and updated.

Then, when an active chunk passes off-screen, I deactivate it, stopping the drawing and updating of all enemies within the chunk.

I would like to thank all the people who responded, answered or inquired about the problem, as you were all instrumental in pushing me in the correct direction. (Massive props to OriginalDaemon!)