# Best way to get the maximum moveable Area

I was thinking about creating a polygonal area, for a given unit, in which it can move with a given range (radius) but with care for obstacles.

Here is a picture to visualize my idea:

My Ideas so far...

# The Pathfinding Way

• Create a Circle around 'unit' with given 'radius'
• Check for intersections with obstacles
• If an intersection is found, create a Path from 'unit' to intersectionPoint, but with pathLength == 'radius'
• connect all endPoints to get the maximum moveable area
• But what if no intersection is found because the obstacle is fully into the circle?

# The Ray Way

• Cast #Rays into all directions (e.g. 8 Rays for N, NE, E, SE, S, SW, W, NW) from 'unit'
• Check for intersections between each Ray and the obstacles
• If an intersectionPoint is found, create a Path from 'unit' to rayEndPoint with pathLength == 'radius'
• connect all endPoints to get the maximum moveable area
• But this needs more than 8 rays to be accurate enough and this will take calculation time

Have you got an idea on how to do this the best way? Thanks in advance - LuaNoob

Edit #1:

# The Flood Fill Way

Read something about flood filling algorithm. I guess this will be the best thing to try.

Example for maximum moveable range = 4

• 'X' = unit
• '#' = wall

Edit #2:

# Current attempt: Custom Visibility Graph (not tried yet)

I now got i to work to create fast and accurate visible Areas. What im gonna to do next is:

• try to find the first point on the obstacle, that is in a line of sight by 'unit' and the not reachable endPoint of the Visibility-Ray-Cast
• create a new Visibility Graph from there but with 'newRadius' = 'radius' - distance(unit, firstPointOnObstacle)
• connect the Points
• repeat it for every not reachable Point with custom 'newradius'
• One Problem left: Holes cant be created, but these are the rarest occuring situations, where i can fit with
• I'd recommend reading up on visibility polygons, as they solve a similar problem, at least along the near face of the occlusion. In the linked article, the problem of ray density is solved by firing rays only at obstacles' vertices, skipping uninteresting areas in between (any edge crossings in these zones can be caught by your circle intersection step) Commented Apr 24, 2017 at 22:50