2
\$\begingroup\$

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: enter image description here

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

# # # # #

3 3 3 3 # 4

2 2 2 # 3 4

1 1 1 2 3 4

1 X 1 # # 4

1 1 1 #

# # #

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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) \$\endgroup\$
    – DMGregory ♦
    Commented Apr 24, 2017 at 22:50

1 Answer 1

Reset to default
1
\$\begingroup\$

Place the origin z at what you call the "unit." In that coordinate system, list all the vertices of your objects. Sort them angularly about z. Walk through the sorted list, and determine whether you are (a) just now entering an obstacle, (b) already inside an obstacle, or (b) just now leaving an obstacle. You can intersect a ray with the relevant object to decide. Then you have determined a star-shaped polygon centered on z representing the visible region.

*shaped
Wikipedia image.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for that answer, but i give the visibility Polygons a try. \$\endgroup\$
    – LuaNoob
    Commented Apr 27, 2017 at 9:35
  • \$\begingroup\$ @LuaNoob: What I described is a visibility polygon. \$\endgroup\$
    – Joseph O'Rourke
    Commented Apr 27, 2017 at 10:39
  • \$\begingroup\$ Well DMGregory already told me about those, so why twice then? And your Description is a bit hard to read, also you talk about star shaped polygons, why not say visibility polygons? \$\endgroup\$
    – LuaNoob
    Commented Apr 27, 2017 at 10:42

You must log in to answer this question.

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