This article was originally written for Darren Hebden's RLNews
Written by Régis Dubois the 19/07/99.
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:
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;// array implemented by 5 degrees. 5*72=360
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:
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)
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;
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)
if (m.visible[py][px]==0) //is the square visible?
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...
if (m.data[py][px]!=Empty && m.data[py][px]!=OpenDoor)
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:
struct coord c;
c=CastRay(p.px,p.py,p.sight,i*5); //we get the coordonates of the line of sight
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: