與A-Star不同的像素級尋路算法上
來自： http://www.alloyteam.com/2016/03/and-a-star-on-different-pixel-pathfinding-algorithm/
前言：
尋路是游戲中非常重要的一項功能，這項功能將直接體現出AI的智商如何。那說起尋路的算法，就不得不提標題上面的A star算法了。A Star（又稱A*），是結合了Dijkstra算法和貪心算法優點的算法，對此不了解的同學可以去搜索一下，這里不具體介紹實現，而是簡單的說一下原理，為后面我們的主角鋪墊。
A Star的核心在于將游戲背景 分為一個又一個格子 ，每個格子有自己的靠譜值，然后通過遍歷起點的格子去找到周圍靠譜的格子，接著繼續遍歷周圍……最終找到終點。好了，A Star的介紹就到這里了，因為它不是文章的主角。
文章篇幅較長所以分為上下文，下文地址：
上下文各有一種實現方式，區別看了就知道，此外上文包含了一些研究尋路的思考。
開頭介紹A Star我們提及了格子，這是A Star最核心的一個地方，不過并不是所有游戲都引入了格子的概念，還有很多的游戲是像素級別的。雖然說像素也是一個個的格子，如果用A Star針對像素來尋路，試想如果一個1366*768分辨率的屏幕，那格子的總數將會有1049088個，這明顯是很不合適的。
那么接下來就有請我們的文章主角出場了，算法沒有名字，因為百分百原創，可能還有一些自己沒有發現的坑點，希望和大家一起討論研究~
1、尋路的本質是什么
在現實生活中尋路就是從起點到達目的地，在游戲中也是如此，區別在于我們人在現實中會自己避開各個障礙物，而計算機不會，所以尋路本質就是 我們幫助計算機避開一個又一個障礙物
如果我們對計算機下達一個從紅點到藍點的命令，如圖
第二幅圖中我們必須要幫助計算機繞開多邊形
2、該以怎么樣的方式繞開
下圖中紅線和藍線都是繞開的表現，但所有人都不會選擇藍色的方式，因為它遠
遠的路徑有很多很多，那么什么是最近的呢，我們知道： 兩點之間，線段最短
但我們用最短路徑的話一定與障礙物多邊形相交，這時候我們換一種思維，不考慮繞過，而考慮什么時候不會相交，如圖
看！只要將起點終點平移了就沒有相交了！
先別慌著噴我……看下圖
這里A點我稱之為必過點，就是以最短繞開路徑一定會經過的點，①
我們剛剛通過平移移動起點和終點的絕對位置，不改變它們相對位置，掃過了障礙物區域，發現了一個必過點
整個尋路的思想就是如此！
接下來說具體在程序中是如何實現的
a、先將起點終點連接
b、針對連線的垂直平分線方向平移
c、直到發現連線沒有與障礙物相交即可
d、去障礙物上與那個沒有相交的線最近點(也就是必過點)，分別與起點和終點相連
整個流程就是如此，下面說實現過程中的一些難點和坑點
1、如何找到必過點
因為我們所說的連線與障礙物相交，本質上是與障礙物中的某一條線相交了
圖中藍線和紅線相交所以說與障礙物相交了
我們找必過點的方式就是首先找到連線最后相交的障礙物的兩點，然后針對這兩點分別求到起點和終點的距離
就是圖中比較a1+a2和b1+b2的大小，距離小的就是必過點
2、第一次找到的必過點無法直接和終點或起點相連
這個就是用核心思想遞歸的再去找下一個必過點
不過代碼里面我是用循環做的
給出一張開啟debug的演示圖
那么多黑點黑線是平移的軌跡，然后黃點是第一個必過點，此時發現黃點無法與藍色點相連，那么continue，以黃點為起點和藍點為終點，找出第二個必過點粉色的點
3、平移連線穿過必過點，大坑
注意小標題中的 穿 字，先用一個例子表示出來
開啟debug我們走一遍看看~
注：我這里設定了只找一個必過點，所以出現了穿越的情況
但問題是怎么必過點（綠點）會出現在這兒！！
因為那個紅框， 平行線（紅框內的那個）過了障礙物沒問題，但它是穿越過去的！ 不是按我們想的橫掃過去的！
那該如何解決，這時候就需要我們矯正起點和終點了
只需要把起點和終點都保證在障礙物的AABB外就可以了，AABB就是將一個多邊形看成長方形，它的x，y，width和height
這個在AABB外也不是隨便取得，必須按照連線的方向去延長，讓我們看看效果
如圖所示
在線演示地址：http://westanhui.github.io/navigate/index.html
注意：點擊畫障礙物，通過左鍵單擊畫多邊形最后右鍵自動閉合圖像
下面貼核心代碼和解釋（完整代碼可查看頁面源代碼）
function determinant(a, b, c, d) {
return (a * d - b * c);
}
function isLineCross(a1, a2, b1, b2) {
if(globalIndex++ > 1000) {
throw 'to much times';
}
var delta = determinant(a2.x - a1.x, b1.x - b2.x, a2.y - a1.y, b1.y - b2.y);
if(delta <= (1e-6) && delta >= -(1e-6)) {
return false;
}
var namenda = determinant(b1.x - a1.x, b1.x - b2.x, b1.y - a1.y, b1.y - b2.y) / delta;
if(namenda > 1 || namenda < 0) {
return false;
}
var miu = determinant(a2.x - a1.x, b1.x - a1.x, a2.y - a1.y, b1.y - a1.y) / delta;
if(miu > 1 || miu < 0) {
return false;
}
return true;
}
這個是工具方法，判斷兩條線是否相交的，用的是矩陣的方法
// 首先判斷起點終點是不是在障礙物內
var outPoint = getPointOutside(obstacles);
if(isInObstacles(outPoint, start, obstacles)) {
alert('fuck');
return ;
}
if(isInObstacles(outPoint, end, obstacles)) {
alert('fuck');
return ;
}
function isInObstacles(start, end, obstacles) {
var index = 0;
var result;
for(var i = 0; i < obstacles.length - 1; i++) {
result = isLineCross(start, end, obstacles[i], obstacles[i + 1]);
if(result) {
index++;
}
}
index = index % 2;
if(index === 0) {
return false;
} else {
return true;
}
}
這個用了經典的射線法去判斷某個點是否在一個多邊形內
原理就是在多邊形外面取一點，然后和判斷的點相連，與多邊形相交個數為偶數則點不在多邊形內，為奇數則在多邊形內
// 計算斜率 k = (end.y - start.y) / (end.x - start.x); // 連線的斜率 kk = -1 / k; // 連線的垂直平分線的斜率
// 判斷起點終點是否在障礙物的AABB內
limit = getAABB(obstacles);
// 矯正位置
var currStart = redressPoint(start, end, limit);
var currEnd = redressPoint(end, start, limit);
function redressPoint(aPoint, bPoint, limit) {
var tmpX;
var tmpY;
var tmpPoint;
if(isInAABB(aPoint, limit)) { // 如果點在障礙物的AABB內就矯正位置
if(bPoint.x > aPoint.x) { // 計算兩點x的相對位置，這里先以x來偏移y
tmpX = limit.minX; // 如果a點x小于b點，那么就默認移動到AABB中最小的x點位置
tmpY = aPoint.y - (aPoint.x - tmpX) * k; // 根據斜率算y的偏移
} else { // 與上同理
tmpX = limit.maxX;
tmpY = aPoint.y - (aPoint.x - tmpX) * k;
}
tmpPoint = {
x: tmpX,
y: tmpY
};
if(tmpY < limit.maxY && tmpY > limit.minY) { // 根據剛剛矯正偏移的x，y判斷是否出了AABB，沒有則以y為基準偏移x重新矯正
if(bPoint.y > aPoint.y) {
tmpY = limit.minY;
tmpX = aPoint.x - (aPoint.y - tmpY) / k;
} else {
tmpY = limit.maxY;
tmpX = aPoint.x - (aPoint.y - tmpY) / k;
}
tmpPoint = { // 該點就是矯正點
x: tmpX,
y: tmpY
};
}
} else {
tmpPoint = aPoint; // 無須矯正
}
if(isDebug) { // debug模式下顯示矯正的點在哪
drawCircle(tmpPoint, 'yellow');
}
return tmpPoint;
}
這里是矯正起點終點的代碼，其中主要都是關于斜率的數學計算，感興趣的同學可以走一遍看看，注意其中先是按x為基準根據斜率算出矯正后的y，得到新的(x,y)，然后判斷這個點是否出了障礙物的AABB，沒有的話重新按y為基準去算x，兩種情況肯定有一種會將點矯正出障礙物的AABB
function check(start, end, obstacles) {
var isCollision = true; // 結束判斷符
var dir = 0; // 方向
isBodyCross(start, end, obstacles);
function isBodyCross(currStart, currEnd, obstacles) {
var unit = 50; // 每次平移的基數單位
var index = 0; // 偏移的次數
var changeX = 0; // 平移x方向的具體改變量
var changeY = 0; // 平移y方向的具體改變量
var door1 = true;
var door2 = true;
k = (currEnd.y - currStart.y) / (currEnd.x - currStart.x); // 連線的斜率
kk = -1 / k; // 連線的垂直線的斜率
if(Math.abs(k) > 1) { // 以x為單位的變動
changeX = 10;
changeY = 10 * kk;
} else { // 以y為單位的變動
changeX = 10 / kk;
changeY = 10;
}
while(isCollision) { // 當不碰撞的時候結束循環
if(index > 1000) { // 增加一個界限
alert('Error');
return ;
}
// 開始某個方向的尋路
door1 = true;
nextStart = {
x: currStart.x + changeX * index,
y: currStart.y + changeY * index
};
nextEnd = {
x: currEnd.x + changeX * index,
y: currEnd.y + changeY * index
};
for(var i = 0; i < obstacles.length - 1; i++) {
result = isLineCross(nextStart, nextEnd, obstacles[i], obstacles[i + 1]);
if(result) { // 連線碰撞
x1 = obstacles[i]; // 最后碰撞邊上的點
y1 = obstacles[i + 1]; // 最后碰撞邊上的點
door1 = false;
drawRole(nextStart, nextEnd);
break;
}
}
if(door1) { // 沒有阻礙
dir = 1;
isCollision = false;
break;
}
// 另一個方向的尋路
door2 = true;
nextStart = {
x: currStart.x - (changeX * index),
y: currStart.y - (changeY * index)
};
nextEnd = {
x: currEnd.x - (changeX * index),
y: currEnd.y - (changeY * index)
};
for(i = 0; i < obstacles.length - 1; i++) {
result = isLineCross(nextStart, nextEnd, obstacles[i], obstacles[i + 1]);
if(result) {
x2 = obstacles[i];
y2 = obstacles[i + 1];
door2 = false;
drawRole(nextStart, nextEnd);
break;
}
}
if(i === obstacles.length - 1) { // 檢測完障礙物上的邊，沒有碰撞
dir = -1;
isCollision = false;
break;
}
index++;
}
if(door1 || door2) {
fixPoint(changeX, changeY); // 確定必過點
}
}
function fixPoint(changeX, changeY) {
var dis1;
var dis2;
var f;
var x, y;
if(dir === 1) {
x = x1;
y = y1;
} else {
x = x2;
y = y2;
}
if(typeof x === 'undefined') {
return ;
}
// 算距離
dis1 = distance(x, nextStart, nextEnd);
dis2 = distance(y, nextStart, nextEnd);
var symbolX;
var symbolY;
if(dis1 < dis2) { // 比較距離的大小，得出必過點，此時x是必過點
// 下面兩個if用來將必過點往整個障礙物外面偏移一點
if(x.y > y.y) {
symbolY = 1;
} else {
symbolY = -1;
}
if(x.x > y.x) {
symbolX = 1;
} else {
symbolX = -1;
}
f = { // 偏移后的必過點
x: x.x + (5 * symbolX),
y: x.y + (5 * symbolY)
};
drawCircle(f, 'green');
} else { // 必過點是y
if(y.y > x.y) {
symbolY = 1;
} else {
symbolY = -1;
}
if(y.x > x.x) {
symbolX = 1;
} else {
symbolX = -1;
}
f = { // 最終必過點的位置
x: y.x + (5 * symbolX),
y: y.y + (5 * symbolY)
};
drawCircle(f, 'pink');
}
// 將必過點添加到最終路徑
f.index = end.index;
globalPath.splice(f.index, 0, f);
for(var i = 0; i < globalPath.length; i++) {
globalPath[i].index = i;
}
// 下一輪計算前這些值設置為undefined
x1 = undefined;
y1 = undefined;
x2 = undefined;
y2 = undefined;
var tmp = redressPoint(globalPath[f.index - 1], f, limit); // 矯正
check(tmp, f, obstacles);
tmp = redressPoint(globalPath[f.index + 1], f, limit); // 矯正
check(f, tmp, obstacles);
}
}
核心的代碼，先看外面的dir，它是方向，因為這個平行是要按照兩個方向去判斷的
unit值的大小決定平移的精度，我自己用的是50px，感覺還不錯，如果這個值過大，可能會出現跳過障礙物某條邊的情況，如果這個值過小，會影響性能
changeX和changeY是x方向和y方向變動的值，根據斜率計算出來的
然后while循環就開始不停的找到每一個必過點，而確定必過點就是通過fixPoint函數，dis1和dis2是用來計算長度判斷一個邊上的兩個點哪個是必過點，前面有說過。symbolX和symbolY是當時有些畫蛇添足的一步，用來 把找到的必過點向外偏移一點 ，方便看清楚，看demo效果挺好，不過實際上是不需要的
——————————————————我是分隔符————————————————————
說了這么多，也貼出了在線演示地址，簡單易操作，就不說了，下面說一下這個方法不足的地方
有一個不足，但也是一個很致命的不足，就是一旦 起點或者終點就在障礙物的AABB內，而且這個AABB內很怪異的時候 ，會出現問題，下面舉出例子
一旦起點或者終點被障礙物這樣詭異的包圍的時候，整個尋路就會出現問題，即使我們將點矯正出障礙物的AABB也不行
原因的本質是我們的算法核心是 連線平移去繞過障礙物 ，只要出現 連線平移穿過障礙物 的情況那就違背繞的本質
有問題我們自然要解決
我嘗試了一些方法，比如分割障礙物，多次矯正等等，都不合適，本身算法核心的問題再怎么hack也沒辦法
那怎么辦，看之前標注的①，我們將關注點由連線變成多邊形上的每個點，因為每個點都可能是必過點不是么~
下文會詳細講解另外一種方法
最后：
既然該方法有致命的弱點，那它能用嗎？
我認為是可以的，但有一定的條件，就是重點和起點盡量不要在障礙物的AABB內， 障礙物不是多邊形也沒事 ，這是該方法優勢的一個情況，目前我們的障礙物都是多邊形，如果是圓呢？因為該方法考慮的是起點和終點的連線，對障礙物幾乎沒有要求，只需要根據平行后的連線算出必過點就可以了，所以對障礙物形狀沒有要求，只有對位置有一定的要求
好了，這篇文章就說到這兒了，下篇文章我們將以另一個角度去尋路，無視起點終點被詭異的障礙物包裹
請看下文：
http://www.alloyteam.com/2016/03/with-a-star-under-different-pixel-pathfinding-algorithm/
</div>