Jump to content
  • Advertisement
Sign in to follow this  
chaosavy

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

This topic is 2516 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

[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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!