1
\$\begingroup\$

I'm developing an RTS, and having a little difficulty with collision detection. From what I understand RTS generally don't bother with collision detection and just try to avoid collision, and that is what I am trying to accomplish.

My game uses a grid for static obstacles, but units are not bound to the grid for movement. How do I allow for units to avoid collisions, both with static obstacles and with other units? Right now my workaround is to redirect units around static obstacles every time they move from point to point (and every time a new obstruction is placed on map, units replan their routes). This doesn't seem like an ideal solution, but it works. I have no idea how to handle unit-unit collisions.

\$\endgroup\$
  • \$\begingroup\$ See into Recast Navigation, RVO2. \$\endgroup\$ – Kromster Jan 23 '17 at 4:42
  • \$\begingroup\$ I looked up RVO2 and downloaded the source, but it won't compile for me and I can't decipher what everything is supposed to do. Can someone explain how RVO works like I'm five? \$\endgroup\$ – blip Jan 24 '17 at 19:52
1
\$\begingroup\$

You are on the right track.

I have re-implemented collision avoidance for my RTS taking Recast as example. General approach is quite simple: Each agent (that's how they call units in collision-avoidance) checks for neighbours and obstacles and chooses path depending on its desired movement direction, other agents desired directions and allowed space. Complications arise from making this efficiently.

All agents are usually implemented as circles. Each agent keeps a list of 6-8 closest agents and sees if they are in their way. Obstacles are usually circles or NavMesh boundaries. Agents emit rays and check if they collide with any obstacles edges.

There are many pitfalls in implementation, so unless you want to make your game specifically-unique collision-avoidance based, better take an existing library.


I have researched the topic and have made a list of available libraries (actualized in 2014), that implement agents navigation and collision avoidance:

  • Recast Navigation/Detour/Crowd
  • ORCA: Optimal Reciprocal Collision Avoidance
  • RVO2
  • HRVO
  • ClearPath: Highly Parallel Collision Avoidance
  • OpenSteer
  • SimplePath

You might want to see their sites, some had explanatory videos and texts.

\$\endgroup\$
  • \$\begingroup\$ But my problem is that the RVO2 library won't compile (Visual Studio 2017). Do I need to use Unity or something for this to work? If so I might have problems (right now I'm using SDL and visual c++ for my test program). So, how for instance do I determine the boundaries of the velocity obstacle / reciprocal velocity obstacle? The math I found in their examples has me confused. \$\endgroup\$ – blip Jan 28 '17 at 0:18
  • \$\begingroup\$ @blip Added some details \$\endgroup\$ – Kromster Jan 28 '17 at 10:39
  • \$\begingroup\$ Okay, I found a YT video for ClearPath and I think I have an idea of how to implement this... my question now is how do I determine the closest velocity when adjusting movement? \$\endgroup\$ – blip Jan 29 '17 at 22:18
  • \$\begingroup\$ Thank you for the help! I got something working with velocity obstacles (programmed from the ground up). It has a few bugs to be worked out but it should work well enough for the project I'm working on. \$\endgroup\$ – blip Feb 5 '17 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.