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.

The example at the geocities website looks really nice. Do you perhaps know who the author is? We could use the images to explain the algorithms better. --Soyweiser 13:59, 26 December 2008 (CET)

#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)