**COPYRIGHT NOTICE:**

This document is (c)copyright 1995 Chris Palmer.

All rights reserved.

This document is freely redistributable provided this copyright notice is included verbatim.

A tile based game is often presented with the problem of limiting what to display for the player. This is required to stop the player from seeing through walls and thereby giving away secret areas.

The algorithm presented here is an O(n), n=# of tiles being displayed, algorithm which constructs pseudo sight lines from the player's position to each tile on the display.

The crux of the algorithm is realizing that there are one or two points beside any square which can be used to determine whether or not the square has been blocked. The information about which squares are obscured may then be propagated out within the displayable portion.

### Game Information

This algorithm is based on an attribute "opaqueness" for each square on the map. If a square is opaque then it is not possible to see through it. The key word here being through.

```
For example, if '*' represents a square which is opaque and ****
'.' represents a square which is not, the opaqueness of the *..*
squares will be used to limit the displayable portion to *..*
this section only. ****
```

The actual implementation of the opaqueness is irrelevant.

Otherwise, it is assumed that the game has an absolution top-left hand corner at (0,0) each tile takes exactly one square of the map.

### Cartesian Algebra

As mentioned earlier, the crux of the algorithm is identifying the two points which may or may not be obscuring the square that you are considering. I'll briefly explain how the one or two points are selected.

```
We are seperating the visual field into the four + A +
quadrants as indicated in figure 2. It is important + +
to notice that area A&C and B&D differ only in the sign + +
of the vectors. We will be using an origin of (mid,mid) + +
which will be translated to the actual map coordinates D + B
when we need information about the opaqueness of a + +
square or when we actually display a tile. + +
+ +
We may now use these quadrants to easily select the + C +
point(s) we wil be using at each step. For any point [ figure 2]
(x,y) we will find a point in the diagonal direction
to the origin and one in the horizontal or vertical direction to the
origin. For any point (x,+/-y) these two points will actually
end up being the same.
```

For a vector (u,v) (in a tile based system), the unit vector in the direction of (u,v) is (sign(u), sign(v)). So for selecting point 1, we want the diagonal direction to the origin. That is for any vector (u,v) with a unit vector (as defined above) (u',v') then the diagonal direction to the origin is -(u',v').

For the second point, we need to determine whether or not we are in quadrants A/C or B/D. For quadrants A/C we will find a vertical vector in the direction to the origin. For quadrants B/D we will find a horizontal vector in the direction to the origin.

So for any map point (x,y) with origin (o_x, o_y) and any position (i,j) in our translated coordinate system we simply choose

```
point 1 = (-1 * sign (i) + i, -1 * sign (j) + j)
point 2 = { (i, -1 * sign(j) +j) IF |j| > |i|
{ (-1 * sign (i) + i, j) IF |j| < |i|
{ point 1 IF |j| = |i|
```

### Algorithm

Say we want to display the map with the player at some point (o_x,o_y). The notation ||(x,y)|| means the distance from (x,y) to the origin (o_x,o_y) which is sqrt ((x-o_x)^2 + (y-o_y)^2).

Let sign(x) = |x|/x which is defined for all x != 0

Let U = (u,v) be a vector relative to the origin.

Let U' = (u+o_x,v+o_y) be U in the actual map coordinates.

Let from_map = (o_x - DELTA, o_y - DELTA) translate from map coordinates to the coordinate system described above.

Let opaque be a matrix 2*DELTA+1 x 2*DELTA+1 whose initial contents are undefined.

