Jump to content
• Advertisement

Working out best path around circle

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

Hi, First off I apologise if this is a simple problem, but I am unsure of the correct terms to google for an answer. I have a problem where agents approach an obstacle (a circle, defined as center point and radius), when the agent "see's" the obstacle, I wish for the agent to choose a correct direction based on the shortest path around the circle, and the path which would give the least deviation from its target. Here's an image to help explain my problem: As you can see the highlighted agent has seen the obstacle (the yellow circle is its "look distance", the agent is trying to get to a point ont he other side of the obstacle. At this point I think what I need to do is work out the lines which would touch the edge of the circle (the red lines) and then compare them to my desired direction in order to work out which direction would be the best. This is hopefully to solve a problem where my agents are walking right up to the edge of the obstacle and then taking their time to choose the correct direction. Any help or google terms, or pointers will be very appreciated. Thanks, Scott

Share this post

Share on other sites
Advertisement
Quick answer:

You're right about your red line segments. Now also draw similar segments from the goal point to the circle (I'll call them "magenta segments," simply because that's a color you haven't used). The optimal path will be composed of red segments, green arcs, and magenta segments.

More involved answer:

The "red segments" and "magenta segments" referred to above lie on the bitangents of the set

S = {OBSTACLE POINTS} [union] {GOAL POINT} [union] {START POINT}

(Note that all lines passing through an isolated point are tangent to it.)

Now, you can think about a graph whose vertices are the points at which bitangents graze obstacles, whose edges are (1) the bitangent segments between these vertices, and (2) arcs on the edges of obstacles between vertices; this is called the generalized visibility graph (or sometimes generalized reduced visibility graph)*, and you can simply do A* on it to find the shortest path.

Note that by "shortest path" I do not just mean the shortest path in the graph; I mean the absolute shortest path in your continuous domain!

*(The word "generalized" is used because in the early literature visibility graphs only considered polygons; when people started thinking about curved obstacles they because "generalized." When people realized that not all the edges that they used to think needed to be in the graph actually need to be, they started talking about "reduced" visibility graphs. Hence "generalized reduced visibility graph." That said, people often will leave out these adjectives nowadays.)

The reduced visibility graph for polygonal environments is described briefly starting on p. 261, in Ch. 6 of Steve LaValle's planning book. It only handles the polygonal case, and is a little brief, but it's the best free online reference I was able to find. IIRC, Principles of Robot Motion also has a good explanation.

Share this post

Share on other sites
Hi, thanks for the reply.

Unfortunately looks like I was digging down the wrong rabbit hole with this idea, I'm implementing it along side RVO's for agent local navigation, and it didnt really help.

I think a better solution may be something along the lines of giving the obstacle a pseudo velocity traveling towards the agent when the agents tests it for avoidance.

Thankyou anyway, Scott

Share this post

Share on other sites

• Advertisement
• Advertisement

• Popular Contributors

1. 1
2. 2
3. 3
Rutin
24
4. 4
5. 5
khawk
14
• Advertisement

• 11
• 11
• 23
• 10
• 9
• Forum Statistics

• Total Topics
633650
• Total Posts
3013123
×

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!