Written by Régis Dubois the 19/07/99.
email: heroicjourneys@altern.org
homepage: www.altern.org/heroicjourneys
All sources in C. Use them at will!

Ok here is another article relating about the famous "line of sight" 
problem. Why such an article? Because even with all the help provided 
through the internet I wasn't able to find an easy and efficient solution 
to solve the problem. So here I'll expose my method. This is a VERY simple 
method, ok? It means that it is probably slow, that the result isn't very 
accurate but it is easy to implement and understand. So stop talking and 
let's start over!

<< Euh... yes a last thing. Forgive my poor english but I'm french and like 
lot of you guys know about it, French people aren't famous for their 
performance in english :) >>

Remark: we will use the following structures all through the examples:
struct coord
{
  int x,y;
};

struct map
{
  int data[line][col];
  short visible[line][col]; 0 if invisible, 1 otherwise
};


Ok, what we want is to highlight the area around the character, representing
what he can see. It means that our character can see every empty spaces or 
monsters in his line of sight but can not see what is behind walls or closed
doors. How to do this? Well we will just throw some rays from the character,
in circle motion, so that it covers all what the player can see. Hey! I can
hear you scream from here! You think "A circle? So we gonna need to use cos 
and sin huh?". Well you are right, we need them but we won't let the CPU 
calculate them at run-time, we will use pre-generated arrays, what we lose in
memory, we gain it in speed:

const double Pi = 3.1415926535; //need explanation for that?
double Cosinus[71];// array implemented by 5 degrees. 5*72=360
double Sinus[71];//

Why an implementation of 5 degrees? Well, huh, why not? I found it efficient
like this but you may arrange it so that it fits your sight range.

Let's generate the arrays now:
				
void GenerateTables()
{
  int i;

  for (i=0;i<72;i++)
  {
	 Cosinus[i]=cos(i*5*Pi/180);
  }
  for (i=0;i<72;i++)
  {
	 Sinus[i]=sin(i*5*Pi/180);
  }
}

I think I don't need to explain these function.

Ok what we need now is a function to round a double properly. For example 
if we have 2,3 we want the function to return us 2 and if we have 2,6 we 
want the function to return us 3. I checked all the standard libraries in 
C but couldn't find one. If you know one, please email me!

//Round a number to the closest integer
int round(double x)
{
  double b;

   if (modf(x,&b)>0.5)
    return((int)b+1);
  else
    return((int)b);
}

The next step is to get the co-ordinates of the ray we gonna cast. We will 
cast it from the player, according to a certain angle. So we have the origin
of the line we cast (the player x,y) but we want the co-ordinates of the end
of the line. Here is the function that will give them to us:

struct coord CastRay(int x,int y,int r, int angle)
{
	struct coord c;
	c.x=round(x+r*Cosinus[(int)angle/5]);
	c.y=round(y-r*Sinus[(int)angle/5]);
	return (c);
}

Hey guys don't you understand this? This is simple geometry! A small 
projection. Please note that here r is the radian or length of the ray we 
cast. It means the sight range.

Good we have the co-ordinate of the ray we want to cast, so we have to cast 
it. We will use the well known Bresenham's line algorithm for this. Here is
the line of sight routine, I'll explain it later:

int Sgn(int x)
{
  if (x==0) return(0);
  if (x>0) return(1);
  if (x<0) return(-1);
}
// The line of Sight routine.
struct Map Los(struct Map m,int x1,int y1,int x2,int y2)
{
  int i,j,dx,dy,sdx,sdy,dxabs,dyabs,x,y,px,py;

  dx=x2-x1;
  dy=y2-y1;
  dxabs=abs(dx);
  dyabs=abs(dy);
  sdx=Sgn(dx);
  sdy=Sgn(dy);
  x=dyabs/2;
  y=dxabs/2;
  px=x1;
  py=y1;
  if (dxabs>=dyabs)
  {
    for (i=0;i<dxabs;i++)
    {
      y+=dyabs;
      if (y>=dxabs)
      {
        y-=dxabs;
        py+=sdy;
      }
       px+=sdx;
      if (m.visible[py][px]==0) //is the square visible?
      {			//no?
       m.visible[py][px]=1;  //no it is
       PutTile(px,py,m.data[py][px]); //we draw the tile on screen
      }
      if (m.data[py][px]!=Empty && m.data[py][px]!=OpenDoor) //if it is neither empty or an opened door, we stop...
      return(m);
    }
  }   
  else 
  {
    for (i=0;i<dyabs;i++)
    {
       x+=dxabs;
       if (x>dyabs)
       {
         x-=dyabs;
         px+=sdx;
       }
       py+=sdy;
       if (m.visible[py][px]==0)
       {
         m.visible[py][px]=1;
         PutTile(px,py,m.data[py][px]);
       }
       if (m.data[py][px]!=Empty && m.data[py][px]!=OpenDoor)
         return(m);
    }
  }
  return(m);
}

The only thing we do here is to cast the ray and checked every square it 
crosses, if it is empty we light it and carry on further, but if it is a 
wall we stop. Easy no?

Ok it was the tough part, now let's finish by writing the LookAround() 
function which will cast the 72 rays from the player so that it makes a 
circle and hence, a field of vision:

void LookAround()
{
  struct coord c;
  int i;

  for (i=0;i<72;i++)
  {
     c=CastRay(p.px,p.py,p.sight,i*5); //we get the coordonates of the line of sight
     map=Los(map,player.px,player.py,c.x,c.y); 
  };
}

And it's done! 
I know this method isn't the fastest you can find, but it works for sure 
because I use it in my own Rogue-like project. I hope the explanations were
not too dark... If so, feel free to e-mail me:

heroicjourneys@altern.org
www.altern.org/heroicjourneys

Good Luck!
Regis.