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.