---------------------------------------- -- APPENDIX I : Limiting the display -- ---------------------------------------- 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. There are no restrictions on works derived from this document. A common problem to most tile based games is "what can the player see?". For example, in a dungeon setting you must be very careful to limit what is shown to the player or else there is just no point including secret doors. Map: Display: ************* ********* [ assume that S is a secret *...*.......* ===> *.......* door and most likely looks *...S.......* S.......* like the rest of the walls ] ************* ********* I've come up with my method of choice which anyone is free to dispute with me or to offer up a better solution. This algorith is O(n) with a moderate constant (that is, the algorithm looks at each square only once and doesn't have a particularily large or small overhead). You need one extra piece of information in your map (which hasn't been discussed in the tileFAQ) which is opaqueness of each square. That is you need to be able to get a value of: 1 = You cannot see through this square. This does not mean that the square is never visible just that things "behind" it won't be visible. 0 = You can see through this square. It does not matter how you store this information. Where this algorithm came from I defined all my objects to have many attributes one of which was opaqueness. Another approach would be to embed it in the map itself (along the lines of the walkability flag described in the FAQ). I'll be using a standard coordinate system where the map is located on a cartesian plane and i'll be using (x,y) as a normal notation. I'm assuming that the player is at position (o_x, o_y) and that you want to draw the map with the player in the center of the square and with a radius of DELTA (that means that you want to draw DELTA*2+1 by DELTA*2+1 tiles). For any pedantic readers: define the radius of a square as being the length of any orthogonal vector from the origin to the square. Throughout the remainder of this explanation i'll include the "pedantic people" comments in square brackets. If you don't care, then don't read the information in square brackets. For the non-pedantic readers, we'll build successively larger squares starting with the squares one space from the origin. For any given point (x,y) we will approximate whether or not it is viewable by finding one or two points that lie on the previous square [Let R = radius of the square containing (x,y), find (x1,y1), (x2,y2) which lie on the square of radius R-1] between (x,y) and the origin. It turns out that the statement "one or two" points is easiest to implement if we always have two points. For any point which lies in a horizontal, vertical or diagonal line from the origin we will simply use the same point twice. The one last thing that we need is a sign function (not sine). For those who don't happen to know what that is |u| sign(u) = -------, for all u != 0, let sign(0) = 0. u To restate, assume that we have origin (o_x, o_y) and point (x,y). Let (i, j) = (x - o_x, y - o_y) [be the vector from (o_x, o_y) to (i,j)] We can then easily calculate the two points as: point_1 = (-1 * sign (i) + x, -1 * sign (j) + y) { (x, -1 * sign (j) + y) IF |j| > |i| point_2 = { (-1 * sign (i) + x, y) IF |j| < |i| { point_1 IF |j| = |i| [ point_1 is in the diagonal direction from (x,y) to (o_x,o_y) and point_2 is in the horizontal/vertical direction from (x,y) to (o_x, o_y). Pretty easy to prove that that statement is true and from that you can convincingly assert that this provides an good O(n) determination of which squares are blocked from view. Notice that the definition of sign(0)=0 means that point_2 collapses to point_1 if j = 0 or i = 0 which is why i've decided to always use two points. Well, that and the use of the constant 2 in the algorith, see the comments after the algorithm. ] From the calculation of those two points it because almost criminally easy to decide which tiles can be seen and which cannot. Let opaque be an array DELTA*2+1 by DELTA*2+1 which undefined value (ie: you don't have to initialize it). Remember that DELTA is the number of tiles in any direction [radius of the display] that we will be drawing. Here's the pseudo-code of how to do it: { cheat and do the case of delta=0 so that we don't have to worry about any kind of special case } middle = DELTA+1 { This is the middle of the display } opaque[middle][middle] = 0 { delta=0 wasn't so hard :-) } FOR delta = 1 TO DELTA DO FOR each (x,y) that lie on the square of radius delta Calculate the two points as described above, call them p1_x, p1_y, p2_x, p2_x. Make sure that (p1_x,p1_y) and (p2_x,p2_y) are on the map. IF Opaque[p1_x - o_x + middle][p1_y - o_y + middle] + Opaque[p2_x - o_x + middle][p2_y - o_y + middle] >= 2 I THEN { You can't see this square } Opaque[x - o_x + middle][y - o_y + middle] = 1 II ELSE Opaque[x - o_x + middle][y - o_y + middle] = ??? III { You might want to draw the tile now if you can } ENDIF ENDFOR ENDFOR That looks a lot more complicated than it really is. The hardest part in implementing that loop is the "FOR each (x,y) that ..." line. If you are a little creative you can do that easily enough. On line I and II the constants 2 and 1 are used to give the algorithm a little flexibility. By setting the opaqueness of unviewable squares to 1 and requiring that both "blocking" squares to be opaque (the value 2) the algorithm will allow for looking "around" minor obstacles. To make the routine much more strict you could use a value of 2 on line II which will often give more realistic displays but (IMHO) less playable results. If you would like a more detailed explanation of the derivation of the two points or something a pretty close to an actual C implementation (I have my first attempt at writing this appendix which was far too formal but did have some code with it) you can send me an email and politely ask me to forward it to you or if you have a web browser (mosaic, netscape, lynx) you could find both documents at http://www.cs.cmu.edu/~crpalmer/ Any questions/comments/criticisms can be directed to me via email at: crpalmer+@cs.cmu.edu