Designing my own rather than picking one of the existing ones was not a decision I undertook lightly. There were several listed on roguebasin, and Restrictive Precise Angle Shadowcasting, as well as Precise Permissive Field of View were of particular note. However, I wanted something more than just a FOV algorithm. I wanted a solution that would also calculate cover for the purpose of lighting, and stealth and ranged combat mechanics.
There were several requirements. First, LOS needed to be symmetrical, i.e. if the target can see you, you can see the target. However, the amount by which each is seen can vary, to simulate, for instance, peeking around corners. In such a circumstance the actor doing the peeking would have a relatively slim chance of being spotted, and would benefit more from stealth, as well as having additional protection against ranged attacks. Second, it should work with both hex and square grids. Most existing algorithm implementations are designed for square grids, so this requirement made building one from scratch a good alternative. Third, it should not assume a point origin, but instead consider that the actors can be at any point in their respective tiles. This is a requirement that most current FOV algorithms do not meet, as they assume that the observer is at one point within a tile. It must be pointed out that Permissive Field of View does consider this, but it still doesn't compute cover.
When trying to come up with something that would satisfy these requirements I have hit a number of dead ends. One that worked rather well was a sampling approach. It would draw segments through the observer's tile as well as each target tile within a certain radius that would be perpendicular to the angle of view. It would then place n points on each tile, and compute which of the n points of one tile were unobstructed from each of the other tile's points. This produced very pleasing and relatively accurate results even with n as low as 5, and had the benefit of computing FOV for both tiles. The downside was that it was painfully slow, though this was partially due to the implementation being done in Python. With 5 sample points and a radius of 6 (distance computed as sqrt(x^2+y^2+xy) in hex coordinates) it would take at least a minute. With more points it would take considerably longer. While rewriting it in C++ would probably make the performance tolerable, I felt that I could arrive at a solution that would scale much better, without resorting to sampling and thus being more accurate.
My answer lay in vector algebra, and relied on the properties of the cross product of two vectors. In particular, the cross product of two vectors is negative if the second vector is to the right of the first, and positive if it is to the left. Moreover, by constructing a unit vector coming from the observer and crossing it with the vector to the target, the amount by which it is off can be directly translated into the amount of cover! To clarify, by representing the shadow-projecting area source as a pair of unit vectors positioned on the circumference of the observer's tile, we can treat any tile as covered if it is fully covered by the area that is bound by these two vectors. That is, if the target tile is fully left of the right-side vector, and fully right of the left-side vector, then we know it is fully in cover. Similarly, if the cross product of either of the unit vectors with the respective sides of the target tile has a magnitude between 0 and 1, we know we have partial cover. The computations get a little tricky with angles approaching 180 degrees and also reflex angles, but this is basically the gist of it. The algorithm mostly involves iterating over tiles arranged by distance, and forming new -- or extending existing -- vector pairs from any tiles that are construed as walls, i.e. block line of sight. The algorithm is relatively slow for a "forest" of tiles with infinite sight radius, but fairly quick for a more cave-like structure. By migrating the entire algorithm into C-land and adding caching further performance gains could be reached, while maintaining an extremely precise cover calculation mathematically.
Here's a screenshot of the FOV in action, also showcasing the (unoriginal) cave generation algorithm (to be discussed later).
No comments:
Post a Comment