How to determine visibility in 2D

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:

alt 开发者_开发百科text http://img231.imageshack.us/img231/2972/shadows.png

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?

This isn't the fastest algorithm but it produces a polygon which might be useful for further analysis by your AI:

1. For each line segment, calculate the angle between the entity and the two endpoints.
2. Sort the points by angle.
3. “Sweep” around 360°, keeping track of which line segments intersect with the sweep line. When you cross the beginning-of-segment point, you add that segment to the set; when you cross the end-of-segment point, you remove that segment from the set.
4. The closest line segments form a polygon of what's visible. The polygon is the union of triangle slivers.

I realize this explanation isn't great, but I have an online demo here that you can play with to get a sense for how it works. Extending it to work with circles probably isn't too bad (famous last words).

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.

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.