# How do game engines mitigate CPU cost for many trigger zones & entities? [closed]

It's a rather simple question, but a somewhat fundamental in computing in general. Let's say we have a player controlled character in an open world. The world is large. In this game-world we have a vast amount of trigger zones that basically responsible for changing music, changing lighting, changing animation and so on. And the game clock runs at 60 fps.

In this situation we have so many subroutines which sensitive to "If a player has entered the area" that we can count then by thousands. Here's where I'm not sure. Since we have so many trigger subroutines it seems we can't just simply put them to check, if a player has entered the area, every 60th of a second even though this simple "listening" is not gonna take up a lot of resources; but scaling the world bigger and bigger will create a performance hit for sure, with this approach. So, there must be some other mechanism to manage all of those trigger zones. I inclined to think that the mechanism goes like this:

• a player's character subroutine constantly (at 60 fps) updates its position. With each update frame the playable character subroutine goes something like this: Hey, I'm at the position x(5.0),y(3.0),z(10.5) so what branch of code should I execute being at this position? And the respond comes from an indexed map where we have every possible coordinates and corresponding code to execute. (of course we can have a lossless compression going on for saving up the memory)

Am I correct? ...or does every subroutine listen for an input every update frame? (hope it's not :) )

Edit addition: I'm not asking if games divide their worlds into chunks, areas or grid cells for saving up memory, but asking about their approach on saving up CPU/GPU cycles and how unactivated triggers are treated.

• An SQL request and a bunch of events can take care of anything! :P And some routines don't need to be called every frame, such as AI. Jun 28 '15 at 0:53
• I think your edit indicates a strange incarnation of the XY problem. You started from the assumption that you have to run each of those checks every frame, so you asked how to save CPU while doing so. The real answer is: don't run all the checks. @Chris covers it with "only listen to events in this chunk". Jun 28 '15 at 18:10

Typical approaches to reduce processing are:

Spatial subdivision / coherence - Don't process everything in the whole world, instead only do so in pertinent regions - usually only those in close proximity to the player(s). - Group units close together as a single unit to reduce overall count (Rome: Total War). Common in real-time rendering fields.

Selective processing - Don't process every entity type for a particular effect. For example, maybe only magical objects need to be processed for particle emissions, only baddies need to be processed for collision detection against your forcefield, only non-flying units must be tested against pit trap triggers, etc. You will find that there are often discrete processing regimes for certain closely-releated types, this is why in many engines a type Particle is discrete from the more general type Entity... the only thing they share is transform information, outside of that Particle is an entirely different beast without collision physics, pathfinding, depth write during render, mesh animation etc.

Temporal discretization - Don't process every 60th of a second. Rather, do say 1 update in 4 frames, i.e. 15 updates a second (Age of Empires). This enables 4x more logic per update than you would have at 60fps. You can work this idea further by having triggers act say only once in those 15 updates, i.e. once a second. There is nothing that says you need to do all processing, every frame.

Outside of these things, it comes down to improving engineering through adaptation of game design / loosening design constraints. Oftentimes, you just don't need as much processing as you originally thought, and in those areas where you overrun capacity, you adapt your design to reduce complexity.

P.S. Conditionals tend to be costly because of branch mispredictions. Forward-running, linear loops don't in themselves suffer from the degree of branch mispredictions that arbitrary conditionals may suffer; and arbitrary conditionals may take (compiler-specific) hints to indicate which branch they are likely to take in most cases, though this only applies in certain, rarer logical cases. Most of the time you want to avoid deeply nested conditionals, and too many conditionals per se. This is where the above approaches come into play. Having said that, these days you also have multiple cores to work with.

One way to go is to split the whole world into chunks, and load just the chunk the player character is currently in (or any number of chunks that are closest). This way you only have to listen for events in this chunk. This does not mean you have to split everything into "levels". Minecraft is a fairly good example of splitting a giant world into chunks that are only loaded when necessary. All of the other data can be stored in files so you don't have to keep everything in memory.

• I believe that the main reason Minecraft divides the world into chunks is because procedurally generated nature of the world. Since the world is potentially "infinite" and the memory is not, so it has to offload some generated data and only keep what's relevant at the moment. Jun 27 '15 at 22:29
• @FloatingPoint Even games which are not procedurally generated tend to stream in level data in chunks - open world games most notably. Game levels have long been too big to fit entirely in memory with everything else going on, especially on consoles. Even within the loaded level chunks, games tend to use spatial datastructures like quad/oct/bsp- trees to be able to quickly query objects & triggers close to the player, and shift more distant objects to lower levels of detail, both in graphics and sometimes in their gameplay logic. Jun 27 '15 at 23:19
• Even if you disregard the part about only keeping one part of the world in memory at a time, the main take away from this good answer is that you don't check the triggers of the entire world each frame (or each time the player moves). You break the world up into sections (like say, a grid) and you only check against the triggers in the current grid cell. This is super fast if the grid cell itself has the list of triggers it contains, so you have only very short lists to check. Jun 28 '15 at 2:19
• Well, I didn't say "the only reason..." I said "the main reason...", about Minecraft. I know that games with big worlds do all sorts of techniques to ease on memory: LoD, tessellation, dynamic loading, screen-space detailing, etc... but I'm not really talking about memory issues, more of a CPU/GPU cycles issue. I understand that if we have a time trigger event, driven by a counter, for example a spike going in and out of a wall with 0.5Hz frequency, and the spike is in close proximity or in screen space, then yes, we have to evaluate every time when the counter's time is up. Jun 28 '15 at 8:10

As mentioned in one of the comments, you want to partition the world into sections by using oct/quad trees. Then as the player moves, using the tree you can quickly get all the nearest elements in your world. Only those closest to the player are the ones you have to react to.