Difference between revisions of "Line of sight"

From RogueBasin
Jump to navigation Jump to search
m (added new article: lua 2d line of sight code)
 
(14 intermediate revisions by 10 users not shown)
Line 1: Line 1:
One of the more popular methods of determining wether something in the game world is visible (or targetable) is to input the x,y coords for the target and the player and then walk along a line between them. At each step on the line, the game checks to see if anything is in the world at these coords that would prevent a player's sight (like a wall).
One of the more popular (simple) methods of determining whether something in the game world is [[visible|visibility]] (or targetable) is to input the x,y coords for the target and the player and then walk along a line between them. At each step on the line, the game checks to see if anything is in the world at these coords that would prevent a player's sight (like a wall).


There are a couple of articles describing how to do line of sight:
* [[Bresenham's Line Algorithm]]
* [[Another version of BLA]]
* [[Simple Line of Sight]]
* [[Digital lines]]
* [[LUA 2d Line of sight]]


You may be searching for [[:Category:FOV]].


Taken from wikipedia: (they will delete this code soon, I thought it might find a welcome home here)
[[Category:Articles]]
 
An implementation of [http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm Bresenham s line algorithm] in [[C_programming_language|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_swap_algorithm|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;
        }
    }
}

Latest revision as of 22:29, 25 December 2011

One of the more popular (simple) methods of determining whether something in the game world is visibility (or targetable) is to input the x,y coords for the target and the player and then walk along a line between them. At each step on the line, the game checks to see if anything is in the world at these coords that would prevent a player's sight (like a wall).

There are a couple of articles describing how to do line of sight:

You may be searching for Category:FOV.