# Have the concept - but need help to express it mathematically (object avoidance)

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

## Recommended Posts

[attachment=6762:illustration.jpg]

Hey guys, I'm trying to avoid the red object for my 3d space sim/rts project.

I cast a ray from the starting position to the go to position.
My physics engine tells me the hit point and the normal of the triangle intersected.

My goal is to travel along the normal at the hit point (away from the obstacle), for about a quater of the obstacle's size, then travel perpendicular to the normal for about a quater of the obstacle's size (this is the green line aproximation from the start position), then re-check the ray again.

Problem is: I have no idea how to express this mathemtaically (actual formulas, math involved).

Essencially:
How do I use the normal and the hit position to get a position away from the obstacle in 3D?
When I have that position: How do I use the obstacle's center position, the hit position and size (or whatever else) to determine where to go from there?

I hope I'm not using some terms incorrectly or a faulty method... any help is greatly appreciated.

##### Share on other sites
Thinking about this a bit more: I think what it boils down to is how do I use the direction vector (the normal of the hit surface) to generate a positional vector - the new go to position?

##### Share on other sites
Rotate normal vector by 90 degrees and you'll have your green line.
I'm not sure how this would work for complex triangle meshes, but if you loop this algorithm it should manage to go around basic shapes (box, sphere, ...), I think might work for convex mesh too, just have to be sure destination isn't inside collision object.

##### Share on other sites
I think I pretty much figured it out. Googled enough vector and normal definitions online to get it to work. Not sure exactly how, did a bunch of tests and it seems fairly stable.

I've used the cross product math with the help of a "UP Y" vector and hte normal so I'm guessing this is what you are refering to.

Anyway it seems to work

##### Share on other sites
You can still get stuck in concave obstacles.
Suppose you have a more or less spherical cave with one small opening; you are inside, near the bottom, and you suddenly want to go somewhere beyond the bottom of the cave.
The correct pathfinding would be exiting the cave, directly away from the target location, then turning sideways and navigating around the more or less convex exterior of the cave.
Instead, your algorithm makes you follow the interior of the cave, more or less tangent to the interior surface, for a little while; then the direction of the movement, instead of following the cave (which would be longer than the shortest path but acceptable), turns back because you are on the opposite side of your target. You mill around near the interior point of the cave that is closest to the destination, never leaving the cave because you never come close to the exit.

Maybe you can decompose the free space into convex regions and treat the borders between such regions as portals that your path has to cross; in the cave example, you would figure out that you have to reach the cave entrance first and not re-enter the cave after you pass it (as if it were a solid obstacle).

##### Share on other sites
Good points, but I don't think i have to worry too much, if there's a hollow asteroid or some such then the player can manually fly in and fly out. The AI won't have to do any sort of complex path finding, just mostly obstacle avoidance.

##### Share on other sites
Obstacle avoidance can be achieved with steering behaviors.
http://www.red3d.com/cwr/steer/

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 21
• 21
• 11
• 25