Simple Line of Sight
Jump to navigation
Jump to search
Line of Sight - Steve Register [arns@arns.freeservers.com].txt
This is an article that some of you may find of interest. At the time that
I started this club I was looking for some simple line_of_sight code. After
much searching I found some source code that was similar to what I was
looking for. On the x2ftp site I found the graphical gems collection which
contained a c program called Digital Line Drawing by Paul Heckbert. The
program was described as "digline: draw digital line from (x1,y1) to
(x2,y2), calling a user-supplied procedure at each pixel. Does no clipping.
Uses Bresenham's algorithm." If you are interested in seeing the original
code I can send it to you or you can find it at the x2ftp site.
The original LOS code that was in my game only checked to see if the player
was in the same sector as the monster. If it was then the monster could see
the player. I wanted my LOS code to be of the type that knowing the
monsters x,y coords and the players x,y coords you would draw a line
between the two checking to see if the monsters sight was blocked by any
objects. This is what I have now. As of now it doesn't matter how far the
player is, if the monsters sight is not blocked it can see him. Later I
will change it to limit the distance that a monster can see, but I also
want it so that some monsters can see further that others.
The code that I will be explaining will be the modified code that I am
using in my program. I started out by trying to use the code with as little
changes as possible. Running my program after doing this caused it to hang
big time. After a lot of troubleshooting and changing I finaly got it to
work (sort of.) I found out that if the player was in a certain position
in reference to the monster that the code would not work. I found out that
if the player's y coord was equal to or less than the monster's it work ok.
If the player's x was less than the monster's x and the player's y was
greater than monster's y then the monster would not see the player, but
the program didn't hang up. If the player's x and y were greater than the
monster's x and y the program would hang.
After much hair pulling and uttering many colorful programing phrases :+)
I finally found the problem. The original code used a macro called SGN to
return the sign of the delta x and y. It was defined as the following:
#define SGN(a) (((a)<0) ? -1 : 0)
Looking at the description of the macro "take binary sign of a, either -1,
or 1 if >= 0". I'm still learning but that looked like it wuold only
return either -1 or 0 and not -1 or 1 like the description says.
After changing the macro to this:
#define SGN(a) (((a)<0) ? -1 : 1)
everything seemed to start working.
The following is the code that I use in my program. The remarks explain the
code as best as I can. If I have something wrong in my explanation if
someone would let me know I will change it. I hope this helps someone
looking to do something similar.
/* Line of sight code *
* this is a Boolean function *
* that returns FALSE if the *
* monster cannot see the *
* player and TRUE if it can *
* *
* It has the monsters x and y*
* coords as parameters */
BOOL los(coord mx, coord my)
{
int t, x, y, ax, ay, sx, sy, dx, dy;
/* Delta x is the players x minus the monsters x *
* d is my dungeon structure and px is the players *
* x position. mx is the monsters x position passed *
* to the function. */
dx = d.px - mx;
/* dy is the same as dx using the y coordinates */
dy = d.py - my;
/* ax & ay: these are the absolute values of dx & dy *
* multiplied by 2 ( shift left 1 position) */
ax = abs(dx)<<1;
ay = abs(dy)<<1;
/* sx & sy: these are the signs of dx & dy */
sx = SGN(dx);
sy = SGN(dy);
/* x & y: these are the monster's x & y coords */
x = mx;
y = my;
/* The following if statement checks to see if the line *
* is x dominate or y dominate and loops accordingly */
if(ax > ay)
{
/* X dominate loop */
/* t = the absolute of y minus the absolute of x divided *
by 2 (shift right 1 position) */
t = ay - (ax >> 1);
do
{
if(t >= 0)
{
/* if t is greater than or equal to zero then *
* add the sign of dy to y *
* subtract the absolute of dx from t */
y += sy;
t -= ax;
}
/* add the sign of dx to x *
* add the adsolute of dy to t */
x += sx;
t += ay;
/* check to see if we are at the player's position */
if x == d.px && y == d.py)
{
/* return that the monster can see the player */
return TRUE;
}
/* keep looping until the monster's sight is blocked *
* by an object at the updated x,y coord */
}
while(sight_blocked(x,y) == FALSE);
/* NOTE: sight_blocked is a function that returns true *
* if an object at the x,y coord. would block the monster's *
* sight */
/* the loop was exited because the monster's sight was blocked *
* return FALSE: the monster cannot see the player */
return FALSE;
}
else
{
/* Y dominate loop, this loop is basically the same as the x loop */
t = ax - (ay >> 1);
do
{
if(t >= 0)
{
x += sx;
t -= ay;
}
y += sy;
t += ax;
if(x == d.px && y == d.py)
{
return TRUE;
}
}
while(sight_blocked(x,y) == FALSE);
return FALSE;
}
}
Well that's it. Not much to it once I figured out what was going on. I have
looked at a lot of line_of_sight code but I was unable to figure out what
was going on. This is very simple but it gets the job done. Later I plan to
make changes but you have to start somewhere.
I hope this will help someone just starting out like me to understand some
of the mysteries of coding a Roguelike game.
Keep Coding
Steve Register
Note: the above code doesn't deal with the case where the monster and player are the same location. The easy fix is to detect that and exit with TRUE.