Objects near coordinate

Topics: Developer Forum
Sep 30, 2012 at 12:19 PM

Hi!.

I'm wondering what the best way to get all bodies within a certain distance of a point is?
I want to run custom logic on all objects which are (d) distance from point (x,y).
Possible?

Sep 30, 2012 at 3:13 PM
Edited Sep 30, 2012 at 3:17 PM

Depends how many bodies you have and what perfrormance you need. 

One way:

foreach(body in World.BodyList) distanceSquared=(body.Position-point.Position).LengthSquared; if (distanceSquared<=d*d) Action();

Considering a moderately big world (about 500 bodies) that's an easy way with just a few calculations (use LengthSquared to avoid a square root).

Important note: you wrote bodies so I gave you a calculation for bodies. A body has a position and is infinitely large. It is a plane whose origin lies at Body.Position. What you probably need is not bodies but fixtures which are shapes on the plane. The fixture, however, may be fat, it may be any polygon etc. So when you speak of a distance to a fixture you really mean the distance to the border and not to the center even if the fixture is attached to the center of the body. That's a more complicated problem. There are classes in Collision/Distance.cs that implement the necessary algorithms.

Since calculating a precise distance to every fixture is expensive in the general case you need a so-called spatial query. In Farseer it is achieved using World.QueryAABB where the center of the axis-aligned bouding box is your point, the dimensions are your distance*2. The callback will give you a list of fixtures overlapping the AABB. Since the space spanning a maximum distance d from a point is a disk, whereas the AABB is a box in which the disk is inscribed, you might want to refilter the results further to make sure they are inside the disk and not between the border of disk and the border of the box.

Another way that I have used successfully: shoot rays (World.Raycast()) from the point in a circular manner from 0 to 360 degrees. Performance will depend on your angle step and can be tuned. Get only the first intersection of the ray. This has some benefits as it provides additional information like line of sight (!), the intersection point and the normal of the edge.

If you need this to happen often you might want to add a circular fixture to a ghost body centered at the point and set it to sensor so it reports collisions.

Sep 30, 2012 at 7:46 PM

Hey!

Thanks for the reply, I think I need to clarify what I intend to to ;)

I am toying with the idea of having a multiplayer game. What I want to do is send information about what is happening in the servers simulation near a certain position over the network to the client simulation.

Basically I have two simulations running at the same time, one is the authorative server, the other a slave client. I want to get all objects near the clients position and force their positions (interpolate) them onto the client. I have a very basic example working with just 2 bodies, but as I intend to have a couple of hundred bodies in the simulation I cant really afford to keep them all synced perfectly.

As you wrote there is a big difference between the origin/position of the body and the edge of the fixture... But as no object will be very big I am going to send all objects which are 1.5x the size of the screen away from the client to them.

I'm not sure doing a foreach(body in World.BodyList) to get what objects are near for every client in every network update will be a good idea (500+ objects 10+ clients..). Am toying with the idea of making a Quadtree of positions, but was hoping I wouldent have to go there.

Sep 30, 2012 at 9:20 PM
Edited Sep 30, 2012 at 9:22 PM

Hi,

You should profile various methods to find out which is best. But don't dismiss the basic maths loop. First of it's very simple. Second your network update will happen once about every few seconds, not even every frame and you can stagger the updates so not all clients are updated simultaneously. Third it is only a few additions and multiplications even though it's for every body. That means it won't scale but doesn't mean it's not fast for a smallish number of bodies. Once you pull the positions you can also offload processing to other threads/cores.

Have a look at QuadTree.cs (QueryAABB). It does have some overhead. On the QuadTree side of the argument (apart from it being a real spatial query) - it's already there as well as the facilities to work with it so...

In any case I don't really think pulling the data you need will create you any performance headaches. Synchronizing the clients properly is immensly more difficult.