Using AABB's for Path Finding

Apr 9, 2009 at 2:58 PM
I've been working on using AABB's and CollisionHelper for Path Finding, but the thing is I'm checking every Geom against every Geom.  Not good if you have a crowded asteroid field.

Does anybody know if their is already a method I have access to that can just return the geom's within a certain range of a geom?
Coordinator
Apr 9, 2009 at 4:40 PM
To find a geometry, you will have to do at least O(n) checks. If you need to find the closest geometry, you will have to do at least O(n^2) checks. (check each geom against each other).
If want to find geometries in an area, you can use AABBs. Depending on how precise you are checking, you will have to do at least O(n) checks.

I can understand you would want to use AABB's and line-of-sight checking, but as your objects increase, so will the amount of checks you are doing. The solution is to cut down the amount of checks you are doing and take it from there. A friend of mine wrote this tutorial on Axis based partitioning and collision: http://www.flatredball.com/frb/docs/index.php?title=FlatRedBallXna:Tutorials:Axis_Based_Partitioning_And_Collision
It may help you to understand how checking should be done.

Depending on how your AI should work, you could also have a look at graph search algorithms such as A*: http://en.wikipedia.org/wiki/A*_search_algorithm
(take at look at the right pane, it contains more good search algorithms such as Dijkstra's algorithm)

Also, Farseer Physics does have a crude (read: fast) way of checking if geometries are near each other. In the engine they are called broad phase as they are only checking if geometries are able to collide, and not really if they are colliding.
You have multiple ways of using the broad phase collision system in your path finding. You can use the OnBroadPhaseCollision event that fires when 2 geometries are in range (to collide) or use the ArbitersList collection on the PhysicsSimulator object. Once the broad phase determines that 2 geometries are able to collide (near each other), an Arbiter will be created and put into the ArbitersList.
Apr 12, 2009 at 7:56 AM
I have an idea: you could use the spatial hashing algorithm newly added to farseer, and when it detects that there are nearby objects, you could steer away from them.
Apr 21, 2009 at 7:58 PM
Is there anyway to supply an AABB that could query the Broad Phase?  Box2D currently does this with their Query method.

Basically, I have a similar use case where I'm trying to path find around physical objects in the world.  I'm creating a A* graph but in order to do that, I need to be able to query Farseer to know whats in the near vicinity of a node.