Data structure for storing / looking up type objects representing different item types

Question

I'm still learning C++ and am no way an expert so I could be conceptualizing this wrong.

I'm having trouble getting the right data structure for items in my game. I don't need actual object instance data (x, y, z locations etc. There's an "item" object that just gets filled with the data from the item table when an instance is created)

The type of system I want is similar to Bethesda's creation engine, where I could basically start an array from 0 and increment it as an item is added to the game. Then I could just make each item in the array a struct holding all the item's variables. The reason I'm doing it this way is it makes it simple to get an item variable: item[56].size returns that item's size variable. (Meaning its gameplay dimensions, not its memory footprint)

The issue I'm having is different types of items require different variables. So for weapons there would need to be a damage variable that wouldn't exist for say a healing potion, or a gun requires different variables than a chair. So my current solution is to have many different arrays of structs, each array containing its own struct base that has only the relevant variables for that type. This leads to an unconnected series of arrays that get called like item_weapon[22].damage. I can't do a multi-dimensional array because it requires each type to have the same amount of items which they won't.

It'd be more ideal to just have 1 unified data structure holding all the items' data. (I would think, I'm still new to programming). So my idea would be to use an enum to increment the different types, then each enum holds an array of all the items of that type and each item in the arrays is a struct that only has variables similar to those in the same enum number. However my instinct is that doing this would still require each array to be the same length, but I'm not sure.

I can't find much on enum of arrays of structs. Is there a better solution? Is this maybe too complicated or not a good idea? Any help would be appreciated!

Answer 1

Disclaimer: I'm not fluent in C++ myself, so I'm going to describe high-level strategies, but I'd welcome edits or alternative answers from C++ experts regarding exact implementation considerations and syntax.

---

If your item types are similar in total memory footprint, you might want to try making your array of item type data hold entries of type std::variant<Weapon, Potion, etc...>, which is effectively a type-safe tagged union of multiple types.

It has a memory footprint equal to the largest of its constituent types, plus an index to identify which type it's storing currently, plus padding for alignment if necessary. So it's not such a great choice if some items need 100 variables but most others need 0 — you end up leaving "empty slots" for those extra variables in every array index that's storing a smaller item type. But if you have fewer than a thousand item types or the biggest item type is still smaller than a kilobyte then even that might be an acceptable trade-off for the simplicity and convenience it offers.

---

If you require dense storage (because you have many thousands of item types, or some item types need megabytes of memory, or you're targeting a very memory-constrained environment like a retro console, or these items are iterated in a hot path where using full cache lines is critical to performance), then like many things in programming, it can be solved by adding another layer of indirection.

Each entry in the item types array stores a pair of two values: an enum value identifying the item's "meta-type" (eg. Weapon, Potion...), and an index identifying the item type's position in a separate array specific to that meta-type. It can also store any variables that are common to all item meta-types (eg. localized name, icon, sale value, quest item flags, weight), or those can be stored in parallel array(s) for an SoA approach.

To look up the weapon damage value of "BroadSword" = item type #56, you confirm/assert that itemTypes[56].metaTypeId == Weapon, then look up WeaponTypes[itemTypes[56].subIndex] to get the WeaponTypeData associated with that type. This allows you to have densely packed arrays of each meta-type, of potentially different lengths, while still addressing them all uniquely from one primary item type enumeration as a lookup key.

This indirection has a cost, but a modest one. Because you have dense storage, non-random access patterns (you'll likely hit the weapon and armour tables repeatedly when evaluating combat, without needing to load the gemstone, crafting ingredient, or quest item meta-type tables into cache), and no hashing/probing/searching, I'd wager this will outperform other classic approaches like a hashmap.

---

Another thing you may want to consider is composition: "has-a" relationships rather than "is-a". So an item that can be used as a melee weapon "isn't" itself a MeleeWeapon type, it "has" a MeleeDamage component. Each item type is then a collection of components (could be a vector of pointers/references to those component instances, or similar to the above, it could be an index or reference to an "Archetype" containing parallel arrays of a specific subset of component types, plus an index into that collection).

This style is commonly used in Entity Component System approaches in games, and makes it easier to support "hybrid" items, like a spiked shield with both defensive and offensive stats, a gunblade or bayonet with both ranged and melee attacks, or a potion you can both drink and throw as a grenade, without needing to make hard-coded specialized types for each of these combinations. This encourages code re-use, and can enable remixing by designers/modders/players to craft novel items without writing new code.

But if you only need a closed set of a few item meta-types with little to no overlap in behaviours, then that's probably over-engineering for your needs.