Spiral Path FOV

Spiral Path FOV - Ray Dillinger


Okay; Basically it uses a table of squares, and a queue of pointers to
the table elements.  In the table, it keeps track of the minimum and
maximum lit angle reaching the corresponding square, plus static
precomputed information such as the angles from the origin to the
square corners.


There are two things that can happen to a square; you can either pass
light to it, or you can pass light from it.  When you're passing light
to it, you record (or expand) the minimum and maximum lit angles.
When you're passing light from it,  you mark the square as
lit/seen, take the minimum and maximum angle of the light
that's reaching it, and if it's transparent, pass light to
the squares that are adjacent to it and further from the
center.

The tricky bit with spiral-path is using the queue of pointers
correctly, so no pointer to a square that's not lit/seen is ever
put there, while at the same time putting the squares into the
queue an the order that guarantees that all light will be passed
to each before any light is passed from it.  Each square can get
light passed to it once, or twice; the first time light is passed to
it, a pointer to it gets added to the processing queue.  The
second time light gets added to it, if there is a second time,
its minimum and maximum lit angles are adjusted.

It has to be a queue of pointers (or the moral equivalent)
because you have to be able to get at the squares two ways:
First you have to be able to find it in constant time by
its coordinates when you're adding light to it.  Second,
you've got to be able to get at it in constant time when
you're taking it off the front of the queue. So basically,
you have your choice whether to implement the queue as a
queue of coordinates into the table or as a queue of
literal pointers.

Spiral-path consists in loading the queue with the initial four
squares, (one space east, north, west, and south of the center,
in that order), marking each with the minimum and maximum angle
of light reaching it (nominally equal to its minimum and maximum
angles), then
   repeat:
   take one square off the front of the queue.*1
   mark it visible/lit.
   If it's within the sight radius and not opaque then
      pass light from it
          (this may add things to the end of the queue,
      or add light to things that are already in the queue)
   : until the queue is empty.



Efficiency note:

*1 There can never be more elements in the queue than twice
the sight diameter, so you can use a static array of fixed
size, plus head and tail indexes that get incremented modulo
its length, for the queue.  You halt processing when head
is equal to tail.


The reason it's called spiral-path is that when you're passing
light from a square, it MUST be passed to new squares in the
correct order, or else you will wind up passing light from
something before all its light has been passed to it.  And the
correct order, where light/vision is unobstructed, is a spiral.

The path in which squares actually get added to the queue (where
unobstructed) is: (digits, then letters, beginning from *)

      I
     J8H
    K927G
   LA3*16F
    MB45E
     NCD
      0

etc... spiraling out from the center.  Squares 1,2,3,4 get added
in initialization.  Squares 5,6,7 get added when  passing light
from square 1.  Passing light from square 2 adds light to square 7
which is already on the queue, then adds squares 8 and 9 to the
queue.  Passing light from square 3 adds light to square 9 which
is already on the queue, then adds squares A and B to the queue.
Passing light from square 4 adds light to B, then adds square C
to the queue, then adds light to square 5 which is already on the
queue. Passing light from square 5 adds D and E to the queue.
Passing light from square 6 adds light to E which is already on
the queue, then adds F and G to the queue.  And so on.

The tricky bit was making sure things got added in the right order
so that all the light that 5 was going to get, got to it before
light was passed from it.  With the added condition that you don't
know in advance which squares light will actually come through to a
given square, and that cone effects or directional light can start
on any angle, not just with square 1, that turns out to depend on
the order of additions being a spiral.

So...  when passing light from square S, you figure out from the
minimum and maximum lit angles of S which of its neighbors it will
pass light to, and then add whichever of those neighbor squares
you need to add in this order:

If S is on the east axis:
    3
    S2
    1

If S is in the northeast quadrant:
     2
     S1

If S is on the North axis:
     2
    3S1

If S is in the northwest quadrant:
     1
    2S

If S is on the West axis:
     1
    2S
     3

If S is in the southwest quadrant:
    1S
     2

If S is on the South Axis:
    1S3
     2

If S is in the southeast quadrant:
     S2
     1


That way, no matter which squares get skipped (because no
light is getting to them) the squares that get added will
get added in such an order that none of them ever passes
light to a square that light has already been passed from,
and no square that light has been passed from will ever be
re-added to the queue.

There is one more fiddly bit:  Along one of your axes, you'll
have the "zero line" of your angle measurement.  So the code
to pass light to and from squares on that axis has to take
into account the wraparound in angles.

There's no need for floating-point in it; you're keeping
track of angles, but all you have to do is look them up
in tables and compare them to each other;It's simple
enough to multiply the angles by a million and round them
off to integers.



Finally, there's the corner patchup:  If you want spiral-
path to fill in the corners of your rooms so you get


########                #######
.......#                .......#
.......#    instead of  .......#,

add that an opaque square whose maximum-angle corner is
lit, passes an infinitely narrow beam of light through
that corner to the *last* square it would otherwise pass
light to.