Introducing: Large Actor Recursive Shadowcasting FoV algo

[tiger_eye]

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 18083 times

Large Ass FoV may be characterized as follows:

1. "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.
2. "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.
3. A visibility region of a tile is a full-width diamond (as shown above).
4. Visibility and targetability are equivalent; you can shoot an enemy if and only if you can see it.
5. 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.
6. 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 18083 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 18083 times

Alright, to configure a module to use Large Ass FoV and tune parameters, add the following to the module's "load.lua":

Code: Select all

core.fov.set_algorithm("large_ass")  -- or "large_actor_recursive_shadowcasting"
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

FAQ

Q: 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 and rarely 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 Actor Recursive Shadowcasting". 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. ... tegory:FOV
http://roguebasin.roguelikedevelopment. ... _of_Vision
http://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.game ... ent/topics

Q: 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: Nope!

Q: 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 17831 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 17831 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.

[chezzo]

Tiger_eye, man this is awesome. I am really glad you are working where you are, which is for this engine, instead of where you should be, which is a goddamned aeronautical institute where you would be in charge of being smart.

You gave a very good description. When I first learned of this, I was a little confused. Then you cleared it up, and I sort of got it. But now I totally get it and could teach it. But where is it implemented!? I heard this part:

Code: Select all

core.fov.set_algorithm(val)  -- "large_ass" or "large_actor_recursive_shadowcasting"
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

If I wanted digital perfect FOV, would I do this in load.lua?

Code: Select all

-- Birther descriptor
Birther:loadDefinition("/data/birth/descriptors.lua")

-- Large Actor Recursive Shadowcasting FoV
core.fov.set_algorithm(1)  -- "large_ass" or "large_actor_recursive_shadowcasting"
core.fov.set_permissiveness(1)  -- 0.0 for least permissive, 1.0 for most permissive
core.fov.set_actor_vision_size(1)  -- 0.0 for least symmetric, 1.0 for perfectly symmetric

What would be the negatives to setting this puppy to 1 for everything, making digital perfect FOV? Would it slowdown the engine at all?

I am so glad this is built into the engine, so I didn't have to code it. I wouldn't even know where to start. Tiger_eye is a man, a mystery, and a legend.

[tiger_eye]

Hahaha, thanks, Chezzo, that was great

If I wanted digital perfect FOV, would I do this in load.lua? [...]

Yeah, that's the right place, and you had it pretty much correct (one can reference an algorithm by its enumerated integer--as you did--but a string should probably be preferred):

Code: Select all

core.fov.set_algorithm("large_ass")  -- or "large_actor_recursive_shadowcasting"
core.fov.set_permissiveness(1.0)  -- 0.0 for least permissive, 1.0 for most permissive
core.fov.set_actor_vision_size(1.0)  -- 0.0 for least symmetric, 1.0 for perfectly symmetric

Note that this isn't implemented yet for hexagonal grids, but I plan to complete it in time for v1. Once available for hex grids, you would add the following line to the above:

Code: Select all

core.fov.set_vision_shape("hex")  -- core.fov.set_algorithm("hex") also works for backwards compatibility

What would be the negatives to setting this puppy to 1 for everything, making digital perfect FOV? Would it slowdown the engine at all?

