本人在业余时间开发一个兔子围城游戏的时候，在网上寻找一种高效的寻路算法。最终找到这篇文章
四种寻路算法计算步骤比较
遂从C++代码移植到了AS（Flash版，使用Player.IO作为后端），现在又从AS移植到了JS（微信小游戏需要），并使用ES6语法进行优化。使得代码尽量精简。

源码

const dx = [0, 0, -1, 1]; //四种移动方向对x和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) //根据距离排序，先探索距离近的方向
        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;
}

分析

基于游戏本身的规则，这个算法是四方向的，首先定义每一个方向的编号
0：↑ 1：↓ 2：← 3：→ 即[上,下,左,右]
或者这么想象

  0
2   3
  1

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

const dx = [0, 0, -1, 1]; //四种移动方向对x和y坐标的影响
const dy = [-1, 1, 0, 0];

如果此时方向向上，即编号为0，我们取得的dx[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给它强行覆盖（没有的时候会创建）属性
past用于存储已经寻路过的坐标，orders存放最优方向顺序，后面两个参数和业务逻辑有关先忽略
pos.pass = true 用来指明当前坐标已经经过，其执行过程是这样的。
会调用Position的set pass方法，即

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

其中this.past是之前初始化的past对象，方括号赋值，就是以this作为键。此时js会进行转换，this转成string类型，就会去调用

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

好吧，我承认是装逼写法而已。应该这么写this.past[this.x + "," + this.y] = v
pos.createOrders() 用于创建优先方向列表

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

这个所谓的优先方向，就是启发式搜索算法里面的东西。就是朝4个方向前进一步后和目标距离进行比较，如果更接近目标那么就是优先的方向，目的是加快朝目标寻路。
我们把列表保存，一会儿要用到。push(-1)的目的是代表方向都搜索结束的结束标志。
计算距离首先调用forwardPos函数

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

这个函数再次使用给对象指定父类的方式返回一个新的坐标的pos对象，这样可以方便的调用Position中的方法。紧接着就调用了distance

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

返回了两点之间的距离，其中target[0]存放的是目标属性名称（‘x’或者‘y’），target[1]存放的是目标值。由于游戏规则设定，目标不是一个点，而是一条线，所以只需判断其中一个坐标即可。

接下来进入主循环

    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)
        }
    }

其实就是一个死循环，path变量存放的是路径数组，其元素是行走方向，用于回退。
首先我们调用getNextAct方法，用于获取下一步的方向

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

this.order.p存放的是优先列表的下标，从0开始，我们尝试每一个方向的探索。
if (currAct < 0) 判断了是否在这个位置的4个方向都已经探索结束。

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

上面这段表示如果路径不为空，则后退一步，否则说明无路可退，搜索结束，不可达。
后退函数

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

把当前坐标设置为没有经过，方向列表下标恢复为0，坐标朝反方向移动一格

下面我们看如果该方向尚未探索的逻辑

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

我们先调用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时临时向前走一步，判断是否撞墙或者出界，如果可以走，那么就真的走一步，调用move函数

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

坐标根据方向改变，设置当前路径已经走过，然后再次调用获取优先方向的函数。

 if (pos.distance == 0) return false

代表已经抵达终点，路径可达，退出循环。
否则path.push(currAct)把改方向放入路径数组中，循环一下一步。