How is the data being kept in a more or less professional game. You have units, particles, buildings, map features like trees, rocks, etc. Where does all that go? Linked lists?

I'm using c++ arrays to hold data in my project.

My guess is that storage of data depends on their access patterns.

If you have data that is always accessed sequentially, you use a list. If you have data that is accessed by position, you may want to store it spatially, eg with an octet tree.

There are also possibly differences due to stability of the data. Eg rocks typically don't move or disappear during the entire game, so you can optimize its access offline. Units on the other hand are mostly moving around all the time. Also you get new units every now and then or existing ones die. For such data you need something that is quick to update/change.

EDIT: On the other hand, don't assume there will be a problem and optimize, before confirming there is actually a problem that needs to be fixed. It is easy to fall in the trap of prematurely trying to improve performance and then afterwards find there was no need for that at all.

Yup, they depend on access patterns and lifetime patterns.

There's metadata about the objects that gets loaded initially, usually into large arrays, and pointers to those are placed in lookup tables for faster searching. That data is persistent for the duration of the game and there's really no reason not to have it as a block of tight, flat memory.

The active simulation is often a bunch of trees of pointers. Depending on details you may want strong or weak smart pointers there depending on how ownership and lifetime is configured, the objects themselves either live in stable collections or dynamically managed as regions of the world load and unload. A stable array of trees is another common pattern.

The simulation references instances of metadata, which in turn refer to the rendering details among their various systems. The textures and meshes for the units, buildings, trees, and rocks are usually smart pointers to proxy objects, and those proxy objects need a stable place to live. Often they can live in pools that are allocated in memory pages like a deque, other times lists for the stability. The actual textures and meshes get loaded and unloaded all the time mostly into video memory, so those allocations come and go. The games simulation itself doesn't care if a mesh is loaded at any particular LOD or billboard, or even if it is completely culled or unloaded, so they're pointers to the hidden internal implementation. It is similar with physics data and audio data.

References between objects are often best as smart pointers unless you have additional knowledge about the lifetime of the system, with memory for the objects in the smart pointers managed in place through memory pools and fancier containers as far as it makes sense for the designs.

And if you're using a a major engine, they do virtually all the work for you behind the scenes.

eg with an octet tree.

Isn't the data you store in the pyramid duplicate data? If it's units or trees on the map or something else you still need to keep the data into a list for other purposes.

There's metadata about the objects that gets loaded initially, usually into large arrays, and pointers to those are placed in lookup tables for faster searching.

I understand

Typically you want to be as close to an array as possible. For particles usually you explode or have something like continuous smoke. These will be in an array and as the particle is no longer alive, you just mark it as such and skip of it when looping. For something like smoke, when a new smoke particle comes alive, you can insert it into a dead particle spot. This way your array stays packed.
All particles likely exist in one bigger memory allocation (array of void*/char*). You call char* newParticleBuffer[100000]; Then you push a smoke particle or explosion into gaps in that memory. This all gets maintained by you or some other programmer to create and remove objects within this same 100000 byte allocation.

“I'm using c++ arrays to hold data in my project.”

You can. It just depends. For my first 3 years of programming I stored all my data within arrays in my c++ files. This included the 3D models as well. They were embedded in my program. But isn't super flexible.

dpadam450 said:
Typically you want to be as close to an array as possible.

Details always matter. What you wrote about particle systems is true, in that scenario you want a blocks of memory laid out in continuous strips to help the system cache, but even then it's not always easy. There are still choices about exactly how you lay details out in memory, as often it's more efficient to work with a structure of arrays rather than an array of structures.

For example:

positions.x[i] = positions.x[i] + velocities.x[i] * elapsed;
positions.y[i] = positions.y[i] + velocities.y[i] * elapsed;
positions.z[i] = positions.z[i] + velocities.z[i] * elapsed;

vs

particles[i].pos.x = particles[i].pos.x + particles[i].vel.x * elapsed;
particles[i].pos.y = particles[i].pos.y + particles[i].vel.y * elapsed;
particles[i].pos.z = particles[i].pos.z + particles[i].vel.z * elapsed;

Or even better working those out with SIMD intrinsics for the graphics cards or processor. Parallel instructions like like mm256_add_ps(), mm256_mul_ps() or mm256_fmadd_ps() can help you if the layout is correct.

Other times it isn't array layout that you want, it's the stability that is preferred regardless of the ultimate location, where structures like hash maps give the biggest improvement.

Calin said:
Isn't the data you store in the pyramid duplicate data? If it's units or trees on the map or something else you still need to keep the data into a list for other purposes.

An octet tree is designed to quickly find an object from its position. You can store all its data in the tree as well of course, and if you only need the object from its position that is optimal, but it is not required. As frob said, you can use (smart or unique) pointers, or proxy objects if you need the data at several places.

For example, if you have the data of the objects in a list, you can store their indices in the octet tree. That is one form of a proxy object or smart pointers. Where to store the position of the object is then a next question. Inside the tree is optimal for speed, together with the other data of the object may be more convenient for some cases.

You constantly get these kind of decisions, where you get a trade-off between a desirable property like performance against a undesirable properties like lots of de-references through eg an index to look up information, or needing to duplicate information, or getting more convoluted ways to obtain the information. There is never a solution that only has advantages, unfortunately.

Alberth: I think I understand what you're saying, thank you.

I just noticed the thread title should have been “holding the data”

frob said:
Details always matter.

Think you brought advanced knowledge to a beginners question. All entries in a hash map are still optimal if stored within an array. A hash map is a search algorithm. An array is a memory block. An array is not an algorithm. Details matter for sure, which is why I said the word typically.