Line of sight

Taken from wikipedia: (they will delete this code soon, I thought it might find a welcome home here)

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm <-- someone figure out how to make this an external link please

An implementation of Bresenham's line algorithm in C follows. The plot() function is not shown and is assumed to render a single point of the line in the chosen color. This variation produces solid lines of a uniform color.

void drawline2d(int x0, int y0, int x1, int y1, int color)
{
       int i;
       int steep = 1;
       int sx, sy;  /* step positive or negative (1 or -1) */
       int dx, dy;  /* delta (difference in X and Y between points) */
       int e;
 
       /*
        * inline swap. On some architectures, the XOR trick may be faster
        */
       int tmpswap;
#define SWAP(a,b) tmpswap = a; a = b; b = tmpswap;
 
       /*
        * optimize for vertical and horizontal lines here
        */
        
       dx = abs(x1 - x0);
       sx = ((x1 - x0) > 0) ? 1 : -1;
       dy = abs(y1 - y0);
       sy = ((y1 - y0) > 0) ? 1 : -1;
       if (dy > dx) {
               steep = 0;
               SWAP(x0, y0);
               SWAP(dx, dy);
               SWAP(sx, sy);
       }
       e = (dy << 1) - dx;
       for (i = 0; i < dx; i++) {
               if (steep) {
                       plot(x0,y0,color);
               } else {
                       plot(y0,x0,color);
               }
               while (e >= 0) {
                       y0 += sy;
                       e -= (dx << 1);
               }
               x0 += sx;
               e += (dy << 1);
       }
}

A slightly more optimized version of the above (might be a bit harder to read, though):

void drawline2d(int x0, int y0, int x1, int y1, int color) {
   int i;
   int sx, sy;  /* step positive or negative (1 or -1) */
   int dx, dy;  /* delta (difference in X and Y between points) */
   int dx2, dy2;
   int e;
   int temp;
 
   dx = x1 - x0;
   sx = (dx > 0) ? 1 : -1;
   if (dx < 0)
       dx = -dx;
 
   dy = y1 - y0;
   sy = (dy > 0) ? 1 : -1;
   if (dy < 0)
       dy = -dy;
 
   dx2 = dx << 1; /* dx2 = 2 * dx */
   dy2 = dy << 1; /* dy2 = 2 * dy */
 
   if (dy <= dx) { /* steep */
       e = dy2 - dx;
 
       for (i = 0; i <= dx; ++i) {
           plot(x0, y0, color);
 
           while (e >= 0) {
               y0 += sy;
               e -= dx2;
           }
 
           x0 += sx;
           e += dy2;
       }
   } else {
       /* swap x0 <-> y0 */
       temp = x0;
       x0 = y0;
       y0 = temp;
 
       /* swap dx <-> dy */
       temp = dx;
       dx = dy;
       dy = temp;
 
       /* swap dx2 <-> dy2 */
       temp = dx2;
       dx2 = dy2;
       dy2 = temp;
 
       /* swap sx <-> sy */
       temp = sx;
       sx = sy;
       sy = temp;
 
       e = dy2 - dx;
 
       for (i = 0; i <= dx; ++i) {
           plot(y0, x0, color);
 
           while (e >= 0) {
               y0 += sy;
               e -= dx2;
           }
 
           x0 += sx;
           e += dy2;
       }
   }
}