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 (object *op) { player *pl = op->contr; int max_radius = max (pl->ns->mapx, pl->ns->mapy) / 2; memset (los, 0, sizeof (los)); q1 = 0; q2 = 0; // initialise queue, not strictly required 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; //int distance = idistance (dx, dy); if (distance > max_radius) continue;//D int distance = 0;//D 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 ? max (0, 2 - max_radius + distance) : 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)