How to determine visibility in 2D

Question

Hello, I'm developing an AI sandbox and I would like to calculate what every living entity can see.

The rule is to simply hide what's behind the edges of the shapes from the point of view of the entity. The image clarifies everything:

I need it either as an input to the artificial intelligence either graphically, to show it for a specific entity while it moves..

Any cool ideas?

Answer 1

If you're using simple shapes to block the entity's view, there is an easy way to do this that I have implemented:

Create a VisionWave object which can move either horizontally or vertically. You can define a VisionWave using a source coordinate, two lines that intersect that point, and a distance from the source point.

You should have 4 waves: one going up, one down, one left, and one right, and the lines that define them should have a slope of 1 and -1 (i.e., an X). My crude drawing below shows one wave (going right) as represented by the > character.

  \     /
   \   />
    \ / >
     @  >
    / \ >
   /   \>
  /     \

Make a loop that propagates each wave one pixel at a time. When you propagate the wave, you want to do the following:

1. Mark every pixel that the wave is touching as visible.
2. If any of the pixels that the wave touches block light, then you want to split the wave into two, and recursively propagate each one.

I implemented a system like this in my Roguelike and it is very fast. Make sure to profile your code for bottlenecks.

If you're very clever you might try circular waves instead of straight lines, but I don't know if it would be faster due to the trigonometric calculations.

Answer 2

Determine which vertices are visible to your eye point, then project those vertices back away from the eye point on a straight line to make new vertices. Close the shape and you will have created a polygon representing the invisible area.

See shadow volumes for the 3D equivalent.