Monday, March 26, 2007

Raytracing on a grid

Gnast’e Villon fires his death ray wildly as Hirsutia, intrepid heroine, dives for cover. Will she escape his palace or leave a nasty stain on his tapestry?

The last two articles have been about computing everything that’s visible from a single viewpoint. Sometimes, though, all we need is a line-of-sight check between two specific points (i.e. a gun and a target). We want to identify all grid squares that intersect the line segment. If any square is solid, the line of sight is blocked.

The Bresenham line-drawing algorithm is fairly well known and might seem to be a reasonable candidate for this task. However, in its usual form it does not generate all squares that intersect the line. Fortunately there is a simple algorithm that will.

Here is a sample problem:



The numbers at top and right are the grid coordinates; the line segment goes from (0.5, 0.5) to (2.5, 3.5). We want to identify all the squares marked in pink.

In pseudocode the algorithm is as follows:

Start at the square containing the line segment’s starting endpoint.
For the number of intersected squares:
If the next intersection is with a vertical grid line:
Move one square horizontally toward the other endpoint
Else:
Move one square vertically toward the other endpoint


The number of squares intersected by the line is fairly easy to compute; it’s one (for the starting square) plus the number of horizontal and vertical grid line crossings.

As we move along the line, we can track where we are as a fraction of the line’s total length. Call this variable t. In the example, we’d start with t = 0 in the lower left corner. The first horizontal grid intersection is at 1/4, while the first vertical intersection is at 1/6. Since the vertical one is closer, we step up one square and advance t to 1/6. Now the next vertical intersection is at 3/6, while the next horizontal intersection is still at 1/4, so we move horizontally, advancing t to 1/4, and so forth.

The fraction of the line between grid intersections in the horizontal direction is simply one over the line’s horizontal extent. Likewise, the line fraction between vertical grid intersections is one over the line’s vertical extent. These values go to infinity when the line is exactly horizontal or exactly vertical. Fortunately, IEEE 754 floating-point (used by all modern computers) can represent positive or negative infinity exactly and compute correctly with them, so the divisions by zero work fine.

The only gotcha (which I missed until it was pointed out in the comments) is that zero times infinity is undefined; the result is the dreaded NaN (Not a Number). So we still have to check for zero horizontal or vertical movement to avoid trying to multiply by dt_dx or dt_dy.

Here’s code to do this:

void raytrace(double x0, double y0, double x1, double y1)
{
double dx = fabs(x1 - x0);
double dy = fabs(y1 - y0);

int x = int(floor(x0));
int y = int(floor(y0));

double dt_dx = 1.0 / dx;
double dt_dy = 1.0 / dy;

double t = 0;

int n = 1;
int x_inc, y_inc;
double t_next_vertical, t_next_horizontal;

if (dx == 0)
{
x_inc = 0;
t_next_horizontal = dt_dx; // infinity
}
else if (x1 > x0)
{
x_inc = 1;
n += int(floor(x1)) - x;
t_next_horizontal = (floor(x0) + 1 - x0) * dt_dx;
}
else
{
x_inc = -1;
n += x - int(floor(x1));
t_next_horizontal = (x0 - floor(x0)) * dt_dx;
}

if (dy == 0)
{
y_inc = 0;
t_next_vertical = dt_dy; // infinity
}
else if (y1 > y0)
{
y_inc = 1;
n += int(floor(y1)) - y;
t_next_vertical = (floor(y0) + 1 - y0) * dt_dy;
}
else
{
y_inc = -1;
n += y - int(floor(y1));
t_next_vertical = (y0 - floor(y0)) * dt_dy;
}

for (; n > 0; --n)
{
visit(x, y);

if (t_next_vertical < t_next_horizontal)
{
y += y_inc;
t = t_next_vertical;
t_next_vertical += dt_dy;
}
else
{
x += x_inc;
t = t_next_horizontal;
t_next_horizontal += dt_dx;
}
}
}


Simplifying, Round One

The above algorithm generalizes nicely to three dimensions, if you ever find yourself needing to traverse a voxel grid. However, the 2D case can be simplified a bit.

