I have some questions about designing an efficient data structure in my game.
In my Scene Class, there is a GameObject dictionary pool, where the int key a unique id of every game object. E.g
public class Scene ()
{
Dictionary<int,gameobject> gameObjectPool
}
In my GameObject class, there is a child pool where keep the game object reference under this gameObject.
Should I use a list of the game objects to keep reference?
public class GameObject()
{
List<“gameobject”> childPool << just keep a gameobject reference
}
or just keep the unique id and use it as a key refer back to the main pool? Which 1 is more effecient and faster?
public class GameObject()
{
List<“int”> childPool << to store unique id and use it as key to refer back from the scene pool
}
List<GameObject> should be faster.
It will point directly to your data. If you use the ID it will first have make a hastable lookup of the KeyValuePairs in the Dictionary.
Hashtables are incredibly fast so don’t be scared to use them if you have a use for them, but even then it would be good practice only to do one lookup inside the encapsulation of a given function.
You may be considering storing IDs for reference if you saw that in an Entity Component System framework, or any number of other places. The comments here are right that storing object references is faster because you don’t need to do the extra lookup. The reason frameworks store IDs for lookup is because they have distributed, reusable memory.
Reusable
Imagine you didn’t want to allocate and deallocate memory whenever you create and destroy objects. Then you could have a list of 1000 empty objects, initialize them when you need them, and zero them out when you’re done. This is now better optimized, but you’d still be fine storing object references into this list.
Distributed
Now imagine you want your objects to be built from different types of data. Both a bullet and a tower are collidable, but only one moves, and only the other has health. So instead of having a GameObject that contains properties for any possible combination of characteristics, you have a bullet that’s Collidable + Movable and a tower that’s Collidable + Destructible. Then you’d have to store references into each of those lists. But what’s better and infinitely reusable is to say: “This bullet is object #4. For any of its characteristics, look at the 4th one in the list.”
Anyway, if you need to optimize memory usage and entity composition patterns, that’s basically the motivation for an Entity Component System (ECS). But it’s not really necessary for simpler cases.
I would say that you need to consider how you are getting the data out of the list. Iterating a list is slower than using a dictionary, on average, but if you have to iterate a list to get a key to look something up in a dictionary, that will certainly be slower than iterating a list to get an item directly (as Ozego pointed out). However, that still leaves the question: If you have the dictionary for efficiency, does the list truly make sense?
In any case, the difference is going to be VERY small. A minor optimization, at best. If there is an algorithm change that can remove the need for the list, that’s where a benefit might be found.
The trade off for fast code is complexity so only make your code more complex when you’ve actually measured your games performance and are improving the slowest parts otherwise your code base will be more complex than it needs to be.
I don’t think there’s an answer for that. What do you mean by a “free API solution”? Are you trying to create an API, and if so for what? Are you trying to use an API, and if so, for what?