Difference between revisions of "Ray-Tracing Field-Of-View Demo"

From RogueBasin
Jump to navigation Jump to search
m (fixed link to ncurses)
m (→‎Usage: Indented some code. More needed, but I need sleep.)
 
(One intermediate revision by the same user not shown)
Line 85: Line 85:


<pre>
<pre>
#include &ltcurses.h>
#include <curses.h>


/* DEFINES -------------------------------------------------------- */
/* DEFINES -------------------------------------------------------- */
Line 121: Line 121:


typedef struct {
typedef struct {
int x, y;
    int x, y;
} COORD;
} COORD;


typedef struct {
typedef struct {
char ch; /* this tile's ASCII character */
    char ch; /* this tile's ASCII character */
bool seen; /* this tile can be seen by the player */
    bool seen; /* this tile can be seen by the player */
bool remembered; /* this tile has been seen by the player */
    bool remembered; /* this tile has been seen by the player */
} TILE;
} TILE;


Line 165: Line 165:
int main(void)
int main(void)
{
{
int k; /* keystoke */
    int k; /* keystoke */
int ret; /* return code */
    int ret; /* return code */


if ((ret = init_curses()) != 0) {
    if ((ret = init_curses()) != 0) {
return ret;
        return ret;
}
    }


create_map();
    create_map();
create_octant();
    create_octant();


/* main loop */
    /* main loop */
for (;;) {
    for (;;) {


/* draw map */
        /* draw map */
draw_map();
        draw_map();


k = getch();
        k = getch();


/* analyse key press */
        /* analyse key press */
switch (k) {
        switch (k) {
case ('8'): move_player( 0, -1); break;  
            case ('8'): move_player( 0, -1); break;  
case ('2'): move_player( 0, 1); break;
            case ('2'): move_player( 0, 1); break;
case ('4'): move_player(-1, 0); break;
            case ('4'): move_player(-1, 0); break;
case ('6'): move_player( 1, 0); break;
            case ('6'): move_player( 1, 0); break;
case ('7'): move_player(-1, -1); break;
            case ('7'): move_player(-1, -1); break;
case ('3'): move_player( 1, 1); break;
            case ('3'): move_player( 1, 1); break;
case ('9'): move_player( 1, -1); break;
            case ('9'): move_player( 1, -1); break;
case ('1'): move_player(-1, 1); break;
            case ('1'): move_player(-1, 1); break;


case ('q'):
            case ('q'):
case ('Q'):
            case ('Q'):
case (27):  
            case (27):  
goto end;
                goto end;
};
        };


}
    }


end:
    end:
exit_curses();
    exit_curses();
return 0;
    return 0;
}
}


