Tileset Design Tip

Older games such as the early Ultimas had one tile for each type of terrain. Here's a screenshot of Ultima IV:



The look of the terrain improves dramatically if we add transitions from one type of terrain to another. Here's Ultima V:



Adding transitions can greatly increase the number of tiles required.

Here is a simple terrain consisting of two types of locations: ground and water. As in Ultima IV, there is one tile for each terrain type; the white lines indicate the boundaries of the tile bitmaps.



To add artistic transitions, a natural progression from the Ultima IV-style tiles is to turn the ground tile into a set of ground tiles and the water tile into a set of water tiles. Each tile in a set corresponds to a different configuration of neighbor terrain types. This solution looks something like this:



The terrain types are effectively defined at the centers of the tiles. This is not a good solution; it creates a combinatorial explosion because the tile's appearance is affected by nine different grid locations.

It is much better to define terrain types at the corners of the tiles:



Now each tile is defined by only four grid locations.

Addendum (5/13/07)

I got a comment about how foreground tiles should be aligned relative to the background tiles. The commenter is exactly right; foreground tiles are generally centered on the background tiles' corners. Here's an example with programmer art by me (except for the character which is from Zelda: Minish Cap):



The road, forest, and castle tiles are all offset so they are centered on the corners of the background tiles.

Hex grids

Geometry

A tiling of regular hexagons can be laid out on a rectangular grid:


Via the Pythagorean Theorem, the relationship between horizontal and vertical grid line spacing is:

For every hexagonal tiling there is an isomorphic triangular tiling representing hexagon adjacencies:



Coordinates

How should coordinates be assigned to the hexagons in the grid? The first thing many people think of is to try to approximate the rows and columns of a rectangular grid:



Transforming the isomorphic triangle grid to rectangular form shows the problem with this, though:



Because the diagonals between adjacent hexes run in different directions on alternate rows, working with the hex grid is more complicated. For instance, a pathfinding routine needs to know the coordinates of each hex's neighbors. With this layout it is necessary to see if the hex is on an even row or an odd row, and generate a different set of neighbor coordinates for each.

A better way to number hexes is to keep both horizontal and “vertical” axes straight:



Now, the transformation between the hexagonal layout and the square layout preserves all straight lines, and each hex looks like every other:



It's fairly easy to convert back and forth between the two coordinate systems if the first one is desired from an interface standpoint.

Converting from plane coordinates to hex coordinates

How can a position in the continuous Cartesian plane be converted into hex grid coordinates? Examine this affine transformation:



Four of each hex's edges now line up with the unit grid, and the two remaining diagonal edges are between hexes with the same X coordinate. Thus, every point within a square on the unit grid corresponds to the same X coordinate in the hex grid. After transforming the input point, round each component down (the floor() function in C) to get the integer coordinates of a unit grid square. From these unit grid square coordinates compute the hex X coordinate by summing the grid square X and Y, adding 2 (or whatever offset is necessary given your hex layout), and integer-dividing by 3, since the band of squares that correspond to the same hex X coordinate is 3 grid squares wide. In equation form:

The hex Y coordinate is determined via a similar method. Using a different affine transform, once again align the hexes such that four of the hex edges are aligned with the unit grid, but this time ensure diagonal edges are between hexes with the same Y coordinate:



Again, determine integer grid square coordinates by rounding down the transformed point's coordinates, then sum them, add 2, and integer-divide by 3 to yield the hex's Y coordinate.

The precise A, B, C, and D coefficients for each of the transforms will depend on the scale and geometry of your hex grid.

To build a transformation matrix, think about what you want to come out when you put in (1, 0) and (0, 1). (1, 0) becomes (A, C) with our equations, while (0, 1) becomes (B, D).

Distance

Given the signed offset of a hex in x and y (in integer grid coordinates), it's easy to compute the number of steps needed to move to it. The formula is slightly different depending on which direction the grid's diagonals go.

If (1, 0) and (0, 1) are adjacent in the hex grid:

If (0, 0) and (1, 1) are adjacent in the hex grid:

References

Amit Patel has an excellent site covering lots of game-related topics, including a section on hex grids.

Aiming a projectile at a moving target

To hit a moving target by shooting a gun you have to lead it, aiming at the spot where the target will be when the bullet reaches it. In this article we consider three successively harder versions of this problem.

