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

Question

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!

---

(Additional information)

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

Answer 1

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.

Answer 2

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.

Answer 3

(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!)