Difference between revisions of "Simple Line of Sight"

From RogueBasin
Jump to navigation Jump to search
(Noted a special case to alogrythm.)
(monster_y -> my)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
<pre>
; Line of Sight - Steve Register [arns@arns.freeservers.com].txt
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
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.
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  
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.
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  
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.
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 :+)  
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:
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)
<syntaxhighlight lang="c">
#define SGN(a) (((a)<0) ? -1 : 0)
</syntaxhighlight>


Looking at the description of the macro "take binary sign of a, either -1,  
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 would only return either -1 or 0 and not -1 or 1 like the description says.
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:
After changing the macro to this:


    #define SGN(a) (((a)<0) ? -1 : 1)
<syntaxhighlight lang="c">
#define SGN(a) (((a)<0) ? -1 : 1)
</syntaxhighlight>


everything seemed to start working.
everything seemed to start working.


The following is the code that I use in my program. The remarks explain the  
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.
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.
 
 


<syntaxhighlight lang="c">
/* Line of sight code        *
/* Line of sight code        *
  * this is a Boolean function *
  * this is a Boolean function *
Line 65: Line 34:
  * It has the monsters x and y*
  * It has the monsters x and y*
  * coords as parameters      */
  * coords as parameters      */
BOOL los(coord mx, coord my)
BOOL los(coord monster_x, coord monster_y)
{
{
int t, x, y, ax, ay, sx, sy, dx, dy;
    int t, x, y, abs_delta_x, abs_delta_y, sign_x, sign_y, delta_x, delta_y;


   /* Delta x is the players x minus the monsters x    *
   /* Delta x is the players x minus the monsters x    *
     * d is my dungeon structure and px is the players  *
     * d is my dungeon structure and px is the players  *
     * x position. mx is the monsters x position passed *
     * x position. monster_x is the monsters x position passed *
     * to the function.                                */
     * to the function.                                */
   dx = d.px - mx;
   delta_x = d.px - monster_x;


   /* dy is the same as dx using the y coordinates */
   /* delta_y is the same as delta_x using the y coordinates */
   dy = d.py - my;
   delta_y = d.py - monster_y;


   /* ax & ay: these are the absolute values of dx & dy *
   /* abs_delta_x & abs_delta_y: these are the absolute values of delta_x & delta_y */
    * multiplied by 2 ( shift left 1 position)          */
   abs_delta_x = abs(delta_x);
   ax = abs(dx)<<1;
   abs_delta_y = abs(delta_y);
   ay = abs(dy)<<1;


   /* sx & sy: these are the signs of dx & dy */
   /* sign_x & sign_y: these are the signs of delta_x & delta_y */
   sx = SGN(dx);
   sign_x = SGN(delta_x);
   sy = SGN(dy);
   sign_y = SGN(delta_y);


   /* x & y: these are the monster's x & y coords */
   /* x & y: these are the monster's x & y coords */
   x = mx;
   x = monster_x;
   y = my;
   y = monster_y;


   /* The following if statement checks to see if the line *
   /* The following if statement checks to see if the line *
     * is x dominate or y dominate and loops accordingly    */
     * is x dominate or y dominate and loops accordingly    */
   if(ax > ay)
   if(abs_delta_x > abs_delta_y)
   {
   {
       /* X dominate loop */
       /* X dominate loop */
       /* t = the absolute of y minus the absolute of x divided *
       /* t = twice the absolute of y minus the absolute of x*/
        by 2 (shift right 1 position)                        */
       t = abs_delta_y * 2 - abs_delta_x;
       t = ay - (ax >> 1);
       do
       do
       {
       {
Line 104: Line 71:
         {
         {
             /* if t is greater than or equal to zero then *
             /* if t is greater than or equal to zero then *
             * add the sign of dy to y                    *
             * add the sign of delta_y to y                    *
             * subtract the absolute of dx from t         */
             * subtract twice the absolute of delta_x from t   */
             y += sy;
             y += sign_y;
             t -= ax;
             t -= abs_delta_x*2;
         }
         }
          
          
         /* add the sign of dx to x      *
         /* add the sign of delta_x to x      *
           * add the adsolute of dy to t  */
           * add twice the adsolute of delta_y to t  */
         x += sx;
         x += sign_x;
         t += ay;
         t += abs_delta_y * 2;
          
          
         /* check to see if we are at the player's position */
         /* check to see if we are at the player's position */
Line 137: Line 104:
   {
   {
       /* Y dominate loop, this loop is basically the same as the x loop */
       /* Y dominate loop, this loop is basically the same as the x loop */
       t = ax - (ay >> 1);
       t = abs_delta_x * 2 - abs_delta_y;
       do
       do
       {
       {
         if(t >= 0)
         if(t >= 0)
         {
         {
             x += sx;
             x += sign_x;
             t -= ay;
             t -= abs_delta_y * 2;
         }
         }
         y += sy;
         y += sign_y;
         t += ax;
         t += abs_delta_x * 2;
         if(x == d.px && y == d.py)
         if(x == d.px && y == d.py)
         {
         {
Line 156: Line 123:
   }
   }
}
}
</syntaxhighlight>


Well that's it. Not much to it once I figured out what was going on. I have  
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.
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  
I hope this will help someone just starting out like me to understand some of the mysteries of coding a Roguelike game.
of the mysteries of coding a Roguelike game.


Keep Coding
Keep Coding
Steve Register
: Steve Register
</pre>


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


[[Category:LOS]]
[[Category:LOS]]
delta_y */
  abs_delta_x = abs(delta_x);
  abs_delta_y = abs(delta_y);
  /* sign_x

Latest revision as of 21:19, 15 December 2014

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 would 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 monster_x, coord monster_y)
{
    int t, x, y, abs_delta_x, abs_delta_y, sign_x, sign_y, delta_x, delta_y;

   /* Delta x is the players x minus the monsters x    *
    * d is my dungeon structure and px is the players  *
    * x position. monster_x is the monsters x position passed *
    * to the function.                                 */
   delta_x = d.px - monster_x;

   /* delta_y is the same as delta_x using the y coordinates */
   delta_y = d.py - monster_y;

   /* abs_delta_x & abs_delta_y: these are the absolute values of delta_x & delta_y */
   abs_delta_x = abs(delta_x);
   abs_delta_y = abs(delta_y);

   /* sign_x & sign_y: these are the signs of delta_x & delta_y */
   sign_x = SGN(delta_x);
   sign_y = SGN(delta_y);

   /* x & y: these are the monster's x & y coords */
   x = monster_x;
   y = monster_y;

   /* The following if statement checks to see if the line *
    * is x dominate or y dominate and loops accordingly    */
   if(abs_delta_x > abs_delta_y)
   {
      /* X dominate loop */
      /* t = twice the absolute of y minus the absolute of x*/
      t = abs_delta_y * 2 - abs_delta_x;
      do
      {
         if(t >= 0)
         {
            /* if t is greater than or equal to zero then *
             * add the sign of delta_y to y                    *
             * subtract twice the absolute of delta_x from t   */
            y += sign_y;
            t -= abs_delta_x*2;
         }
         
         /* add the sign of delta_x to x      *
          * add twice the adsolute of delta_y to t  */
         x += sign_x;
         t += abs_delta_y * 2;
         
         /* 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 = abs_delta_x * 2 - abs_delta_y;
      do
      {
         if(t >= 0)
         {
            x += sign_x;
            t -= abs_delta_y * 2;
         }
         y += sign_y;
         t += abs_delta_x * 2;
         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.

delta_y */
  abs_delta_x = abs(delta_x);
  abs_delta_y = abs(delta_y);
  /* sign_x