Closest body

[KingSnail]

Hi, is there an easy way to get the closest bodies to a body.
Currently I have a giant loop that does vector distance squared equation. But its waaay too slow for some reason

[Julio Jerez]

you can use get bodies in AABB,
How many bodies are we talking about?

[KingSnail]

I mean I want to know every single body that is close to another body. (So a player knows what enemies are around him)

[Julio Jerez]

There are different ways to do that. depend on how hard in tuern fo bodies count the problem is.

If you are doing it for just for few objets, and easy way is the brute force using a AABB test.
has an AABB predefined size and get the bodies in that AABB using the newton function which is very efficent.
then you do the same thing you are doing but only in the bodies returned by the AABB query.

if you are doing for lot of actors, then the best way is to build a Voronoid diagram, which gives you all of the closest points to all other closest point in one go.
you can buidl a Vornoid diagram by using the NewtonMeshCreate Convex Mesh, by pasing the projection of the position of each point in teh 2d planes, lifted to the 3d space like tghis.
p(i) = 2d position of body(i)
p(i)._z = p(i).x * p(i).x + p(i).z * p(i).z;
then for each body in the mesh the closest point is the collection of all point around the mesh.
using the Newtn mesh is a quick way to protype it, but you can searh in the net for algorithm for build incremental voronoid diagrams.

but like I said the method using using the bodies in a predifined AABB should be sufficent, and only if you are doing this with lots, and lot of bodies at the same time.
here is a mathematical; explanation of the voronid diagram
http://mathworld.wolfram.com/VoronoiDiagram.html
if the picture you can see how the diagram, build a cell struture arund each points, the neigbodi to each point in teh diagam is is teh set of all boides that are closet to taht point to any othe point in teh set. so you get all the closer point, not only for one point but for all other points.

This is an elegant way to solve the problem, and voriniud diagrams are at the core of the most sofistcated AI algorithm in the world,
including Robotic path finding for Vehicle navegation, even the mars rober uses it. It makes yours AI almost look human, beleive me.
but it is more expensive than just calculation the closest point for one or very few bodies, so I recomend it only if the problem is very large.
lot of players and lot of enemies, because you just do once for all bodies.

[PJani]

the best solution would be your own system for such things, because you will need to process all bodies in your world with newton. In some list or array you store all players with their newton body pointers. When you need to check the closest in the list you just iterate thru player list and check their distances( probably squared distance its faster vs sqrt) between your player and enemies( excluding player-player relation ). this is the simplest way.
maybe if you put more effort in it you can get even better thru than O(n).

[KingSnail]

Hey Julio do you know any 3D incremental fast voronoi diagram library/code with nearest neighbour output.
I looked everywhere and only found voro++ but I dont think thats incremental and I have no idea how to ask it to get nearest neighbours

[KingSnail]

Julio do you think you would be able to implement such a diagram? Your a very good mathematician

Would it be possible for Newton to include an internal voronoi diagram processor which can be set by something like
NewtonSetComputeVoronoi(NewtonWorld * world, int state);

and then each body can be queried like:
NewtonBody ** NewtonBodyGetClosestBodiesToBody(NewtonBody * body, int & count)

Damn I wish I could understand maths as good as you, so I could attempt it myself

[Julio Jerez]

How fast do you need it to be?
if it is a 2d problem it is very eassy to solve and can even be very very fast.

if it is 3d is can be a be slower by still much faster than teh brute force.

teh best thing is teh Netwon do have that funtionality, and nwo that newton is open source (the cat is out of the bag so to epeak)
i can tell you how to do it us the engine to get it.

The engien uses vonoiri diganam for soem internal algorithm, I will not add extrnanl funtionality to do that but I can tell you teh step for that you cna make you own usin teh newton
Computational geomnetry library. There is funtionality fo buiding increamental Voroni and Delanay structure already.

[KingSnail]

Well my game is 3D.

Yes if you could provide a small tutorial would be great

I also thought of doing a hash map. Would that be faster?

Could you please have a look at this thread as well, its about proximity checks in MMORPG's
http://www.devmaster.net/forums/showthread.php?t=4416

Thanks

[Julio Jerez]

are you Noname in tha thread?
some people gave advices, that can be good aproximation to the problem but I do not think any of the advices really adress the problem.
in fact any of the solutions they propose can lead to a n^2 search and never to the correct solution, only to an aproximation.

