Beginning in b43, T-Engine has a new field of vision (FoV) algorithm: "Large Actor Recursive Shadowcasting FoV algorithm", or "Large Ass FoV" for short. This article will explain what it is and how to use it. Perhaps the main selling point is that it can offer symmetric
FoV with variable permissiveness (Note: it also offers asymmetric FoV).
Quick overview: Large Ass FoV is a significant enhancement of the standard recursive shadowcasting algorithm (which I'll describe later), and it has two tunable parameters that control (1) the level of permissiveness (how much or little is seen beyond an obstruction) and (2) the level of symmetry (if I can see you, can you see me?). For the lowest
level of permissiveness and lowest
level of symmetry, Large Ass FoV is virtually equivalent to the standard recursive shadowcasting algorithm that ToME currently uses. For the highest
level of permissiveness and highest
level of symmetry, it is equivalent to Digital FoV. And, Large Ass FoV can be anything in-between (because the parameters are floating point numbers).
Here is a diagram:
large_ass.png [ 46.89 KiB | Viewed 6229 times ]
Large Ass FoV may be characterized as follows:
- "Vision Size" may range from 0.0 to 1.0. The source actor is a single point in the center of the tile when set to 0.0, and a full-width diamond when set to 1.0.
- "Permissiveness" may range from 0.0 to 1.0. An obstruction is a full-width square when set to 0.0, and a full-width diamond when set to 1.0.
- A visibility region of a tile is a full-width diamond (as shown above).
- Visibility and targetability are equivalent; you can shoot an enemy if and only if you can see it.
- A tile is visible (and targetable) if there is a finite-width cone that intersects with the source actor and the visibility region of the tile. In other words, there must be more than one line or ray that intersects with the source actor and the tile visibility region.
- Line of fire (i.e., the path a projectile will take) attempts to go from the center of the source tile to the center of the target tile. Specifically, it minimizes the distance squared from the line to the center of the source and destination tiles.
The standard recursive shadowcasting algorithm differs only slightly from the above. Specifically, (1)
"Vision Size" is always 0.0, because the source actor is a point source; and (5)
a tile is visible if there is a single line
or ray from the source actor that intersects with the visibility region. Therefore, for Large Ass FoV to behave the same as standard shadowcasting, permissiveness should be set to a small, non-zero number, such as 0.01. Finally, the original
shadowcasting algorithm didn't have (2)
(variable permissiveness), but the standard shadowcasting algorithm in T-Engine has had this for a long time.
Below shows a consequence of characteristic (5)
(finite-width cone) when permissiveness is 0.0:
large_ass_pinched.png [ 11.25 KiB | Viewed 6229 times ]
If permissiveness were instead 0.01, then the tile that says "Not Seen!" would again be visible.
T-Engine also has a hexagonal implementation of the standard recursive shadowcasting algorithm. It now has
Large Ass FoV implemented for hexagonal grids, and the simple diagram below shows what it is (Note that it doesn't (yet) have a "permissiveness" setting, because it would add too much complication for too little gain):
large_ass_hex.png [ 62.08 KiB | Viewed 6229 times ]
Alright, to configure a module to use Large Ass FoV and tune parameters, add the following to the module's "load.lua":
core.fov.set_algorithm("large_ass") -- or "large_actor_recursive_shadowcasting"FAQQ
core.fov.set_permissiveness(val) -- 0.0 for least permissive, 1.0 for most permissive
core.fov.set_actor_vision_size(val) -- 0.0 for least symmetric, 1.0 for perfectly symmetric
: Are there any known asymmetries?A
: No. There are currently no known asymmetries
when actor_vision_size is set to 1. I performed rigorous testing for various levels of permissiveness for vision ranges up to around 50. Floating point errors causing asymmetries will eventually
appear for very large vision ranges (I don't know how large, because I haven't observed any asymmetries yet), but the algorithm should be regarded as perfect for vision ranges reasonable for roguelikes: less than 50 or so.Q
: How does the speed
of Large Ass FoV compare to other symmetric FoV algorithms? A
: Performance-wise, Large Ass FoV should be very competitive, but direct comparisons have not yet been done. It is fast enough that one shouldn't worry about possible marginal improvements or slowdowns.Q
: How does the behavior
of Large Ass FoV compare to other symmetric FoV algorithms?A
: As I said above, when permissiveness is 1.0 and actor_vision_size (a.k.a. symmetry) is 1.0, it is equivalent to (a correct implementation of) Digital FoV, which treats all actors, obstructions, and tile visibility regions as full-width diamonds. Another symmetric algorithm is Precise Permissive FoV, which treats all actors, obstructions, and tile visibility regions as full-width squares. From its description on Roguebasin: "a destination square is visible if and only if there is an unobstructed line from some point in the source square to some point in the destination square". Large Ass FoV can have obstructions as full-width squares, but actors must be diamonds. On a general note, Digital FoV and Precise Permissive FoV are both regarded as being very
permissive, and the high degree of permissiveness is often cited as the least liked or desired characteristic of these algorithms. Large Ass FoV, on the other hand, can be less
permissive than either of them by setting permissiveness to 0.Q
: Has this algorithm been implemented before?A
: Not to my knowledge. If I am incorrect, then please notify me and I will give due credit. There appear to be similar algorithms, but nothing that matches the generality and flexibility of Large Ass FoV.Q
: Why not? (i.e., why hasn't this algorithm been implemented before?)A
: Oh, I'm sure I'm not the first one to think of it. After all, it appears to just be a "simple improvement" to the standard recursive shadowcasting, right? Ha! Implementing it isn't the same as thinking it up, and, as I learned, implementing it turns out to be very non-trivial.Q
: Where is code for the algorithm located?A
: It is included in the source of T-Engine. The main algorithm is located in file "src/fov/fov.c" and is currently near lines 560 through 870 (and 1600 through 1850 for "smart LoS"). If you value your sanity, though, I would recommend that you never, ever look at it!Q
: Why "Large Ass FoV"?A
: "Large A
hadowcasting". Okay, so it's not quite a perfect acronym--what are you going to do to me?! I had to code this up, discuss it, and write about it, so I needed a shorter name, and nothing better came up. And, yes, the pun is on purpose: another way to view this algorithm is that all actors have large asses and are easily hit. This is because although the vision size of a source
actor may be any size, the size of a target
actor is always the full-width of the tile. Large. Ass.Q
: What terrain configurations were difficult to handle during development of the algorithm?A
: *edit: see image below*
Huh, wow, good question. I'll get back to you. If some brazen soul wants to code this up himself or herself, then there are a couple tricky configurations that would be best to know about from the start.Q
: Will the size of a target actor ever be configurable?A
: Ssssssssssshhhhhhhhhhhhhhhhhhhhhhhhhh!*edit: moar*Q
: Where can I learn more about FoV algorithms?A
: I can't guarantee any of these links will actually help you understand FoV any better:http://roguebasin.roguelikedevelopment.org/index.php?title=Category:FOVhttp://roguebasin.roguelikedevelopment.org/index.php?title=Discussion:Field_of_Visionhttp://roguecentral.org/libtcod/fov/fov.pdf
You may also search for FoV and Field of Vision/View in the rgrd newsgroup. There were many discussions about FoV in 2007 through 2009 (and earlier), which, while occasionally interesting, probably aren't all that useful:http://groups.google.com/group/rec.games.roguelike.development/topicsQ
: This is a Field of Vision algorithm. What about Line of Sight (LoS)?A
: Indeed, FoV and LoS are different things. LoS is used to determine whether tile A is visible from tile B, and the specific path a projectile will take. All FoV algorithms in T-Engine are also adapted to LoS algorithms, so FoV and LoS will always be self-consistent whenever you make an algorithm or configuration change.Q
: Is this algorithm easy to implement from scratch?A
: Can the algorithm be modified to do XXX?A
: Possibly. Ask, and if you are serious about creating a module that requires XXX, then we can try to work together to implement it.Q
: I want a symmetric algorithm, but Large Ass FoV is still too permissive for my tastes when permissiveness is set to 0. Can an algorithm be symmetric and even less permissive?A
: Yes... but it comes at a cost (and that algorithm won't be Large Ass FoV). The cost may be that what is visible may not necessarily be targetable, or vice versa. Visibility, targetability, projectile paths (possible trick shots), etc. can become fuzzy when you try to make a symmetric algorithm with low permissiveness. There are many (partially-finished) roguelikes out there, and several of the developers hacked together their own FoV algorithm into something that was "good enough" for them. I'm sure some of these had symmetric FoV as well as exploits and other sins. Are there any *good* algorithms that are symmetric, but aren't very permissive? Not to my knowledge... or at least not yet...Q
: Do you plan to create any other FoV algorithms?A
: Yes. Two others are currently planned and partially implemented: Savvy FoV and THE LAST FoV. I don't know when I'll be able to finish them, but the end is in sight.Q
: Do you plan to directly compare the performance and behavior of the algorithm to other existing algorithms?A
: Perhaps at some point. Any help in doing so would be appreciated. This isn't a high priority for me at the moment, but it would be nice to compare the performance of this to other algorithms in, for example, libtcod (http://doryen.eptalys.net/
And, finally, here are more images:
digital_fov1.png [ 14.86 KiB | Viewed 5977 times ]
This image shows that Large Ass FoV and Digital FoV are indeed equivalent, because neither of the "?" tiles should be visible in either algorithm.
digital_fov2.png [ 38.69 KiB | Viewed 5977 times ]
This shows a more complicated configuration and all the funky ray traces. The "A" beam needs to keep track of upper obstruction 9, and lower obstructions 3 and 5. The "B" beam needs to keep track of upper obstruction 6, and lower obstructions 1 and 9. The "C" beam needs to keep track of upper obstructions 2, 4, and 10, and lower obstructions 7.