FoV and LoS with obscurants (smoke)

[Omnivore]

Adding partial obscurants such as smoke to a roguelike map.  I'm looking at the following algorithm to compute a ray (Python generator form):

Code: [Select]

def generate_ray(grid, ptA, ptB):
    rem = abs(ptA.distance(ptB))
    last_pt = ptA
    for pt in ptA.generate_line(ptB):
        vis = grid.visibility(pt) # visibility factor [0.0..1.0]
        yield pt, vis # return pt and visibility info to the caller at each step
        rem = (rem - abs(last_pt.distance(pt))) * vis
        last_pt = pt
        if rem < 1.0:
            break

In the above, grid is some level map that is indexed by a point and has a method returning the visibility factor of the cell with 0.0 being fully opaque and 1.0 being fully transparent.  Obviously the code is not optimized.

Which FoV algorithm would be most suitable for modification to exhibit the same general characteristics as a ray casting FoV generator using the above?

My initial guess is that a recursive shadowcaster variant could be work, although splitting the cones becomes more complex.

Thanks,
Omnivore

[Kevin Granade]

I'm not sure what you mean by more complex, there will certainly be more cones, but you'll just recurse on any significant change in opacity instead of just boolean opacity change and pass the amount of transmitted sight to the recursive invocations, or am I missing something?

FYI, here's the DDA implementation in C++ https://github.com/CleverRaven/Cataclysm-DDA/blob/master/src/lightmap.cpp#L372
I'm planning on doing what you outline, but haven't gotten around to it yet.

[Omnivore]

@Kevin Granade: thanks for the tip and code reference   I had trouble with keeping predecessor cells correctly identified with shadow casting, I'll have to follow your lead in DDA if my new stupid approach doesn't work.

Speaking of my new stupid approach:
1) Using Bresenham's circle algorithm, create a list of all points on the circumference of a circle of the desired radius r about origin (0,0). 
2) For each point on the circumference, create a line path from the origin to the point using Bresenham's line algorithm.
3) Create a tree/directed acyclic graph with the origin as root, leaves as points on the circumference, and intermediate nodes as nodes shared by one or more lines.
4) Save the tree as the search pattern for radius r FoV determination.

Its stupidly simple so there must be a fatal flaw there somewhere.  Just haven't found it yet.

[Eben]

I spent quite a bit of time working on this problem, you can see my approach here. Specifically TranslucenceWrapperFOV in combination with any other.

Basically running two FOV algos, with one that overbends light and one that does a great calc and then merge the results. I use shadowcasting for the actual FOV and a spreading algo for the transparency.

[miki151]

Omnivore, I like your algorithm. I'm not sure though how it would work if it indeed generates a DAG a not a tree. I guess it depends on the specific line algorithm, but it's possible that two lines touch in one pixel and then diverge. It would add some not so nice ambiguity to traversing the graph.

[Omnivore]

@Eben: thanks for the tips, I'll definitely be looking.

@miki151: thanks, It generates a tree, and at the moment its working though it has a few blind spots due to missing coverage.  Going to fix that and run some more tests.

First draft, code too ugly to post lol.  It works, cost of initial precalculation is rather high but worst case could load from file, though I expect better performance down the road.  In use it is fast, though the current recursive tree walk may not be ideal.  Not sure yet how it stacks up against standard algorithms but it is O(n^2), only hits each tile once and only operates within the circle bounds.

Thanks again,
Omnivore

[miki151]

Pardon my gimp skills, but this is what I meant, looks like not a tree to me. Maybe I didn't understand your algorithm.

[Omnivore]

You are right that the Bresenham lines themselves wouldn't form a tree, but what I'm doing is:

Code: [Select]

        while fifo:
            layer.clear()
            node = fifo.pop()
            xy0 = Point2d(node.x, node.y)
            for line in lines:
                for i, val in zip(xrange(len(line)), line):
                    if val == xy0 and i < len(line)-1:
                        xy1 = line[i+1]
                        xy2 = tuple(xy1)
                        if origin.distance_squared(xy1) < rsqd and xy2 not in layer:
                            child = FoVNode(xy2)
                            node.add_child(child)
                            fifo.appendleft(child)
                            layer.add(xy2)

Pardon the code, its under construction and horribly mismatched to some of the libs at present.  However it should be enough to see what is going on. 

It begins with the origin node and adds children whose line contains the current node and whose next cell is not already included.  In the case you show, the splits are addressed in the outbound direction - they are not rejoined.... and I just found a bug with the way layer is being used.  Gah!  No wonder precalc was taking so long!

There are no doubt a number of speedups that could be made in this precalculation phase but putting those off till I address the artifacts.  Now that I've figured out how to deal with some of the artifacts, I'll be going back to a variant based on the circle circumference with some additional rays added to cover missing cells.  Also there's a bunch of clean up to do.

[EDIT] Cleaned up and tried a few different raycasting fov approaches to generate the lines that are used to create the tree.  I'm running into artifact hell though lol.  I think it might help if I sort the lines, unsure of sort order to use though.

[UPDATE] Finally an acceptable grouping of artifacts.  Sorting the lines helped quite a bit and I switched to a line end point selection using plain old squares.  A few more tweaks and I'll clean up and post a link to the result.

[Kevin Granade]

Speaking of my new stupid approach:
1) Using Bresenham's circle algorithm, create a list of all points on the circumference of a circle of the desired radius r about origin (0,0). 
2) For each point on the circumference, create a line path from the origin to the point using Bresenham's line algorithm.
3) Create a tree/directed acyclic graph with the origin as root, leaves as points on the circumference, and intermediate nodes as nodes shared by one or more lines.
4) Save the tree as the search pattern for radius r FoV determination.

Its stupidly simple so there must be a fatal flaw there somewhere.  Just haven't found it yet.

