Jump to content
  • Advertisement
Sign in to follow this  

3D collision avoidance: finding the updated velocity vector (outside the “collision-velocities” cones)

This topic is 972 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all, my first post here!

First of all, let me notify (and explain) you that I have posted this question in gamedev.stackexchange a month ago, with no answers or comments at all so far. Now, when having to go back to the problem, I thought that these forums here might be a better suited place for the insights such a question might need.

So, I am trying to understand and implement the mechanism of a fully 3D collision avoidance (steering behavior) system for flight movement (six degrees of freedom), currently focusing on circumventing static obstacles (all with the shape of a sphere).

However, I don't quite get how to figure it out the new velocity vector of the moving agent. The figure below illustrates the scene. The moving agent (green) has to steer three static objects (blue). The red line represents the initial ahead velocity vector.


Notice that there are also three white/semi-transparent cones. These represent the "forbidden velocity vectors" regarding each obstacle. It means, the set of velocity vectors that, if used as the new ahead vectors of the agent, would make the agent collide with one or more of the obstacles (also note that the radius of each cone is equal the radius of the given obstacle plus the radius of agent, so to allow an offset for the player to maneuver around).

In order to find out the new ahead vector of the moving agent in such 3D environment, considering the three obstacles, a naïve approach would be to simply port to 3D the classic solution explainedin this often cited article and exemplified by the following 2D image:


There, a new velocity (orange arrow) is simply calculated by normalizing the minimum distance (black arrow) between the original velocity and the center of the obstacle and then multiplying such normal by the sum between the radius of the obstacle and the radius of the moving agent. Then, an average of the new velocities calculated for each of the obstacles would give the total final velocity.

In many cases, that is sufficient. However, take a look at the cases below (exemplified in 2D to ease visualization):


In all of them, the naïve approach will result in a collision. In a and b, the final new velocity will coincide with the original velocity (red arrow) and the moving agent will move forward despite being partially or fully blocked. In c) and d), the new velocity (orange arrow) will still result in the same consequence.

So, my question is: what is the most computationally efficient way to find out the new ahead vector of the moving agent in such 3D environment, considering the three obstacles, in a way that avoids collision? Or, in other words, the new ahead vector that:

1) is not inside any of the cones;

2) is the closest possible to the original ahead vector (red line in the picture).

As a final note, I should stress that I am not looking for a library, I am looking to learn how to achieve that - either in conceptual and in coding terms alike.

Share this post

Link to post
Share on other sites
Just off the top of my head, the math seems wrong here. Your final corrected vector should shorten to reflect an imminent collision, not stay at the same magnitude as the input vector.

Another trick is to scale the vector away from the obstacle non-linearly, based on how close you are in both space and time. Say you have an obstacle directly in front of you and you're one tick away from impact. The correction math should work out such that your desired velocity is pointing away from the obstacle, i.e. almost exactly the negative of the input vector.

This holds true in 2D as well as 3D.

In my experience as long as your obstacles are sparse, it's actually easier to do steering avoidance in 3D because you have an extra dimension to try and "escape" along.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!