Implement Symmetrical FOV Algorithms

[tckerr]

Edit: forgot to mention how much I'm enjoying using this library. Makes roguelike development so much easier, so thanks!

Version: 2.6.4

It's possible I'm doing something wrong, or have the improper expectations, but using the following code:

private FOV CalculateFov(IMapView<bool> visibleMap, Coord coord)
{
   var fov = new FOV(visibleMap);
   fov.Calculate(coord, 6);
   return fov;
}

I am getting inconsistent results based on the placement of my entity. You'll notice that in position A, I cannot see position B, however in position B, I can see position A.

I'm thinking about using a different algorithm for calculating FOV in the meantime. But I'm curious -- Is this expected?

A

B

[Chris3606]

GoRogue FOV uses shadowcasting, and unfortunately shadowcasting (at least as traditionally implemented) is not a fully symmetric algorithm; so if you have two positions A and B, unfortunately it is expected behavior that B may be visible from A, but not A from B in some cases.

There are algorithm implementations (even of shadowcasting specifically) that are symmetric (or at least, more-so), however in my past experience they typically come at a noticeable performance cost. Even so, I would like to provide symmetric options for FOV in GoRogue, for cases where the loss in performance is acceptable.

One option is to either modify the existing shadowcasting algorithm, or create a derivation, that is in fact symmetric. An example of how to do that can potentially be found here. I haven't fully verified it, and that article has what in my opinion are some pretty strong claims about what "correct" looks like, but in any case does provide a potentially reasonable means of implementing shadowcasting in a more symmetric way.

Speaking of performance, I will note that very frequently recreating FOV structures like you're doing may lead to performance issues; although it works either way, the FOV is really intended to be re-used; eg. to create one FOV, and call Calculate on the same instance whenever you need to move it. It won't affect the symmetry issue, but is good to be aware of if it becomes a performance issue for you later.

In any case, I'll look into adding a symmetric FOV option; thank you for taking the time to bring it up!

[tckerr]

Got it, thanks for the detailed explanation. I'll do some research to see what options are out there.

Speaking of performance, I will note that very frequently recreating FOV structures like you're doing may lead to performance issues

Makes sense. I'm not running too many of these at the moment and maps are fairly small so it's not an issue yet. I'll try what you suggested though.

[Chris3606]

Notes on this; there is now an FOV abstraction implemented in the form of IFOV/FOVBase which allows the library to more easily handle having multiple implementations of FOV algorithms.

Currently, the only implementation provided by the library is recursive shadowcasting (the same implementation that used to be contained within FOV); so this issue remains open since that implementation is not symmetric. However it should at least be possible now for a user to implement their own algorithm within the structure if they need a symmetric FOV algorithm in the meantime.

[Chris3606]

Note that it is also possible to implement a recursive-shadowcasting algorithm which is symmetrical (at a performance cost). Ideally, we can introduce an option to the existing recursive shadowcasting implementation to be symmetrical.