Isn't it logically the most expensive thing to create 4 trees at every step? By not doing this, I am providing 5-fold optimization. What do you think wrong with that?
well if creating trees is expensive yes. As i mentioned before, i suspect your node creation is very expensive, hence i suggest a flat representation. For example you could use a list, where each entry is the index of the child nodes.
You would group child nodes together in groups of 4. so the children indices of node "index" would be { list[| index], list[| index] + 1, list[| index] + 2, list[| index] + 3 }.
Another aproach is to use a map, where the keys represent the node. because each quad tree node has 4 children, its easy to represent each node key with a binary number, each group of two bits represents one of the children.
for example 00 01 11 10 would be {00: top left, ==> 01: top right ==> 11: bottom right ==> 10 bottom left.
The advantage of this is that its really easy to go up the tree (shift right) and back down (add bits on the end).
Because a quad-tree is completely implicit (you can know a nodes size just by knowing its key and the size of the root) its really easy to traverse just by checking if keys exist.
your reference is ready in memory,
your reference is hard for the cpu to prefetch, so it has to wait hundreds of cycles for the memory to be fetched.
In the meantime, the processor takes over the reading process in the memory, but the processor also undertakes the search process and functions.
CPUs are pipelined, if their next task doesnt rely on something being read from memory, it can keep doing a bunch of maths. So if you are fetching data for object 1, you can calculate object 0 whilst you wait.
If however you fetch data, then test it, then do something, the cpu can do some speculative execution but you will probably also end up stalling it somewhat. Especially if you do dependent memory reads (derefencing a value you get from a reference, then the cpu cant do that much but wait)
I don't think array loops are any better than this, I also give you an example for this; when you start from the top of the tree with the string loop to get the collision list (I'm talking about the 3-4 nodes to go) it costs you a lot.
im suggesting creating a tight loop around your objects rather than using methods. methods are slow because you don't really know what you are executing next.
If instead you have a loop that contains all your logic here and there, you can get much better perf.
I loop all the objects one step at a time, these objects are stored in an array.
here is your loop. the loop you said you didn't have. its just higher up your call stack.
I'm not using a recursive loop,
For example, I write the following to the function that updates the obj_sample position and sizes;
aabb.parent.check_data (aabb);
The tree on which it is located does what is necessary, if necessary.
Therefore, I can reach the tree this way, I can also reach the hill from the tree. For example, each tree branch has a reference named parent, it goes up to the upper branch.
it sounds to me like aabb.parent.check_data(...) can itself call parent.check_data if needed. that's recursive right?
What is correct? Saving all trees in an array and searching within?
all trees? what do you mean all trees? i am so confused now....
I guess what I wrote is not well understood by you. Why should I delete nodes?
if you create or destroy objects your tree will change.
Also when creating the tree the first time, you will create nodes.
When deleting the tree, if you change levels, you will leave a ton of nodes lying around, now the garbage collector has a lot of work to do cleaning that mess up.
eferencing structure bad, many game engines rely on this reference structure.
And yet you seem to be having performance issues
don't make sense to find it more economical to search for arrays for each objects instead.
its the whole linked list vs array list thing. Sure on paper a linked list has o[1] add and remove, but in real life an array list in many many times faster than a linked list.
Also i'm not suggesting you do a linear array search. that would be slow.
One structure that can do that is a spatial hash.
Essentially a grid that has a list of instances for each cell. They are very quick to build and query since determining which cell an object is in is very quick. The downside is that they use more memory.
I would really recommend you look into this if you want to speed up your query.
its super trivial to figure out what cells your AABB covers, and then you have nice linear lists of objects to do your narrow phase against.
Its not sexy, its not high tech, but its hella fast.
It kinda breaks down for general purpose physics engines where you have to cover a wide range of applications, but if you have full control over how things are created you can tune the grid size etc to get very good behavior.
I think it would be helpful if you posted some code to demonstrate fully how your system currently operates.