First of all, we can avoid the two divisions by scaling our t value by the product of the two denominators. Instead of going from 0 to 1, it goes from 0 to dx*dy. This makes dt_dx = dy, and dt_dy = dx. Note that now, when a line is horizontal, dt_dx is zero, instead of dt_dy being infinity. (Conversely for vertical lines.) This means that the next horizontal crossing is always at 0, and thus t never advances. Since the next vertical crossing is greater than zero, the algorithm ends up always moving horizontally. This works fine as long as we don’t rely on t reaching the end of the line to indicate completion.

Secondly, we can combine the t, t_next_horizontal, and t_next_vertical variables into one “error” term. The “error” is the difference between t_next_horizontal and t_next_vertical; if it’s positive, we know one is closer; if it’s negative, the other is closer. We add or subtract dt_dx and dt_dy as appropriate when we move.

Here’s the simplified code:

#include <limits> // for infinity
void raytrace(double x0, double y0, double x1, double y1)
{
double dx = fabs(x1 - x0);
double dy = fabs(y1 - y0);

int x = int(floor(x0));
int y = int(floor(y0));

int n = 1;
int x_inc, y_inc;
double error;

if (dx == 0)
{
x_inc = 0;
error = std::numeric_limits<double>::infinity();
}
else if (x1 > x0)
{
x_inc = 1;
n += int(floor(x1)) - x;
error = (floor(x0) + 1 - x0) * dy;
}
else
{
x_inc = -1;
n += x - int(floor(x1));
error = (x0 - floor(x0)) * dy;
}

if (dy == 0)
{
y_inc = 0;
error -= std::numeric_limits<double>::infinity();
}
else if (y1 > y0)
{
y_inc = 1;
n += int(floor(y1)) - y;
error -= (floor(y0) + 1 - y0) * dx;
}
else
{
y_inc = -1;
n += y - int(floor(y1));
error -= (y0 - floor(y0)) * dx;
}

for (; n > 0; --n)
{
visit(x, y);

if (error > 0)
{
y += y_inc;
error -= dx;
}
else
{
x += x_inc;
error += dy;
}
}
}


All-Integer Math

The above algorithm works with any input coordinates. If we restrict ourselves to integral input coordinates, or known fractions thereof, the algorithm can be converted to operate entirely with integer math. As an example let us assume that, if the (integral) input coordinates are (x0, y0) and (x1, y1), the line should be traced from (x0 + 0.5, y0 + 0.5) to (x1 + 0.5, y1 + 0.5). This is what’s going on in the example diagram, and is a reasonable choice for line-of-sight of actors who are standing in the centers of the grid squares.

As can be seen in the previous code, if the input coordinates are an integral distance apart, the only fractional number is the error term. We can once again scale everything up to make this number an integer as well. With endpoints offset from the grid by 0.5, it suffices to multiply by 2. The numerous floor() and ceil() operations are no longer needed, and the resulting code is quite simple:

void raytrace(int x0, int y0, int x1, int y1)
{
int dx = abs(x1 - x0);
int dy = abs(y1 - y0);
int x = x0;
int y = y0;
int n = 1 + dx + dy;
int x_inc = (x1 > x0) ? 1 : -1;
int y_inc = (y1 > y0) ? 1 : -1;
int error = dx - dy;
dx *= 2;
dy *= 2;

for (; n > 0; --n)
{
visit(x, y);

if (error > 0)
{
x += x_inc;
error -= dy;
}
else
{
y += y_inc;
error += dx;
}
}
}


Finally: The code above does not always return the same set of squares if you swap the endpoints. When error is zero, the line is passing through a vertical grid line and a horizontal grid line simultaneously. In this case, the code currently will always move vertically (the else clause), then horizontally. If this is undesirable, you could make the if statement break ties differently when moving up vs. down; or you could have a third clause for error == 0 which considers both moves (horizontal-then-vertical and vertical-then-horizontal).

Monday, March 19, 2007

2D portal visibility, Part 2

The last installment gave a simple algorithm for portal-based visibility computation on a 2D grid. This time let's add some features to that basis.

Range Cutoff

Cutting off the visibility search is the first obvious thing to do. If the view is a window that scrolls around to keep the player centered, the cutoff could be the edges of the viewport. Alternatively, the cutoff could be a circle around the player. In my case I made the cutoff elliptical so it would look circular on-screen:



Wall Visibility

Another easy change is to track visibility of walls in addition to (and independently from) floors. Solid squares are not marked as visible. The psuedocode for the algorithm changes to something like this:

