• 原文链接：点击跳转
• 作者：Sébastien Bénard
• 译者：mnikn

1. 什么是 Bresenham 直线算法

• 视线检测
• 寻路算法优化
• 平滑寻路路径
• 视野检测（圆锥）
• 光照
• ...

2. 实现

function getLine(x0:Int, y0:Int, x1:Int, y1:Int) : Array<{x:Int, y:Int}> {
    var pts = [];
    var swapXY = fastAbs( y1 - y0 ) > fastAbs( x1 - x0 );
    var tmp : Int;
    if ( swapXY ) {
        // 交换 x 和 y
        tmp = x0; x0 = y0; y0 = tmp; // 交换 x0 和 y0
        tmp = x1; x1 = y1; y1 = tmp; // 交换 x1 和 y1
    }
​
    if ( x0 > x1 ) {
        // 确保 x0 < x1
        tmp = x0; x0 = x1; x1 = tmp; // 交换 x0 和 x1
        tmp = y0; y0 = y1; y1 = tmp; // 交换 y0 和 y1
    }
​
    var deltax = x1 - x0;
    var deltay = fastFloor( fastAbs( y1 - y0 ) );
    var error = fastFloor( deltax / 2 );
    var y = y0;
    var ystep = if ( y0 < y1 ) 1 else -1;
    if( swapXY )
        // Y / X
        for ( x in x0 ... x1+1 ) {
            pts.push({x:y, y:x});
            error -= deltay;
            if ( error < 0 ) {
                y = y + ystep;
                error = error + deltax;
            }
        }
    else
        // X / Y
        for ( x in x0 ... x1+1 ) {
            pts.push({x:x, y:y});
            error -= deltay;
            if ( error < 0 ) {
                y = y + ystep;
                error = error + deltax;
            }
        }
    return pts;
}

static inline function fastAbs(v:Int) : Int {
    return (v ^ (v >> 31)) - (v >> 31);
}
​
static inline function fastFloor(v:Float) : Int {
    return Std.int(v); // 实际上更多时候是在去除后面的小数值而不是向零取舍
}

• 它很容易实现，而且很高效。
• 为了性能，我把 if( swapXY ) 移到了循环外面（只有当调用次数很多的时候才需要这么做）。
• 数组的内存分配（例如 var pts = []）是有性能损耗的。出于性能考虑你可能想要特殊处理下这个函数，不让这个函数每次执行都新建一个数组存点。
• 数组里点的顺序可能会变化。这点非常重要！这意味着数组可能返回 x0,y0 到 x1,y1的点或者刚好相反，这取决于直线的角度。

3. 使用案例

3.1. AI

• 怪物和玩家接近吗（基础的做法是检查之间的距离）
• 怪物能够看到玩家吗

function checkLine(x0:Int, y0:Int, x1:Int, y1:Int, rayCanPass:Int->Int->Bool) {
    var swapXY = fastAbs( y1 - y0 ) > fastAbs( x1 - x0 );
    var tmp : Int;
    if ( swapXY ) {
        // swap x and y
        tmp = x0; x0 = y0; y0 = tmp; // swap x0 and y0
        tmp = x1; x1 = y1; y1 = tmp; // swap x1 and y1
    }
​
    if ( x0 > x1 ) {
        // make sure x0 < x1
        tmp = x0; x0 = x1; x1 = tmp; // swap x0 and x1
        tmp = y0; y0 = y1; y1 = tmp; // swap y0 and y1
    }
​
    var deltax = x1 - x0;
    var deltay = fastFloor( fastAbs( y1 - y0 ) );
    var error = fastFloor( deltax / 2 );
    var y = y0;
    var ystep = if ( y0 < y1 ) 1 else -1;
​
    if( swapXY )
        // Y / X
        for ( x in x0 ... x1+1 ) {
            if( !rayCanPass(y,x) )
            return false;
​
            error -= deltay;
            if ( error < 0 ) {
                y = y + ystep;
                error = error + deltax;
            }
        }
    else
        // X / Y
        for ( x in x0 ... x1+1 ) {
            if( !rayCanPass(x,y) )
            return false;
​
            error -= deltay;
            if ( error < 0 ) {
                y = y + ystep;
                error = error + deltax;
            }
        }
    return true;
}

checkLine(
    mob.x, mob.y, 
    player.x, player.y,
    function(x,y) return collisionMap[x][y] == false
);

3.2. 寻路算法优化

3.3. 平滑寻路路径

• 设置一个叫 REF 点，这个点等于起点
• 检测 REF 点能否在路径上“看见”第三个点，如果可以的话，把第二个点去掉，因为这个点没用
• 重复检测操作，如 REF 点能否看到第四个点，以此类推
• 如果 REF 点不能看到我们给过去的点，那么上一个点就有用了，我们保留它。在这种情况下，REF 点就变成了上一个点，然后对于剩下的点，重复刚才的算法
• 最后，通过只保留能够相互看见的有用点，你就可以让路径更加简洁

• 检查下两者间的距离
• 如果在范围内，计算敌人和玩家之间的角度（Math.atan2）
• 如果计算出来的角度和敌人的方向角度之间的角距离小于圆锥范围 / 2，开始 Bresenham 直线算法检测
• 如果玩家没有躲着什么障碍物后面...警报响起来吧！

3.5. 关于对角的注意点

3.6. 光照

var intensity = 1 - dist / maxDist; // 0=没有光照, 1=全光照

for (dx in -radius...radius+1)
    for(dy in -radius...radius+1) {
        var x = source.x + dx;
        var y = source.y + dy;
​
        var d = distance(source.x, source.y, x, y);
        if( d<=radius && checkLine(source.x,source.y, x,y, hasNoCollision) ){
            var intensity = 1 - d/radius;
            // 更新光照值，绘制，...
        }
    }

3.7. Pixel perfect 的圆

译者的话