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