3
\$\begingroup\$

I have a game grid and I need to figure out which game grid points are not behind occupied grid point from players view. The visible points. I'd like to define a visible point first, because it can mean many things and I had to figure it out:

  • I call a point visible point if lines from refference point's centre to two closest point's corners do not intersect with any occupied point. On image bellow, illustration shows invisible in orange, visible in green.
    image description

By this definition, we can make a map like this:

image description

Legend:

  • image description - visible pixel
  • image description - partially visible pixel
  • image description - occupied pixel
  • image description - player

I'm not interested in partially visible pixels, but I need to find out which pixels are visible. I don't know where to start. My only idea was to loop angles, but that doesn't work on larger map, where one iteration skips many actual pixels.

How do I check the visible pixels, or ideally, only the furthest visible pixels, as on this map:

image description

And looping through all pixels must be probably avoided, that would eat up too much performance.

\$\endgroup\$
2
\$\begingroup\$

The trick is to cast rays from the source point to the edges of occupied squares.

Then sort the rays by their angle. You then 'sweep' those angles and cull the pixels that are behind the intersection points. There are ways to optimize the algorithm by removing rays that have multiple intersections, as these rays will always be between rays that have only one intersection point.

See also my answer on a similar question: 2D - Smooth lighting with shadows for a tile-based game

And an example of the algorithm in a polygon environment: http://ncase.me/sight-and-light/ The theory is also easily applied to a grid, since that could be represented by bunch of square polygons.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.