JS实现深度+启发（Heuristic DFS）寻路算法
本人在业余时间开发一个兔子围城游戏的时候，在网上寻找一种高效的寻路算法。最终找到这篇文章 四种寻路算法计算步骤比较 遂从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)把改方向放入路径数组中，循环一下一步。
腾讯云开发者