compute_visibility(frustum, region):
if region is not solid:
mark floor as visible
for each edge of region:
clip frustum to the portion exiting through that edge
if clipped frustum is valid:
mark edge as visible
compute_visibility(clipped frustum, region beyond edge)


This produces results like this:



Note in particular the left wall of the room, which is only partially visible. The darkened walls are not visible from the yellow sphere, even though the floors of the adjacent squares are visible.

Sub-Grid Resolution: Pictures

As noted last week, one of the problems with the visibility algorithm so far is that it doesn’t show the corners of walls. Here’s an example world, shown first without line-of-sight restrictions (and with the world grid lightly superimposed):



With the current algorithm, the gray smiley-faced man can see:



This is because grid squares are considered to be wholly solid or wholly empty:



The wall pieces on either side of a corner block all sightlines to it. Very unsightly!

For my project I solved this by complicating the world representation so that grid squares no longer have to be totally solid or totally empty. The walls are represented more accurately:



The line-of-sight results are now much closer to what you would expect given the walls’ visual shape:



Because the walls don’t completely fill their squares it’s now possible to see into the corners. Gray Man can also see out the windows to the north from where he is standing.

Here's another example, first with basic full-grid visibility:



...and then with sub-grid visibility:



Note the increased visibility around corners. By having enemies use a more-restrictive visibility check for seeing the player (a raytrace using whole grid squares, for instance), I can allow the player to “peek” around a corner without being spotted.

Sub-Grid Resolution: Implementation

An obvious way to implement sub-grid resolution would be to simply have a visibility grid with a higher resolution than the game grid. In my case the game grid cells are drawn using characters from an 8x16 pixel font. I could have a visibility grid that is eight times larger horizontally and sixteen times larger vertically. Before running the game the visibility grid would be filled in by stamping in bitmaps based on the font characters. This simple approach wastes time and space, though, by storing and traversing through many more regions than necessary, especially in the squares that are completely open.

Most of the additional space requirement can be eliminated by looking up grid cell bitmaps as needed rather than copying them into one giant grid.

We can waste less time by moving away from grid-based regions. The algorithm only requires that regions be convex and polygonal. Each bitmap can be replaced by a set of connected regions. For instance, here is the northwest-corner bitmap:



Here are three convex regions, outlined in green, that represent the visible portion of the tile:



To represent these polygonal regions I turned to one of my favorite data structures, the half-edge. Here’s the data structure I’m using:

struct REGION_EDGE
{
int origin_x;
int origin_y;
bool has_area; // does this region have area?
const REGION_EDGE * next; // next edge CCW around region
const REGION_EDGE * over; // neighboring edge
};


Each half-edge contains its right endpoint, when looking at the edge from inside the region. The left vertex can be obtained by looking at the next edge’s origin. The next pointer is always non-NULL, while the over pointer is NULL if the edge represents a solid wall.

To make the collection of regions for a grid square pluggable against any other grid square, I add adapter regions so that every grid square has a single edge along each of its north, south, east, and west boundaries. These adapter regions have no area, so if the search enters them it doesn’t count as making the square visible. The area could be computed by walking around the polygon’s edges, but it’s easier to just store it in a has_area flag on each edge.

I define four special edges which indicate that an edge borders a neighboring square. When an edge is up against a border, its over member points to the special edge indicating a north, south, east, or west exit. This signals the traversal to increment its grid coordinates, and look up the set of regions for the new square.

There is a final data structure which points to the entrance edges for the four sides of each of the possible grid square types. In my case I have thirteen different types of tiles for visibility purposes.

Since getting all these pointers right is rather tedious, I wrote a program to parse a simpler description of the regions and produce source files containing the half-edge data structures. These source files are included in the game. Here are example definitions for three grid square types:

open

0 0, 8 0, 8 16, 0 16 ;

pillar

0 0, 8 0, 6 5, 1 5 ;
8 0, 8 16, 6 10, 6 5 ;
8 16, 0 16, 1 10, 6 10 ;
0 16, 0 0, 1 5, 1 10 ;

ew

0 0, 8 0, 8 6, 0 6 ;
8 0, 8 16, 8 10, 8 6 ;
8 16, 0 16, 0 10, 8 10 ;
0 16, 0 0, 0 6, 0 10 ;


