【译】Bresenham 直线算法

内容纲要

原文链接:https://deepnight.net/tutorial/bresenham-magic-raycasting-line-of-sight-pathfinding/
作者:Sébastien Bénard
译者:mnikn

1. 什么是 Bresenham 直线算法

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

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

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

2. 实现

你可以看下基于 Haxe 的实现,这部分代码在我的 GitHub 仓库里面:BRESENHAM.HXFrom deepnightLibs on GitHub

以下是基于 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;
}

注意 fastAbsfastFloor都是 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;
            // 更新光照值,绘制,...
        }
    }

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

3.7. Pixel perfect 的圆

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

它不像直线那么常用,但是在一些情况下还是有作用的,而且很容易实现。更多的细节可以在 Wikipedia 上看到。

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

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

留下评论