Temple of The Roguelike Forums
Development => Programming => Topic started by: Bear on September 04, 2011, 02:48:46 PM
-
Hi. I started this thread to encourage code sharing. If you have some code that you feel to be particularly elegant and useful and related to roguelike development, This is a nice thread to post it in. Remember to give it a title that indicates both the programming language and what it does. And if it relies on some particular framework (openGL, libcotd, etc) mention that in the title too. I'll start with a nice C routine for finding the nearest square answering some arbitrary test.
-
/* returns 1 for success and 0 for failure. If successful, sets bestx and besty to
the coordinates of the closest tile to the given coordinates that satisfies the test.
The function fails iff there is no tile in the map that satisfies the test.
If it finds a tile that satisfies the test, it continues to search until it
has verified that there are no nearer tiles which also satisfy the test,
then returns. It searches in squares of equal chebyshev distance, so
if your distance function returns euclidean or manhattan distance it
may need to search an extra square or two.
The last parameter is a function pointer to a test that takes a map, an x
coordinate and a y coordinate and returns an integer. The test is satisfied
if the function returns nonzero. The test function must handle coordinates
that are not in the current map and must return zero for them.
An example invocation of this function to find the nearest walkable square
(for, eg, a teleport arrival) would be
Map_FindClosestTest(map, x, y, &retx, &rety, Map_IsWalkable);
To find the nearest downstairs, you'd call
Map_FindClosestTest(map, x, y, &retx, &rety, Map_IsDownStair);
etc.
*/
int Map_FindClosestTest(maptype map, int locx, int locy, int *bestx, int *besty,
int (*test)(maptype map, int x, int y)){
int offset;
int radius;
int count;
int currentx, currenty;
int bestx, besty;
double bestinradius;
/* IMPOSSIBLE_DISTANCE is a distance further than any the map can generate */
double bestdistance = IMPOSSIBLE_DISTANCE;
/* MAPSIZE is the width or height of the map, whichever's larger. */
for (radius = 0; radius < MAPSIZE; radius++){
for (offset = -radius; offset < radius; offset++){
for (count = 0; count < 4; count++){
switch(count) {
case 0:
currentx = locx + offset;
currenty = locy + radius;
break;
case 1:
currentx = locx - offset;
currenty = locy - radius;
break;
case 2:
currentx = locx + radius;
currenty = locy - offset;
break;
case 3:
currentx = locx - radius;
currenty = locy + offset;
if (offset == 0){
bestinradius = Map_Distance(currentx, currenty, locx, locy);
if (bestinradius >= bestdistance)
return(1);
}
break;
}
if (test(map, currentx, currenty)){
if (Map_Distance(currentx, currenty, locx, locy) < bestdistance){
bestdistance = Map_Distance(currentx, currenty, locx, locy);
*bestx = currentx;
*besty = currenty;
}
}
}
}
}
/* at this point we have searched every square out to a chebyshev radius of
MAPSIZE, and found no tiles satisfying the test. */
return(0);
}
-
This code is a member function for characters in the game. It 'sees' all squares within 5 of any given unit as long as they aren't completely obstructed by walls.
public void uncover() //gives everyone their line of sight
{
int bestx = xcoord;
int besty = ycoord;
seen_squares[xcoord, ycoord, zcoord] = true; //this square is visible to the character and, by extension, the player
for (int xdelta = 0; xdelta <= 5; xdelta++)
{
for (int ydelta = 0; ydelta <= 5 - xdelta; ydelta++)
{
if(xcoord+xdelta < seen_squares.GetLength(0) && ycoord+ydelta < seen_squares.GetLength(1) && seen_squares[xcoord + xdelta, ycoord + ydelta, zcoord] == false)
{
if (bool_between(xcoord, ycoord, xcoord + xdelta, ycoord + ydelta)) //bool_between(x, y, z) checks to see if the way between the character and the point being targeted is clear of walls
{
bestx = xcoord + xdelta;
besty = ycoord + ydelta;
seen_squares[xcoord + xdelta, ycoord + ydelta, zcoord] = true;
}
}
if(xcoord+xdelta < seen_squares.GetLength(0) && ycoord-ydelta >= 0 && seen_squares[xcoord + xdelta, ycoord - ydelta, zcoord] == false)
{
if (bool_between(xcoord, ycoord, xcoord + xdelta, ycoord - ydelta))
{
bestx = xcoord + xdelta;
besty = ycoord - ydelta;
seen_squares[xcoord + xdelta, ycoord - ydelta, zcoord] = true;
}
}
if(xcoord-xdelta >= 0 && ycoord+ydelta < seen_squares.GetLength(1) &&seen_squares[xcoord - xdelta, ycoord + ydelta, zcoord] == false)
{
if (bool_between(xcoord, ycoord, xcoord - xdelta, ycoord + ydelta))
{
bestx = xcoord - xdelta;
besty = ycoord + ydelta;
seen_squares[xcoord - xdelta, ycoord + ydelta, zcoord] = true;
}
}
if(xcoord-xdelta >= 0 && ycoord-ydelta >= 0 &&seen_squares[xcoord - xdelta, ycoord - ydelta, zcoord] == false)
{
if (bool_between(xcoord, ycoord, xcoord - xdelta, ycoord - ydelta))
{
bestx = xcoord - xdelta;
besty = ycoord - ydelta;
seen_squares[xcoord - xdelta, ycoord - ydelta, zcoord] = true;
}
}
}
}
if (dur_provoke > 0) //If the unit is being provoked, it follows the nearest enemy unit's location
{
if (waypoint == null) waypoint = new point(nearest().xcoord, nearest().ycoord, nearest().zcoord);
else waypoint.set_point(nearest().xcoord, nearest().ycoord, nearest().zcoord);
}
else
{
if (team_id == 0) //otherwise, if it's a unit allied to the player it follows the active unit in the player's team.
{
if (waypoint == null) waypoint = new point(core.teamlist[0].mychar[core.active].xcoord, core.teamlist[0].mychar[core.active].ycoord, core.teamlist[0].mychar[core.active].zcoord);
else waypoint.set_point(core.teamlist[0].mychar[core.active].xcoord, core.teamlist[0].mychar[core.active].ycoord, core.teamlist[0].mychar[core.active].zcoord);
//else waypoint.set_point(bestx, besty, zcoord); //only create a waypoint if none is taken. If movement AI is still goofy after all this time I'll just make it so that any inactive units just follow the active one until I can make them act more intelligently
}
else //otherwise it will just look for the point that makes sense based on an arbitrary condition
{
if (waypoint != null) waypoint.set_point(bestx, besty, zcoord); //only create a waypoint if none is taken
else waypoint = new point(bestx, besty, zcoord);
}
}
}
-
Is there a reason you are not going from -5 to 5? Anyway; i'm impressed you both are sharing some of your bad code. SCNR.
-
/* The following is a complete implementation of Spiral Path FOV code in C.
Spiral Path visits each square with light passing through it or into it
exactly once, and does not visit any other squares -- so it's in the most
efficient class of FOV algorithms. I have not measured its performance
against comparable implementations of other algorithms in the class; it
may be a constant factor faster or slower.
It calls out to three functions in a different module; These functions are
Map_Distance to calculate distances,
Map_Transparent to tell whether light can pass through a square, and
Map_FovCallback to actually do the marking of squares in the map.
It assumes that two of its own functions (and only two) may be called from
outside the module; these functions are
FOV_Init, which is called exactly once to initialize the data structures, and
FOV_SpiralPath, which is called whenever we want to do radius or arc lighting,
whenever we want to calculate a field of view, whenever we want to mark
squares to be subject to a radius or cone effect that can be blocked, etc.
Module written by Ray Dillinger in 2011. This is an adaptation/rewrite of an
original implementation, also by Ray Dillinger, from 2004 which was harder
to understand. Use and enjoy, subject to any Debian-Approved
free-software license of your choice.
*/
#include <math.h>
#include <assert.h>
#include "fov.h"
#include "map.h"
/* a data type that stores the minimum and maximum lit angles of a
given tile. */
typedef struct{
double minlit;
double maxlit;
} FOVsquare;
/* FOV_grid stores the angle from the center of the origin square or
(0.5,0.5) to the corner of the tile at the given coordinates (to
the true (0,0) corner in the case of the origin square. From these
we derive all corner coordinates we need for all tiles. This has
the benefit of avoiding repeating potentially-slow trig operations,
but it's mainly for consistency.
Since we're using a lot of doubles, and we need particular angles
that we get to in several different ways, deriving all angles in an
absolutely consistent way from this grid ensures that equality
tests are meaningful and do what we want, despite possible roundoff
errors and peculiarities of implementation.
In principle this could use Integers instead of doubles, given a
monotonic mapping of integers to angles occurring in the grid. */
double FOV_grid[FOV_SIGHTDIAMETER+1 ][FOV_SIGHTDIAMETER+1 ];
/* This array stores the minimum and maximum lit angles of each square
within the sight radius. Unlit squares are represented as 0,0.
each FOV operation must begin and end with minlit and maxlit angles
in FOV_lightgrid set equal to zero. These angles change during the
operation; if either (or both) are nonzero, then the corresponding
element is in the queue. Angles related to each (xy) square are
stored in FOV_grid(x-sightradius,y-sightradius) because C doesn't
allow non-zerobased arrays. */
FOVsquare FOV_lightgrid[FOV_SIGHTDIAMETER][FOV_SIGHTDIAMETER];
/* this function is a 'shim' that handles the map referring to
loctypes and the SpiralPath code referring to integer coordinates.
We have loctypes available because we've included map.h above,
but this FOV code doesn't use them outside of shim functions. */
int FOV_Transparent(maptype map, int x, int y, int z){
loctype testloc;
testloc.x = x;
testloc.y = y;
testloc.z = z;
return(Loc_Transparent(map, testloc));
}
/* this function is a 'shim' that handles the map code referring to
loctypes and the FOV code referring to integer coordinates. I'm
referring back to the map distance function in order to assure that
the "distance" expressed by radius, etc, is the same distance as
measured by the Map module's distance function. */
double FOV_Distance(int x, int y, int x2, int y2){
loctype loc1;
loctype loc2;
loc1.x = x;
loc2.x = x2;
loc1.y = y;
loc2.y = y2;
/* For FOV purposes we're finding distances on the same z plane -
hence the z coordinate (as long as it's > 0) does not actually
matter. */
loc1.z = loc2.z = 1;
return(Map_Distance(loc1, loc2));
}
/* normalizes angles to between zero and 2pi. */
double FOV_Anglenorm(double angle){
while (angle < 0.0) angle += 2*PI;
while (angle > 2*PI) angle -= 2*PI;
return(angle);
}
/* Initializes the light grid. Called from FOV_Init. After that we
are meticulous in re-zeroing these whenever we dequeue them so the
grid will always be ready when one Spiralpath traversal is done to
begin another. */
void FOV_InitLightGrid() {
int x; int y;
for (x = 0; x < FOV_SIGHTDIAMETER; x++)
for (y = 0; y < FOV_SIGHTDIAMETER; y++){
FOV_lightgrid[x][y].minlit = 0.0;
FOV_lightgrid[x][y].maxlit = 0.0;
}
}
/* Initializes the geometry grid. Called from FOV_Init.
The geometry grid is never altered after initialization. */
void FOV_InitGrid(){
int x;
int y;
for (x = 0; x <= FOV_SIGHTDIAMETER; x++)
for (y = 0; y <= FOV_SIGHTDIAMETER; y++){
/* this is the angle from the center of the 0,0 square to the
closest-to-origin corner of each square. All angles except
the angles to the squares in the zero row/column will be in
the range 0 to pi/2. */
FOV_grid[x][y] = FOV_Anglenorm(atan2((y-0.5),(x-0.5)));
}
}
/* Needs called once during game setup. Handling it by calling
it from Map_Init. */
void FOV_Init(){
FOV_InitGrid();
FOV_InitLightGrid();
}
/*returns the angle that "oughta" be in the geometry grid for given
coordinates, if the grid went to those coordinates.*/
double FOV_Coordangle(int x, int y){
if (x > FOV_SIGHTRADIUS || y > FOV_SIGHTRADIUS ||
-x > FOV_SIGHTRADIUS || -y > FOV_SIGHTRADIUS )
/* if it's outside of the precomputed zone and its rotations about
the origin, then calculate it directly. */
return(FOV_Anglenorm(atan2(y-0.5, x-0.5)));
/* otherwise get it from the correct zone rotation & offset. */
if (x >= 0 && y >= 0) return (FOV_grid[x][y]);
if (x < 0 && y > 0) return (PI - FOV_grid[1-x][y]);
if (x >= 0 && y < 0) return (2*PI - FOV_grid[x][1-y]);
return(PI + FOV_grid[1-x][1-y]);
}
/* The minimum angle of the tile; that is, the angle of the
smallest - angled corner.*/
double FOV_MinAngle(int x, int y){
if (x == 0 && y == 0) return (0.0); /* origin special case */
if (x >= 0 && y > 0) return (FOV_Coordangle(x+1,y)); /* first quadrant */
if (x < 0 && y >= 0) return (FOV_Coordangle(x+1,y+1)); /* second quadrant*/
if (x <= 0 && y < 0) return (FOV_Coordangle(x,y+1)); /* third quadrant */
return(FOV_Coordangle(x,y)); /* fourth quadrant */
}
/* The maximum angle of the tile; that is, the angle of the
largest-angled corner.*/
double FOV_MaxAngle(int x, int y){
if (x == 0 && y == 0) return (2*PI); /* origin special case */
if (x > 0 && y >= 0) return (FOV_Coordangle(x,y+1)); /* first quadrant */
if (x <= 0 && y > 0) return (FOV_Coordangle(x,y)); /* second quadrant */
if (x < 0 && y <= 0) return (FOV_Coordangle(x+1,y));/* third quadrant */
return(FOV_Coordangle(x+1,y+1)); /* fourth quadrant */
}
/* The angle of the outer corner of each tile: On the origin lines,
the angle of the FIRST outer corner. */
double FOV_OuterAngle(int x, int y){
if (x == 0 && y == 0) return (0.0); /* origin special case */
if (x >= 0 && y > 0) return (FOV_Coordangle(x+1,y+1)); /* first quadrant with positive y axis*/
if (x < 0 && y >= 0) return (FOV_Coordangle(x,y+1)); /* second quadrant with negative x axis*/
if (x <= 0 && y < 0) return (FOV_Coordangle(x,y)); /* third quadrant with negative y axis */
return(FOV_Coordangle(x+1,y)); /* fourth quadrant with positive x axis */
}
/* The squares on the axes (x or y == 0) have a second outer corner.
This function identifies the angle from the center of the origin
square to that corner. */
double FOV_OuterAngle2(int x, int y){
if (x != 0 && y != 0) return (0.0); /* meaningless on non-axis squares */
if (x > 0) return(FOV_Coordangle(x+1,y+1));
if (x < 0) return(FOV_Coordangle(x,y));
if (y > 0) return(FOV_Coordangle(x, y+1));
if (y < 0) return(FOV_Coordangle(x+1,y));
return(0.0); /* meaningless on origin */
}
/* true iff a given square could pass any light inside a desired arc. */
int FOV_In_Arc(int x, int y, double arcstart, double arcend){
if (arcstart > arcend) /* arc includes anomaly line */
return (FOV_MinAngle(x,y) < arcstart ||
FOV_MaxAngle(x,y) < arcstart ||
FOV_MinAngle(x,y) > arcend ||
FOV_MaxAngle(x,y) > arcend);
else /* arc does not include anomaly line */
return (FOV_MaxAngle(x,y) > arcstart ||
FOV_MinAngle(x,y) < arcend);
}
/* find the first "child" tile to which light may be passed from x y.
This is also the tile to be revealed as a corner touchup if x y is
illuminated from its minimum-angle corner and is opaque. */
void FOV_FirstChild(int x, int y, int *childx, int *childy){
if (x == 0 && y == 0) {*childx = x; *childy = y; return; } /* origin */
if (x >= 0 && y > 0) {*childx = x+1; *childy = y; return; } /* quadrant 1 */
if (x < 0 && y >= 0) {*childx = x; *childy = y+1; return; } /* quadrant 2 */
if (x <= 0 && y < 0) {*childx = x-1; *childy = y; return; } /* quadrant 3 */
*childx = x; *childy = y-1; return; /* quadrant 4 */
}
/* find the second "child" tile to which light may be passed from x y. */
void FOV_SecondChild(int x, int y, int *childx, int *childy){
if (x == 0 && y == 0) {*childx = x; *childy = y; return; } /* origin */
if (x >= 0 && y > 0) {*childx = x; *childy = y+1; return; } /* quadrant 1 */
if (x < 0 && y >= 0) {*childx = x-1; *childy = y; return; } /* quadrant 2 */
if (x <= 0 && y < 0) {*childx = x; *childy = y-1; return; } /* quadrant 3 */
*childx = x+1; *childy = y; return; /* quadrant 4 */
}
/* find the third "child" tile to which light may be passed from x y.
Meaningful only for axis tiles (x == 0 or y == 0) because they
have a third child; non-axis tiles don't. */
void FOV_ThirdChild(int x, int y, int *childx, int *childy){
if (x != 0 && y != 0) {*childx = *childy = 0; return;} /* non-axis*/
if (x > 0) {*childx = x; *childy = y+1; return;}
if (x < 0) {*childx = x; *childy = y-1; return;}
if (y > 0) {*childx = x-1; *childy = y; return;}
if (y < 0) {*childx = x+1; *childy = y; return;}
*childx = 0; *childy = 0; return; /* origin */
}
void FOV_SetLitAngle(int x, int y, double minlit, double maxlit){
/* boundary checking just to make sure.... I know of no way this
code can ever violate these boundary checks, but the code that
implements relevant preconditions is non-centralized and if
they're violated we segfault, so leaving the checks in to catch
any possible mistakes present or future. */
assert(x+FOV_SIGHTRADIUS >= 0);
assert(y+FOV_SIGHTRADIUS >= 0);
assert(x+FOV_SIGHTRADIUS < FOV_SIGHTDIAMETER);
assert(y+FOV_SIGHTRADIUS < FOV_SIGHTDIAMETER);
FOV_lightgrid[x+FOV_SIGHTRADIUS][y+FOV_SIGHTRADIUS].minlit = minlit;
FOV_lightgrid[x+FOV_SIGHTRADIUS][y+FOV_SIGHTRADIUS].maxlit = maxlit;
}
void FOV_GetLitAngle(int x, int y, double *minlit, double *maxlit){
/* Again, boundary checking just to make sure.... */
assert(x+FOV_SIGHTRADIUS >= 0);
assert(y+FOV_SIGHTRADIUS >= 0);
assert(x+FOV_SIGHTRADIUS < FOV_SIGHTDIAMETER);
assert(y+FOV_SIGHTRADIUS < FOV_SIGHTDIAMETER);
*minlit = FOV_lightgrid[x+FOV_SIGHTRADIUS][y+FOV_SIGHTRADIUS].minlit;
*maxlit = FOV_lightgrid[x+FOV_SIGHTRADIUS][y+FOV_SIGHTRADIUS].maxlit;
}
/* we dequeue one item and set all the particulars. Also, we set the
squarelighting to zero for that tile so we know it's off the queue
next time we come across it. */
void FOV_Dequeue(int *QX, int *QY, int *Qhead, int *curx, int *cury, int *child1X,
int *child1Y, int *child2X, int *child2Y, int *child3X, int *child3Y,
double *leastangle, double *outerangle, double *outerangle2,
double *greatestangle, double *leastlitangle, double *greatestlitangle){
*curx = QX[*Qhead];
*cury = QY[*Qhead];
*Qhead = (*Qhead + 1) % (2 * FOV_SIGHTDIAMETER);
FOV_FirstChild(*curx, *cury, child1X, child1Y);
FOV_SecondChild(*curx, *cury, child2X, child2Y);
FOV_ThirdChild(*curx, *cury, child3X, child3Y);
*leastangle = FOV_MinAngle(*curx, *cury);
*outerangle = FOV_OuterAngle(*curx, *cury);
*outerangle2 = FOV_OuterAngle2(*curx, *cury);
*greatestangle = FOV_MaxAngle(*curx, *cury);
FOV_GetLitAngle(*curx, *cury, leastlitangle, greatestlitangle);
/* and this is off the queue now so we zero it for next time. */
FOV_SetLitAngle(*curx, *cury, 0.0, 0.0);
}
void FOV_enqueue(int *QX, int *QY, int *Qtail, int x, int y){
QX[*Qtail] = x;
QY[*Qtail] = y;
*Qtail = (*Qtail + 1) % (2 * FOV_SIGHTDIAMETER);
}
/* This adds light to a tile. Also, if a tile is not in the queue,
it enqueues it.*/
void FOV_Mark(int *QX, int *QY, int *Qtail, int x, int y, double min, double max){
double minlit, maxlit;
FOV_GetLitAngle(x,y, &minlit, &maxlit);
if (minlit == maxlit && maxlit == 0.0){
/* no light -- implies not in queue, so we add it to the queue. */
FOV_SetLitAngle(x,y, min, max);
FOV_enqueue(QX, QY, Qtail, x,y);
}
else {
if (min < minlit) minlit = min;
if (max > maxlit) maxlit = max;
FOV_SetLitAngle(x,y,minlit,maxlit);
}
}
/* The total lit angle is represented by leastlitangle,
greatestlitangle. minangle and maxangle are the minimum and
maximum that can be illuminated in this operation. Our task is to
test and see if we can add light to the tile. If any light is
added, we call FOV_Mark. */
void FOV_TestMark(int *QX, int *QY, int *Qtail, int x, int y, double leastlitangle, double greatestlitangle,
double minangle, double maxangle){
if (leastlitangle > greatestlitangle)
/* we're passing light along the anomaly axis. This takes
advantage of the grid-geometric property that no
less-than-total obstructions are possible. */
FOV_Mark(QX, QY, Qtail, x, y, minangle, maxangle);
else if (maxangle < leastlitangle || minangle > greatestlitangle)
/* lightable area is outside the lighting. */
return;
else if (minangle <= leastlitangle && greatestlitangle <= maxangle)
/* lightable area contains the lighting. */
FOV_Mark(QX, QY, Qtail, x,y, leastlitangle, greatestlitangle);
else if (minangle >= leastlitangle && greatestlitangle >= maxangle)
/* lightable area contained by the lighting. */
FOV_Mark(QX, QY, Qtail, x,y, minangle, maxangle);
else if (minangle >= leastlitangle && greatestlitangle <= maxangle)
/* least of lightable area overlaps greatest of lighting. */
FOV_Mark(QX, QY, Qtail, x,y, minangle, greatestlitangle);
else if (minangle <= leastlitangle && greatestlitangle >= maxangle)
/* greatest of lightable area overlaps least of lighting. */
FOV_Mark(QX, QY, Qtail, x,y, leastlitangle, maxangle);
else /* This never happens. */
assert(1 == 0); /* unhandled case, not on the anomaly line. */
}
/* Mapx, mapy, mapz, are the coordinates of the square where
spiralpath starts. Radius is the range of the effect. Radius must be less
than FOV_SIGHTRADIUS. Arcstart and arcend denote the minimum and
maximum angles to mark. They must be between 0.0 and 2*PI. Action
is a signal to Map_FovCallback what action to do to squares in the area.
Its value doesn't matter to us, we just pass it back to the map
module. */
void FOV_SpiralPath(maptype map, int mapx, int mapy, int mapz, double radius, double arcstart,
double arcend, int action, int cornertouchup){
/* The next 4 variables are a Queue of X Y coordinates. */
int QX[2 * FOV_SIGHTDIAMETER];
int QY[2 * FOV_SIGHTDIAMETER];
int Qhead = 0;
int Qtail = 0;
int curx, cury, child1X, child1Y, child2X, child2Y, child3X, child3Y;
double leastangle, greatestangle, outerangle, outerangle2, leastlitangle, greatestlitangle;
/* the point of origin is always marked by the traverse. */
Map_FovCallback(map, mapx, mapy, mapz, mapx, mapy, 0, 2*PI, 0, 2*PI, action);
/* these 4 squares (in this order) are a valid "starting set" for Spiralpath traversal.
A valid starting set is either a clockwise or counterclockwise traversal of all
the points with manhattan distance 1 from the origin. */
FOV_TestMark(QX, QY, &Qtail, 1, 0, arcstart, arcend, FOV_MinAngle(1,0), FOV_MaxAngle(1,0));
FOV_TestMark(QX, QY, &Qtail, 0, 1, arcstart, arcend, FOV_MinAngle(0,1), FOV_MaxAngle(0,1));
FOV_TestMark(QX, QY, &Qtail, -1,0, arcstart, arcend, FOV_MinAngle(-1,0), FOV_MaxAngle(-1,0));
FOV_TestMark(QX, QY, &Qtail, 0,-1, arcstart, arcend, FOV_MinAngle(0,-1), FOV_MaxAngle(0,-1));
while(Qhead != Qtail){
FOV_Dequeue(QX, QY, &Qhead, &curx, &cury, &child1X, &child1Y, &child2X, &child2Y, &child3X,
&child3Y, &leastangle, &outerangle, &outerangle2, &greatestangle,
&leastlitangle, &greatestlitangle);
if (FOV_Distance(0,0,curx,cury) <= radius && FOV_In_Arc(curx, cury, arcstart, arcend)){
Map_FovCallback(map, mapx, mapy, mapz, mapx+curx, mapy+cury,
leastangle, greatestangle, leastlitangle, greatestlitangle, action);
if (FOV_Transparent(map, mapx+curx,mapy+cury, mapz)){
FOV_TestMark(QX, QY, &Qtail, child1X, child1Y, leastlitangle, greatestlitangle, leastangle, outerangle);
if (outerangle2 != 0.0){
FOV_TestMark(QX, QY, &Qtail, child2X, child2Y, leastlitangle, greatestlitangle, outerangle, outerangle2);
FOV_TestMark(QX, QY, &Qtail, child3X, child3Y, leastlitangle, greatestlitangle, outerangle2, greatestangle);
}
else
FOV_TestMark(QX, QY, &Qtail, child2X, child2Y, leastlitangle, greatestlitangle, outerangle, greatestangle);
}
else /* cell is opaque. We pass an infinitely-narrow ray of
light from its first corner to its first child if we
are doing corner touchup. */
if (cornertouchup && (leastlitangle == leastangle))
FOV_Mark(QX, QY, &Qtail, child1X, child1Y, leastangle, leastangle);
}
}
}