Comparison of Doom 1, Quake, and Doom 3 entity references system

http://blog.noctua-software.com/entity-references.html

by guillaumec • 11 years ago

140 16 11 years ago

It would be cool if you gave the actual code snippets where the routine happens rather than just a summary. Not that I don't appreciate the explanation--I'd just like to see how it's actually done, if only because Carmack's code is always interesting to read.

kleer001• 11 years ago

Super fun! I wish all abstract computing topics could be shoe horned into a convenient model like a familiar video game. So easy to grok!

ajuc2• 11 years ago

From my (limited) experience - using indexes instead of pointers has additional advantage - it makes it super easy to serialize/deserialize arbitrary graphs of objects.

Save game if you use index for referencing objects = one fwrite call.

Save game if you use pointers = a lot of pain.

perdunov3• 11 years ago

Pointers can be easily mapped from and into integer indices or file offsets in-place, so there is no big difference really.

I think it is generally not a good idea when in-memory representation of objects is identical to the serialized representation. This approach tends to backfire in a number of ways, such as format incompatibility between software versions, or hardware architecture differences, so it is always better to assume that your serialized representation will be different from in-memory representation.

TwoBit• 11 years ago

These solutions are fine for old and simple games, but don't scale as solutions to large scale games.

Source: I've worked on such games.

mkesper• 11 years ago

Can you share any of the used approaches?

M8• 11 years ago

Modern approach: http://en.wikipedia.org/wiki/Entity_component_system

One of the proponents: http://t-machine.org

lentil_soup• 11 years ago

How would a component based system solve the problem of removing the entities (or components in this case)?

ivanmilles• 11 years ago

This echoes the tribulations of the original Starcraft devs. [1]

...based on my experiences the biggest problems in StarCraft related to the use of doubly-linked linked lists. Linked lists were used extensively in the engine to track units with shared behavior. [...] Some of the link fields were shared among several lists, so it was necessary to know exactly which list an object was linked into in order to safely unlink. And some link fields were even stored in C unions with other data types to keep memory utilization to a minimum. So the game would blow up all the time. All the time.

Serialising game state to disk was done by moving all those scattered objects into a contiguous memory block, re-link, save to disk, and then restore the game engine's internal state.

It was necessary to fixup all the link pointers (taking special care of unioned pointer fields) so that all 1600 units could be written at once. And then unfixup the link pointers to keep playing. Yuck.

[1] http://www.codeofhonor.com/blog/tough-times-on-the-road-to-s...

weeber• 11 years ago

Is C++ shared pointers the solution?

Adding a dead boolean field, then all the entities with links removes their pointers when possible by looking at the dead field, at the end the object is freed.

ajuc2• 11 years ago

GC is the no-sweat solution :)

But it's considered too slow (or too unpredictable) for games.

perdunov3• 11 years ago

I think it's quite easy to build a GC-like system for a particular subsystem of the engine.

The only nuisance is the lack of reflection in C++, as usual.

fulafel• 11 years ago

Yet most games are written in GC languages (flash, java on android, objc+arc on ios, javascript, C# on unity).

axilmar• 11 years ago

Why a shared_ptr/weak_ptr solution wouldn't work?

The main entity list would use shared ptrs, while objects themselves would have weak references to other objects.

When an object wants to use another object, then it has to create a shared_ptr to it.

It might be a little slower than simple integer ids, but it can save a lot of trouble.

TheLoneWolfling• 11 years ago

You answered it yourself - speed.

Comparison of Doom 1, Quake, and Doom 3 entity references system

Related Stories