FoV and LoS with obscurants (smoke)

[Kyzrati]

@Kyzrati - Thanks for the links, been following along with your blog posts on other subjects as well. I must say you are a very good technical writer in addition to your programming talents.  I'm not sure with sound and smell just how detailed a treatment I need as I am only using them for 'alert checks' - waking up a mob AI on successful smell or sound detection or providing a notice to the player.

Aw, thanks

If it's just for check purposes and there's only one or few player actors I'd use A* w/heuristics for sound. Smell I've never done but I'm sure you've seen others use Dijkstra-updated maps for that.

The steps I'm using to create a low artifact ray cache are:

I remember using a similar pre-calculated FOV cache in a game many years ago, but there were so many different/possible (and huge) values for R that storing all that data took quite a lot of memory. In that case I ended up optimizing the cache so it only calculated one octant, since all others can be extrapolated at run time by flipping coordinates to rely on the same small slice of cache data. Now looking back on it it was such a huge amount of work just for FOV when Bresenham gets the job done fine without any artifacts. I even use 3D Bresenham in X@COM which includes all kinds of strange angles and potential complete or partial (e.g. smoke) FOV blockages.

[Xecutor]

@Omnivore - my is a little different. The only problem I see with yours is that one tile technically can block two tiles.
And depending on how you handle this, you might encounter one kind of oddity or another.

In my case instead of a tree I have an array of offsets of points of circles.
And a list of blocked angles (with some additional info).
This way I can make tiles that block vision temporary (emulating half-height objects) and other interesting things.

[Omnivore]

@Omnivore - my is a little different. The only problem I see with yours is that one tile technically can block two tiles.
And depending on how you handle this, you might encounter one kind of oddity or another.

The problem is more difficult than I thought.  Actually not sure a reasonable solution exists, although it is possible I could lean towards the form that gives wall artifacts which can be cleaned up in a post process step.  The root of the problem with the algorithm is that it is impossible to eliminate curve balls - los paths that do not resemble a straight line by any stretch of the imagination.

I'm not giving up on it as an experimental project, but for my fov needs I've switched to ray casting with Bresenham lines and post processing to clean up lit wall artifacts.  I'm still able to get proportional falloff of obscured los's so my main goal is met.

[Xecutor]

@Omnivore - my is a little different. The only problem I see with yours is that one tile technically can block two tiles.
And depending on how you handle this, you might encounter one kind of oddity or another.

The problem is more difficult than I thought.  Actually not sure a reasonable solution exists, although it is possible I could lean towards the form that gives wall artifacts which can be cleaned up in a post process step.  The root of the problem with the algorithm is that it is impossible to eliminate curve balls - los paths that do not resemble a straight line by any stretch of the imagination.

See? When I came up with circular fov I started with the same idea as yours
And cfov is very fast, btw.

[Omnivore]

See? When I came up with circular fov I started with the same idea as yours
And cfov is very fast, btw.

Yes, interesting approach, basically the inverse - precomputation of blockage rather than view paths.

Upon reflection I realize there is one possible application of the approach I outlined in this topic where its flaws are relatively unimportant and that is to create the awareness field for mob AI.  Admittedly though it is probably unnecessary as a simple point in rectangle bounds check followed by a range and bresenham los check per mob is likely far faster and more reliable.  Eh well, yet another solution in search of a problem!

For the primary FoV, I now have a working implementation based on the approach Kyzrati recommended.  Post processing of artifacts was a bit of a pain, but I'm satisfied with the results and the potential to extend the technique to allow custom 'shaping' of the field of view - for example corner peeking.  The multiplicative falloff of vision through obstructions works as I desired and even in pure Python it is fast enough for my intended use as the primary player-centric field of view generator.

Thanks to everyone who responded to this topic!
Omnivore

[Kyzrati]

For the primary FoV, I now have a working implementation based on the approach Kyzrati recommended.  Post processing of artifacts was a bit of a pain, but I'm satisfied with the results and the potential to extend the technique to allow custom 'shaping' of the field of view - for example corner peeking.  The multiplicative falloff of vision through obstructions works as I desired and even in pure Python it is fast enough for my intended use as the primary player-centric field of view generator.

Thanks to everyone who responded to this topic!
Omnivore

Glad it's working out for you. In the past I've found it plenty fast for dozens of units with large FOV and a mix of open and closed spaces, but there was unacceptable slowdown for a game with potentially many hundreds of units (Cogmind, even in C++), so this time around I decided to use it only for the player and any shared-FOV allies, and use the alternate system you describe for everyone else, i.e. range check + Bresenham LOS. This can result in slight/rare discrepancies between what the player can see vs. their enemies due to the refinements of a full FOV calculation, but it's generally okay (and there's not much choice if you need hundreds of units that can see far!).

[Omnivore]

One last ray cast artifact I can't seem to find a way to fix; namely the inverted corner peeking case (see: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds#Corner_peeking).

If it only showed up while within a one wide tunnel, it would be easy to fix, but it shows up in many other places if you are watching for it (and have most all the other artifacts fixed). 

Only thing I can think of is to check all wall tiles for the case where there is an adjacent open tile further away from the player along the major axis.  In that case then cast a ray back to the player to double check the visibility.

Any better fixes?

[Kyzrati]

If you're using the full brute force method of allowing every ray to update every cell it passes through, then at least the result doesn't leave holes in the inverted peeking image as it does in BASIC shown in your link.

But it does still mean that if you're standing next to a corner you won't be able to see along the whole edge of the wall around that corner, while someone standing around the corner further away along the wall edge *will* see you.

That's a case I didn't fix since it isn't a big issue in Cogmind, although I recall considering a fix during FOV implementation that would detect when you are standing at a corner like that and then calculate your FOV as if you were standing one cell ahead of where you are. Something to think about--maybe a variation on that would help? Depending on your game something like that might work.

[Omnivore]

If you're using the full brute force method of allowing every ray to update every cell it passes through, then at least the result doesn't leave holes in the inverted peeking image as it does in BASIC shown in your link.

The holes are positions where you can see around the corner.  As you move down the corridor you hit positions where you can see around the it, then move closer and not be able to see around it, closer still and see around it again.  However, that's with Bresenham lines.  I'm now using a stricter variant called the 'Bresenham-based supercover line algorithm' http://eugen.dedu.free.fr/projects/bresenham/ and no more holes!

But it does still mean that if you're standing next to a corner you won't be able to see along the whole edge of the wall around that corner, while someone standing around the corner further away along the wall edge *will* see you.

That's a case I didn't fix since it isn't a big issue in Cogmind, although I recall considering a fix during FOV implementation that would detect when you are standing at a corner like that and then calculate your FOV as if you were standing one cell ahead of where you are. Something to think about--maybe a variation on that would help? Depending on your game something like that might work.

The case changes with the switch to supercover lines but a variant still exists (favors the viewer in the corridor for some odd reason).  What I've done is implement a 'peek' command that gives you the 'one step ahead' view as you describe.  As the cases where it is most useful are easy to detect, I may automate it for use with a 'cautious' movement option later.

[EDIT]  I should note that the additions to the lines caused by supercover are only used for blocking purposes, the area 'seen' is limited to the Bresenham line portion.

[EDIT2] The last artifact is fixed!  Accidentally fixed it when I added a symmetry check and dropped the doubled diagonals from the supercover blocking checks.  While I'm still using the basic raycasting approach (casting supercover lines from origin to each perimeter cell), I added a symmetry check that, only on the first encounter of a given cell, checks that an unblocked supercover line exists back to the player.  It still seems fast enough for my intended purposes.