[c++] non-recursive way to iterate tree
Oh sorry, it would be a breadth-first search, if the items were going in one end of the data structure and out the other end.
On second examination, this does not appear to be the case.
For a a scene tree the best solution is to use recursion ?
Usually a world has multiple data structures involved.
A scene or level or world is usually going to be used for many frequent searches and lookups. Queries are both for existence and also for position. There will be frequent changes to objects in the world.
Generally there is a hash table containing all the objects. The hash should be a guid assigned to each object. This is generally the master list.
There is also generally a spatial tree, such as a loose quadtree, that indicates where the guid lives in the world. When an object's position is updated this spatial tree needs to also get updated.
There may be yet another graph, called the scene graph, used for display. Quite likely this graph is not part of the game world since it is part of the renderer's responsibility, not world management's responsibility.
Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?
Use the recursion to save/load and the array for other operations ?
Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?
The idea is that you don't use a single data structure for everything. Many old engines tried to put absolutely everything into a "scene graph" (one graph to rule them all), which was a massive tree with a root node like you're describing, but that's a really bad idea. Data that's used for different purposes should be stored in different ways.
struct TransformNode
{
Mat44 local;
Mat44 global;
vector<TransformNode*> children;
};
struct BoundingSphere
{
Vec3 position;
float radius;
};
struct Actor
{
TransformNode* transform;
BoundingSphere* sphere;
Mesh* mesh;
Material* material;
};
struct Scene
{
TransformNode* rootTransform;//tree of data
vector<BoundingSphere> spheres;//array of data
list<Actor> actors;//linked list of data, pointers into the above array and tree
};
