Hi
I’m working on a little game mainly to experiment with navigation meshes and path finding. Thanks to Don McCurdy’s library, path finding is working great. But now I have multiple characters I’m pondering how best to avoid collisions. I could just stop them, but I’d prefer to make them pass each other while staying within the confines of the Nav Mesh. If anyone has done this before and can suggest a technique I’d prefer not to reinvent the wheel.
The definitive answer here would be the Detour library… in theory it could be compiled to WASM or JS, and it handles “crowd” pathfinding nicely. Unfortunately that’s a somewhat complicated task – I’d love to see it ported someday, but haven’t managed to do so myself. See:
Short of that, there may be tricks you can manage with just three-pathfinding and some extra collision-avoidance code, but I don’t know how to do it without reinventing the wheel either.
Another option is the usage of a so called ObstacleAvoidance steering behavior like suggest by Mat Buckland in Programming Game AI by Example. Using force-based steering behaviors for the actual movement/steering of game entities is a best practise in game development in any case.
Besides, it’s also possible to use a Separation steering behavior in certain scenarios. If you have a strict non-penetration constraint, you can compute very fast solutions based on intersections test with bounding spheres. With a simple cellspace partitioning it’s straightforward to respect just the nearest neighbors of a given game entity. All this stuff is not hard to implement and runs very performant in JavaScript. Take a closer look at Yuka where this code is actually used. BTW: A basic NavMesh solution is also available.