take for example the grid solution, wich is a special case of a quadtree, it will give you a quick seach if the bodies are clostered together, and expensive if the bodies are far appart.
furthermore wrong solution if a body that is father away that the very few one and it is still part of the closest set.
the problem with all the solutions they present to you is that you will never know which of the objects are the exact closest.

for example say you have 100 bodies and you want to know the closest to one body, how do you know that the first say 4 bodies are the closest and not the first 5.
That kind of expert advice is what had lead the Video game industry to mediocre AI solutions. That is the kind of solution that make an AI some time looks good and must of the time look moronic.
for example you will have to set a critiria lei the N closest bodies. say N = 5 and you have a case where they are 7 closest enemy, your abatar will die instead of running away.
but if there are only 3 closest enemy then your abatar end up attacking an eneny that may be irrelevant.
but it get worse, say you want to know the closest closest to make a formation, or to plan an ambush or any kind of strategy, with the false information your ai will also looks stupid.

The Voronoi/Delanay diagrams gives you the exact solution every time. and then from there you can make your AI decisions.
also the Voronoi/Delanay provide information in constant time. and can be maintained incrementally.

having said, it seems you formulated the propblem in terms of the closets points within some radius, have you tried any of those solutions yet?

I'm looking for some background on the following problem: I have a (3d or 2d) point cloud, and for every point (player) I need to calculate a visibility set of all other points within a radius r (let's say that all players have the same r for now). The naive solution is n^2.

if this is what you want, then the solution they provided will solve the problem, but like I say it will give you stupid AI. just think of the case when on body is with in the radius,
but 5 more and just outside the radio just waiting you avatar move toward the bait, your avatar will die everytime.

stil remaind the probmem of maintaninbg the data structure whic they do no adress, and for that Newton comutational geometry library can help too.

but you need to tell me what solution you want also how many objects are we talking about?
and if this a MMOR could the problem be aproximate in teh 2d map?

[KingSnail]

Thanks for reply and useful advice.

Thats not me in that forum, the thread is pretty old. I just found it through google.

I want to be able to have up to 1000 players in a zone and enemies.

The player position are x,y,z so I am not sure if I can solve it with a 2D diagram.

What I ultimatly need is to send an array of players that the player can see over the network.
and eventually add monsters/npc's to that array as well. Right now im focusing on the players.

I just need to get a list of bodies that is around a body within (150.0f?) gl units. And ofcourse I dont want to calculate 2 bodies
twice that I already checked the distance of.

[Julio Jerez]

I want to be able to have up to 1000 players in a zone and enemies.
The player position are x,y,z so I am not sure if I can solve it with a 2D diagram.

these are peoppe on a map, we are talking about, aren't we, yo ucna solev is the 3d floor and then if that si no suffucent you can try the 3d case.
not reason to make if general when a simply solution will do, beside the algoirth in 3d is way more compels than it is is 2d.

if you want to do it is 2d I cna give you some pointer, teh form ther you cna invetigate the 3d case, but I beleive 2d is sufficent.

[KingSnail]

Sorry im a bit stupid in maths but how can 2D work in a 3D environment?
Discard the Y value coordinate of player position or something?
What if the player jumps really high then it would not still think that player is on the ground?

[Julio Jerez]

2d word in 3d because most of 3d stuff in a map, (people moving on a map) is almost 2d,
basically you take the coordinat of the floor and ignore the elevation and that leads to a 2d map.

when you compare the difference in elevation beteeen points on the map as they move, to the chnage in location on fhe floor
you will see that the changes in altitude are neglegible compare to the changes on the plane.
so you can neglette the elevation and the result will be the same as if you use the elevation.
but the level of complexity is reduced by one dimension.

in you example if one player jump really hight.
when you queres the close biodies you will get that player if it is close in two 2d.

buit sicn eteh algorithm aways give you teh correct number of point in 2d all you nee to do is test teh point and check for the Y values.
if it is very high you simple do not use it. in other word you will get Positive that are false whis are eassy to deal with.
never you will get a Negative that is positive whis are improsibel to correct and it is what you will get if you use the "Object is some radio method"

[KingSnail]

Ah I understand it a bit more now.
So build the voronoi diagram 2D
and if player is close to another in XZ then test the Y manually?

Now I just need to know how to build the 2D diagram with newton then