Each line lists the vertices of a single region in counterclockwise order. “open” is the basic, nonoccluding square; “pillar” is a pillar standing in the middle of the square; and “ew” is a horizontal wall. The first two lines in the “ew” region set are the zero-area adapter regions, since the wall abuts those sides of the grid square.

In addition to the REGION_EDGE structure above, the generated header file includes this information:

struct REGION_SET
{
const REGION_EDGE * north_entrance;
const REGION_EDGE * south_entrance;
const REGION_EDGE * east_entrance;
const REGION_EDGE * west_entrance;

static const REGION_EDGE north_exit;
static const REGION_EDGE south_exit;
static const REGION_EDGE east_exit;
static const REGION_EDGE west_exit;
};

extern const REGION_SET region_open;
extern const REGION_SET region_pillar;
extern const REGION_SET region_ew;
extern const REGION_SET region_ns;
extern const REGION_SET region_ne;
extern const REGION_SET region_nw;
extern const REGION_SET region_se;
extern const REGION_SET region_sw;
extern const REGION_SET region_nse;
extern const REGION_SET region_nsw;
extern const REGION_SET region_new;
extern const REGION_SET region_sew;
extern const REGION_SET region_nsew;


The first few lines of the corresponding generated source file:

#include "portals.h"
#include <stdlib.h>

const REGION_EDGE REGION_SET::north_exit = { 0, 0, NULL, NULL };
const REGION_EDGE REGION_SET::south_exit = { 0, 0, NULL, NULL };
const REGION_EDGE REGION_SET::east_exit = { 0, 0, NULL, NULL };
const REGION_EDGE REGION_SET::west_exit = { 0, 0, NULL, NULL };

