Restrict A* pathfinding to overlapping "safe zones" within map

Question

I've been bashing my head against this idea for a few days without luck, I'm hoping someone sees something I don't.

So I have a 2D map containing walls and obstacles, and I have a unit that navigates through it (A* and funnel algorithm). So far so good. Now, for gameplay purposes, I need to limit the movement of this unit to circular safe zones that I can place on the map. Think of them like cell towers, the unit has to stay within range of at least one tower, with the max range dictated by the tower (possibly different for each tower). Effectively, imagine drawing a set of interlocking circles over the map, and the unit must remain within that.

Now for the complicated part. The map is a constrained Delaunay triangulation, not a grid, so the triangles that A* is using can vary in size and shape. With a grid, I could imagine limiting individual grid cells by circle distances, but in my case these triangles could be larger than any one circle. There could even be cases where the start and end points of a path are within the same triangle, but because of the network of circles, an indirect path would have to be chosen to stay within the circles.

The only option I can think of involves adding these circles into the triangulation as additional edges, altering the map. This would mean rebuilding the map triangulation each time a player adds or removes these circles, and would require that I maintain a separate copy of that triangulation per player. And since these circles don't care about map walls, I'd have to alter my triangulation method to allow edge splitting and removal, to prevent overlapping lines from rendering the triangulation invalid.

I feel like there has to be another way to do this. I've considered:

• Running A* purely on the circles first, then placing that intermediate path on the map and re-pathing it to avoid obstacles.
• Finding all of the circle intersections between the start and end points, and treat those lines as portals that I must pass through, somehow altering the A* pathing to prioritize passing through them.
• Performing a regular path search on the triangulation, but forcing a dead-end whenever entering a triangle that is too far from a circle. Then refining that path to conform to the circles themselves.

Each of these have issues, or scenarios where they fall apart.

Has this been done before? Any input on how this might possibly be achieved would be appreciated.

Edit: Adding an image to show what I'm trying to accomplish. The red lines show the path that A* would generate using just the map triangulation. The green lines show the desired path, taking the circle bounds into account.

Answer 1

Your nodes in A* can be anything you want them to be. So you don't have to use either the circles or the triangles as your nodes. Each node can contain information about both:

Node(C, T) = portion of {circle C} overlapping {triangle T}

Now when you want to enumerate the neighbours of a given node, you search for...

• circles that overlap circle C in the same triangle:

  CircleNeighbours(C, T) = portion of {circle B} overlapping {triangle T}
...for each {circle B} overlapping {circle C}

• OR, edge neighours of triangle T that also overlap circle C:

  TriangleNeighbours(C, T) = portion of {circle C} overlapping {triangle R}
...for each {triangle R} overlapping {circle C}

By swapping just one member of the pair at a time like this, you're guaranteed that your path never leaves the safe circles, nor passes through an obstacle, nor contains a discontinuous jump.

Note that the nodes defined this way are always unique (a circle can never overlap a triangle in two disjoint places) and convex in shape, so they're still quite convenient to use as stepping stones of pathfinding.

And as a bonus, you don't have to do a bunch of complex spline math to construct the exact contours of all these nodes. Just computing that there is an overlap between these two circles (sum of radii vs distance) or this circle and that triangle (radius vs distance from triangle) is enough for the pathfinding algorithm to navigate the graph.

You can run A* on this pair-based node graph to find a sequence of neighbouring circle/triangle swaps connecting your origin and destination node.

Here's a visualization of that at work on your example image, where I've coloured each circle-triangle-pair node differently from its neighbours (but note that nodes can overlap, so that purple lens shape where a blue and pink circle meet is not a third node, just a region that's a valid part of either node)

Because each of these nodes is still convex, you can make an initial path by drawing a straight line from your current point to...

• The closest point on/in the neighbouring circle that's inside the same triangle (no-op if we're already inside that circle)

• The closest point on the segment of the neighbouring triangle edge overlapping our current circle

Granted, you'll need to modify your funnel algorithm to then pull this path straight. That part will be "left as an exercise for the reader" for now. 😉