译介丨简单介绍 Bresenham 直线算法


3楼猫 发布时间:2022-05-08 10:13:47 作者:mnikn Language

  • 原文链接:点击跳转
  • 作者: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; }
注意 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; // 更新光照值,绘制,... } }
对于玩家你还是可以拥有动态光照的,像 roguelike 游戏,只有在玩家的单元格发生变化时才重新计算光照(例如移动)。这里面还有很多优化的空间,不过具体如何实现取决于你的需求。

3.7. Pixel perfect 的圆

Bresenham 直线算法通常用作画直线,不过其实也可以用来画圆。实际上实现这一点的作者并不是 Bresenham 本人,不过这个实现方法深受 Bresenham 的启发。
它不像直线那么常用,但是在一些情况下还是有作用的,而且很容易实现。更多的细节可以在 Wikipedia “Midpoint circle algorithm” 词条页面上看到。
在检测中通过添加一些额外的点来修正圆:你可以修正圆里面的中断的地方(例如 error < 0),检测中断周围的其它点。效果是在不影响水平线和垂直线的情况下,让对角线变得更粗。(译注:这段作者说得有点云里雾里,简单来说就是让一个不 pixel perfect 的圆通过修正变得 pixel perfect)

译者的话

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

© 2022 3楼猫 下载APP 站点地图 广告合作:asmrly666@gmail.com