My team is working on an RTS http://www.iron-harvest.com) where we’re combining A* pathfinding with local avoidance. Our current implementation uses a custom corner-graph based pathfinding and an opensource C# library called RVO2 (http://gamma.cs.unc.edu/RVO2/downloads/). RVO2 worked well to show that the general approach is feasable but it doesn’t meet all our requirements and so I’m currently evaluating your avoidance solution as a possible alternative. I like the code quality & comments but also the promise of using a matured library that has been used by countless of game developers. There are features that you have and RVO2 is missing: Especially the support for Collision Layers and Priorities.
But it seems that your implementation has it’s own set of weaknesses, too:
Obstacles are not avoided in a way that the agents radius is taken into account. Our use case has agents of many different sizes so we can’t just add a single “extruded version” of the obstacle. Instead we’d have to create and add multiple versions of the same obstacle, putting them on different Layers so they only affect units of the correct size. Considering how GenerateObstacleVOs() seems to generate VOs for all obstacles instead of only considering the local ones I fear that, even if I’d spend time to adapt your solution and calculate extrusions for the obstalces (not trivial) it still wouldn’t work for performance reasons. (Our level has a complexity of hundreds of obstacles!)
Another question I’ve had is wether there’s a reason you didn’t use ORCA lines over RVO? Are some of your features not possible to be implemented with the ORCA based solver? Because, from reading the papers this approach seems to be superior to RVO without any obvious disadvantages.
I don’t want to critisize you with my post. It’s just that I’m faced with the difficult choice which solution is more promising to adapt and transform into something that’s meeting all our requirements and all info that could help me make the right decision would be very much appreciated.
Hi
Initially my package did implement ORCA. However due to the similarity of my code to the RVO2 library (as I had to look at that to figure out how they handled some special cases that are not mentioned in the papers) I was faced with a cease and desist letter from the university that owns ORCA. This was a long time before they changed the license to a more permissive license. Therefore I had to rewrite my local avoidance solution into a less efficient but distinctly different solution. During that rewrite I did cut some corners to get it released, one of them being that obstacles are not expanded by the agent’s radius (it makes the math a lot trickier). And yes, obstacles are not particularly performant when you have a lot of them at the moment (that datastructure also had to go during the rewrite unfortunately). My package does however include ways to keep the agents on the navmesh in other ways. E.g the AIPath movement script has an option to clamp the agent to the navmesh which will also communicate to the local avoidance system that it has collided with a wall. The agents will not anticipate collisions with the walls (pathfinding is assumed to take care of that) however they will handle being pushed into walls in an acceptable way. Now that ORCA does use a more permissive license, I have considered changing back to that, but I haven’t gotten around to it yet.
To be honest though, collision layers and priorities are really tiny changes that do not affect the code that much. Collision layers in particular is only a 2 line change or something like that. I doubt it would be hard for you to add that to the RVO2 library yourself if you needed to.
Thanks for the background info. I didn’t know about the licensing issue - that explains a lot.
It’s not only layers and priorites thats missing from the RVO2 library. You can’t remove agents and obstacles either for example. So to realy integrate RVO2 in a way that it fits nicely and meets all requirements it will require a bit more then a few 2 line changes I fear. Because, once I get started, where do I even stop? RVO2 rebuilds their spatial datastructres a lot. Agents each frame, Obstacles whenever one gets added or removed (once removal is even possible). Considering that other game systems allready provide/use fast local queries many cycles could be saved by integrating it even more tightly with our existing systems and get rid of potentially costly redundancy. But at the price of opening the black box and taking complete ownership over something I hoped I could just “outsource” because, to be honest, the math involved is a bit over my head. 
1 Like
This is interesting and actually a big issue for my game as well.
Aron, can you recommend a path forward for someone who DOES want to own your library as their own code base now?
I need to take radius into account (I’m not actually sure how this even works if you don’t).
@cplepel
Currently you’d have to expand the obstacles by the agent’s radius, anything more fancy than that unfortunately doesn’t exist at the moment. Good thing is that most navmeshes in this package are already expanded by the agent’s radius (e.g the recast graph) as they treat the walkable surface as points where the agent’s center is allowed to be.
Just to clarify, it does of course take other agents’ radii into account during avoidance. Otherwise it wouldn’t really do anything.