To simplify the math, express the target's position and velocity relative to the shooter's, so that the shooter is effectively stationary at the origin. Assume that the target moves in a straight line, if it is moving. Also assume no air drag.

Motion without gravity

Without gravity, bullets travel in a straight line at constant velocity. To determine where to shoot, imagine shooting an infinite number of bullets simultaneously in all directions, forming an expanding sphere of death. While the sphere is expanding, the target is moving along a straight line (or standing still). If we can determine the instant at which this expanding sphere touches the moving target, we know where to aim: at the target's position when it gets hit by the expanding sphere of death.

Variable definitions:

Equation for the time when the target and bullet are equidistant from the shooter:

Square both sides:

Expand:

Group terms by powers of t:

Examine the equation above. If the target's velocity is zero, the impact time works out to simply be target distance divided by bullet speed, which makes sense. The constant term is never negative; it is positive as long as shooter and target are not at the same position. The quadratic term curves upward if the target's speed is faster than the bullet speed. In this case, only the linear term would be capable of bringing the curve below the zero line. In problem terms: if the target is faster than the bullet, the bullet can hit the target only if the target is moving toward the shooter fast enough.

Code for solving this quadratic might look like this:

double time_of_impact(double px, double py, double vx, double vy, double s)
{
    double a = s * s - (vx * vx + vy * vy);
    double b = px * vx + py * vy;
    double c = px * px + py * py;

    double d = b*b + a*c;

    double t = 0;
    if (d >= 0)
    {
        t = (b + sqrt(d)) / a;
        if (t < 0)
            t = 0;
    }

    return t;
}

I've done a bit more simplification in going from the equation to the code. Any time there's a 2 on the linear coefficient of the quadratic (which actually happens fairly frequently in my experience), it cancels with the 2 in the denominator and the 4 in the discriminant of the usual quadratic formula. Also, negating the quadratic coefficient (a in the code) cleans out a few minus signs.

Once t is known, plug it into the expression for the motion of the target to find the point to aim at:

This code works equally well with 3D vectors. In a real game I'd be using a vector data type rather than passing around the X, Y, and Z components individually, and I'd have a function for doing dot products instead of writing out x1*x2 + y1*y2 + z1*z2 every time.

If the discriminant (d in the code) is less than zero, it means there are no real roots. In real terms this means the target is moving away faster than the bullet can travel, so there is no possibility of an impact. The code deals with the no-root situation by clamping t to zero, which will cause the gun to aim at the target's current position. A more sensible thing to do might be to find the time t that minimizes distance between bullet and target, and aim at the target's position then.

There is also generally a negative root which corresponds to playing time backwards from the current moment, and as such is not usable.

Space combat games such as Freelancer or Darkstar One draw a targeting reticle ahead of enemy ships, at the spot where you need to shoot in order to hit them. Now you can go forth and do likewise. Obviously, the aim position is different for different bullet speeds, so if you have turbolasers that shoot at 4.5 km/sec and linear tachyon atomizers that shoot at 6 km/sec, you might want two reticles.

Gravity without motion

