A*寻路算法初探及Js实现寻路过程

JavaScript
, ,

最近为了开发 王牌特工 这款小游戏，学习了A*寻路算法，来实现避开障碍物并抵达目标地点的功能。

算法具体实现过程可以学习这篇文章,本篇主要记录我使用Js实现寻路算法的过程（算法学习真是头疼- -）。

一、4个功能模块：

  • 二维方块地图

A*寻路算法是基于点到点的关系，而在游戏开发场景中，我们常常把地图划分成一个个小方块，通过二维数组记录每个方块的坐标值，从而可以定位到某个点。因此我们需要构建坐标系。我使用的是HTML5中的Canvas绘图，在创建2D上下文环境中以40X40为一方块分割画布。

1
2
3
4
5
6
7
8
9
// 每个方块对象具有的属性
var block = {
  x:……, // 横坐标
  y:……, // 纵坐标
  G:……, // 到该点的消耗
  H:……, // 到终点的消耗
  F:……, // G + H
  parents:…… // 父节点
}
  • 开启队列

存放需要遍历查找的方块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 开启队列
var openList = (function() {
  // 存放开启队列
  var _openArr = [];
  return {
    // 添加到队列
    add: function(point){……},
    // 计算队列长度
    count: function(){……},
    // 得到开放队列中f值最小的点
    minPoint: function(){……},
    // 删除某个点
    removeAt: function(index) {……},
    // 是否可以加入开启队列
    exists: function(obj) {……},
    // 点已经在开启队列中
    foundPoint: function(tempStart, end, point) {……},
    // 点不在开启队列中,计算G、H、F值
    notFoundPoint: function(tempStart, end, point) {……},
    // 是否到达目标点
    get: function(end) {……},
    // 队列初始化
    init: function() {……}
  };
})();
  • 关闭队列

存放不需要查找的方块

1
2
3
4
5
6
7
8
// 闭合队列
var closeList = (function() {
  var _closeArr = [];
  return {
    add: function(point) {……},
    init: function() {……}
  };
})();
  • A*寻路算法函数

见下一节

二、A*寻路算法的实现

  • A*寻路算法函数

findPath为寻路算法函数，该函数接受两个参数start(开始点)和 end(终点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var findPath = function(start, end) {
  // 是否抵达标志位
  var isArrive = false;
  openList.add(start);
  // 循环
  while(!isArrive)
  {
    // 找出F值最小的点
    var tempStart = openList.minPoint();
    openList.removeAt(0);
    closeList.add(tempStart);
    // 找出它相邻的点
    var aroundPoints = sAroundPoints(tempStart);
    // 遍历所有相邻的点
    aroundPoints.forEach(function(item, index) {
      // 是否已经在开启队列中
      if (openList.exists(item)) {
        //计算G值, 如果比原来的大, 就什么都不做, 否则设置它的父节点为当前点,并更新G和F
        openList.foundPoint(tempStart, end, item);
      } else {
        //如果它们不在开始列表里, 就加入, 并设置父节点,并计算GHF
        openList.notFoundPoint(tempStart, end, item);
      }
    });
    // 是否抵达终点
    openList.get(end);
  }
  // 找回路径
  foundPathRoad(end);
};
  • 如何找回路径

通过终点对象的parents属性值，逐层递归找到上级节点，将每个父节点存入数组。

1
2
3
4
5
6
7
var foundPathRoad = function(obj) {
  if ('parents' in obj) {
    roadArr.unshift(obj);
    arguments.callee(obj.parents);
  }
  return roadArr;
};