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.
History:
--------
96-11-22, edan@netcom.com pointed out the fact that Graph_DrawTile
was incorrectly defined and used in the C source code example.
At the same time, I wrote some really ugly code that implements
simple ascii interfaces on top of the code. In doing so, I found
that there were even more bugs in the old code. Sorry.
I took the time to make a few minor corrections and additions.
96-11-22, history created :-)
Limiting the displayed portion (version: 96-11-22)
--------------------------------------------------
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. This
statement is, of course, only true up to some amount of error. For
large display areas, say 50x50 squares, this error begin to be
noticable around the edges of the display area.
This document is organized by explaining the preconditions that are
assumed about the game. Next is a lengthy explanation of how the
points are found [this section is provided for people who are interested
in the algorithm but is not required for someone who wants to implement
the algorith]. After this explanation the actual algorithm will be
presented and some C code snippets will be included. Last but not
least, i'll leave you with some parting words.
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) and that each tile takes exactly one square of the map.
Cartesian Algebra:
------------------
As mentionned 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. The map uses (x,y) coordinates which are independent
of the area being displayed. The display uses (i, j) coordinates which
assume that the map is being displayed to some area that has a top
left-corner of (0,0).
Graph_ClearTile (i, j)
Blank the display for tile (i,j) [of the display area]
Graph_DrawTile (i,j,x,y)
At the display area coordinates (i,j) display the tile from the
map location (x,y)
Map_Opaque (x,y)
return TRUE/FALSE as an answer to the question: "is (x,y) opaque?"
The source code is included at the very end of this document.
NOTES:
------
The astute reader will have noticed that this is really a general
information propogation algorithm with a focal point. It can easily
be adapted to implement sound waves (eg: player smashes through a door,
start a sound wave of intensity I from (x,y) and propagate it using the
discussed algorithm). Another easily seen application of this
algorithm is to implement light sources with a radius and intensity.
------------------------------------------------------------------------------
/* displayable
* -----------
* This source file implements an algorithm that crops the view area for
* a tile-type adventure game. A complete description may be found from
* my home-page
* http://www.cs.cmu.edu/~crpalmer
*
* Email may be sent to me at crpalmer+@cs.cmu.edu
*
* This source code is pretty ugly. I've grafted on a simple terminal
* neutral interface. Probably the best use for this source code would
* be to strip out the routines that do the work and to write your
* own map and graphics layer.
*
* However, compiling this source code will give you something that I
* believe works.
*
* As always, this source code is copyright (c) 1996, Chris Palmer. All
* Rights Reserved. You are granted the rights to use and redistribute
* this source code provided that this copyright notice remains intact.
* I take no responsibility for any effect of running this program, be it
* good or bad.
*
* Chris Palmer
* November 22, 1996.
*/
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
/* You can see what happens when you go to a larger display area by
* changing this parameter
*/
#if 1
#define DELTA 6 /* gives 13 tiles on the screen */
#else
#define DELTA 10 /* gives 21x21 */
#endif
/* Changing VOID_OPAQUE makes the viewable area more strict. It is no
* longer possible to "look around" small obstructions. You can try it
* and see what happens....
*/
#define VOID_OPAQUE 1
/* MAX_TILE_SQUARE is convenient */
#define MAX_TILE_SQUARE (2*DELTA+1) /* # of tiles being displayed */
/* basic math, you could write sign(u) without the division. If you use
* this software, I would recommend doing so!!! It's coded like this
* simply to illustrate the meaning of sign(u).
*/
#define abs(u) ((u) >= 0 ? (u) : -(u))
#define sign(u) ((u) == 0 ? 0 : abs(u)/u)
/* --------------------------------------------------------------------- */
/* UGLY SOURCE CODE ALERT:
*
* I've spent several minutes writing this interface. Whatever you do,
* never write code like this!
*
* screen[row][column] is the screen buffer of ascii characters
* map_data[row][column] may be either '*' for a wall or '.' for floor
* map0 and map are just stupidity to avoid changing the main algorithm
* which I've previously written.
*
* The following functions are implemented:
* Map_Opaque(x,y): is map(x,y) opaque?
* Map_MayMove(x,y) : can you walk on map(x,y)?
* Graph_ClearTile(i,j) : clear screen position (i,j)
* Graph_DrawTile(i,j,x,y) : fill screen position (i,j) with map(x,y)
* Graph_Blit() : write the screen
*/
static char screen[2*DELTA+1][2*DELTA+1];
static char *map_data[] = {
"****************************************",
"*...............****...................*",
"*.....*........**..**..................*",
"*.....*.......**....**.................*",
"***********.***......***********..******",
"*......................................*",
"*..........................****........*",
"*........*****............**..**.......*",
"*..........***...........**.**.**...**.*",
"*...........**..................**.**..*",
"*.....**...***...........**......****..*",
"*.....**..****.........********........*",
"*........***..........******...........*",
"*....*****..........******.............*",
"*..****.............***................*",
"****************************************"
};
struct {
int width, height;
} map0, *map = &map0;
struct _vector {
int x, y;
};
static int
Map_Opaque(int x, int y)
{
return(map_data[y][x] == '*');
}
static int
Map_MayMove(int x, int y)
{
return(map_data[y][x] != '*');
}
static void
Graph_ClearTile(int i, int j)
{
screen[j][i] = ' ';
}
static void
Graph_DrawTile(int i, int j, int x, int y)
{
if (map_data[y][x] == ' ') printf("space at (%d,%d)\n", x, y);
screen[j][i] = map_data[y][x];
}
static void
Graph_Blit(void)
{
int i;
screen[DELTA][DELTA] = '&';
for (i = 0; i < 2*DELTA+1+2; i++) putc('^', stdout);
putc('\n', stdout);
for (i = 0; i < 2*DELTA+1; i++) {
printf("^%-*.*s^\n", 2*DELTA+1, 2*DELTA+1, screen[i]);
}
for (i = 0; i < 2*DELTA+1+2; i++) putc('^', stdout);
putc('\n', stdout);
memset(screen, '?', sizeof(screen));
}
/* ----------------------------------------------------------------------- */
/* clip here....
*
* This starts the displayable algorithm proper. calc_displayable_point
* is the worker. Map_DisplayAt() will call it for each square in the map.
* If you have a compiler that inlines, this would be a great candidate!
*/
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_ClearTile (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] = VOID_OPAQUE;
} else {
/* The player can see this square */
Graph_DrawTile (i+mid, j+mid, x + i, y + j);
opaque [i + mid][j + mid] = Map_Opaque (x+i, y+j);
}
}
int Map_DisplayAt (int x, int y)
{
int i, j, dist, mid;
char opaque [MAX_TILE_SQUARE][MAX_TILE_SQUARE];
mid = DELTA;
Graph_DrawTile (mid, mid, 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);
}
/* ---------------------------------------------------------------------- */
/* back to the ugly code ..... */
int
main(int argc, char **argv)
{
int x = 3, y = 10;
int new_x, new_y;
char line[10];
map->width = strlen(map_data[0]);
map->height = sizeof(map_data) / sizeof(map_data[0]);
for(;;) {
Map_DisplayAt(x,y);
Graph_Blit();
if (fgets(line, 10, stdin) == NULL) break;
new_x = x;
new_y = y;
switch(line[0]) {
case 'i': new_y--; break;
case 'j': new_x--; break;
case 'k': new_y++; break;
case 'l': new_x++; break;
default:
printf("i = up, j = left, k = down, l = right, you are at (%d, %d)\n", x, y);
}
if (new_x < 0) new_x = 0;
if (new_y < 0) new_y = 0;
if (new_x >= map->width) new_x = map->width-1;
if (new_y >= map->height) new_y = map->height-1;
if (Map_MayMove(new_x, new_y)) {
x = new_x;
y = new_y;
}
}
return(0);
}