On earth, gravity pulls bullets downward as they fly. (They also slow down quite a bit due to air resistance, but I'm not going to get into that today.) To counteract gravity you have to aim higher for far-away targets. Let's figure out how to do this with a stationary target first.

Returning to our expanding sphere of death, we could imagine it falling due to gravity as it expands. Equivalently, we could think of the stationary target “falling” upward into the sky instead. This allows us to leave the sphere centered on the origin. Here's the equation for a target which starts at rest and falls upward until it hits the expanding sphere:

In a typical game, gravity operates along a single axis. In this case, the G vector will have zeros in all the other components. Squaring:

Expand:

Group terms by power of t:

Although we have a fourth power of t, we can substitute u = t² and be left with a quadratic instead:

The two solutions to this u quadratic correspond to the two parabolic arcs that pass through the target point. There's a short, low arc and a longer, high arc. (At maximum range they merge together into one.) Choose whichever one works best for your situation.

Once you've solved for t, plug it into the equation for motion of the target to get the aim position:

Be sure that your targeting code integrates to the same position your simulation will when it moves the bullet through the air. The equations above assume correct integration, but as a kid I wrote things that weren't quite right. For instance:

newPosition = oldPosition + oldVelocity;
newVelocity = oldVelocity + acceleration;

The code is assuming that velocity is expressed in distance per frame, and acceleration in distance per frame squared. However, it should be adding half the acceleration to the position as well, like this:

newPosition = oldPosition + oldVelocity + 0.5 * acceleration;
newVelocity = oldVelocity + acceleration;

Gravity and motion together

Finally, let's shoot an arcing projectile at a moving target! The initial equation is just a combination of the starting equations for the previous two cases:

Square:

Expand:

Collect terms by power of t:

This is a quartic equation and there's no way around it. Let's start by sanity-checking it.

If gravity is zero, the quartic and cubic terms drop out (as well as part of the quadratic term) and we're left with the motion-but-no-gravity equation. If velocity is zero instead, the cubic and linear terms drop out (as well as part of the quadratic term) and we're left with the gravity-but-no-motion equation.

When I'm working on solving problems like this, I find it helpful to rig up my game to plot graphs in real time. In this case, I drive the target around and get a constantly-updated graph of the polynomial and its derivatives for shooting at it. This allows me to quickly get a feel for the nature of the problem. Here's an example graph (with added labels):



Looking at the equation, you can see that the fourth-order term will always be positive, which means that the red curve will always turn upward on the outer ends. The constant term will always be positive as long as the target is not at the same place as the shooter, which means the curve will be positive as it crosses the Y axis.

The quartic curve has (up to) three points where it changes direction from upward to downward or vice versa. One way to find the roots would be to divide the curve up into intervals between these points. If one end of an interval is above zero and the other is below zero, you know there is a root within that interval. You could use a binary search to locate it, or you could use the midpoint of the interval as an initial guess and use Newton's method to converge on the root. The outer intervals are unbounded so binary search wouldn't necessarily work there, but you could double a t value until it evaluates positive and then binary search within that interval.

The extrema of the quartic correspond to zeros (roots) of its first derivative (the green line in the graph). The first derivative of a quartic is a cubic. We could follow a similar procedure to find its roots: find the zeros of its derivative (the blue line); use them to subdivide the curve into intervals; evaluate the function at the interval endpoints; and search for roots in the intervals that cross the X axis.

When there are no roots, I decided I wanted my gun to shoot at an angle that brought the bullets as close as possible to the target. This corresponds to finding the non-negative t that gives the smallest value for the quartic function. Minima have to be either at one of the zeros of the first derivative, or at t = 0. Once the roots of the cubic are known it's simple to evaluate the function at them, and at t = 0, and pick the one with the smallest value.

Jochen Schwarze wrote some cubic/quartic solving code in Graphics Gems I which works great.

Once again, once t is known, plug it into the left-hand side of the original equation to get the aim position:

Ron Levine wrote a Usenet posting a few years ago covering some of the same ground. There's also a page on the Unreal Wiki.

Raytracing on a grid, in Haskell

I attempt to write something in Haskell every now and then. Mainly this is because I think we're going to have to move beyond the imperative model in order to effectively use our increasingly parallel computers. Languages like C are built around the assumption that there is a single locus of control which is reading data from memory, modifying it, and writing it back. Multi-threaded programming is possible in C but it's devilishly difficult.

Haskell's a good-looking language, in my opinion; it is parenthesized like Scheme, but due to its equational and algebraic syntax needs far less of them. It uses layout like Python to indicate block structure, which eliminates even more syntactic verbiage. It's got static typing with type inference, so the compiler catches my stupid mistakes with a minimum of additional typing. In general, when the program compiles, it works, which is a very different experience from coding in, say, Scheme or Python.

For fun, I ported my grid raytracing test program from C++ to Haskell. Here's the original C++ code:

#include <cmath>
#include <windows.h>
#include <gl/glut.h>

static void draw_frame();
static void window_was_resized(int width, int height);
static void key_pressed(unsigned char key, int x, int y);
static void mouse_activity(int button, int state, int x, int y);

static const initial_window_size_x = 800;
static const initial_window_size_y = 800;

static const pixels_per_unit = 64;

static int g_window_width  = 0;
static int g_window_height = 0;

static double g_line_x0 = 4;
static double g_line_y0 = 1;

static double g_line_x1 = 1;
static double g_line_y1 = 1;

static int g_nr_points_defined = 2;

int main(int argc, char * argv[])
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);
    glutInitWindowPosition
    (
        (GetSystemMetrics (SM_CXSCREEN) - initial_window_size_x) / 2,
        (GetSystemMetrics (SM_CYSCREEN) - initial_window_size_y) / 2
    );
    glutInitWindowSize(initial_window_size_x, initial_window_size_y);
    glutCreateWindow("Line Draw Test");

    glutReshapeFunc(window_was_resized);
    glutDisplayFunc(draw_frame);
    glutKeyboardFunc(key_pressed);
    glutMouseFunc(mouse_activity);

    glEnable(GL_COLOR_MATERIAL);

    glutMainLoop();

    return 0;
}

