Obstacle quad Tree

Hi, i got a progrom about rvo. i just want to know why you don’t store the rvo obstacles into a quad tree like the agent tree, cause i find that when i search the valid obstacle on the agent’s range, this code can be found in RVOAgent.cs GenerateObstacleVOs(), you use a for and do-while loop to kick the obstacles that not in the angent’s range. if obstacle also store with quad tree, can it run more fast? Thanks so much!


Some kind of tree structure would be good to accelerate it, yes. It does however need to be more complex than a quadtree because the obstacles are not simple points, but rather polygons. I simply haven’t had time to implement that so far.

soga, thanks, you can have a look the RVO2, it store agents and obstacles with kdtree, but cause kdtree’s insert and delete can’t be done, so we don’t use rvo2 for local avoidance, but currently rvo spend too many cpu, we are trying to improve it , if you get spare time, hope you will add this in to rvo in the future version.

Yep. This package actually did used a ported version of RVO2 a long time ago. At that time it did however not have the permissive license it now has, and I had to remove my ported version due to licensing issues. I may consider adding things back in from RVO2.

1 Like