Hey I''m programmingen a ALife program. There is a class world and in that class I have an array of animals. Each cycle i do animal.live(list); The list has to contain pointers to al the objects the animal can see. My problem is to find a quick way to search in my array of animals and other objects to get all of the obj in a range r around that animal. the easiest way would be : for(int i=0;iBut it would be to slow I think (I will have many animals and other things in my world) Can anyone give me good ideas to do it in an other way

Your data structure should in some way represent the world.

If you were doing cellular automata, for example, in which you have a 2d grid filled with cells, each coordinate on the grid should correspond to an entry in a 2d array for one cell. That way, knowing what's where doesn't take any time.

Now, you're not doing cellular automata, so chances are that wouldn't work. But here's an idea that would: quadtrees (in 2d) (or Octrees in 3d). You could split each square either around its center, or you could split around animals. Alternatively, you could use a KD tree, splitting where there are animals. This will allow you to locate animals more quickly.

Assuming you have a quadtree, then your algorithm is simple. Your world is one big square, split into four smaller ones (and so on down the line). You test each of the big ones and see: Does any corner of one fall within the radius? If it does, do the same thing with the four squares within it.

If you need more clarification, and the resources here on gamedev and on google don't help, post back, and we'll try to clarirfy on quadtrees. There are lots of tutorials on quadtrees though, so you shouldn't have any problem. Just don't be fooled into thinking they deal only with terrain! In reality, there are other things (like sorting your animals) that they're even better at doing.

Good luck!

[edited by - TerranFury on October 15, 2002 6:20:14 PM]

ok I understand that quad tree.
I had tought of laying a grid over my world. and than I had to check witch cells of my grid were in my radius and look for animals in them.

-Is the way with the quad tree faster?
-supose you have your quad tree with the animals in it.
Now an animal move for example from (50,50) to (55,60) is there a nice way of calculating where the animal has to go in the quad tree ? (with my solution it would be easy.)

thanks.

You can quite easily make your quad tree dynamic. Presuming that motion in your world is continuous (i.e., animals cannot telport themselves to random places in the world) then whenever an animal moves out of its highest resolution quad, it must move into (or through) a neighbouring quad of the same resolution. Both of these quads are children of a lower resolution quad one branch up the tree. So, depending on how fast the animal is moving, you can compute the distance it travelled during the frame and work out how many levels up the tree you need to regress. Then, starting from that level, run back down the tree to find the correct highest-resolution quad to place the animal in.

If you design your quad tree resolution taking into account the usual velocities of animals, you wont need to regress more than a level or two up the tree, making reassignment much faster.

Make sense?

Cheers,

Timkin

reaction on Timkin:

I split my world in 4 and these parts again in 4 etc
. the center of my world is for example (100,100).


there is an animal on (99,99) and moves to (101,99) then I have to go back to the start of the tree.
==> the quads are neighbourings but they aren''t children of a lower resolution quad one branch up the tree like you said.

on wich point I take the wrong conclusions, or have I to build up my tree in an other way ?

That is the worst case scenario, and it could happen, but it''s really not all that bad, and it''s still a whole lot faster than rebuilding the whole tree each frame.

Go dynamic quadtrees!!

quote: Original post by CPeX
there is an animal on (99,99) and moves to (101,99) then I have to go back to the start of the tree.
==> the quads are neighbourings but they aren''t children of a lower resolution quad one branch up the tree like you said.

If you read my post again you will note that I did not say you will ALWAYS only have to regress one level... only that in most instances this is what will be required. There are always worst case scenarios and as TF pointed out, this is one of them. I can think of worse scenarios... like building a dynamic quad tree for a torus world!

To find the appropriate new quad, write a recursive function that checks (based on the new location of the animal) if the animal is within the quad passed as an argument. If it is, return that quad (which automatically returns the same quad if the animal didn''t move outside of this quad). If it isn''t, have the function call itself passing the parent quad as the argument. What I was saying in my last post was that in most situations (particularly if you define your quad size based on animal velocities), this recursion will be between of a low depth (usually from 0 to 2).

I hope this makes more sense for you.

Cheers,

Timkin

quote: Original post by fup
Just to chip in with my 2c''s worth: You could use bin-lattice spacial subdivision. This is much easier to implement than quad-trees and will probably be sufficient for the task.

Sounds like CPex''s original idea!