RPG手游中Bresenham算法推導(dǎo)以及應(yīng)用

Bresenham算法是一開始用于圖形學(xué)中繪制直線。無論屏幕的分辨率多么的大，它始終都是由一個個的方形像素點組成的。在屏幕上繪制一條有角度的直線時，像素點并不會都落在直線上。對于直線上的點，需要一種算法算出最接近直線上的點或者說最適合的點。BresenHam算法就是其中一種算法。這個算法只會用到較為快速的整數(shù)加法、減法和位元移位，所以非常高效。
Bresenham算法一般也用于rpg手游或者其他需要尋路的手游。這類手游的地圖會被分成很小的格子(例如:32像素*32像素)，利用工具，可以將地圖的阻擋區(qū)域標(biāo)出，然后導(dǎo)出地圖的配置文件(例如，json或者xml等)。
當(dāng)rpg手游的實體需要尋路的時候，第一步需要根據(jù)地圖的阻擋信息，計算出實體到目標(biāo)點是否可以直線通過，這個時候就需要用到bresenham算法。
本文只考慮直線斜率大于0并且小于1的情況。

先來看一種dda算法：
function dda(x0: number, y0: number, x1: number, y1: number) {
let output = [];
let k = (y1 - y0) / (x1 - x0);
let x = x0 + 1; //x初始值
while (x <= x1) {
let y = Math.floor(k * (x + 1) + 0.5);
output.push({ x: x, y: y });
x = x + 1;
}
return output;
}
代碼很少，但是運算中用到了浮點數(shù)的乘法和加法，不是一種高效的做法。

接著來看下bresenham算法的推導(dǎo)過程。
Bresenham算法有2種推導(dǎo)方法，如下圖所示:

為了簡單起見，設(shè)，直線方程為y = kx，也就是以起始點為坐標(biāo)原點。

1. 設(shè)置變量，xStep = 1；totalXstep = 0；totalYstep = 0；lineY = 0；gridY = 0；preGridY = 0；deltaX = x1-x0；deltaY= y1-y0。其中l(wèi)ineY為直線上真實的縱坐標(biāo)，girdY為選擇的格子坐標(biāo)，preGridY為上一個格子坐標(biāo)。
2. 由y = kx可知道，當(dāng)x每增加1，y的增量為k。
3. 由x0開始推導(dǎo)。
   A．當(dāng)x = x0 + 1，totalXstep = totalXstep +1，lineY = y0 + k，判別式為k-0.5。
   當(dāng)k - 0.5 >= 0時，gridY = y0 + 1，totalYstep = totalYstep + 1；
   當(dāng)k – 0.5 < 0時，gridY = y0；
   preGridY= gridY；
   B．當(dāng)x = x0 + 2，totalXStep = totalXStep + 1，lineY =y0 + totalXstep k，判別式為 totalXstep k – (totalYstep + 0.5);
   當(dāng)totalXstep k – (totalYstep + 0.5) >=0時，gridY = preGridY +1，totalYstep = totalYstep + 1；
   當(dāng)totalXstep k – (totalYstep + 0.5) < 0時，gridY = preGridY，
   preGridY= gridY；
4. 由上可得，判別式為totalXstep k – (totalYstep + 0.5) >=0，k = deltaY / deltaX；將k代入左式，并且兩邊乘以deltaX，再乘以2得:
   2totalXstep deltaY –2deltaXtotalYstep – deltaX >=0
   也可以寫成：
   2totalXstep deltaY > 2deltaX*totalYstep + deltaX
   由此，這個算法只剩下整數(shù)的乘法和加法。

下面我們換另外一種推導(dǎo)方法。
1.設(shè)置變量d1，d2，Xi，Xi+1，Yi，Yi+1，Y，X，Hi，Hi+1

2. d1 = Y- Yi =(k(Xi +1) + b) –Yi
   d2 = Yi +1 - Yi = Yi +1 -(k(Xi +1) + b)
3. d1-d2 = 2k(Xi +1) – 2 Yi +2b-1
   4.將k = deltaY/deltaX，代入上式得
   deltaX(d1-d2) = 2deltaY Xi -2deltaX Yi + c
   令Hi = deltaX(d1-d2) = 2deltaY Xi -2deltaX Yi + c
   則Hi+1 = 2deltaY Xi+1 -2deltaX Yi+1 + c
   Hi+1 - Hi = 2deltaY( Xi+1 - Xi) – 2deltaX( Yi+1 - Yi)
   令Xi+1 = Xi +1，
   Hi+1 = Hi +2deltaY – 2deltaX( Yi+1 - Yi)
   則：
   A． 如果選擇右上方的像素，即：Yi+1 – Yi =1， 則 Hi+1 = Hi +2deltaY – 2deltaX
   B．如果選擇右方像素，即Yi+1 = Yi ，則：Hi+1 = Hi +2deltaY
   在起始像素(x0,y0)的第一個參數(shù)h0為：
   h0 = 2deltaY – deltaX；
   這個算法只會用到較為快速的整數(shù)加法、減法和位元移位，是高效的算法。
   function bresenham(x0: number, y0: number, x1: number, y1: number) {
   let output = [];
   let deltaX = x1 - x0;
   let deltaY = y1 - y0;
   let err = 2 deltaY - deltaX;
   let x = x0;
   let y = y0;
   while (x <= x1) {
   x++;
   //先假設(shè)取右方的點，說明err+2deltaY小于0；
   // 其實也可以假設(shè)取右上方的點，判斷條件要不同
   err = err + 2 deltaY;
   if (err >= 0) { //說明取右方的點是不對的，應(yīng)取右上方的點
   y++;
   err = err - 2 * deltaX;
   }
   output.push({ x: x, y: y });
   }
   }