Wrong FOV near the corners

[LEGOL2]

Hello! The problem is only partially fixed. Field of vision near the corners is too small and causes monsters to get stuck on the edges. Please take a look at below images.

As you can see, the player or monster does not have a vision on 2nd tile, while staying on the wall edge. It will not try to move towards the player and just stay there. I've checked with book source code, and behavior is different.

Edit: @thebracket adding mention, so you get a notification, because I can't reopen the issue.

Edit2: I've originally posted this in #192 but I've decided to create new issue.

Originally posted by @LEGOL2 in https://github.com/amethyst/bracket-lib/issues/192#issuecomment-792251614

[dvidbruhm]

I can confirm that I have the same issue, and after some fiddling i've found that the issue disappears If I downgrade bracket-pathfinding from 0.8.4 -> 0.8.1 by using cargo update -p bracket-pathfinding --precise 0.8.1 as a temporary fix.

[QuantumBJump]

I'm experiencing this problem too. It's a bit annoying when trying to test certain things, as I can't get enemies to follow me through corridors unless they're perfectly lined up.

[logistic-bot]

Experiencing this problem as well. dvidbruhm's fix worked, but introduces gaps in FOV (#192)

[SPuntte]

Hello, and thank you @thebracket for this amazing library! :heart:

While following along the tutorial, I also noticed this behavior and wanted to address it. To be honest, I didn't really try to understand the current algorithm but replaced it with a pretty straightforward adaptation of Albert Ford's symmetric shadowcasting.

I'm not sure if my code is up to the library's standards but I can make a PR if that's something you want to see. Quick benchmarking shows the replacement being around 2-3x slower than the current one so there's definitely room for optimization. The use of rational numbers (which Ford advocates for) adds a dependency, num-rational. I also switched trait objects for generics, which is of course reversible if you prefer the former.

Finally a couple images, inspired by OP's examples, for illustration of the differences in behavior:

• dark cyan background: FOV origin
• white: within FOV of both algorithms
• green: within FOV of the new algorithm only
• red: within FOR of the old algorithm only
• dark magenta background: a BresenhamCircle for reference

[LEGOL2]

My humble opinion is that you could add this as a new function and create new interface for this specific algorithm, so that user can select which fov he wants.

[SPuntte]

That's a fair point, and @thebracket actually mentioned the intention to support this in https://github.com/amethyst/bracket-lib/issues/75#issuecomment-590321669.

I took some inspiration from DistanceAlg in bracket_geometry and hacked together a prototype, see #223.

[thebracket]

I've merged in the PR (with a couple of tweaks to also merge in some Clippy fixes - nothing major), and it seems to work well. That PR was awesome - thank you. I tested with both Hands-on Rust and the tutorial code and absolutely nothing broke. :-)

[SPuntte]

Whoops, I hope you don't mind the delay. Great news! Happy to contribute :)

[LEGOL2]

@SPuntte thank you very much for PR! I've not tested it yet, but I understand that this issue can be closed.