```
/* Manually do delta = 0 by making the origin non-opaque. */
opaque[DELTA+1, DELTA+1] = 0
FOR delta = 1 TO MAX_DELTA
/* U is a vector from (o_x,o_y) to some point in the map */
FOR each vector U where ||U|| is approximately delta
/* You could do is ||U||=delta but that involves circles, we will
* use instead ||U||~delta defined as ||U||~delta IFF U lies
* on the square with sides 2*delta and centered at the origin.
*/
point1 = (-1 * sign (u) + i, -1 * sign (v) + v)
IF |v| < |u| THEN
point2 = (i, -1 * sign (v) + v)
ELSE IF |v| > |u|
point2 = (-1 * sign (u) + u, v)
ELSE point2 = point1
IF opaque[point1] + opaque[point2] >= 2 THEN
/* Both points are opaque or one is *REALLY* hard to see through */
opaque[U] = 1
ClearThe Tile (U - from_map)
ELSE
opaque[U] = Map_OpaqueAtSquare (U - from_map)
DrawTheTile (U - from_map)
ENDIF
```

Believe it or not, that's the entire algorithm which will draw the screen limiting the player's vision.

Now, here is a C implementation of this algorithm which uses the following functions:

```
Graph_ClearTile (x,y) display a blank tile at the map location (x,y)
Graph_DrawTile (x,y) display the tile(s) at the map location (x,y)
Map_Opaque (x,y) returns TRUE/FALSE to is (x,y) opaque?
#define DELTA 6 /* gives 13 tiles on the screen */
#define MAX_TILE_SQUARE (2*DELTA+1) /* # of tiles being displayed */
#define abs(u) ((u) >= 0 ? (u) : -(u))
#define sign(u) (((u) >= 0 ? (u) : -(u)) / (u))
static void calc_displayable_point (int x, int y, int i, int j, int mid,
char opaque[MAX_TILE_SQUARE][MAX_TILE_SQUARE])
{
struct _vector p1, p2;
if (mid + i < 0 || mid+i >= MAX_TILE_SQUARE || mid+j < 0 || mid+j >= MAX_TILE_SQUARE) {
fprintf (stderr, "FATAL: calc_displayable_point is seriously broken!\n");
exit (10);
}
if (x + i < 0 || x + i >= map->width || y + j < 0 || y + j >= map->height) {
Graph_DrawTile (i+mid, j+mid);
opaque [i + mid][j + mid] = TRUE;
return;
}
/* We may now safely assume that all array indices will be safely
* within the required ranges. We shouldn't need the first check but,
* hey, I never said I was perfect and I sometimes do violate my own
* preconditions ...
*/
/* Calculate the two points on the sight path to check */
p1.x = -1 * sign (i) + i + mid;
p1.y = -1 * sign (j) + j + mid;
if (abs (j) > abs (i)) {
p2.x = i + mid;
p2.y = -1*sign(j) + j + mid;
} else if (abs (j) < abs (i)) {
p2.x = -1*sign(i) + i + mid;
p2.y = j + mid;
} else {
p2.x = p1.x;
p2.y = p1.y;
}
if (opaque[p1.x][p1.y] + opaque[p2.x][p2.y] >= 2) {
Graph_ClearTile (i+mid, j+mid);
opaque [i + mid][j + mid] = 1;
} else {
/* The player can see this square */
Graph_DrawTile (i+mid, j+mid);
opaque [i + mid][j + mid] = Map_Opaque (i+mid, j+mid);
}
}
int Map_DisplayAt (int x, int y)
{
int i, j, dist, mid;
char opaque [MAX_TILE_SQUARE][MAX_TILE_SQUARE];
mid = DELTA+1;
Graph_DrawTile (x, y);
opaque [mid][mid] = FALSE;
for (dist = 1; dist <= DELTA; dist++) {
for (i = -dist; i <= dist; i++)
for (j = -dist; j <= dist; j += (2 * dist))
calc_displayable_point (x, y, i, j, mid, opaque);
/* We've already covered (x +- dist, y +- dist), skip those corneri
* points
*/
for (j = -dist+1; j < dist; j++)
for (i = -dist; i <= dist; i += (2 * dist))
calc_displayable_point (x, y, i, j, mid, opaque);
}
return (0);
}
```

### NOTES