Hah, that's the route I investigated before biting the bullet and doing a shadowcasting implementation.
Looks like your step 3 addresses the performance problem I had, but I think it makes the other issue worse.  I'm guessing that you effectively merge overlapping lines in your implementation so that each square is only visited once?

The real issue is drawing artifacts.  They might be small enough that they aren't a problem for your needs, but they're there.  The issue is that the bresenham line TO a square is not necessarily the same as a bresenham line THROUGH the square.  There's a subtle skew, and it appears in situations like visibility of distant wall sections on a wall you're adjacent to.

[Eben]

One really good way to address the problems with Bresenham lines (at least mostly) is to use Elias' modification of Wu lines. Which is a way to anti-alias Bresenham.

http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

For the record, I implemented this as well in SquidLib and it gives very nice symmetric results, but is rather time expensive to compute. But time expensive may not actually matter depending on the size and makeup of your FOV area.

[mushroom patch]

If you're precomputing a tree, why are you using approximations to lines? Especially given that you're considering partially occluded line of sight, I would think you'd want to use actual lines (say through the center of each tile) with weighted contributions to occlusion from every tile they touch (I guess this could be thought of as similar to antialiasing, but you could specify the weights by a formula, not some kind of kernel or sth). My feeling is that these weights can be packed into a DAG/dependency graph type structure (as edge weights) and processed by some inclusion-exclusion scheme so computing field of view with degree of occlusion can be done recursively with each tile requiring information from only boundedly many (like 2 or 3) tiles already visited. (Admittedly, I haven't thought through this processing stage.)

[edit:] In fact, this inclusion-exclusion stuff on weights is a linear algebra problem. Even if there's no exactly correct way to do it (as I somewhat suspect), a least squares solution assuming an a priori layer structure in the DAG and comparing with the exact answer using the full dependency graph would probably yield very good results.

[Omnivore]

@mushroom patch: yep exactly right on the use of 'real' rays.   It is likely that a more accurate treatment could be done by using weighted contributions, but that's a bit beyond my intentions for now.  Thanks for the ideas though.

@Eben: I thought about those (or at least I think I was looking at the same thing) but the use of floating point rays took care of my immediate concerns.  Might have to look into those later for other uses.

@Kevin Granade: Yes the drawing artifacts were a pain.  However, since I'm precalculating the nodes, I can afford a bit of extra processing, so I switched from using Bresenham's to doing true raycasting with floating point (180 steps for one octant).  I also found that line order was very important, evaluating axis aligned rays first and diagonals last helped to eliminate the major artifacts.

Smoke obscuration is now working as intended.  I pretty much consider this to be a done job at present, perhaps some additional cleanup and later down the road perhaps some optimizations.

Of course, now this has me wondering.. what about a sound map? 

Walls and corner - no artifacts!

And smoke (8's are smoke):

[Xecutor]

Some time ago I posted circular fov algo.
IMO it's easy to adapt it for the task.
I'm not entirely sure that I understand what Omnivore wrote, but it looks similar to cfov.

[Kyzrati]

Of course, now this has me wondering.. what about a sound map? 

For sound I like the idea of using Dijkstra so it can turn corners, and you can even use a callback for each cell while its spreading to dampen/diffuse the sound by a certain amount from that point. I wrote a bit on that before.

For FOV I always found that Bresenham is so fast that while raycasting to the edge of FOV there's plenty of time to re-check every cell along every ray and allow the most liberal value to win out. This way you can also easy modify intermediate cells with any kind of FOV obstruction (-1 strength to rays passing through, for example) and it handles smoke and other effects quite elegantly.

[Omnivore]

@Xecutor - It may well be similar, I'll detail the steps below for the 'final' version I'm using.

@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.

The steps I'm using to create a low artifact ray cache are:
1) Calculate one octant's worth of floating point rays from offset origin (0.5, 0.5) in steps of A radians, beginning with an axis aligned ray.  (I've been using A = pi/720 which yields 180 rays per quadrant octant, likely an excessive number for small values of R and perhaps a low value for extremely large values of R).

2) For each ray create eight line paths (one per octant) of the desired radius R with the lines having integer point values as offsets from the origin (0,0).  Maintain the order (octal axis aligned -> diagonal).

3) Translate the lines into a tree having one node per cell in the field of view.  Begin with the root (origin) cell and iterate through the lines created in step 2.  For each point in each line, if the point is not already included in the tree, add it as a child of the preceding point's cell.

4) (Optional) Remap the tree into an array format with index offsets as a cpu cache optimization.  The cache can be stored externally if desired since for any given values of A and R you will get the same results.

Usage:
Using the cache is simply a matter of walking the tree, skipping children of any blocked nodes.  Since you are walking the tree in ray path order, you can easily apply any calculations which require values from both previous and current cells along the path.


Characteristics:
Memory: Each cache contains one node per cell in the fully open (no blocks) field of view.  Each node consists of an integer pair representing the relative coordinate value and a reference to each child node.  The maximum number of child nodes per node is 8, however it is worth noting that only the root node has that many children.  Except for the root node, the maximum number of children is three.

Speed: Each possible cell in the field of view is touched at most once and only once.  Except for cells on the circumference, blocked cells will reduce the number of cells checked.  I do not believe any faster algorithms exist.

Shape: Low artifact variant of the basic raycasting algorithm (see BASIC in http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds#Symmetry).  Due to the use of floating point rays and axis alignment ordering, many of the artifacts normally associated with ray casting in a roguelike are eliminated.  Note that there are some oddities with diagonals especially near a pillar - still working on correcting.

Sometime in the next couple days I'll create a command line Python script to generate the ray caches for given values of A and R which I'll publish along with example tree source for anyone who wants to test this in more detail.