[测试] 【译】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;
  }

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

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

3.7. Pixel perfect 的圆

Bresenham 直线算法通常用作画直线，不过其实也可以用来画圆。实际上实现这一点的作者并不是 Bresenham 本人，不过这个实现方法深受 Bresenham 的启发。它不像直线那么常用，但是在一些情况下还是有作用的，而且很容易实现。更多的细节可以在 Wikipedia 上看到。

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

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

【译】Bresenham 直线算法