Sort your arrays so parents always precede children.

The cost of the sort is cheap, especially as they're just indices. Various approaches can ensure that the sort is implicit without actually performing a sort operation, e.g. by swapping the parent and child entry in the array when the relationship is formed if the parent is after the child. You really want to keep the array to be sorted parent-to-child with as small a distance as possible between parent and child; this means your update loop just iterates (not recurses) over the data once with children back-referencing parents' indices and the parents data is highly likely to still be in cache.

You can at the very least ensure parents come before children by swapping the parent and child data when the relationship is formed if the parent comes after the child (or just initially placing data in the proper order if you know the relationships ahead of time). An indirection table can allow your game objects to use stable ids/handles into this scene node system while allowing the scene node arrays to be reordered as needed.

#1: Multiple representations of a scene within a scene manager are completely normal. You will have a linear array of objects, and then perhaps a quadtree/octree of objects, and perhaps a list of static vs. animated objects, and perhaps a list of player-controlled characters, etc. Each serves its own purpose—the linear array is the master list of objects when you simply want to find one based on a property, while spatial partitions may (or may not) improve performance when searching for objects to draw.
Each object exists only once; you are just duplicating the pointers to them.

#2: But your case is not a case where multiple lists of objects is necessary. Nor does it matter that children can come before their parents. You are making a false problem where none really exists.

#3: The hierarchy of objects (the “scene graph”) exists as part of the actor objects themselves. There’s no second array for this. Actors themselves manage the scene graph, and it doesn’t make sense for any other objects (including the scene manager) to have knowledge of this hierarchy.


I have already covered this in detail: Scene Graphs
See “How is a Scene Graph NOT Used?”, point #4: “Scene graphs do not act as the primary representation of your scene. A scene graph can optionally be used to provide a spatial representation of the scene, but when the scene manager wants to iterate over all objects it does not do so by traversing the scene graph. The scene manager should have a simple linear array of all the objects in the scene. The scene graph itself is implemented within those objects by themselves, separately from the scene manager.”

Every actor has a list of children and a single pointer to a parent.
This hierarchy is part of the actors themselves, so it exists within a scene no matter how the scene manager stores the objects. A single linear array of all of the objects in the scene must by definition also contain the object hierarchy within it, and no other arrays etc. are necessary. Additionally, there is no purpose in ensuring parents “come before” children.

#1: Actors have pointers directly to their parents and their children, and it doesn’t matter where they exist in the linear array—you traverse them using the pointers inside the actors themselves, leaving linear arrays completely out of the picture.
#2: Actors aren’t even stored in a linear array in the first place. Pointers to actors are stored in a linear array. The actors themselves are each allocated separately, so you aren’t gaining any cache performance etc. by ensuring they come in any specific order within the linear array of pointers to actors.

#3: They don’t have to be in any specific order for saving either. Just save them all linearly and include the parent ID of each actor. Then make a pass to connect parents and children based on ID’s.

If you want to hold a second array of pointers to top-level (NULL-parent) actors then that is your choice, just as some people choose to keep a secondary array of pointers to playable characters. It is not necessary, and you will have to be careful to keep it updated as objects gain and lose parents, etc.

L. Spiro

I would greatly take Sean's recommendation of listing parents before their children in cases when nodes needs to be organized in N-trees. The number of nodes is fixed per level, and finding and updating nodes is quick and trivial with bitwise functions.