Talk:Spiral Path FOV

Here is an example of a spiral-path-like algorithm, modelled after the one found at http://www.geocities.com/temerra/los_rays.html, written in C-like C++.

It is used in the game "deliantra", and posted here because I couldn't find nice and simple spirla path examples.

If somebody knows a better place than the disucssion page, feel free to move it, or delete it. I hereby place this code into the public domain.

The code places a value from 0..3 (fully visible .. hardly visible) or 100 (not seen) into the pl->los array. It uses a special diagonal edge fixup. The sign function returns -1 or +1, depending on the sign, and sign0 additionally 0 for 0. It is good for coordinates <<128 only, but both los_info and point structures can usually be indexed very efficiently due to their small size.

#define MAP_CLIENT_X 32
#define MAP_CLIENT_Y 32

#define LOS_BLOCKED 100

enum {
  LOS_XI = 0x01,
  LOS_YI = 0x02,
};

struct los_info
{
  sint8 xo, yo;  // obscure angle
  sint8 xe, ye;  // angle deviation
  uint8 culled;  // culled from "tree"
  uint8 queued;  // already queued
  uint8 visible; 
  uint8 flags;   // LOS_XI/YI
};

// temporary storage for the los algorithm,
// one los_info for each lightable map space
static los_info los[MAP_CLIENT_X][MAP_CLIENT_Y];

struct point
{
  sint8 x, y;
};

// minimum size, but must be a power of two
#define QUEUE_LENGTH ((MAP_CLIENT_X + MAP_CLIENT_Y) * 2)

// a queue of spaces to calculate
static point queue [QUEUE_LENGTH];
static int q1, q2; // queue start, end

// enqueue a single mapspace, but only if it hasn't
// been enqueued yet.
static void
enqueue (sint8 dx, sint8 dy, uint8 flags = 0)
{
  sint8 x = LOS_X0 + dx;
  sint8 y = LOS_Y0 + dy;

  if (x < 0 || x >= MAP_CLIENT_X) return;
  if (y < 0 || y >= MAP_CLIENT_Y) return;

  los_info &l = los[x][y];

  l.flags |= flags;

  if (l.queued)
    return;

  l.queued = 1;

  queue[q1].x = dx;
  queue[q1].y = dy;

  q1 = (q1 + 1) & (QUEUE_LENGTH - 1);
}


// run the los algorithm
// this is a variant of a spiral los algorithm taken from
// http://www.geocities.com/temerra/los_rays.html
// which has been simplified and changed considerably, but
// still is basically the same algorithm.
static void
do_los (player *pl)
{
  memset (los, 0, sizeof (los));

  q1 = 0; q2 = 0;
  enqueue (0, 0); // enqueue center

  // treat the origin specially
  los[LOS_X0][LOS_Y0].visible = 1;
  pl->los[LOS_X0][LOS_Y0] = 0;

  // loop over all enqueued points until the queue is empty
  // the order in which this is done ensures that we
  // never touch a mapspace whose input spaces we haven't checked
  // yet.
  while (q1 != q2)
    {
      sint8 dx = queue[q2].x;
      sint8 dy = queue[q2].y;

      q2 = (q2 + 1) & (QUEUE_LENGTH - 1);

      sint8 x = LOS_X0 + dx;
      sint8 y = LOS_Y0 + dy;

      los_info &l = los[x][y];

      if (expect_true (l.flags & (LOS_XI | LOS_YI)))
        {
          l.culled = 1;

          // check contributing spaces, first horizontal
          if (expect_true (l.flags & LOS_XI))
            {
              los_info *xi = &los[x - sign (dx)][y];

              // don't cull unless obscured
              l.culled &= !xi->visible;

              /* merge input space */
              if (expect_false (xi->xo || xi->yo))
                {
                  // The X input can provide two main pieces of information: 
                  // 1. Progressive X obscurity.
                  // 2. Recessive Y obscurity.


                  // Progressive X obscurity, favouring recessive input angle
                  if (xi->xe > 0 && l.xo == 0)
                    {
                      l.xe = xi->xe - xi->yo;
                      l.ye = xi->ye + xi->yo;
                      l.xo = xi->xo;
                      l.yo = xi->yo;
                    }

                  // Recessive Y obscurity
                  if (xi->ye <= 0 && xi->yo > 0 && xi->xe > 0)
                    {
                      l.ye = xi->yo + xi->ye;
                      l.xe = xi->xe - xi->yo;
                      l.xo = xi->xo;
                      l.yo = xi->yo;
                    }
                }
            }

          // check contributing spaces, last vertical, identical structure
          if (expect_true (l.flags & LOS_YI))
            {
              los_info *yi = &los[x][y - sign (dy)];

              // don't cull unless obscured
              l.culled &= !yi->visible;

              /* merge input space */
              if (expect_false (yi->yo || yi->xo))
                {
                  // The Y input can provide two main pieces of information: 
                  // 1. Progressive Y obscurity.
                  // 2. Recessive X obscurity.

                  // Progressive Y obscurity, favouring recessive input angle
                  if (yi->ye > 0 && l.yo == 0)
                    {
                      l.ye = yi->ye - yi->xo;
                      l.xe = yi->xe + yi->xo;
                      l.yo = yi->yo;
                      l.xo = yi->xo;
                    }

                  // Recessive X obscurity
                  if (yi->xe <= 0 && yi->xo > 0 && yi->ye > 0)
                    {
                      l.xe = yi->xo + yi->xe;
                      l.ye = yi->ye - yi->xo;
                      l.yo = yi->yo;
                      l.xo = yi->xo;
                    }
                }
            }

          // check whether this space blocks the view
          if (world_blocksview_at (x, y))
            {
              l.xo = l.xe = abs (dx);
              l.yo = l.ye = abs (dy);

              // we obscure dependents, but might be visible
              // copy the los from the square towards the player,
              // so outward diagonal corners are lit.
              pl->los[x][y] = los[x - sign0 (dx)][y - sign0 (dy)].visible ? 0 : LOS_BLOCKED;
              l.visible = false;
            }
          else
            {
              // we are not blocked, so calculate visibility, by checking
              // whether we are inside or outside the shadow
              l.visible = (l.xe <= 0 || l.xe > l.xo)
                       && (l.ye <= 0 || l.ye > l.yo);

              pl->los[x][y] = l.culled  ? LOS_BLOCKED
                            : l.visible ? 0
                                        : 3;
            }

        }

      // Expands by the unit length in each component's current direction.
      // If a component has no direction, then it is expanded in both of its 
      // positive and negative directions.
      if (!l.culled)
        {
          if (dx >= 0) enqueue (dx + 1, dy, LOS_XI);
          if (dx <= 0) enqueue (dx - 1, dy, LOS_XI);
          if (dy >= 0) enqueue (dx, dy + 1, LOS_YI);
          if (dy <= 0) enqueue (dx, dy - 1, LOS_YI);
        }
    }
}

--schmorp 04:53, 20 December 2008 (CET)