static void plot_squares(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 (x1 > x0)
    {
        x_inc = 1;
        n += int(floor(x1)) - x;
        error = (ceil(x0) - x0) * dy;
    }
    else
    {
        x_inc = -1;
        n += x - int(floor(x1));
        error = (x0 - floor(x0)) * dy;
    }

    if (y1 > y0)
    {
        y_inc = 1;
        n += int(floor(y1)) - y;
        error -= (ceil(y0) - y0) * dx;
    }
    else
    {
        y_inc = -1;
        n += y - int(floor(y1));
        error -= (y0 - floor(y0)) * dx;
    }

    glColor3d(0.25, 0.25, 0.5);
    glBegin(GL_QUADS);

    for (; n > 0; --n)
    {
        glVertex2i(x,   y  );
        glVertex2i(x+1, y  );
        glVertex2i(x+1, y+1);
        glVertex2i(x,   y+1);

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

    glEnd();
}

static void draw_frame()
{
    glClear(GL_COLOR_BUFFER_BIT);

    // Set up the projection matrix.

    double window_world_size_x = double(g_window_width ) / pixels_per_unit;
    double window_world_size_y = double(g_window_height) / pixels_per_unit;

    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0, window_world_size_x, 0, window_world_size_y);

    // Plot the line's squares if the line is defined.

    if (g_nr_points_defined >= 2)
    {
        plot_squares(g_line_x0, g_line_y0, g_line_x1, g_line_y1);
    }

    // Draw a background grid.

    int number_of_lines_x = int(ceil(window_world_size_x));
    int number_of_lines_y = int(ceil(window_world_size_y));

    glColor3d(0.5, 0.5, 0.5);
    glBegin(GL_LINES);

    int i;
    for (i = 0; i < number_of_lines_x; ++ i)
    {
        glVertex2d(i, 0);
        glVertex2d(i, window_world_size_y);
    }

    for (i = 0; i < number_of_lines_y; ++ i)
    {
        glVertex2d(0, i);
        glVertex2d(window_world_size_x, i);
    }

    glEnd();

    // Draw the actual line, if defined.

    if (g_nr_points_defined == 1)
    {
        glColor3d(1, 1, 1);
        glBegin(GL_POINTS);
        glVertex2d(g_line_x0, g_line_y0);
        glEnd();
    }
    else if (g_nr_points_defined >= 2)
    {
        glColor3d(1, 1, 1);
        glBegin(GL_LINES);
        glVertex2d(g_line_x0, g_line_y0);
        glVertex2d(g_line_x1, g_line_y1);
        glEnd();
    }

    glutSwapBuffers();
}

static void window_was_resized(int width, int height)
{
    g_window_width  = width;
    g_window_height = height;

    glViewport(0, 0, width, height);
}

static void key_pressed(unsigned char key, int x, int y)
{
    if (key == 27)
    {
        exit (0);
    }
}

static void mouse_activity(int button, int state, int x, int y)
{
    if (state == GLUT_DOWN)
    {
        if (button == GLUT_LEFT_BUTTON)
        {
            // Get the coordinates of the mouse click in world coordinates.

            GLdouble modelview_matrix[16];
            GLdouble projection_matrix[16];
            GLint viewport[4];

            glGetDoublev(GL_MODELVIEW_MATRIX, modelview_matrix);
            glGetDoublev(GL_PROJECTION_MATRIX, projection_matrix);
            glGetIntegerv(GL_VIEWPORT, viewport);

            double wx, wy, wz;

            gluUnProject(x, (g_window_height - 1) - y, 0, modelview_matrix,
                projection_matrix, viewport, &wx, &wy, &wz);

            if (g_nr_points_defined == 1)
            {
                g_line_x1 = wx;
                g_line_y1 = wy;
                g_nr_points_defined = 2;
            }
            else
            {
                g_line_x0 = wx;
                g_line_y0 = wy;
                g_nr_points_defined = 1;
            }

            glutPostRedisplay();
        }
    }
}

