Home

Implementation notes

Navigation mesh path finding

We use Delaunay triangulation to find a global path. It is very fast, but can only work for static obstacles that are known ahead of time.

RRT* path finding

We use RRT* algorithm (sort of) to avoid dynamic objects.

Binary search collision checking

It is very costly to compare collision of two OBBs in every state in every potential path. We use binary search approach to reduce this check cost.

The idea is illustrated by the pseudocode below.

fn bsearch_collision(obj1, motion, obj2) -> bool {
   collision_internal(obj1, motion, obj2, 0).hit
}

fn collision_internal(obj1, motion, obj2, level) -> (hit, max_level) {
    let bounding_sphere = obj1.radius + obj2.radius + motion.length();
    if bounding_sphere < (obj1 + motion / 2.).distance(obj2) {
        return (false, level);
    }
    if level < MAX_LEVEL {
        collision_internal(obj, motion / 2., obj2, level + 1) ||
        collision_internal(obj + motion / 2., motion / 2., obj2, level + 1)
    } else {
        obj1.intersects(obj2)
    }
}

The actual code is obviously a lot more complex.

One thing to be careful with this is that we need to check the last state outside of recursion, because obj1 will never reach obj2 with this recursion. In particular, it would intersect with the obstacle like below. In this visualization, green rectangle is the obstacle, and the white lines and rectangles are the search tree and potential agent states. The white rectangles and the green should never intersect, but it does.

(Other unimportant info about the visualization: the thickness of the white lines indicate how many recursions were performed, and the dots along the lines are the points that intersection checking was performed.)

In order to fix this issue, we need to modify bsearch_collision function like below.

fn bsearch_collision(obj1, motion, obj2) -> bool {
   let (hit, max_level) = collision_internal(obj1, motion, obj2, 0);
   if hit {
       // If we detected the collision somewhere in the recursion, we can return immediately
       true
   } else if max_level == MAX_LEVEL {
       // If we had to recurse all the way, but are still not sure if intersection happened,
       // Check intersection with full motion
       (obj1 + motion).intersects(obj2)
   } else {
       // Otherwise, it did not hit
       false
   }
}

The result looks like this. It does not have intersection at all.