How does an Engine like Source process entities?

Question

On the Source engine (and it's antecessor, goldsrc, quake's) the game objects are divided in two types, world and entities. The world is the map geometry and the entities are players, particles, sounds, scores, etc (for the Source Engine).

Every entity has a think function, which do all the logic for that entity.

So, if everything that needs to be processed comes from a base class with the think function, the game engine could store everything on a list and, on every frame, loop through it and call that function.

On a first look, this idea is reasonable, but it can take too much resources, if the game has a lot of entities..

So, how does a engine like Source take care (process, update, draw, etc) of the game objects?

Answer 1

Well, there's pretty much no other way to do it - you're going to have to loop through and call think() for every entity at least once every few frames.

You could put entities on their own thread, but then you have the whole state-synchronization nightmare, which is definitely not worth it.

On a first look, this idea is reasonable, but it can take too much resources, if the game has a lot of entities..

That is why the Source engine puts a hard limit to the number of entities which can exist at one time: 4096 entities, of which only half (2048) can be networked. Go over either of these limits, and the game will crash.

That is also why, when creating a map, they recommend you don't use more than about 800 entities.

Answer 2

These steps You mention are most likely done in separate engines. It is just that simple game engines usually have them in one pass. Your sequence

for each object
    do physics
    do game logic
    draw

becomes

call physics subsystem
call game logic subsystem
call drawing subsystem

Physics Engine takes care of positions and sizes.

Game Logic Engine takes care of interpreting what Physics Engine changed (he could obstruct some waypoints ...), what goals characters have and what behaviour they should be doing, he runs scheduled scripts (this think function).

Drawing Engine draws what objects are visible, and he knows what objects are visible because Quake engines kind of cheat here (see Draw section).

My advice to You is to rather study how simulations are done rather that game engines. There is a huge pop-culture relating game development and game engines are made in imperative languages (because of tradition&speed); so it was more enlightening to me to get good textbooks (rather theory) and THEN look at engines (practice) rather than look at engines and puzzle for hours how they did it.

Physics

Whole notion of iterate all entities and do {think, draw} will probably lead to problems. There will be conflicts and so on. I belive Valve have Havok and I guess Havok takes care of enough-correct physics.

Think

Think function is run when a time in a game equals time in nextthink. It works this way in Quake engine, and Quake engine is basis for Half Life engines. It is NOT run every time.

Internally it should be a simple iterating through a list of entities and checking if time has passed to call think function. Time complexity will be O(N), where N is number of entities.

If there is a very large number of entities You should measure how much it will improve the fps. Note, that because of Amdahl's law it is potentially invisible speedup. I mean, You just iterate trough all items and decrease&check one number.

I would speed it up by sorting entities by nextthink (create list of pointers to entities and sort it each time; not array of entities, because entities might change their nextthink anytime, so rearanging them in array takes O(N) instead of O(1) in list).

You should also look at O(1) scheduler in Linux.

Draw

Engine draws what is approximately visible from area at which is camera. Game level is partition into a tree, and a area is leaf of that tree. I won't bother You with details about it... So if an entity is visible it is put into a set of visible entities and they are drawn.

They store what areas are potentially visible areas. It is called "potentialy visible set", PVS for short. There is visualisation of PVS, green capsule is player and around him is rendered what his PVS contains.

Answer 3

So, if everything that needs to be processed comes from a base class with the think function, the game engine could store everything on a list and, on every frame, loop through it and call that function.

On a first look, this idea is reasonable, but it can take too much resources, if the game has a lot of entities..

Actually putting everything in one big list is usually less than desirable; if you were to group the entities in lists based on, for example, their type, you could better distribute the processing over multiple threads. For example if you know all entities of type Foo never interact with any other entities during the simulation phase, you can offload them entirely. If they were scattered willy-nilly throughout some big singular list this would be much harder to do.

You don't necessarily even need to be deriving everything from a common base class at that point; Source goes fairly overboard with inheritance abuse for what could otherwise be implemented as data in that respect.

You will of course always have an upper limit on the number of entities you can process per frame, even if you start offloading work to other cores. There's no way around that, you just need to have an idea of what that limit is in your implementation and takes steps to alleviate it (proper culling of processing phases on objects that won't need them, avoiding over-granularity in objects, et cetera).

Answer 4

What you have to take into account and this following the train of thought of previous answers is that your performance will also be on when and how you call these think functions.

Looking at the link you posted on the source engine you can also read that you can setup think times and different think contexts for each of your entities, besides the obvious hard limit that someone already pointed out, this will be the key to achieving greater performance with a higher number of entities, either by creating stepped updates that spread performance hungry processing through multiple frames of execution, or by culling out un-needed processing depending on the current context ( i.e. entities that are too far away or beyond player perception dont need the same level of "think detail" as characters that are close a player simply wont see a character 2 miles away picking his nose ).

And there are other more specific levels of optimization depending on your specific game logic and situation.