Here is the same program written in Haskell:

-- Raytracing on a grid

import Data.IORef (IORef, newIORef, readIORef, modifyIORef)
import System.Exit (exitWith, ExitCode(ExitSuccess))
import Graphics.Rendering.OpenGL
import Graphics.UI.GLUT

initialWindowSizeX = 800
initialWindowSizeY = 800

pixelsPerUnit = 64

main = do
    getArgsAndInitialize
    initialDisplayMode $= [RGBAMode, DoubleBuffered]
    initialWindowSize $= Size initialWindowSizeX initialWindowSizeY
    (Size screenSizeX screenSizeY) <- get screenSize
    let initialPos = Position x y where
        x = (screenSizeX - initialWindowSizeX) `div` 2
        y = (screenSizeY - initialWindowSizeY) `div` 2
    initialWindowPosition $= initialPos
    createWindow "Grid Raytracing Demo"

    endpoints <- newIORef []

    displayCallback $= display endpoints
    reshapeCallback $= Just reshape
    keyboardMouseCallback $= Just (keyboard endpoints)
    matrixMode $= Projection
    
    mainLoop

display endpoints = do
    clear [ColorBuffer]
    points <- readIORef endpoints
    windowPixelSize <- get windowSize
    drawSquares points
    drawGrid windowPixelSize
    drawLine points
    swapBuffers

reshape size@(Size w h) = do
    viewport $= (Position 0 0, size)
    loadIdentity
    ortho2D 0 ((fromIntegral w) / pixelsPerUnit) 0 ((fromIntegral h) / pixelsPerUnit)

keyboard _ (Char '\27') Down _ _ = exitWith ExitSuccess
keyboard endpoints (MouseButton LeftButton) Down _ pos = do
    (wx, wy) <- worldFromScreen pos
    modifyIORef endpoints (addEndpoint (wx, wy))
    postRedisplay Nothing
keyboard _ _ _ _ _ = return ()

addEndpoint pos (_:_:_) = [pos]
addEndpoint pos endPoints = pos : endPoints

drawSquares (end1 : end0 : _) = do
    currentColor $= Color4 0.25 0.25 0.5 1
    renderPrimitive Quads $ mapM_ drawQuad (squaresOnLine end0 end1)
    where
        drawQuad (x, y) = do
            vertex $ Vertex2 x0 y0
            vertex $ Vertex2 x1 y0
            vertex $ Vertex2 x1 y1
            vertex $ Vertex2 x0 y1
            where
                x0 :: GLint
                x0 = fromIntegral x
                x1 = fromIntegral x + 1
                y0 = fromIntegral y
                y1 = fromIntegral y + 1
drawSquares _ = return ()

drawGrid (Size sizeX sizeY) = do
    currentColor $= Color4 0.5 0.5 0.5 1
    renderPrimitive Lines $ mapM_ (\(x, y) -> vertex $ Vertex2 x y) points
    where
        points = (interleave minYs maxYs) ++ (interleave minXs maxXs)
        minXs = zip (repeat 0) ys
        maxXs = zip (repeat maxX) ys
        minYs = zip xs (repeat 0)
        maxYs = zip xs (repeat maxY)
        xs = take (ceiling maxX) [0..]
        ys = take (ceiling maxY) [0..]
        maxX = (fromIntegral sizeX) / pixelsPerUnit
        maxY = (fromIntegral sizeY) / pixelsPerUnit

interleave (x:xs) (y:ys) = x : y : interleave xs ys
interleave _ _ = []

drawLine ((x0, y0) : (x1, y1) : _) = do
    currentColor $= Color4 1 1 1 1
    renderPrimitive Lines $ do
        vertex $ Vertex2 x0 y0
        vertex $ Vertex2 x1 y1
drawLine ((x0, y0) : _) = do
    currentColor $= Color4 1 1 1 1
    renderPrimitive Points $ do
        vertex $ Vertex2 x0 y0
drawLine _ = return ()

worldFromScreen (Position sx sy) = do
    viewport@(_, Size _ viewSizeY) <- get viewport
    projectionMatrix <- get (matrix $ Just Projection) :: IO (GLmatrix GLdouble)
    modelviewMatrix <- get (matrix $ Just $ Modelview 0) :: IO (GLmatrix GLdouble)
    let screenPos = Vertex3 (fromIntegral sx) (fromIntegral ((viewSizeY - 1) - sy)) 0
    (Vertex3 wx wy wz) <- unProject screenPos projectionMatrix modelviewMatrix viewport
    return (wx, wy)

