Sign in to follow this  

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

This topic is 667 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.

QIGTN.png

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:

ib748.png

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):

lEDAn.png

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

This topic is 667 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this