# How can I efficiently update only the entities that matter in a given frame?

I'm making a RTS, which can potentially have lots of units in one map (think Age of Empires).

I'm looking for a way to update my units. I want to avoid calling a virtual Update() method every frame on every entity. On the other hand, units that are not in view should still be updated and behave "normally."

I'm assuming this is a fairly standard question; what would be a way to handle this situation?

First, consider a design that avoids the need for a virtual update entirely. The overhead of dynamic dispatch is trivial, but non-zero. More importantly, however, the fact that one is necessary generally suggests that you may have poor cache coherency in the storage of your units. That is, you may have something like a vector<Unit *> which contains units of various concrete subtypes in effectively random order.

An approach where you store lists of concrete unit types and update each unit type in large blocks has better coherency, and avoids both the indirection needed for the dispatch and the dispatch itself. The outboard component entity architecture is particularly amenable to this.

Related, consider whether the type hierarchy for units makes sense: do you really need inheritance here, or can you instead compose the differences between units as data?

Second, use an appropriate spatial partitioning technique to determine which units are more important (for example, visible units are probably very important) and must have constant, immediate updates versus which units are far away and don't need as frequent updates.

Units with less priority can be updated less frequently, such as by subdividing them into N groups which are updated every N frames, effectively amortizing the cost of their update over multiple frames of update time.

There's no magic bullet: you basically need to make sure your updates are cheap (make sure you profile, so you know the updates are actually expensive, where they are expensive, and how to cheapen them) and that you do fewer of them (prioritizing the units that matter over ones that are less important).

You can amortize some things over multiple frames. I am sure Update (...) consists of multiple potentially independent tasks, that you could easily queue up.

Rather than completely deferring distant/unimportant unit processing and then having the unpleasant requirement of completing the entire update in the span of a single future frame, you could simply do half of their processing on one frame and the other half the next and only commit the end result when all sub-tasks are done. The net result is the same as if you only updated them once every other frame, but you will have less trouble meeting deadlines in some cases if you split the work that way.

I realize that     in this question is not so much about real-time computing :P But the whole thought process behind meeting deadlines is still useful... you can prioritize certain tasks such as position update so that they appear more responsive to the player. Even if a unit is not completely finished thinking, if it knows where it should be spatially before the next frame is drawn, go ahead and put the unit there.

You can vary the priority of each sub-task inside of your Update (...) according to distance, age, rank, or any number of different metrics. In fact, rather than calling an Update (...) function at all per-entity, you might consider a (priority) queue of tasks that need to be done. Your entities can add their tasks to this queue every time they need to think, and doing it this way makes distributing the workload across threads a lot easier.

The bottom line is that generally not everything needs to be finished every frame. If your requirement is that a unit has to completely update itself (complete every one of its update tasks) in the period of one frame, then that can create some awkward situations where framerates start to vary wildly even if you do only process 1/N-many units per-frame. If, instead, you prioritize certain aspects of unit updates you can do the important things more frequently and even tolerate situations where some update tasks take an unpredictable amount of time to complete.