最近剛好有需求研究A*路徑搜尋，查找了許多範例，發現地圖格式幾乎都是二維陣列，和我們定義的地圖格式不同，考量到地圖點位數量直接影響運算效率，我一直在思考如何使用原本的地圖格式進行運算，有空時就不自覺在腦海中想著可能的方式，終於靈光乍現，讓我想到最終實作出一個Demo網頁，點我前往。
本篇會直接說明修改方式，需要對於A*有基礎了解，比較能看懂後續的說明，可以到最下方的參考清單看看。先介紹一下，網上常見範例都是這種二維陣列的網格，再標記該點是否可通行，如下圖的(1, 1), (1, 2)是不能通行的，其他則是可通行。
而我的地圖格式則是定義好存在的點，再用線連起來代表這兩點可通行，每個點是有xy座標的，也允許非網格式排法，像是不等距，不規則形，資料結構也有所不同，如下所示
class Point {
Id = -1;
X = -1;
Y = -1;
constructor(id, x, y) {
this.Id = id;
this.X = x;
this.Y = y;
}
}
//定義點位
let points = [
new Point(0, 0, 0),
new Point(1, 0, 100),
new Point(2, 0, 200),
new Point(3, 0, 300),
new Point(4, 100, 300),
new Point(5, 200, 300),
new Point(6, 200, 200),
new Point(7, 200, 100),
new Point(8, 300, 300),
new Point(9, 300, 200),
new Point(10, 300, 100),
new Point(11, 300, 0),
new Point(12, 200, 0),
new Point(13, 100, 0),
new Point(14, 100, 100)
];
//定義兩點相連的線
let lines = [
[0, 1],
[1, 2],
[2, 3],
[3, 4],
[4, 5],
[5, 6],
[5, 8],
[6, 7],
[6, 9],
[8, 9],
[9, 10],
[10, 11],
[11, 12],
[12, 13]
];
關鍵的地方在於，只要你有方式可以找到鄰居的點，是不是二維陣列也沒那麼重要了，核心算法不變，都可以依據你的格式來演算，真該早點發現這點的，被範例洗腦了。考量到線未來可以乘載更多的屬性影響路徑成本，我希望同樣一個點，但來自不同方向，也可以有不同的成本區別，為此我增加了路徑屬性，紀錄該點的移動歷程。
//紀錄該點成本
class PointCost extends Point {
Cost = -1;
Path = [];
/**
* @var Point here
* @var Point start
* @var Point end
* @var PointCost last
*/
constructor(here, start, end, last = null) {
super(here.Id, here.X, here.Y);
this.Cost = PointCost.CalCost(here, start, end);
if (last !== null) {
//若有上一個點，則繼承其路徑，並加入自身點為最後一點
this.Path = last.Path.concat();
}
this.Path.push(here.Id);
}
/**
* 計算該點路徑的成本，和起訖點xy座標的差值，因為我的情境不走斜線，
* 所以這樣就行，未來有某些特殊需求要優先的，都是在這邊增加對應的判斷
* @var Point here current point
* @var Point start start point
* @var Point end end point
*/
static CalCost(here, start, end) {
return (Math.abs(here.X - start.X) + Math.abs(here.Y - start.Y) +
Math.abs(here.X - end.X) + Math.abs(here.Y - end.Y));
}
}
/**
* 計算該點路徑的成本，和起訖點xy座標的差值，因為我的情境不走斜線，
* 所以這樣就行，另外會判斷是否避免轉彎，若轉彎會增加額外Cost
* 未來有某些特殊需求的話，都需要在Cost這邊做文章，影響下一個點的選擇
* @var Point here current point
* @var Point start start point
* @var Point end end point
*/
CalCost(here, start, end) {
//distance between start and end points
let cost = (Math.abs(here.X - start.X) + Math.abs(here.Y - start.Y) + Math.abs(here.X - end.X) + Math.abs(here.Y - end.Y));
//calculate turn need at least 3 points
if (this.Config?.AvoidRotation && here.Path.length >= 3) {
let turn_cost = 0;
for (let i = 0; i < here.Path.length - 2; i++) {
let x_offset = Math.abs(this.Points[here.Path[i]].X - this.Points[here.Path[i + 1]].X);
let y_offset = Math.abs(this.Points[here.Path[i]].Y - this.Points[here.Path[i + 1]].Y);
x_offset += Math.abs(this.Points[here.Path[i + 1]].X - this.Points[here.Path[i + 2]].X);
y_offset += Math.abs(this.Points[here.Path[i + 1]].Y - this.Points[here.Path[i + 2]].Y);
if (x_offset > 0 && y_offset > 0) {
turn_cost += this._TURN_COST_VALUE;
}
}
cost += turn_cost;
}
return cost;
}
尋找相鄰點的方式，簡單粗暴，過濾包含該點的值，攤平後，再去掉當前點
/**
* @var int id
*/
FindNearPoint(id) {
let near_id =
this.Lines.filter(x => x.includes(id)) //x=2, [1, 2], [2,3]
.flat() //[1,2,2,3]
.filter(x => x != id); //[1,3]
return near_id;
}
主要的搜尋方式，由於已經有路徑屬性，因此可以省略CloseList，將起始點計算成本加入OpenList，接著不斷從中取鄰近點，需判斷是否為回頭路，避免無窮迴圈
/**
* @var Point start start point
* @var Point end end point
*/
GetPath(start, end) {
this.OpenList.push(new PointCost(start, start, end));
let min_idx = 0;
let short_path = null;
while (this.OpenList.length > 0) {
//找到成本最低的路線
min_idx = 0;
let next = this.OpenList.length === 1 ? this.OpenList[0] : this.OpenList.reduce((prev, curr, idx) => {
if (prev.Cost < curr.Cost) {
return prev;
} else {
min_idx = idx;
return curr;
}
});
let nearPointIds = this.FindNearPoint(next.Id);
this.OpenList.splice(min_idx, 1);
for (let i = 0; i < nearPointIds.length; i++) {
//若該點路徑已包含鄰近點，代表回頭路，跳過不處理
if (next.Path.includes(nearPointIds[i])) {
continue;
}
let point_cost = new PointCost(this.Points[nearPointIds[i]], start, end, next);
//若鄰近點為終點，找到路徑，清空OpenList，跳出迴圈
if (nearPointIds[i] === end.Id) {
short_path = point_cost.Path;
this.OpenList.length = 0;
break;
}
//將鄰近點放入OpenList，繼續探索新路徑
this.OpenList.push(point_cost);
}
}
return short_path;
}
寫完後參考Wiki上的A*才發現，原來英文版有提示這種作法，但中文版沒有，看來原文還是比較詳細~
最後，這次有發現幾個要注意的點和學習到的用法，像是
- 陣列複製，要注意不能複製物件，要複製值，避免影響運算結果
- 陣列刪除元素要使用slice避免長度不變
- 如何用reduce一行從陣列找出屬性值最小的物件
參考
木澤的研發腦 