squaresOnLine (x0, y0) (x1, y1) = take n (genSquares (floor x0) (floor y0) error) where
    n = 1 + abs((floor x1) - (floor x0)) + abs((floor y1) - (floor y0))
    dx = abs (x1 - x0)
    dy = abs (y1 - y0)
    xInc = if x1 > x0 then 1 else -1
    yInc = if y1 > y0 then 1 else -1
    error = dy * tNextX - dx * tNextY
    tNextX
        | x1 > x0   = (fromIntegral (ceiling x0)) - x0
        | otherwise = x0 - (fromIntegral (floor x0))
    tNextY
        | y1 > y0   = (fromIntegral (ceiling y0)) - y0
        | otherwise = y0 - (fromIntegral (floor y0))
    genSquares x y error
        | error > 0 = (x, y) : genSquares x (y + yInc) (error - dx)
        | otherwise = (x, y) : genSquares (x + xInc) y (error + dy)

Both versions use OpenGL with the GLUT library for handling window creation/resizing and keyboard/mouse input. The Haskell version clocks in at around 126 lines, while the C++ version has around 230 lines. I have much more experience writing C++ than Haskell, so the Haskell version may not be great style.

Obvious differences:

Haskell, like Python, uses indentation to indicate the block structure of the code, instead of explicit markers. In C++ I prefer to keep my block markers lined up vertically to aid in matching them visually; this adds lines to the code.

The C++ code contains much more type annotation than the Haskell code. (Haskell type annotations are the phrases beginning with :: such as :: GLint.) Because types are largely inferred, this Haskell program contains only three type annotations. These are needed because Haskell's OpenGL binding is parameterized on input types, so for instance the Vertex2 constructor can take integer, 32-, or 64-bit floating point values as input. Because the input numbers don't offer any clues, the compiler needs a hint to know which one to use. If the constructors for the different types were named differently (Vertex2i, Vertex2f, and Vertex2d, say, as is done in the C API) then these type annotations would not be necessary.

C++ inherits C's single-pass compilation model to some extent, so forward declarations are necessary to be able to call functions before the lines where they are defined. Haskell allows you to define and use functions in any order.

Because OpenGL is implemented as a state machine, and because of the nature of input and output in general, most of the Haskell code has an imperative structure. In fact, the only functions that are purely functional (meaning all inputs and outputs are explicitly listed) are addEndpoint, interleave, and squaresOnLine.

Conditionals tend to be represented without if-statements in the Haskell code. Some if statements transform into multiple function definitions, with each definition covering a portion of the possible input. For instance, drawLine draws nothing if no endpoints are defined; draws a single point if only one endpoint has been defined; and draws a line between endpoints otherwise. Other if statements transform into patterns on a single function definition. For instance, tNextX in squaresOnLine is defined differently depending on the relative magnitudes of x0 and x1.

Loops, likewise, are less obvious in the Haskell version. The first line of squaresOnLine calls take to take the first n items of a list, for instance. It gets an infinite list from the genSquares subfunction which uses recursion to produce the list. Recursion is the heart of how loops are handled in Haskell, but often it's possible to call a function to handle the recursion internally. The mapM_ in drawGrid is an example of this.

Some less obvious differences:

The Haskell program separates concerns better. For instance, the squaresOnLine function generates all the squares intersected by the line segment, but drawing those squares is done in drawSquares. If we need to find the squares to do something else it is easy to reuse squaresOnLine. This could (and probably should) be done in the C++ version, but would likely add a fair amount of additional code.

Internal functions are extremely handy. Note that genSquares inside squaresOnLine can see the variables dx, dy, xInc, and yInc defined in the outer function. This simplifies the interface to genSquares so that it only contains the values that change during generation.

Haskell has no implicit conversion from integer to floating-point types, so lots of fromIntegral calls are needed.

Managing mutable state is kind of a pain. Fortunately for this program, the only state we have is the endpoints that the user has chosen. The program creates a mutable variable (an “IORef”) at startup, modifies it when the user clicks the mouse, and reads it to draw the view.

Notes on Outcast

