1. 什麼是 Bresenham 直線算法
Bresenham 直線算法是個很通用的算法，幾個月前我才剛剛了解到它，它在許多用途上都很實用。這個算法基本用來在兩點之間基於網格（例如像素網格）繪制一條直線，繪制出來的直線是 pixel perfect 的，看起來很酷（譯註：pixel perfect 的定義參考這篇文章中有關線條的說法，幸好學過像素畫不然還不知道這個是什麼）。
不過這個算法還有很多有趣的用途：
2. 實現
你可以看下基於 Haxe 的實現，這部分代碼在我的 GitHub 倉庫里面：BRESENHAM.HX
以下是基於 Haxe 的實現：
注意 fastAbs 和 fastFloor都是 absolute 和 floor 的極致性能實現版：
對於 Bresenham 算法，你需要了解的是:
我建議你讀下 Wikipedia 上有關 Bresenham 直線算法的常規實現，尤其是如果你想要根據情況對它做一些特殊處理，在上面你還能發現一些有趣的優化技巧。
所以這個算法我們要怎麼去用呢？
3. 使用案例
3.1. AI
當你想要寫一個怪物敵人的 AI 時，你通常會遇到兩個很基礎的問題：
第二個問題可以用 Bresenham 直線算法來輕松解答，只需要用它來檢測怪物的視線和玩家中是否有障礙物就好。
這個版本沒有返回任何位置點，它只是對於線上的每個點都調用下函數（rayCanPass），如果函數返回為 false，那麼整個 checkLine 就停止運行然後返回 false。
例如:
這樣的實現很簡潔而且高效，尤其是當發現障礙就停止循環。注意如果你讓 checkLine 函數循環太多次的話，Flash 上的性能可能不會太好，因為 Flash 函數調用性能損耗挺高。 （譯註：這篇文章發布在 2013 年，現在 Flash 都已經進入墳墓了……）
3.2. 尋路算法優化
當你在寫尋路算法的時候（例如 A-star 算法），現實會讓你發現調用這些算法在實時遊戲中會消耗不少性能。所以你要盡可能不去調用尋路算法。
根據我們上述的例子，如果你能夠回答「怪物能夠看到玩家嗎」這個問題，你就可以利用這種方式來減少不必要的尋路算法調用。
3.3. 平滑尋路路徑
大部分的尋路算法會返回從起點到終點間的所有的位置點，不過對於網格來說會有點生硬。
Bresenham 直線算法可以很輕松就讓尋路算法的結果更加「平滑」一些，你需要做的是：
3.4. 視野檢測（圓錐）
想要實現像 Metal Gear Solid or Commando 那樣的圓錐視野不難。
檢測敵人是否看到玩家的做法：
3.5. 關於對角的注意點
注意如果你的遊戲中有對角的牆，基礎的 bresenham 直線算法還是能夠穿牆而望的。
3.6. 光照
如果你需要遍歷范圍內的所有點，例如 rouge-like 遊戲里面的火炬，你可以使用 Bresenham 直線算法來檢測火炬是否能夠看到某個特定點。如果可以，那你就可以點亮那個單元格，然後光照的亮度等於單元格距離火炬的距離 / 最大光照距離。
這樣一個算法實時運行的話會相當耗性能，因為你需要遍歷每個點和火炬來計算光照值。不過如果你不需要很實時，例如火炬不需要動態移動，你可以在遊戲開始前預計算你的光照值，這樣消耗基本上就忽略不計了，而且這實現起來一點都不難。
對於玩家你還是可以擁有動態光照的，像 roguelike 遊戲，只有在玩家的單元格發生變化時才重新計算光照（例如移動）。這里面還有很多優化的空間，不過具體如何實現取決於你的需求。
3.7. Pixel perfect 的圓
Bresenham 直線算法通常用作畫直線，不過其實也可以用來畫圓。實際上實現這一點的作者並不是 Bresenham 本人，不過這個實現方法深受 Bresenham 的啟發。
它不像直線那麼常用，但是在一些情況下還是有作用的，而且很容易實現。更多的細節可以在 Wikipedia 「Midpoint circle algorithm」 詞條頁面上看到。
在檢測中通過添加一些額外的點來修正圓：你可以修正圓里面的中斷的地方（例如 error < 0），檢測中斷周圍的其它點。效果是在不影響水平線和垂直線的情況下，讓對角線變得更粗。（譯註：這段作者說得有點雲里霧里，簡單來說就是讓一個不 pixel perfect 的圓通過修正變得 pixel perfect）
譯者的話
現在大部分遊戲引擎都內置了尋路算法、動態光照等，可能大多數情況下使用內置的算法就能解決問題，不過文章中的思路還是很值得借鑒的，尤其是當發現內置的算法不滿足需求時。
來源：機核
