本人在業(yè)余時間開發(fā)一個兔子圍城游戲的時候，在網(wǎng)上尋找一種高效的尋路算法。最終找到這篇文章
四種尋路算法計算步驟比較
遂從C++代碼移植到了AS（Flash版，使用Player.IO作為后端），現(xiàn)在又從AS移植到了JS（微信小游戲需要），并使用ES6語法進行優(yōu)化。使得代碼盡量精簡。

源碼

const dx = [0, 0, -1, 1]; //四種移動方向?qū)和y坐標的影響
const dy = [-1, 1, 0, 0];
const Position = {
    move(direction) {
        this.x += dx[direction];
        this.y += dy[direction];
        this.pass = true
        this.createOrders()
    },
    back(direction) {
        this.pass = false
        this.order.p = 0
        this.x -= dx[direction];
        this.y -= dy[direction];
    },
    forwardPos(direction) {
        return Object.setPrototypeOf({ x: this.x + dx[direction], y: this.y + dy[direction] }, Position)
    },
    set pass(v) {
        this.past[this] = v
    },
    get pass() {
        return this.past[this]
    },
    ActOK(currAct) {
        var tempPos = this.forwardPos(currAct)
        if (tempPos.x > 8 || tempPos.x < 0 || tempPos.y > 8 || tempPos.y < 0 || tempPos.pass || this.chessboard.getGridByXY(this.x, this.y).walls[currAct]) //坐標出界？|| 已到過？
            return false;
        this.move(currAct)
        return true;
    },
    get distance() {
        return Math.abs(this[this.target[0]] - this.target[1])
    },
    createOrders() {
        var directions = [0, 1, 2, 3].map(i => ({ i, dis: this.forwardPos(i).distance }));
        directions.sort((a, b) => a.dis - b.dis) //根據(jù)距離排序，先探索距離近的方向
        var order = directions.map(x => x.i)
        order.push(-1)
        order.p = 0
        this.orders[this] = order
    },
    getNextAct() {
        return this.order[this.order.p++]
    },
    get order() {
        return this.orders[this]
    },
    toString() { return this.x + "," + this.y }
}
export default function({ pos: { x, y }, target }) {
    var pos = Object.setPrototypeOf({ x, y }, Object.assign(Position, { past: {}, orders: {}, chessboard: this, target }));
    pos.pass = true
    pos.createOrders()
    for (var path = [];;) {
        var currAct = pos.getNextAct()
        if (currAct < 0) {
            if (path.length)
                pos.back(path.pop())
            else return true
        } else if (pos.ActOK(currAct)) {
            if (pos.distance == 0) return false
            path.push(currAct)
        }
    }
    return true;
}

分析

基于游戲本身的規(guī)則，這個算法是四方向的，首先定義每一個方向的編號
0：↑ 1：↓ 2：← 3：→ 即[上,下,左,右]
或者這么想象

  0
2   3
  1

所以下面的代碼就好理解了

const dx = [0, 0, -1, 1]; //四種移動方向?qū)和y坐標的影響
const dy = [-1, 1, 0, 0];

如果此時方向向上，即編號為0，我們?nèi)〉玫膁x[0]就是x的變化即0，沒有變化
dy[0]是y軸的變化-1代表向上走一格，其他以此類推。

下面定義了一個Position對象，一會兒我們會講
我們先看主邏輯

var pos = Object.setPrototypeOf({ x, y }, Object.assign(Position, { past: {}, orders: {}, chessboard: this, target }));
pos.pass = true
pos.createOrders()

這三行代碼用了一些奇技淫巧
我們需要新建一個pos對象，x,y屬性是傳入的起點坐標。 Object.setPrototypeOf用來給這個對象搞一個父類（這一點不同于其他語言）。這個父類是Position對象，但為了每次初始化方便就用Object.assign給它強行覆蓋（沒有的時候會創(chuàng)建）屬性
past用于存儲已經(jīng)尋路過的坐標，orders存放最優(yōu)方向順序，后面兩個參數(shù)和業(yè)務(wù)邏輯有關(guān)先忽略
pos.pass = true 用來指明當前坐標已經(jīng)經(jīng)過，其執(zhí)行過程是這樣的。
會調(diào)用Position的set pass方法，即

set pass(v) {
     this.past[this] = v
}

