So you have these two shapes, right? One of them is the guy who can see, and the other a bitter enemy who blocks his line of sight.
Stretched between their centres, where their souls live, is an imaginary line.
The red blob is our protagonist, and the blue hexapod an enemy of his sight.
Perpendicular to that line, is another imaginary line
For each point of the hexepod, we want to find where it falls on that line. Or, to calculate the distance from the point to another point on the original line.
Also the line made by those two points should be perpendicular to that original line.
The point at the greatest distance, on each side of the line, is the point we will use when drawing the occlusion shadow. Here, Karl pointed out a problem: Our algorithm assumes parallel vision lines, and so the approach will break down as a shape nears a source, especially if that shape is much larger and irregularly shaped. In many cases, this shouldn’t pose too much of a problem.
Well. In some cases. In the case blogged earlier, at least.
The green dots are the min and max points.
The min and max points are the ones we use to calculate the blocked area. We can draw the lines from the centre of the guy to the points in question, and all we have to do now is extend those lines from the points until they are off the screen.
That is all. Also there are probably some neat optimizations we could implement, especially if the world is based on tiles. Any objects contained within tiles in darkness could easily be excluded from calculations – which would work even better if we first sorted the list of objects by proximity to the character. We could discard any points that lie on tiles which couldn’t possibly hold the most distal points. And if we have control over objects, we could return only points that could possibly block sight.
Your friend,
Brad
With pictures even!
I like this algorithm. It is simple and effective. I probably, presented with the same problem, would’ve done something way more complicated and ended up with a huge mess that never would’ve worked. Props!
Those are slick looking example images — did you make those in flash?
I was thinking for the inaccuracy problem to draw an imaginary line from the viewer to each point, and find the two points which made the largest angle with the centerline. This could be optimised by comparing for the smallest dot products, since dot product ~= cos(angle).
I am wondering if there is a game using this algorithm that at some point we might see. This would be quite exciting.
That solution sounds cool! Also I made the images in Adobe Photoshop Image Something Software, because I was lazy