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

1. 什么是 Bresenham 直线算法

Bresenham 直线算法是个很通用的算法，几个月前我才刚刚了解到它，它在许多用途上都很实用。这个算法基本用来在两点之间基于网格（例如像素网格）绘制一条直线，绘制出来的直线是 pixel perfect 的，看起来很酷（译注：pixel perfect 的定义参考这篇文章中有关线条的说法，幸好学过像素画不然还不知道这个是什么）。

不过这个算法还有很多有趣的用途：

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

2. 实现

你可以看下基于 Haxe 的实现，这部分代码在我的 GitHub 仓库里面：BRESENHAM.HX

以下是基于 Haxe 的实现：

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;
}

注意 fastAbs 和 fastFloor都是 absolute 和 floor 的极致性能实现版：

static inline function fastAbs(v:Int) : Int {
    return (v ^ (v >> 31)) - (v >> 31);
}

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

对于 Bresenham 算法，你需要了解的是:

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

我建议你读下 Wikipedia 上有关 Bresenham 直线算法的常规实现，尤其是如果你想要根据情况对它做一些特殊处理，在上面你还能发现一些有趣的优化技巧。

所以这个算法我们要怎么去用呢？

3. 使用案例

3.1. AI

当你想要写一个怪物敌人的 AI 时，你通常会遇到两个很基础的问题：

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

第二个问题可以用 Bresenham 直线算法来轻松解答，只需要用它来检测怪物的视线和玩家中是否有障碍物就好。

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;
}

这个版本没有返回任何位置点，它只是对于线上的每个点都调用下函数（rayCanPass），如果函数返回为 false，那么整个 checkLine 就停止运行然后返回 false。

例如:

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

这样的实现很简洁而且高效，尤其是当发现障碍就停止循环。注意如果你让 checkLine 函数循环太多次的话，Flash 上的性能可能不会太好，因为 Flash 函数调用性能损耗挺高。（译注：这篇文章发布在 2013 年，现在 Flash 都已经进入坟墓了……）

3.2. 寻路算法优化

当你在写寻路算法的时候（例如 A-star 算法），现实会让你发现调用这些算法在实时游戏中会消耗不少性能。所以你要尽可能不去调用寻路算法。

根据我们上述的例子，如果你能够回答“怪物能够看到玩家吗”这个问题，你就可以利用这种方式来减少不必要的寻路算法调用。

3.3. 平滑寻路路径

大部分的寻路算法会返回从起点到终点间的所有的位置点，不过对于网格来说会有点生硬。

Bresenham 直线算法可以很轻松就让寻路算法的结果更加“平滑”一些，你需要做的是：

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

3.4. 视野检测（圆锥）

想要实现像 Metal Gear Solid

or Commando 那样的圆锥视野不难。

检测敌人是否看到玩家的做法：

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

3.5. 关于对角的注意点

注意如果你的游戏中有对角的墙，基础的 bresenham 直线算法还是能够穿墙而望的。

3.6. 光照

如果你需要遍历范围内的所有点，例如 rouge-like 游戏里面的火炬，你可以使用 Bresenham 直线算法来检测火炬是否能够看到某个特定点。如果可以，那你就可以点亮那个单元格，然后光照的亮度等于单元格距离火炬的距离 / 最大光照距离。

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;
            // 更新光照值，绘制，...
        }
    }

对于玩家你还是可以拥有动态光照的，像 roguelike 游戏，只有在玩家的单元格发生变化时才重新计算光照（例如移动）。这里面还有很多优化的空间，不过具体如何实现取决于你的需求。

3.7. Pixel perfect 的圆

Bresenham 直线算法通常用作画直线，不过其实也可以用来画圆。实际上实现这一点的作者并不是 Bresenham 本人，不过这个实现方法深受 Bresenham 的启发。

它不像直线那么常用，但是在一些情况下还是有作用的，而且很容易实现。更多的细节可以在 Wikipedia “Midpoint circle algorithm” 词条页面上看到。

在检测中通过添加一些额外的点来修正圆：你可以修正圆里面的中断的地方（例如 error < 0），检测中断周围的其它点。效果是在不影响水平线和垂直线的情况下，让对角线变得更粗。（译注：这段作者说得有点云里雾里，简单来说就是让一个不 pixel perfect 的圆通过修正变得 pixel perfect）

译者的话

现在大部分游戏引擎都内置了寻路算法、动态光照等，可能大多数情况下使用内置的算法就能解决问题，不过文章中的思路还是很值得借鉴的，尤其是当发现内置的算法不满足需求时。