其中this.past是之前初始化的past對象，方括號賦值，就是以this作為鍵。此時js會進行轉(zhuǎn)換，this轉(zhuǎn)成string類型，就會去調(diào)用

toString() { return this.x + "," + this.y }

好吧，我承認是裝逼寫法而已。應(yīng)該這么寫this.past[this.x + "," + this.y] = v
pos.createOrders() 用于創(chuàng)建優(yōu)先方向列表

createOrders() {
    var directions = [0, 1, 2, 3].map(i => ({ i, dis: this.forwardPos(i).distance }));
    directions.sort((a, b) => a.dis - b.dis) //根據(jù)距離排序，先探索距離近的方向
    var order = directions.map(x => x.i)
    order.push(-1)
    order.p = 0
    this.orders[this] = order
}

這個所謂的優(yōu)先方向，就是啟發(fā)式搜索算法里面的東西。就是朝4個方向前進一步后和目標距離進行比較，如果更接近目標那么就是優(yōu)先的方向，目的是加快朝目標尋路。
我們把列表保存，一會兒要用到。push(-1)的目的是代表方向都搜索結(jié)束的結(jié)束標志。
計算距離首先調(diào)用forwardPos函數(shù)

    forwardPos(direction) {
        return Object.setPrototypeOf({ x: this.x + dx[direction], y: this.y + dy[direction] }, Position)
    },

這個函數(shù)再次使用給對象指定父類的方式返回一個新的坐標的pos對象，這樣可以方便的調(diào)用Position中的方法。緊接著就調(diào)用了distance

    get distance() {
        return Math.abs(this[this.target[0]] - this.target[1])
    },

返回了兩點之間的距離，其中target[0]存放的是目標屬性名稱（‘x’或者‘y’），target[1]存放的是目標值。由于游戲規(guī)則設(shè)定，目標不是一個點，而是一條線，所以只需判斷其中一個坐標即可。

接下來進入主循環(huán)

    for (var path = [];;) {
        var currAct = pos.getNextAct()
        if (currAct < 0) {
            if (path.length)
                pos.back(path.pop())
            else return true
        } else if (pos.ActOK(currAct)) {
            if (pos.distance == 0) return false
            path.push(currAct)
        }
    }

其實就是一個死循環(huán)，path變量存放的是路徑數(shù)組，其元素是行走方向，用于回退。
首先我們調(diào)用getNextAct方法，用于獲取下一步的方向

    getNextAct() {
        return this.order[this.order.p++]
    },

this.order.p存放的是優(yōu)先列表的下標，從0開始，我們嘗試每一個方向的探索。
if (currAct < 0) 判斷了是否在這個位置的4個方向都已經(jīng)探索結(jié)束。

if (path.length)
  pos.back(path.pop())
else return true

上面這段表示如果路徑不為空，則后退一步，否則說明無路可退，搜索結(jié)束，不可達。
后退函數(shù)

    back(direction) {
        this.pass = false
        this.order.p = 0
        this.x -= dx[direction];
        this.y -= dy[direction];
    },

把當前坐標設(shè)置為沒有經(jīng)過，方向列表下標恢復為0，坐標朝反方向移動一格

下面我們看如果該方向尚未探索的邏輯

        } else if (pos.ActOK(currAct)) {
            if (pos.distance == 0) return false
            path.push(currAct)
        }

我們先調(diào)用ActOK，判斷此路是否可行

    ActOK(currAct) {
        var tempPos = this.forwardPos(currAct)
        if (tempPos.x > 8 || tempPos.x < 0 || tempPos.y > 8 || tempPos.y < 0 || tempPos.pass || this.chessboard.getGridByXY(this.x, this.y).walls[currAct]) //坐標出界？|| 已到過？
            return false;
        this.move(currAct)
        return true;
    },

tempPos時臨時向前走一步，判斷是否撞墻或者出界，如果可以走，那么就真的走一步，調(diào)用move函數(shù)

    move(direction) {
        this.x += dx[direction];
        this.y += dy[direction];
        this.pass = true
        this.createOrders()
    },

坐標根據(jù)方向改變，設(shè)置當前路徑已經(jīng)走過，然后再次調(diào)用獲取優(yōu)先方向的函數(shù)。

 if (pos.distance == 0) return false

代表已經(jīng)抵達終點，路徑可達，退出循環(huán)。
否則path.push(currAct)把改方向放入路徑數(shù)組中，循環(huán)一下一步。