Outcast was a remarkable game produced by the now-defunct Belgian studio Appeal and published by Infogrames (now Atari) in 1999. If you've seen the movie Stargate you have the gist of the game's plot. Your character is transported to a network of worlds connected by stargates (sorry, daokas). These worlds are populated by humanoid aliens who have learned some English (if you've seen the movie you have an idea why), and are ruled by an oppressive tyrant. It seems everyone has been expecting your arrival for many years, and you are thrust into the role of a messiah. It's a lengthy action-adventure, so you can expect much combat, conversation, and carrying of items.

Outcast was released during the early days of hardware 3D acceleration, when accelerators were capable of pushing lots of pixels but not much else. 3D-accelerated games tended to all look pretty similar. Rather than go down the hardware-acceleration road, Appeal opted to use a software renderer. This allowed them to produce gorgeous effects that would not be possible in hardware rendering for several more years. These effects included things like depth-of-field blurring, bump mapping, and environment-mapped water reflections. The terrain was rendered using raycasting (a restricted form of raytracing); doing a terrain with the same density of detail using polygons is a bit of a challenge even today.

Unfortunately, the graphic effects came at a heavy cost: you needed a top-of-the-line PC at the time, but it rendered to sub-640x480 resolutions. These ended up limiting the market of people who wanted to play the game, as gamers with high-end PCs also tended to have 3D accelerators that they wanted to see put to use.

The soundtrack is sumptuous, featuring both the Moscow Symphony and Choir. The songs are wonderful. Dialogue is spoken throughout; the games uses cell-phone GCM compression and so is able to fit vast amounts of speech into a modest amount of disk space.

Outcast made some interesting design decisions that I want to mention:

The aliens had their own language before being introduced to English. Like most situations where a conqueror's language is superimposed on a native language, lots of nouns remain from the native language, and the aliens will occasionally talk to each other entirely in their own language, leaving you feeling somewhat left out. In Outcast you are overwhelmed at first by the new vocabulary, but the game provides you with a lexicon that fills in as you are introduced to new words, and soon you know all about daokas and the rest. I found this to be quite immersive; the designers went the extra mile to make the world feel plausible.

Innumerable games have numbers representing the player's strength, dexterity, and so forth, which improve over the course of the game. Rather than the player character getting stronger or faster, Outcast gives you missions to complete which weaken the enemies. For instance, you can cut off their food supplies, sabotage their weapons production, or cut off their pay. These have different, specific effects: cutting off food reduces their hit points, sabotaging weapons reduces the amount of damage they do, and cutting pay reduces the overall number of soldiers you can encounter. I like this approach very much.

Being an adventure game, there are many, many times when you need to travel somewhere to talk to someone. The game world is fairly densely populated. Some of these characters have names and are important to the game plot; the majority of them are “extras” and can only provide general information. Finding a specific named person among the crowds could be a major challenge, but the designers provided a fantastic mechanism that I am still amazed few other games have done: you can stop and ask for directions.

When you strike up a conversation with someone, one of the things you can ask is “Where's So-and-so?” Depending on how far away the target is, you will get different answers. If the target is in a different world, the person will tell you which one. Once you're in the right world but far away, you will get an indication of the general area the target occupies. As you get closer you get more precise answers, until you are within sight; then the person you are talking to will simply turn and point, saying “That's him, over there.”

The behavior of people in general is quite good. They have business to do: moving boxes, harvesting riss, delivering water, begging, mining, or collecting taxes, to name just a few activities. When gunfights erupt they cower or run. Soldiers take cover and step out to fire. Their leaders will call them to arms, and they circle around to try and get crossfire on you.

To conclude: I'd highly recommend trying out this game if you can get your hands on it. It runs fine on modern computers with a couple of exceptions. Movement through rice paddies is excruciatingly slow (instead of being merely slow, as intended), and mounted riding on twonhas is problematic; they tend to get stuck. I don't remember either of these problems when playing it originally, so it probably has something to do with the vastly higher clock speeds modern computers have. Neither of these problems is a game-breaker.

Addendum: I wrote the post from memory, not having played Outcast in a couple of years. I fired it up tonight to grab a screenshot. Unfortunately it doesn't run so well on my current computer; it crashes consistently when I attempt to travel through the portal shown above. Hopefully your luck will be better. Outcast does some interesting things with its data files (such as the GSM compression for voice) which I hope to cover in a future article.

Next Monday: Grid raytracing code in Haskell

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).

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.