Comparison of Doom 1, Quake, and Doom 3 entity references system | Hacker News Reader

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

blog.noctua-software.com

140 pointsguillaumec16 comments

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.

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.

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.

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!

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...

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

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

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

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.

GC is the no-sweat solution :)

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

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.

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

Do you mean the games that push your hardware to the edge, like DOOM and Quake I-III at the time?

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.

You answered it yourself - speed.

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.

Can you share any of the used approaches?

Reply on news.ycombinator.com