ブレセンハム線分アルゴリズムの新バージョン

New version of Bresenham's Line Algorithm
http://groups.google.co.jp/group/rec.games.roguelike.development/browse_thread/thread/345f4c42c3b25858/29e07a3af3a450e6?show_docid=29e07a3af3a450e6
コピペすれば使えるほどに書かれている。コピペしとく。
これであなたの2Dゲームに視線／射線のシステムを加えられますね。

Nate879   	
6月17日, 午前4:35
ニュースグループ: rec.games.roguelike.development
差出人: Nate879 <n...@clockwatch.info>
日付: Mon, 16 Jun 2008 12:35:19 -0700 (PDT)
ローカル: 2008年6月17日(火) 午前4:35
件名: New version of Bresenham's Line Algorithm

This version of Bresenham's Line Algorithm is symmetric, and can find
distances. This code is in C. It uses function pointers to determine
when a line is blocked and how to plot a point. max_len is the maximum
length of the line. It is also symmetric. To use it for line of sight,
call this function for every square that might be within the field of
view.

To use the function, add it to your code and use something similar to
"bresenham(player.x, player.y, target.x, target.y, is_blocking,
display_point, max_len)". is_blocking and display_point are names of
functions.

void bresenham(int x1, int y1, int x2, int y2, int blocking(int, int),
void plot(int, int), int max_len) {

        max_len <<= 1;
        int len = 0;

        int swappedx = 0;
        int swappedy = 0;

        int xtemp = x2-x1;
        int ytemp = y2-y1;
        if (xtemp < 0) {
                xtemp = -xtemp;
                swappedx = 1;
        }
        if (ytemp < 0) {
                ytemp = -ytemp;
                swappedy = 1;
        }

        int delta_x = xtemp << 1;
        int delta_y = ytemp << 1;

        signed char ix = x2 > x1?1:-1;
        signed char iy = y2 > y1?1:-1;

        plot(x1, y1);

        if (delta_x >= delta_y) {
                int error = delta_y - (delta_x >> 1);

                while (x1 != x2) {
                        if (error == 0 && !swappedx) {
                                plot(x1+ix, y1);
                                if (blocking(x1+ix, y1))
                                        return;
                        }
                        if (error >= 0) {
                                if (error || (ix > 0)) {
                                        y1 += iy;
                                        error -= delta_x;
                                        len++;
                                }
                        }
                        x1 += ix;
                        plot(x1, y1);
                        len += 2;
                        if (blocking(x1, y1) || len >= max_len)
                                return;
                        if (error == 0 && swappedx) {
                                plot(x1, y1+iy);
                                if (blocking(x1, y1+iy))
                                        return;
                        }
                        error += delta_y;
                }
        }
        else {
                int error = delta_x - (delta_y >> 1);

                while (y1 != y2) {
                        if (error == 0 && !swappedy) {
                                plot(x1, y1+iy);
                                if (blocking(x1, y1+iy))
                                        return;
                        }
                        if (error >= 0) {
                                if (error || (iy > 0)) {
                                        x1 += ix;
                                        error -= delta_y;
                                        len++;
                                }
                        }
                        y1 += iy;
                        plot(x1, y1);
                        len += 2;
                        if (blocking(x1, y1) || len >= max_len)
                                return;
                        if (error == 0 && swappedy) {
                                plot(x1+ix, y1);
                                if (blocking(x1+ix, y1))
                                        return;
                        }
                        error += delta_x;
                }
        }
}