Nah, it shouldn't slow things down, because it's designed to be efficient. Perhaps the main negative to setting everything to 1 is it results in very permissive FoV (which is perfectly okay, of course, if it's what you want). Note that if "actor_vision_size" is set to 1, then the algorithm will be symmetric regardless of what "permissiveness" is set to.

[Canderel]

Could you post us some images displaying how big obst ructions are in tome. And thr size of actors.

Does actor size impact its fov?

Could we implement different obstruction sizes for different obstructions? Like make trees an dpillars less obstructive as walls?

[tiger_eye]

Canderel, ToME is currently using actor_vision_size = 1 (so it's symmetric--actors are full-width diamonds) and permissiveness = 0 (so it's the least permissive possible--obstructions are full width squares).

Could we implement different obstruction sizes for different obstructions? Like make trees an dpillars less obstructive as walls?

Yeah, that would be straightforward to do. We would need to add another callback to Lua from C, which I'm hesitant to do unless it's actually needed.

Now I'd like to show some comparisons between Digital FoV (and Precise Permissive FoV) and Large Ass FoV (actor_vision_size=1, permissiveness=0) for a single pillar:

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
....................x..........  ..............xxxxxxxxxxxxxxxxx
...................x...........  .............xxxxxxxxxxxxxxxx..
..................x............  ............xxxxxxxxxxxxxxxx...
.................x.............  ............xxxxxxxxxxxxxx.....
................x..............  ...........xxxxxxxxxxxxxx......
...............x...............  ..........xxxxxxxxxxxxx........
..............x................  ..........xxxxxxxxxxxx.........
.............x.................  .........xxxxxxxxxxx...........
............x..................  ........xxxxxxxxxxx............
...........x...................  ........xxxxxxxxx..............
..........x....................  .......xxxxxxxxx...............
.........x.....................  ......xxxxxxxx.................
........x......................  ......xxxxxxx..................
.......x.......................  .....xxxxxx....................
......x........................  ....xxxxxx.....................
.....x.........................  ....xxxx.......................
....x..........................  ...xxxx........................
...x...........................  ..xxx..........................
..x............................  ..xx...........................
.#.............................  .#.............................
@..............................  @..............................

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
..............................x  .......................xxxxxxxx
............................x..  .....................xxxxxxxxxx
..........................x....  ....................xxxxxxxxxxx
........................x......  ..................xxxxxxxxxxxxx
......................x........  .................xxxxxxxxxxx...
....................x..........  ...............xxxxxxxxxxx.....
..................x............  ..............xxxxxxxxx........
................x..............  ............xxxxxxxxx..........
..............x................  ...........xxxxxxx.............
............x..................  .........xxxxxxx...............
..........x....................  ........xxxxx..................
........x......................  ......xxxxx....................
......x........................  .....xxx.......................
....x..........................  ...xxx.........................
..#............................  ..#............................
@..............................  @..............................

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
...............................  ............................xxx
..............................x  .........................xxxxxx
...........................x...  .......................xxxxxxxx
........................x......  ....................xxxxxxxxx..
.....................x.........  ..................xxxxxxx......
..................x............  ...............xxxxxxx.........
...............x...............  .............xxxxx.............
............x..................  ..........xxxxx................
.........x.....................  ........xxx....................
......x........................  .....xxx.......................
...#...........................  ...#...........................
@..............................  @..............................

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
...............................  ............................xxx
............................x..  .........................xxxxxx
........................x......  .....................xxxxxxx...
....................x..........  ..................xxxxx........
................x..............  ..............xxxxx............
............x..................  ...........xxx.................
........x......................  .......xxx.....................
....#..........................  ....#..........................
@..............................  @..............................

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
........................x......  ....................xxxxxxxxxxx
.......................x.......  ...................xxxxxxxxxx..
......................x........  ..................xxxxxxxxxx...
.....................x.........  .................xxxxxxxxxx....
....................x..........  ................xxxxxxxxxx.....
...................x...........  ................xxxxxxxx.......
..................x............  ...............xxxxxxxx........
.................x.............  ..............xxxxxxxx.........
................x..............  .............xxxxxxxx..........
...............x...............  ............xxxxxxx............
..............x................  ............xxxxxx.............
.............x.................  ...........xxxxxx..............
............x..................  ..........xxxxxx...............
...........x...................  .........xxxxx.................
..........x....................  ........xxxxx..................
.........x.....................  ........xxxx...................
........x......................  .......xxxx....................
.......x.......................  ......xxx......................
......x........................  .....xxx.......................
.....x.........................  ....xxx........................
....x..........................  ....xx.........................
...x...........................  ...x...........................
..#............................  ..#............................
...............................  ...............................
@..............................  @..............................

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
..............................x  .........................xxxxxx
...............................  ........................xxxxxxx
...........................x...  .......................xxxxxxxx
...............................  ......................xxxxxxxx.
........................x......  ....................xxxxxxxxx..
...............................  ...................xxxxxxxx....
.....................x.........  ..................xxxxxxx......
...............................  .................xxxxxx........
..................x............  ...............xxxxxxx.........
...............................  ..............xxxxxx...........
...............x...............  .............xxxxx.............
...............................  ............xxxx...............
............x..................  ..........xxxxx................
...............................  .........xxxx..................
.........x.....................  ........xxx....................
...............................  .......xx......................
......x........................  .....xxx.......................
...............................  ....xx.........................
...#...........................  ...#...........................
...............................  ...............................
@..............................  @..............................

Code: Select all

  Digital/Precise Permissive              Large Ass FoV
...............................  ...............................
@#xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  @#xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Note that by changing the permissiveness parameter, Large Ass FoV can behave as shown in the left column, right column, or anything in between. Also note that a single pillar can provide some cover, which I think is important for gameplay.

For posterity, here is also a link to a post that provides a history of FoV and LoS:

http://forums.te4.org/viewtopic.php?f=38&t=35864

[jenx]

Wow. Barely understood most of this thread. But it looks impressive

[jinsediaoying]

Amazing algorithm!
I'm also curious about Savvy FoV and THE LAST FoV system you mentioned.
Are they done? What are the key features of them?