Multiple data structures containing the same references

Question

I was wondering what the best practice is for creating multiple different data structure which can all contain references to the same objects. As an example, consider a video game with many entities.

For iterating through the entities, one would probably want to use an array or list of entities so that they can be located in contiguous memory blocks and iterated through quickly. For doing physics updates however, you would want those same entities stored in a tree structure or multidimensional array corresponding to their positions (so that you get O(n) scaling for collisions rather than O(n^2).

I'm wondering what the best way to control access to those data structures is such that deleting an entity removes it from both structures. You could add to/remove from the structures only through an auxiliary method/class, but this feels kinda hacky and doesn't prevent someone from just deleting the object from somewhere else. You could store a reference to the containg data structures in the objects and then invoke their removal in the destructor.

Anyone know a particularly good way of doing this?

Answer 1

Managing removal through a central function that also removes the references from related indices is the way to go, despite your concerns:

You could add to/remove from the structures only through an auxiliary method/class, but this feels kinda hacky and doesn't prevent someone from just deleting the object from somewhere else.

If you are working in a garbage-collected language, the object won't be removed while references are active. At least one reference is the contiguous memory block. So you have to remove references explicitly anyway. Using a central function makes this easier. (Of course, most GC languages don't allow you to use contiguous memory blocks at all.)

If you are working in another language like C or C++, then only the the owner of that object should free/delete the object. The function to remove an object and its references should be part of the owner. Here, the owner will be the code that manages the contiguous memory block. If other code frees the object directly that is simply a bug (which you may be able to detect with a memory debugger like Valgrind).

Especially for C++ there are many concepts that might be helpful, such as custom deleters for std::unique_ptr, placement-new, custom allocators, overloaded delete operators, and so on. This allows you to create abstractions that are difficult to misuse, and can help clean up unneeded resources via RAII.

Answer 2

Edit: Second attempt at this answer as I realized I was getting carried away in microscopic details. I'll try to simplify here.

Observer Pattern/Event Queue

So among the most straightforward solutions to this problem is to use something like Observer or some kind of centralized event queue. Your collision detection system can then either be called immediately in an indirect way as an observer of the subject (your game scene) or it can be handed a set of events that occurred indirectly/abstractly from the central system and then discover what happened to the scene (ex: element being inserted/removed). Then you can respond by updating your spatial index accordingly.

However, I have grown a strong distaste for these types of solutions over the years in large projects because, in the unfortunate case that you have to debug something that goes wrong during an event/observer notification, I find that can turn into a nightmarish scenario where I feel like I'm being bounced around like I'm in a pinball machine all over the codebase trying to figure out what went wrong.

Of course I still use these solutions here and there, but try not to lean on them too much. In particular I try to avoid like a recursive scenario where one event emits one or more additional events, or where one observer gets notified only to do something which causes another subject (or worse, same one) to then notify more observers.

"Diffs"

So the main alternative I prefer nowadays is to, instead of either of these solutions, use some kind of data structure which allows you to find like a "changeset" or "delta/diff" of sorts in hindsight.

The data structure is fairly lightweight to copy around and keeps track of the info needed so that you can compare a new version of itself with an old version like new_version.diff(old_version) and it'll tell you everything you need to know as to what happened between the time you stored the old version of it and the time you received the new one, like what elements have been inserted/removed to/from the scene. That's a bit vague as to how you design this data structure but it can vary wildly based on your needs, but the general idea is like this and you can tackle it in many ways.

And I actually started using this solution as a practical requirement. In my case I no longer have one central instance of a scene. I have all sorts of threads/systems running in parallel all storing their own local copy of a scene and generating new modified versions which then get output to some other systems (ex: renderer) which then store their own copy and run in parallel and so forth. So there is no central scene instance in my case anymore which makes any kind of central Observer/event queue impractical if not outright impossible, and this sort of "diffs" solution seemed the most practical way to solve the problem. And in my case that "diffs" kind of functionality is part of the scene itself (new_scene.diff(old_scene)) which then tells me relevant info like what entities have been inserted/removed from the previous copy of the scene I had, and the scene itself an immutable persistent data structure.

Yet after doing that, I've found it so much easier since there's no longer a need to have all this communication between objects/systems/threads to tell each other, directly or indirectly, what has happened to the previous state. Your objects/systems/threads can just look at the new state (game scene) and discover, at their own leisure, in their own processing thread, what happened and make the necessary updates to whatever structures in response (ex: spatial index).

Now typically what I'm recommending is not a list of events that occurred, though that might seem the most straightforward way to keep track of what has happened between new version and old. It's not very practical to compare an entire growing list of things that happened to each other to figure out changes that way, and even if you mitigate the infinite desire for growth by storing some additional data like a "cache point", that's starting to get a bit unwieldy still. What I do in my case is start with a bitset data structure which keeps track of what entities occupy what indices. Comparing old bitset to new using rapid set operations then immediately tells you what entities no longer occupy former indices and what entities now occupy new ones not formerly occupied. But of course that doesn't tell you if some entity was removed and a new one was inserted to occupy its former index, for example, so I also use some change counters and things like that on top of the set operations to quickly drill down and discover what elements have been removed/inserted/modified. That's a basic example and my real-world ones get a lot more nuanced, but should give you a start as to one way you might implement this.