0
\$\begingroup\$

I wish I knew a better way to phrase this, but I want to make an object move from point to point inside a circle. But I also want that "circle" to bend around obstacles, so that no matter what path the object takes inside the circle, the maximum distance traveled remains constant.

To try and simulate what this shape might look like, I wrote a simple program that creates random lines from a center point to the edge of a circle that represents the maximum distance. If the line collides with an obstacle (represented by a smaller circle), it randomly changes direction until it no longer collides. Some of these lines get all the way around the obstacle, but leave a "shadow" behind the obstacle. So far, it looks like the size of the shadow is about equal to the size of the obstacle, but I'm not a good enough mathematician to prove it, or even to know how to describe this problem better.

Here is an image from my program so you can get some idea of what I'm talking about. enter image description here

This problem might be similar to that of calculating what's visible from a point, but I want the unit to be able to move behind the obstacle, so I think it's a little different.

EDIT: The shape reminds me of a cardioid.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

If you can discretize your navigation to a grid or other graph of small discrete hops, then you can use Dijkstra's algorithm to find all locations reachable within a fixed path distance budget of your starting point.

The finer your grid/graph, the more finely this will capture your shape, but also the more computation you'll need to spend traversing it. So you'd need to find the right balance for your game.

If you want a purely geometric solution without the grid/graph approximation, then as you suspected, you can adapt the method used for drawing visibility polygons.

It's easiest to think about with sharp, polygonal obstacles, so we'll start with that. As you sweep your "scanning beam" line around as described in the article above, you remember each time you hit two vertices in a row from different walls — that tells you there's a section occluded from a direct line-of-sight walk.

From this first scan, you'll end up with a set of triangles radiating out from your origin point. Clip them to pie wedges where they exceed your movement radius.

Now we'll come back to the vertices we remembered from the first pass, with those occluded regions behind them. We can run the same algorithm, just pretending our origin point is the nearer of the two disconnected vertices, and our path length budget is our original budget minus the path distance travelled to this vertex. Do the sweep again, over just the arc from the terminator of the previous visibility pass to the wall connecting to this vertex

Recursively sweeping visibility

Along the way, you may discover further occlusions, and continue recursing on them with reduced movement budget until the search bottoms-out at the limits of your path length budget, or when you hit no new vertices you haven't already visited with a shorter path.

Search completed

When you're done, you'll have a collection of clipped pie wedges describing your reachable area. Note that these can overlap — if you could go either left or right around a small obstacle, and the paths meet on the other side.

For curved obstacles, it's a bit trickier, so discretizing them into polygons may be easiest. But if you want a purely continuous solution, instead of drawing more pie wedges at points where they occlude the direct ray, you'd trace an involute curve, representing a path that hugs along the surface before moving away in a straight line along a different tangent.

Involutes tracing the edge of the reachable area behind a circular obstacle

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for this. I'd upvote, but I don't have the points. I think I'll start with djikstra's algorithm and see how that goes. \$\endgroup\$
    – circler
    May 23, 2021 at 16:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .