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.