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.