Hi. I'm new to game development but I have some programming experience (plain C language and some functional ones). I would like to start data orietned programming and I've some questions...
First:
How to implement the scene tree? Suppose I have nodes, which are composed of position and rotation quaternion. I need to find transformation matrices out of that.
How to deal with nodes hierarchy in cache-friendly way? I guess an option could be reordering data according to BST scene tree traversal, so I could process nodes data linearly and have node's parent already processed. The code might look like:
vec3 positions[nodes];
vec4 rotations[nodes];
int parents[nodes];
...
mx4 transform[nodes], invtransform[nodes],totaltransform[nodes];
// STEP 1: Computing local transform for each node
for (i=0;i<nodes;i++) mx4_fromtransform(transform, positions, rotations);
for (i=0;i<nodes;i++) mx4_invfromtransform(invtransform, positions, rotations);
// STEP 2: Composing with parent transform
for (i=0;i<nodes;i++) mx4_multmx4(totaltranform, transform, invtransform[parents]);
I'm worried about STEP 2. I think jumping between array elements backward is bad (transform[parents]), isn't it?
How to do it right?
The next problem with this solution is... dealing with new nodes. To keep BST order in array I should insert new node's data somwhere in the middle of array and shift the 'next' nodes' data a bit. This will make these 'next' indices invalid. What to do? How to maintain indices valid?
Second:
Looking a little further, I'm wondering how to implement Compontent Architecture with DOD paradigm. I've seen only one high level (references, maps) implementation in Java on T=Machine blog.
How to manage the "compontents" data and, again, indices? "Systems" should process the entities' components wich they are interested in. How to filter these entities in a clever way? How to store information on which component belongs to which entity without use of any high level helpers? Maybe I should keep huge map of all entities to system components array index in each system?
system coolSystem
{
int compMap[MAX_ENTITIES];
compType components[MAX_COMPS];
// let -1 in compMap at index id mean that entity id desn't have this component
compType *getComp(int id) {
int mapResult = compMap[id];
return (mapResult == -1 ? null : *components[mapResult]);
}
void processComps() {...}
}
What about duplicates (some components of course may be used by more than one system, i.e. position -> AI, rendering,physics...)? Should I just copy component values from an arbitrary system to other systems?
How to make component architecture dynamically responsive? Some components may depend on state of other ones? Should then system contain all of these components? I think it's very cumbersome to have copy of many components in each system just to do some tests.
First:
How to implement the scene tree? Suppose I have nodes, which are composed of position and rotation quaternion. I need to find transformation matrices out of that.
How to deal with nodes hierarchy in cache-friendly way? I guess an option could be reordering data according to BST scene tree traversal, so I could process nodes data linearly and have node's parent already processed. The code might look like:
vec3 positions[nodes];
vec4 rotations[nodes];
int parents[nodes];
...
mx4 transform[nodes], invtransform[nodes],totaltransform[nodes];
// STEP 1: Computing local transform for each node
for (i=0;i<nodes;i++) mx4_fromtransform(transform, positions, rotations);
for (i=0;i<nodes;i++) mx4_invfromtransform(invtransform, positions, rotations);
// STEP 2: Composing with parent transform
for (i=0;i<nodes;i++) mx4_multmx4(totaltranform, transform, invtransform[parents]);
...
AFAIS there is an error in your code snippet. Computing the world transform should probably looks like
for (i=0;i<nodes;i++) mx4_multmx4(totaltranform, transform, totaltranform[parents]);
Moreover, you apply the parental matrix in each case. That cannot work, because not all nodes will have a parent. You may consider this by multiplying with the identity matrix, of course, but your addressing scheme then requires the identity matrix to appear in the totaltranform array. So, you'll probably store at index 0 the identity matrix (the world node will have it either) and do parenting starting with index 1:
for (i=1;i<nodes;i++) mx4_multmx4(totaltranform, transform, totaltranform[parents]);
... I'm worried about STEP 2. I think jumping between array elements backward is bad (transform[parents]), isn't it?
(BTW: Above it is invtranform[parents] and now you write tranform[parents], but IMHO it should be totaltranform[parents].)
It is "bad" if and only if the matrix is not in the cache. Because you refer backwards while iterating forwards, it is precisely "bad" if and only if the matrix is no longer in the cache.
The next problem with this solution is... dealing with new nodes. To keep BST order in array I should insert new node's data somwhere in the middle of array and shift the 'next' nodes' data a bit. This will make these 'next' indices invalid. What to do? How to maintain indices valid?
Using arrays inherently has this problem. You can use double indexing, but that would derange the order. So you're probably required to adapt the index array as well.
Second:
Looking a little further, I'm wondering how to implement Compontent Architecture with DOD paradigm. I've seen only one high level (references, maps) implementation in Java on T=Machine blog.
How to manage the "compontents" data and, again, indices? "Systems" should process the entities' components wich they are interested in. How to filter these entities in a clever way? How to store information on which component belongs to which entity without use of any high level helpers? Maybe I should keep huge map of all entities to system components array index in each system?
system coolSystem
{
int compMap[MAX_ENTITIES];
compType components[MAX_COMPS];
// let -1 in compMap at index id mean that entity id desn't have this component
compType *getComp(int id) {
int mapResult = compMap[id];
return (mapResult == -1 ? null : *components[mapResult]);
}
void processComps() {...}
}
What about duplicates (some components of course may be used by more than one system, i.e. position -> AI, rendering,physics...)? Should I just copy component values from an arbitrary system to other systems?
How to make component architecture dynamically responsive? Some components may depend on state of other ones? Should then system contain all of these components? I think it's very cumbersome to have copy of many components in each system just to do some tests.
There're already several dozen threads here in GDnet that discuss this issue. Have you searched for them?
Some general thoughts: You'll probably hit the fact that dependencies between objects will not totally fit into a tree structure. You'll probably (in dependence of what you understood under "scene tree") also hit the fact that there are many nodes that doesn't have an own co-ordinate space. So iterating over nodes in your original code snippet should perhaps mean "iterating the placements of (placeable) nodes", and the order will perhaps need to be build from a more general dependency approach.
Thanks for reply!
Yeah, there is an error, I've writting this pseudo code to show idea, so I focused on it and I've completely forgot about details, of course it should be totaltransform, actual code makes no sense.. no hierarchy at all! hehe. Also I though about putting identity matrix at index 0, but that's not very important now.
Because you refer backwards while iterating forwards, it is precisely "bad" if and only if the matrix is no longer in the cache.[/quote]
Any idea to make parent cached for sure? With this pattern I could only store last used parent and have it cached for all it's children, but this changes nothing if nodes don't have many children...
You can use double indexing, but that would derange the order. So you're probably required to adapt the index array as well.[/quote]
You mean some lookup table "int indices[nodes];" which maps global, unique entity id -> data array index, like one I proposed in components array?
There're already several dozen threads here in GDnet that discuss this issue. Have you searched for them?[/quote]
Yeah, but all of them are about OOP ideas, I don't know if event manager and that registering listeners can be implemented in is cache friendly way.
Some general thoughts: You'll probably hit the fact that dependencies between objects will not totally fit into a tree structure. You'll probably (in dependence of what you understood under "scene tree") also hit the fact that there are many nodes that doesn't have an own co-ordinate space. So iterating over nodes in your original code snippet should perhaps mean "iterating the placements of (placeable) nodes", and the order will perhaps need to be build from a more general dependency approach.[/quote]
Right, but in general, visual part of scene has a tree structure of nodes and, of course, in first question I considered only placements of nodes. I think "render system" should just iterate over it using tree order. Other components may be traversed differently.
As I've read, any other relation between entities should be realized using events/messages. How to go about it?
Every component should be able to register itself to listen for specific type of message. I suppose, in DOD I should know the exact number of types of message. Could bit flags do the job (one int->32 types of message)?
How to store and process these messages and their parameters efficiently?
How to code message handlers for components without use of virtual functions/function pointers?
I guess a generic receiver like comp_processmsg(int msgtype, void*params) and gigantic switch{} within is the worst option, but I don't see any other (there must be an "arbiter" switch, or data driven function table, which directs messages to appropriate handling code) ... Miss pattern matching....