Line 210: Line 210:
int init_curses(void)
int init_curses(void)
{
{
/* init curses */
    /* init curses */
initscr();
    initscr();
noecho();
    noecho();
curs_set(0);
    curs_set(0);
if (has_colors()) {
    if (has_colors()) {
start_color();
        start_color();
} else {
    } else {
printf("Your system does not support colour. This demo requires
        printf("Your system does not support colour. This demo requires"
colours!");
              "colours!");
return ERROR_NOCOLOUR;
        return ERROR_NOCOLOUR;
}
    }


/* set up some colours */
    /* set up some colours */
init_pair(0, COLOR_BLACK, COLOR_BLACK);
    init_pair(0, COLOR_BLACK, COLOR_BLACK);
init_pair(REMEMBERED_COLOUR, COLOR_WHITE, COLOR_BLACK);
    init_pair(REMEMBERED_COLOUR, COLOR_WHITE, COLOR_BLACK);
init_pair(PLAYER_COLOUR, COLOR_GREEN, COLOR_BLACK);
    init_pair(PLAYER_COLOUR, COLOR_GREEN, COLOR_BLACK);
init_pair(SEEN_COLOUR, COLOR_BLUE, COLOR_BLACK);
    init_pair(SEEN_COLOUR, COLOR_BLUE, COLOR_BLACK);


return 0;
    return 0;
}
}


Line 235: Line 235:
void exit_curses(void)
void exit_curses(void)
{
{
endwin();
    endwin();
}
}


Line 242: Line 242:
void create_map(void)
void create_map(void)
{
{
int i, j; /* coordinate counters */
    int i, j; /* coordinate counters */


/* initialise the map to ground (GROUND) */
    /* initialise the map to ground (GROUND) */
for (j = 0; j != MAP_HEIGHT; ++j) {
    for (j = 0; j != MAP_HEIGHT; ++j) {
for (i = 0; i != MAP_WIDTH; ++i) {
        for (i = 0; i != MAP_WIDTH; ++i) {
map[i][j].ch = GROUND;
            map[i][j].ch = GROUND;
map[i][j].seen = false;
            map[i][j].seen = false;
map[i][j].remembered = false;
            map[i][j].remembered = false;
}
        }
}
    }


/* draw some fairly arbitrary walls */
    /* draw some fairly arbitrary walls */
for (i = 10; i != 20; ++i)
    for (i = 10; i != 20; ++i)
map[i][10].ch = WALL;
        map[i][10].ch = WALL;
for (i = 10; i != 40; ++i)
    for (i = 10; i != 40; ++i)
map[i][20].ch = WALL;
        map[i][20].ch = WALL;


for (j = 10; j != 21; ++j)
    for (j = 10; j != 21; ++j)
map[10][j].ch = WALL;
        map[10][j].ch = WALL;
for (i = 10; i != 21; ++i)
    for (i = 10; i != 21; ++i)
map[40][i].ch = WALL;
        map[40][i].ch = WALL;


for (i = 10; i != 21; ++i)
    for (i = 10; i != 21; ++i)
map[11][i].ch = WALL;
        map[11][i].ch = WALL;
for (i = 10; i != 21; ++i)
    for (i = 10; i != 21; ++i)
map[12][i].ch = WALL;
        map[12][i].ch = WALL;


for (i = 20; i != 25; ++i)
    for (i = 20; i != 25; ++i)
map[30][i].ch = WALL;
        map[30][i].ch = WALL;


for (j = 15; j != 70; ++j)
    for (j = 15; j != 70; ++j)
map[j][30].ch = WALL;
        map[j][30].ch = WALL;
}
}


Line 280: Line 280:
void create_octant(void)
void create_octant(void)
{
{
/*
    /*
@
    @
|\
    |\
||\
    ||\
||\\
    ||\\
*/
    */
int i;
    int i;
for (i = 0; i != PERCEPTION_RADIUS; ++i) {
    for (i = 0; i != PERCEPTION_RADIUS; ++i) {
do_line(0, 0, i, PERCEPTION_RADIUS);
        do_line(0, 0, i, PERCEPTION_RADIUS);
}
    }
}
}


Line 296: Line 296:
bool valid_tile(int x, int y)
bool valid_tile(int x, int y)
{
{
return (((unsigned)x < MAP_WIDTH) && ((unsigned)y < MAP_HEIGHT));
    return (((unsigned)x < MAP_WIDTH) && ((unsigned)y < MAP_HEIGHT));
}
}


Line 303: Line 303:
TILE *tile(int x, int y)
TILE *tile(int x, int y)
{
{
if (valid_tile(x, y))
    if (valid_tile(x, y))
return &map[x][y];
        return &map[x][y];
else
    else
return NULL;
        return NULL;
}
}


Line 313: Line 313:
void move_player(int dx, int dy)
void move_player(int dx, int dy)
{
{
if (valid_tile(px + dx, py + dy)) {
    if (valid_tile(px + dx, py + dy)) {
if (map[px + dx][py + dy].ch != WALL) {
        if (map[px + dx][py + dy].ch != WALL) {
px += dx;
            px += dx;
py += dy;
            py += dy;
}
        }
}
    }
}
}


Line 325: Line 325:
void do_fov(void)
void do_fov(void)
{
{
int xoff, yoff; /* x offset, y offset */
    int xoff, yoff; /* x offset, y offset */
TILE *t = NULL; /* current tile */
    TILE *t = NULL; /* current tile */
TILE *adj_t = NULL; /* adjacent tile (see explanation at top) */
    TILE *adj_t = NULL; /* adjacent tile (see explanation at top) */
TILE *last_t = NULL; /* last tile */
    TILE *last_t = NULL; /* last tile */
TILE *last_adj_t = NULL; /* last adjacent tile */
    TILE *last_adj_t = NULL; /* last adjacent tile */
int tx, ty; /* current tile x, current tile y */
    int tx, ty; /* current tile x, current tile y */
int i, j; /* counters */
    int i, j; /* counters */
bool wall; /* the current tile is a wall */
    bool wall; /* the current tile is a wall */
bool adj_clear; /* the adjacent tile is clear (not a wall) */
    bool adj_clear; /* the adjacent tile is clear (not a wall) */
bool last_adj_clear; /* the adjacent tile from the last
    bool last_adj_clear; /* the adjacent tile from the last
iteration is clear (not a wall) */
    iteration is clear (not a wall) */


/* un-see everything */
    /* un-see everything */
for (j = 0; j != MAP_HEIGHT; ++j) {
    for (j = 0; j != MAP_HEIGHT; ++j) {
for (i = 0; i != MAP_WIDTH; ++i) {
        for (i = 0; i != MAP_WIDTH; ++i) {
if (tile(i, j)-&gtseen) {
            if (tile(i, j)-&gtseen) {
tile(i, j)-&gtremembered = true;
                tile(i, j)-&gtremembered = true;
}
            }
tile(i, j)-&gtseen = false;
            tile(i, j)-&gtseen = false;
}
        }
}
    }


/* damn ugly octant definition - the heart of the algorithm */
    /* damn ugly octant definition - the heart of the algorithm */


#define DO_OCTANT(x, y, sx, sy, dx, dy) \
#define DO_OCTANT(x, y, sx, sy, dx, dy) \
\
\
for (i = 0; i != PERCEPTION_RADIUS; ++i) { \
    for (i = 0; i != PERCEPTION_RADIUS; ++i) { \
\
\
last_t = NULL; \
        last_t = NULL; \
last_adj_t = NULL; \
        last_adj_t = NULL; \
\
\
for (j = 0; j != PERCEPTION_RADIUS; ++j) { \
        for (j = 0; j != PERCEPTION_RADIUS; ++j) { \
\
\
/* get the current tile offset from the player */ \
            /* get the current tile offset from the player */ \
xoff = octant[i][j].x; \
            xoff = octant[i][j].x; \
yoff = octant[i][j].y; \
            yoff = octant[i][j].y; \
\
\
/* get the current tile */ \
            /* get the current tile */ \
tx = px sx xoff; \
            tx = px sx xoff; \
ty = py sy yoff; \
            ty = py sy yoff; \
t = tile(tx, ty); \
            t = tile(tx, ty); \
\
\
/* if we've gone off into null territory, stop ray */ \
            /* if we've gone off into null territory, stop ray */ \
if (t == NULL) break; \
            if (t == NULL) break; \
\
\
/* get the adjacent tile */ \
            /* get the adjacent tile */ \
adj_t = tile(tx - (sx dx), ty - (sy dy)); \
            adj_t = tile(tx - (sx dx), ty - (sy dy)); \
\
\
if (last_t) { \
            if (last_t) { \
if (last_t-&gtch != WALL) { \
                if (last_t-&gtch != WALL) { \
/* if we're not behind a wall, we can see what's here */\
                    /* if we're not behind a wall, we can see what's here */\
t-&gtseen = true; \
                    t-&gtseen = true; \
} else /* last char was a wall */ { \
                } else /* last char was a wall */ { \
\
\
/* if horizontal/vertical case, stop ray */ \
                    /* if horizontal/vertical case, stop ray */ \
if (x##off == 0) break; \
                    if (x##off == 0) break; \
\
\
/* if we reach here, we've got a potential wall case */ \
                    /* if we reach here, we've got a potential wall case */ \
wall = t-&gtch == WALL; \
                    wall = t-&gtch == WALL; \
adj_clear = adj_t && (adj_t-&gtch != WALL); \
                    adj_clear = adj_t && (adj_t-&gtch != WALL); \
last_adj_clear = last_adj_t && (last_adj_t-&gtch != WALL);\
                    last_adj_clear = last_adj_t && (last_adj_t-&gtch != WALL);\
\
\
/* if we find wall next to clear stuff, continue */ \
                    /* if we find wall next to clear stuff, continue */ \
/* along the wall */ \
                    /* along the wall */ \
if ((wall && adj_clear && last_adj_clear)) { \
                    if ((wall && adj_clear && last_adj_clear)) { \
t-&gtseen = true; \
                        t-&gtseen = true; \
} else { \
                    } else { \
/* stop ray */ \
                        /* stop ray */ \
break; \
                        break; \
} \
                    } \
} \
                } \
} \
            } \
last_t = t; \
            last_t = t; \
last_adj_t = adj_t; \
            last_adj_t = adj_t; \
} \
        } \
}
    }


/* do *that* 8 times, once for each octant */
    /* do *that* 8 times, once for each octant */
DO_OCTANT(x, y, +, +, 1, 0);
    DO_OCTANT(x, y, +, +, 1, 0);
DO_OCTANT(x, y, +, -, 1, 0);
    DO_OCTANT(x, y, +, -, 1, 0);
DO_OCTANT(x, y, -, +, 1, 0);
    DO_OCTANT(x, y, -, +, 1, 0);
DO_OCTANT(x, y, -, -, 1, 0);
    DO_OCTANT(x, y, -, -, 1, 0);
DO_OCTANT(y, x, +, +, 0, 1);
    DO_OCTANT(y, x, +, +, 0, 1);
DO_OCTANT(y, x, +, -, 0, 1);
    DO_OCTANT(y, x, +, -, 0, 1);
DO_OCTANT(y, x, -, +, 0, 1);
    DO_OCTANT(y, x, -, +, 0, 1);
DO_OCTANT(y, x, -, -, 0, 1);
    DO_OCTANT(y, x, -, -, 0, 1);
}
}



Latest revision as of 02:41, 29 July 2010

Ray-Ttracing Field-Of-View Demo - Greg McIntyre [greg@puyo.cjb.net].txt

NB. You can download a Linux source distro of this article here.

The Algorithm

This is a ray-tracing algorithm which uses a bit of precalculation to speed things up, and a hack to make things look (nearly) right.

Each turn, rays are traced from the player in every direction to the end of his perception. These rays mark everything as 'seen' until they hit something opaque.

I believe the algorithm has efficiency O(n^2) (n scaling linearly with the radius of the FOV). But then, I was never terribly good at figuring out orders of efficiency. ;)

The Hack

The hack tests the tile adjacent to the current tile at each step along the ray, to alleviate what I call the 'low angle wall case'.

This is where rays move nearly horizontal to a wall, catch on the wall's tiles and prematurely stop. This leaves gaps in the FOV along the wall and looks wrong.

@xxx
xxxx
########!???########

! = displayed
? = mistake; not displayed!

Without the hack, it looks something like this:

@
########## ### ### ### # # #

The hack checks the tile away from the wall. The 'adjacent' tile, for want of a better name. It also checks the 'adjacent' tile from the previous tile in the ray. If both are clear, then we've encountered that nasty 'low angle wall case', and we know to keep tracing.

aaa
@xxxaaaa
xxxxaaaa
########!!!!a#######

! = displayed

With the hack in place, it looks like this:

@
#############################################

There are still some little jitters around corners and between walls sometimes. This seems fairly unavoidable at such a low resolution, however I am certain some of them can be ironed out. Anyone want to fix this up for me? :)

Compilation

Make sure you have the Curses, Ncurses or PDCurses library. I used ncurses and I haven't tested this with other libraries, but it's very simple and should, in theory, work.

Compile with:

gcc -o fov fov.c -Wall -lncurses

where ncurses can be replaced with curses or pdcurses or whatever.

Usage

Turn numlock on and use the keypad to move. Press 'q'/'Q'/Esc to quit.

#include <curses.h>

/* DEFINES -------------------------------------------------------- */

#define MAP_WIDTH 80
#define MAP_HEIGHT 50
#define PERCEPTION_RADIUS 80

#define PLAYER '@'
#define GROUND '.'
#define WALL '#'

#define REMEMBERED_COLOUR 1
#define PLAYER_COLOUR 2
#define SEEN_COLOUR 3

#define PLAYER_START_X 20
#define PLAYER_START_Y 5

#define ERROR_NOCOLOUR 1

#ifndef bool
#define bool char
#endif

#ifndef true
#define true -1
#endif

#ifndef false
#define false 0
#endif

/* TYPE DEFS ------------------------------------------------------ */

typedef struct {
    int x, y;
} COORD;

typedef struct {
    char ch; /* this tile's ASCII character */
    bool seen; /* this tile can be seen by the player */
    bool remembered; /* this tile has been seen by the player */
} TILE;


/* GLOBAL DATA ---------------------------------------------------- */

/* map */
TILE map[MAP_WIDTH][MAP_HEIGHT];

/* fov lookup table */
COORD octant[PERCEPTION_RADIUS][PERCEPTION_RADIUS];

/* player coodinates */
unsigned char px = PLAYER_START_X, py = PLAYER_START_Y;


/* FUNCTION PROTOTYPES -------------------------------------------- */

int init_curses(void);
void exit_curses(void);

void create_map(void);
void create_octant(void);
void do_line(int x1, int y1, int x2, int y2);

void draw_map(void);
void do_fov(void);

void move_player(int dx, int dy);

TILE * tile(int x, int y);
bool valid_tile(int x, int y);


/* FUNCTION DEFS -------------------------------------------------- */

int main(void)
{
    int k; /* keystoke */
    int ret; /* return code */

    if ((ret = init_curses()) != 0) {
        return ret;
    }

    create_map();
    create_octant();

    /* main loop */
    for (;;) {

        /* draw map */
        draw_map();

        k = getch();

        /* analyse key press */
        switch (k) {
            case ('8'): move_player( 0, -1); break; 
            case ('2'): move_player( 0, 1); break;
            case ('4'): move_player(-1, 0); break;
            case ('6'): move_player( 1, 0); break;
            case ('7'): move_player(-1, -1); break;
            case ('3'): move_player( 1, 1); break;
            case ('9'): move_player( 1, -1); break;
            case ('1'): move_player(-1, 1); break;

            case ('q'):
            case ('Q'):
            case (27): 
                goto end;
        };

    }

    end:
    exit_curses();
    return 0;
}

/* initialise the curses library, for drawing colourful ASCII text */
int init_curses(void)
{
    /* init curses */
    initscr();
    noecho();
    curs_set(0);
    if (has_colors()) {
        start_color();
    } else {
        printf("Your system does not support colour. This demo requires"
               "colours!");
        return ERROR_NOCOLOUR;
    }

    /* set up some colours */
    init_pair(0, COLOR_BLACK, COLOR_BLACK);
    init_pair(REMEMBERED_COLOUR, COLOR_WHITE, COLOR_BLACK);
    init_pair(PLAYER_COLOUR, COLOR_GREEN, COLOR_BLACK);
    init_pair(SEEN_COLOUR, COLOR_BLUE, COLOR_BLACK);

    return 0;
}


/* close curses and return to normal text screen mode */
void exit_curses(void)
{
    endwin();
}


/* create an arbitrary map for the player to walk around */
void create_map(void)
{
    int i, j; /* coordinate counters */

    /* initialise the map to ground (GROUND) */
    for (j = 0; j != MAP_HEIGHT; ++j) {
        for (i = 0; i != MAP_WIDTH; ++i) {
            map[i][j].ch = GROUND;
            map[i][j].seen = false;
            map[i][j].remembered = false;
        }
    }

    /* draw some fairly arbitrary walls */
    for (i = 10; i != 20; ++i)
        map[i][10].ch = WALL;
    for (i = 10; i != 40; ++i)
        map[i][20].ch = WALL;

    for (j = 10; j != 21; ++j)
        map[10][j].ch = WALL;
    for (i = 10; i != 21; ++i)
        map[40][i].ch = WALL;

    for (i = 10; i != 21; ++i)
        map[11][i].ch = WALL;
    for (i = 10; i != 21; ++i)
        map[12][i].ch = WALL;

    for (i = 20; i != 25; ++i)
        map[30][i].ch = WALL;

    for (j = 15; j != 70; ++j)
        map[j][30].ch = WALL;
}


/* pre-calculate a single octant */
void create_octant(void)
{
    /*
    @
    |\
    ||\
    ||\\
    */
    int i;
    for (i = 0; i != PERCEPTION_RADIUS; ++i) {
        do_line(0, 0, i, PERCEPTION_RADIUS);
    }
}


/* (x,y) is inside the map boundary */
bool valid_tile(int x, int y)
{
    return (((unsigned)x < MAP_WIDTH) && ((unsigned)y < MAP_HEIGHT));
}


/* the tile at (x,y) */
TILE *tile(int x, int y)
{
    if (valid_tile(x, y))
        return &map[x][y];
    else
        return NULL;
}


/* move the player by an offset (dx,dy) */
void move_player(int dx, int dy)
{
    if (valid_tile(px + dx, py + dy)) {
        if (map[px + dx][py + dy].ch != WALL) {
            px += dx;
            py += dy;
        }
    }
}


/* calculate which tiles can be seen by the player */
void do_fov(void)
{
    int xoff, yoff; /* x offset, y offset */
    TILE *t = NULL; /* current tile */
    TILE *adj_t = NULL; /* adjacent tile (see explanation at top) */
    TILE *last_t = NULL; /* last tile */
    TILE *last_adj_t = NULL; /* last adjacent tile */
    int tx, ty; /* current tile x, current tile y */
    int i, j; /* counters */
    bool wall; /* the current tile is a wall */
    bool adj_clear; /* the adjacent tile is clear (not a wall) */
    bool last_adj_clear; /* the adjacent tile from the last
    iteration is clear (not a wall) */

    /* un-see everything */
    for (j = 0; j != MAP_HEIGHT; ++j) {
        for (i = 0; i != MAP_WIDTH; ++i) {
            if (tile(i, j)-&gtseen) {
                tile(i, j)-&gtremembered = true;
            }
            tile(i, j)-&gtseen = false;
        }
    }

    /* damn ugly octant definition - the heart of the algorithm */

#define DO_OCTANT(x, y, sx, sy, dx, dy) \
\
    for (i = 0; i != PERCEPTION_RADIUS; ++i) { \
\
        last_t = NULL; \
        last_adj_t = NULL; \
\
        for (j = 0; j != PERCEPTION_RADIUS; ++j) { \
\
            /* get the current tile offset from the player */ \
            xoff = octant[i][j].x; \
            yoff = octant[i][j].y; \
\
            /* get the current tile */ \
            tx = px sx xoff; \
            ty = py sy yoff; \
            t = tile(tx, ty); \
\
            /* if we've gone off into null territory, stop ray */ \
            if (t == NULL) break; \
\
            /* get the adjacent tile */ \
            adj_t = tile(tx - (sx dx), ty - (sy dy)); \
\
            if (last_t) { \
                if (last_t-&gtch != WALL) { \
                    /* if we're not behind a wall, we can see what's here */\
                    t-&gtseen = true; \
                } else /* last char was a wall */ { \
\
                    /* if horizontal/vertical case, stop ray */ \
                    if (x##off == 0) break; \
\
                    /* if we reach here, we've got a potential wall case */ \
                    wall = t-&gtch == WALL; \
                    adj_clear = adj_t && (adj_t-&gtch != WALL); \
                    last_adj_clear = last_adj_t && (last_adj_t-&gtch != WALL);\
\
                    /* if we find wall next to clear stuff, continue */ \
                    /* along the wall */ \
                    if ((wall && adj_clear && last_adj_clear)) { \
                        t-&gtseen = true; \
                    } else { \
                        /* stop ray */ \
                        break; \
                    } \
                } \
            } \
            last_t = t; \
            last_adj_t = adj_t; \
        } \
    }

    /* do *that* 8 times, once for each octant */
    DO_OCTANT(x, y, +, +, 1, 0);
    DO_OCTANT(x, y, +, -, 1, 0);
    DO_OCTANT(x, y, -, +, 1, 0);
    DO_OCTANT(x, y, -, -, 1, 0);
    DO_OCTANT(y, x, +, +, 0, 1);
    DO_OCTANT(y, x, +, -, 0, 1);
    DO_OCTANT(y, x, -, +, 0, 1);
    DO_OCTANT(y, x, -, -, 0, 1);
}


/* draw the map */
void draw_map(void)
{
int i, j;

/* calculate FOV */
do_fov();

/* draw all the tiles */
for (j = 0; j != MAP_HEIGHT; ++j) {
for (i = 0; i != MAP_WIDTH; ++i) {
if (map[i][j].seen) {
mvaddch(j, i, map[i][j].ch | COLOR_PAIR(SEEN_COLOUR));
} else if (map[i][j].remembered) {
mvaddch(j, i, map[i][j].ch | COLOR_PAIR(REMEMBERED_COLOUR));
}
}
}

/* draw the player */
mvaddch(py, px, PLAYER | COLOR_PAIR(PLAYER_COLOUR));
refresh();
}


/* walk along line from (x1, y1) to (x2, y2), setting values in octant
*/
void do_line(int x1, int y1, int x2, int y2)
{
int dx = x2 - x1;
int dy = y2 - y1;
int i1, i2;
int x, y;
int dd;
int i = x2;
int j = 0;

#define DO_LINE(pri_sign, pri_c, pri_cond, sec_sign, sec_c, sec_cond) 
\
{ 
\
if (d##pri_c == 0) 
\
{ 
\
octant[i][j].x = x1; 
\
octant[i][j].y = y1; 
\
++j; 
\
return; 
\
} 
\

\
i1 = 2 * d##sec_c; 
\
dd = i1 - (sec_sign (pri_sign d##pri_c)); 
\
i2 = dd - (sec_sign (pri_sign d##pri_c)); 
\

\
x = x1; 
\
y = y1; 
\

\
while (pri_c pri_cond pri_c##2) 
\
{ 
\
octant[i][j].x = x; 
\
octant[i][j].y = y; 
\
++j; 
\

\
if (dd sec_cond pri_sign##1) 
\
{ 
\
sec_c sec_sign##= 1; 
\
dd += i2; 
\
} 
\
else 
\
dd += i1; 
\

\
pri_c pri_sign##= 1; 
\
} 
\
}

if (dx >= 0)
{
if (dy >= 0)
{
if (dx >= dy)
{
/* (x1 <= x2) && (y1 <= y2) && (dx >= dy) */
DO_LINE(+, x, <=, +, y, >=);
}
else
{
/* (x1 <= x2) && (y1 <= y2) && (dx < dy) */
DO_LINE(+, y, <=, +, x, >=);
}
}
else
{
if (dx >= -dy)
{
/* (x1 <= x2) && (y1 > y2) && (dx >= dy) */
DO_LINE(+, x, <=, -, y, <=);
}
else
{
/* (x1 <= x2) && (y1 > y2) && (dx < dy) */
DO_LINE(-, y, >=, +, x, >=);
}
}
}
else
{
if (dy >= 0)
{
if (-dx >= dy)
{
/* (x1 > x2) && (y1 <= y2) && (dx >= dy) */
DO_LINE(-, x, >=, +, y, >=);
}
else
{
/* (x1 > x2) && (y1 <= y2) && (dx < dy) */
DO_LINE(+, y, <=, -, x, <=);
}
}
else
{
if (-dx >= -dy)
{
/* (x1 > x2) && (y1 > y2) && (dx >= dy) */
DO_LINE(-, x, >=, -, y, <=);
}
else
{
/* (x1 > x2) && (y1 > y2) && (dx < dy) */
DO_LINE(-, y, >=, -, x, <=);
}
}
}
}