At some point or another it seems every game dev must deal with the issue of entity processing. I'm writing my own C++ engine for a 2D game (please don't give me any advice of using an existing engine, as I've firmly made my decision) and I'd like to know what works well for this type of problem.

Namely, what data structures to use? Vectors are nice because they are dynamic and contiguous in memory. The downside however is that removing elements from the middle can be costly. And I expect entities to come into and out of existence frequently.

Perhaps a map or hashmap is more viable?

I should note that the kind of engine I'm developing should be very efficient. Think of games like Factorio.

The engine will load data in chucks, so to speak, and all loaded chunks will be processed each tick. This is nice because I need not process entities in a specific order or priority. Speed alone is simply the name of the game. I fully intend on using multithreading to accomplish this at some point. The typical user's PC shouldn't stutter for example when being zerg-rushed by hundreds of enemies.

Should each chunk contain a list of its own entities, or should the entities be managed globally in one big container? These are the questions I must find an answer to before pressing forward.

Greg4581 said:
Namely, what data structures to use?

It depends to a great extent on your use case. Is this a container you're going to be mainly iterating through repeatedly? Or that exists to hold info for infrequent use? Do you need random access? How often will you iterate vs remove? Do you have an upper-bound on container size? If cache misses are important, contiguous containers are a good starting point. If Big-O is important then hashmaps are a good start.

You will want to ask these questions per-container instance. There is no “best way to process entities," no “I win the performance game” button you can push that covers every possible use case, which is what I took your post as implicitly seeking. There may be a “best way to process these entities," where “these entities” are some specific thing like conveyer belts in Factorio - if you're aiming for perf I can just about guarantee you will have many different “entity” types, because trying to stuff everything in one framework will lead you into inefficiencies. Just because one entity type has a particular access pattern doesn't mean all of them will. Same goes for insert/remove patterns and so on.

tl;dr It depends.

Greg4581 said:
The downside however is that removing elements from the middle can be costly

For truly contiguous containers like vectors, that depends on when you remove it. If you're calling vector::erase (= shuffle all elements above the element to be removed down one slot) on every element when you do it, then yeah that's going to be slow, because if you're going to remove multiple elements you're in a situation bounded by O(n^2). But if you can contrive a situation in which you'd want to remove multiple elements at a particular time and you don't know which elements specifically(eg. “cull all entities whose health is below zero”), then there exists an O(n) algorithm to remove multiple elements at once, which can be done with the C++ standard library algorithms - it's called the “erase-remove” idiom. You can find the documentation for the algorithm part here: https://en.cppreference.com/w/cpp/algorithm/remove.​ The gist of how it works is that the find and erase “shuffle” operations are combined - for each element if we get to an element that is to be removed, we search for the next element that isn't to be removed after it in the container and move that one into the slot where the removed element is.

If the perf hit of iterating a sparse array is acceptable, you could use a “slot map” or “colony” data structure, which is sometimes used to implement a memory pool - essentially a vector, but when you remove an element you instead mark its index as free (and there are multiple ways to do that, each with their own tradeoffs…). Your iterator type would skip the free slots internally and the next time an element is allocated, it would go into the first free slot.

Greg4581 said:
I should note that the kind of engine I'm developing should be very efficient.

Everyone wants their engine to be efficient. That's not a directly actionable design goal, it's more a “value statement.”

Greg4581 said:
Think of games like Factorio.

This is much more helpful spec-wise. Never played Factorio, but I've seen enough of it that this tells me you want large collections of simple things that can interact with each other in specific ways and those interactions are player-controlled.

Greg4581 said:
This is nice because I need not process entities in a specific order or priority. Speed alone is simply the name of the game.