const REGION_EDGE edges[] =
{
{ -4, -8, true, &edges[1], &REGION_SET::south_exit }, // 0
{ 4, -8, true, &edges[2], &REGION_SET::east_exit }, // 1
{ 4, 8, true, &edges[3], &REGION_SET::north_exit }, // 2
{ -4, 8, true, &edges[0], &REGION_SET::west_exit }, // 3
{ -4, -8, true, &edges[5], &REGION_SET::south_exit }, // 4
{ 4, -8, true, &edges[6], &edges[11] }, // 5
{ 2, -3, true, &edges[7], NULL }, // 6
{ -3, -3, true, &edges[4], &edges[17] }, // 7
{ 4, -8, true, &edges[9], &REGION_SET::east_exit }, // 8
{ 4, 8, true, &edges[10], &edges[15] }, // 9
{ 2, 2, true, &edges[11], NULL }, // 10
...


The first four edges in the array correspond to the open grid square; each edge simply exits to a neighboring square. The following edges are the beginning of the pillar grid square; you can see some NULL edges bordering the central pillar, as well as some edges that border other regions within the same region set.

Finally, here is the compute_visibility code altered to use these regions:

const REGION_EDGE * north_entrance(int x, int y)
{
if (!on_map(x, y))
return NULL;

return cell_info[s_map.at(x, y).type].region->north_entrance;
}

const REGION_EDGE * south_entrance(int x, int y)
{
if (!on_map(x, y))
return NULL;

return cell_info[s_map.at(x, y).type].region->south_entrance;
}

const REGION_EDGE * east_entrance(int x, int y)
{
if (!on_map(x, y))
return NULL;

return cell_info[s_map.at(x, y).type].region->east_entrance;
}

const REGION_EDGE * west_entrance(int x, int y)
{
if (!on_map(x, y))
return NULL;

return cell_info[s_map.at(x, y).type].region->west_entrance;
}

static void compute_visibility
(
// Viewer map coordinates:
int viewer_x,
int viewer_y,
// Target cell map coordinates:
int target_x,
int target_y,
// Target region edge:
const REGION_EDGE * edge,
// Left edge of current view frustum (relative to viewer):
int ldx,
int ldy,
// Right edge of current view frustum (relative to viewer):
int rdx,
int rdy
)
{
// Abort if we are out of bounds.
if (!on_map(target_x, target_y) || edge == NULL)
return;

// Target square center position relative to viewer:
int dx = target_x - viewer_x;
int dy = target_y - viewer_y;

if (dx*dx + 4*dy*dy > 600)
return;

dx *= 8;
dy *= 16;

// This square is visible.
mark_visible(target_x, target_y);

const REGION_EDGE * e1 = edge;
while (1)
{
const REGION_EDGE * e2 = e1->next;

if (e1->over != NULL)
{
// Relative positions of the portal's left and right endpoints:
int prdx = dx + e1->origin_x;
int prdy = dy + e1->origin_y;
int pldx = dx + e2->origin_x;
int pldy = dy + e2->origin_y;

// Clip portal against current view frustum:
int cldx, cldy;
if (a_right_of_b(ldx, ldy, pldx, pldy))
{
cldx = ldx;
cldy = ldy;
}
else
{
cldx = pldx;
cldy = pldy;
}
int crdx, crdy;
if (a_right_of_b(rdx, rdy, prdx, prdy))
{
crdx = prdx;
crdy = prdy;
}
else
{
crdx = rdx;
crdy = rdy;
}

// If we can see through the clipped portal, recurse through it.
if (a_right_of_b(crdx, crdy, cldx, cldy))
{
if (e1->over == &REGION_SET::north_exit)
{
compute_visibility
(
viewer_x, viewer_y,
target_x, target_y + 1,
south_entrance(target_x, target_y + 1),
cldx, cldy,
crdx, crdy
);
}
else if (e1->over == &REGION_SET::south_exit)
{
compute_visibility
(
viewer_x, viewer_y,
target_x, target_y - 1,
north_entrance(target_x, target_y - 1),
cldx, cldy,
crdx, crdy
);
}
else if (e1->over == &REGION_SET::east_exit)
{
compute_visibility
(
viewer_x, viewer_y,
target_x + 1, target_y,
west_entrance(target_x + 1, target_y),
cldx, cldy,
crdx, crdy
);
}
else if (e1->over == &REGION_SET::west_exit)
{
compute_visibility
(
viewer_x, viewer_y,
target_x - 1, target_y,
east_entrance(target_x - 1, target_y),
cldx, cldy,
crdx, crdy
);
}
else
{
compute_visibility
(
viewer_x, viewer_y,
target_x, target_y,
e1->over,
cldx, cldy,
crdx, crdy
);
}
}
}

e1 = e2;
if (e1 == edge)
break;
}
}

void compute_visibility(int viewer_x, int viewer_y)
{
clear_visibility();
mark_visible(viewer_x, viewer_y);

compute_visibility(viewer_x, viewer_y, viewer_x, viewer_y - 1, north_entrance(viewer_x, viewer_y - 1), 4, -8, -4, -8);
compute_visibility(viewer_x, viewer_y, viewer_x, viewer_y + 1, south_entrance(viewer_x, viewer_y + 1), -4, 8, 4, 8);
compute_visibility(viewer_x, viewer_y, viewer_x - 1, viewer_y, east_entrance(viewer_x - 1, viewer_y), -4, -8, -4, 8);
compute_visibility(viewer_x, viewer_y, viewer_x + 1, viewer_y, west_entrance(viewer_x + 1, viewer_y), 4, 8, 4, -8);
}


A REGION_EDGE pointer has been added to the parameter list for compute_visibility, and the portion that navigates through a visible edge to the neighboring region is more complicated since it must deal with the various kinds of exits. Finally, the initial entry function (at the bottom) now assumes that it is starting in an empty square and begins the recursion directly in its neighbors, rather than in the same square as the viewer.

This enhanced system is more complicated than the basic visibility algorithm, but it solves the problem of being able to see into corners, and it makes the visibility solution match the visual representations of the walls much more closely.

Next Monday: Raytracing through a grid.

Monday, March 12, 2007

2D portal visibility, Part 1

Many games feature a map that starts out empty and fills in as the player's character moves through the world. There are lots of algorithms for determining what portion of the level is visible from a given vantage point. This article presents one of my favorites for two-dimensional environments.

The world is made up of connected, convex polygonal regions through which sightlines can travel. For grid-based games a natural choice for the regions is the squares of the grid.

The basic idea is simple: Start with a clear view frustum, in the region containing the viewer. At each region, if it is solid it blocks the view. Otherwise, clip the view frustum into bits that pass through each of the region's edges, and recurse to the regions that touch those edges. Pass the clipped frustum into them, so they know what portion of the view they have to concern themselves with. In pseudocode it looks like this:

compute_visibility(frustum, region):
mark region as visible
if region is not solid:
for each edge of region:
clip frustum to the portion exiting through that edge
if clipped frustum is valid:
compute_visibility(clipped frustum, region beyond edge)



There's a nice Java applet by Clark Verbrugge that demonstrates this on a hex grid.

One advantage of this algorithm over raycasting, another common algorithm, is that it does not have aliasing problems. An example you can see in some Roguelikes is when you stand close to a long straight wall and it is not continuously visible all the way down, but has invisible spots along the way. This is because the rays only partially sample the visibility, so they may miss spots. Another example is when you look through a doorway and see spots in the room beyond but the spots are not connected together into a continuous whole.

To crop the view frustum down as the recursion proceeds the algorithm makes use of what is sometimes called the “perp-dot product,” so called because it's a dot product with the second argument turned 90 degrees counterclockwise. It is also the Z component of the vector cross product, if you expand each 2D vector (x, y) to a 3D vector (x, y, 0).

The formula for the perp-dot product is:

perp_dot(a, b) = a.x * b.y - a.y * b.x

If perp_dot(A, B) is greater than zero then the vector A lies on the right when you are standing at the origin looking in the direction of vector B. If it's less than zero then vector A lies to the left. If it is equal to zero then vector A may be pointing either in the same direction as vector B, or in the opposite direction of vector B.

This algorithm is currently written to mark solid squares that terminate the recursion as visible, as is typical for Roguelikes. However, the solid square diagonally adjacent to an inside corner will not be reached by the portal algorithm, since the recursion terminates at the other two solid squares neighboring the inside corner. This results in displays like this:
#####
.....#
.....#
.....#

If the solid squares are regarded as being completely solid, this is technically correct: from inside the room, we cannot see which of these two configurations is correct:
######      #####. (another room)
.....# .....#
.....# or .....#
.....# .....#

If diagonally-adjacent inside corners like option #2 are disallowed, then you could fill in the corners with a post-process that identifies corner situations. On the other hand, if a situation like #2 means the player can move through the diagonal, then the squares on either side are not actually completely solid, and the algorithm would need to be reworked in a different way. You can subdivide squares into sub-pieces that are solid or empty depending on the configuration of neighboring squares, for example. I will present my implementation of this in a future post.

C++ Code

// Externally-defined functions:
bool is_solid(int x, int y); // Does this map cell block the view?
void clear_visibility(); // Clear all visibility markings
void set_visible(int x, int y); // Mark this map cell as being visible

// The visibility function (defined below):
void compute_visibility(int x, int y);

struct PORTAL_INFO
{
// offset of portal's left corner relative to square center (doubled coordinates):
int lx;
int ly;
// offset of portal's right corner relative to square center (doubled coordinates):
int rx;
int ry;
// offset of neighboring cell relative to this cell's coordinates (not doubled):
int nx;
int ny;
};

static const PORTAL_INFO portal[4] =
{
// lx, ly rx, ry nx, ny
{ 1, 1, 1, -1, 1, 0 },
{ -1, 1, 1, 1, 0, 1 },
{ -1, -1, -1, 1, -1, 0 },
{ 1, -1, -1, -1, 0, -1 },
};

// Internal helper function:
static void compute_visibility
(
int viewer_x,
int viewer_y,
int target_x,
int target_y,
int ldx,
int ldy,
int rdx,
int rdy
);

void compute_visibility(int viewer_x, int viewer_y)
{
clear_visibility();
for (int i = 0; i < 4; ++i)
{
compute_visibility
(
viewer_x, viewer_y,
viewer_x, viewer_y,
portal[i].lx, portal[i].ly,
portal[i].rx, portal[i].ry
);
}
}

inline bool a_right_of_b(int ax, int ay, int bx, int by)
{
return ax * by > ay * bx;
}

void compute_visibility
(
// Viewer map coordinates:
int viewer_x,
int viewer_y,
// Target cell map coordinates:
int target_x,
int target_y,
// Left edge of current view frustum (relative to viewer):
int ldx,
int ldy,
// Right edge of current view frustum (relative to viewer):
int rdx,
int rdy
)
{
// Abort if we are out of bounds.
if (target_x < 0 || target_x >= map_size_x)
return;
if (target_y < 0 || target_y >= map_size_y)
return;

// This square is visible.
set_visible(target_x, target_y);

// A solid target square blocks all further visibility through it.
if (is_solid(target_x, target_y))
return;

// Target square center position relative to viewer:
int dx = 2*(target_x - viewer_x);
int dy = 2*(target_y - viewer_y);

for (int i = 0; i < 4; ++i)
{
// Relative positions of the portal's left and right endpoints:
int pldx = dx + portal[i].lx;
int pldy = dy + portal[i].ly;
int prdx = dx + portal[i].rx;
int prdy = dy + portal[i].ry;

// Clip portal against current view frustum:
int cldx, cldy;
if (a_right_of_b(ldx, ldy, pldx, pldy))
{
cldx = ldx;
cldy = ldy;
}
else
{
cldx = pldx;
cldy = pldy;
}
int crdx, crdy;
if (a_right_of_b(rdx, rdy, prdx, prdy))
{
crdx = prdx;
crdy = prdy;
}
else
{
crdx = rdx;
crdy = rdy;
}

// If we can see through the clipped portal, recurse through it.
if (a_right_of_b(crdx, crdy, cldx, cldy))
{
compute_visibility
(
viewer_x, viewer_y,
target_x + portal[i].nx, target_y + portal[i].ny,
cldx, cldy,
crdx, crdy
);
}
}
}


Additional Algorithm Notes

The coordinate system used for portal endpoint offsets is twice the resolution of the map grid, to be able to represent the viewer's position as being at the center of a grid square. This is why dx and dy are multiplied by 2. The offsets to the corners of the squares are then +/- 1 in each direction.

Recursion depth is equal to the maximum line of sight. You may wish to impose a distance cutoff if your world is large.

There is a major subtlety at startup. This implementation starts with the viewer and target in the same square, in order to avoid duplicate code. However, in this situation there is a potential ambiguity. For example, let's say our current view frustum is out the right-hand edge. Its left endpoint is at (1, 1) relative to the viewer, and its right endpoint is at (1, -1). When we clip the opposite portal out of the square against the view frustum we have a potential problem. The portal's left corner is (-1, -1), and its right corner is (-1, 1). The algorithm clips the left edge of the frustum by taking the rightmost of (1, 1) and (-1, -1). But these lie on a parallel line, so neither is rightmost. The same is true for the right edges of the frustum and portal. If in the case of ties we take either both view frustum edges or both portal edges, then we end up with what looks like a valid clipped frustum, even though it's not. This would cause us to recurse in the direction opposite the view frustum.

To get around this problem, the algorithm above breaks ties differently for the left and right edges. One of them gets the view frustum edge, and the other gets the portal edge. For normal cases this doesn't change anything, since it doesn't matter which one we use to define the view frustum boundary. In the startup case, though, it ensures that the resulting portal will be invalid (because its right edge will be left of its left edge).

Next Monday, I hope to go into some of the ways in which this algorithm can be enhanced.

Monday, March 5, 2007

How To Name Transformation Matrices

A transformation matrix is a function for converting a point or vector from one coordinate system to another. Unfortunately people tend to name matrices after only the source or the destination coordinate system which only tells half the story.

Matrices come in two forms depending on whether they are multiplied by row or column vectors. Naturally, both are commonly used.

Direct3D uses the row-vector form, which means the vector is multiplied on the left of the matrix. In this case, name your matrices source-to-destination, where source is the input vector’s coordinate system and destination is the output vector’s coordinate system. For instance, a typical render pipeline might have matrices named modelToWorld, worldToView, and viewToScreen.

OpenGL uses the column-vector form, which means the vector is multiplied on the right of the matrix. In this case, name your matrices destination-from-source, where destination is the output vector’s coordinate system and source is the input vector’s coordinate system. For instance, a typical render pipeline might have matrices named screenFromView, viewFromWorld, and worldFromModel.

Once matrices are named in this manner, multiplying them together in the correct order is a simple matter of connecting matching coordinate systems. Concatenations of the matrices listed above would look like this:

Row-vector form: modelToScreen = modelToWorld * worldToView * viewToScreen;

Column-vector form: screenFromModel = screenFromView * viewFromWorld * worldFromModel;

Introduction

Hello!

This blog is about “play programming” in a couple of senses. It's about my hobby programming projects. Since these projects are mostly related to making computer games, it's also about that.

My plan is to post a new article every Monday.

Next Monday: portal line of sight for grid-based games (i.e. Roguelikes).