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); }