If speed is what you want, then processing entities in a specific order or priority IS what you likely will end up wanting. There will likely come a point where you exceed your frame time budget and start wanting to time-slice behaviours where you can, for example. If you support taking two objects in the world and having a parent-child relationship between them (as in a scene graph), that tends to require a particular order of operations that may vary between specific thing being updated (eg. you'll want to update the parent transform by the child, but maybe tick child physics before parent…). Totally unordered updates have their place, but I would not expect to be able to use them for everything and the likelihood that you start needing to sort entities for perf goes up the more complex your game gets. In fact, your “chunking” idea IS an example of processing entities in a specific priority order.

It's hard to give more specific advice without knowing the precise details of your game and the data we are dealing with, but without that knowledge my gut says you're making some unwarranted assumptions here. Including the notion that all games have “entities” in the sense I'm reading you as meaning. ?

@Oberon_Command

Thank you for your thorough response. I guess it was a bit naïve of me to think there was a “perfect algorithm" out there that could handle all my needs before having specific goals fleshed out.

For example, I haven't considered what do to if and when the hardware becomes overloaded by entities. I might have to implement throttling measures. There will always be players who try to break the game by doing things 99% of players probably wouldn't even consider.

Also by entities I simply mean discrete objects that exist in the game's memory. In my game, some entities will be simple tiles which don't move, but may have animated sprites like for water. Other entities will be dynamic and able to move and interact with things on their own.

Greg4581 said:
Also by entities I simply mean discrete objects that exist in the game's memory. In my game, some entities will be simple tiles which don't move, but may have animated sprites like for water. Other entities will be dynamic and able to move and interact with things on their own.

If your main concern is iteration perf, you're likely going to end up wanting to put each of those in their own container, or move towards the relational model of data (rather than “objects”) and extract the parts of them that are different to their own containers. Repeatedly revisiting this as you add features is likely going to take a lot of developer time, though, which is why most games (or programs in general) don't really aim to be perfectly optimal, but “good enough to ship.” Shipping and getting sales is more important than being optimal in a capitalist video game industry.

I also forgot to mention that there is an advantage to the containers not needing to be ordered or have pointer/index stability, and that's that there is actually an O(1) removal algorithm - the “swap and pop.” The idea there is that removing the last element from the end of the vector (popping) is O(1), and swapping two elements is also O(1), so if you want to remove an item you can swap that item and the last element and then remove the new last element, which has now become the element you were going to remove in the first place. If you do that repeatedly of course it becomes O(number of removals), though, and if your vector is large enough the two elements won't be in the same cache line, so erase-remove is still the algorithm I would reach for when I have that search and remove need.

Of course none of that matters very much if your vectors aren't very large. Small vectors can outperform small hash maps due to the lack of time spent hashing and potentially fewer cache misses.

Greg4581 said:
I guess it was a bit naïve of me to think there was a “perfect algorithm

If such a thing existed, everybody would use it, and it would be the defacto-go-to solution, wouldn't it? Since that is not the case, most likely your assumption is incorrect.

Not much experience with game engine internals, but I would say, be flexible. Create an interface for this processing, and then pick any solution until it fails to work. At that point build a better implementation against the interface. Repeat that until your game(s) run perfectly.

That simplifies the problem to a well-designed interface, and pushes proper implementation further back until the point where you actually have a problem that you can analyze and fight with an improved design.

^^^^ All of that.

As a simple and easy rule, if you have no guidance otherwise (and there usually is guidance of some sort) then a standard vector is a good default choice. It's usually easy enough to swap out if needed later on. If you are writing code, need a container, and just need to type something in to make it work as a first draft, std::vector<> is typically adequate for the first draft.

When you do have additional guidance, use it. You've got five sequential containers, four ordered associative containers, four unordered associative containers, each with useful properties. If you know you're going to need it, use it.

And sometimes you'll need containers that don't fit well with any of the built in containers, there are libraries with high quality pre-built containers there too, focused around topics like lockless functionality and parallel processing, fixed sizes like ring buffers and memory pools, memory and access constraints like working from slow storage or out-of-memory indexes, containers taking advantage of hardware-specific and OS-specific functionality, and much more. And if even THOSE don't work for some reason --- and occasionally you'll encounter reasons --- there are volumes of algorithms and data structure books that cover additional specialty containers you can implement yourself.