JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例

非常感谢你对于本站文章的关注。下面是针对文章“JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例”的完整攻略解析。

1. 介绍

本文主要讲解的是一种常用于解决路径搜索问题的算法—— A*寻路算法。使用该算法可以在搜索空间（如地图、游戏场景等）中找到一条最优路径，可应用于许多领域，如自动驾驶、游戏AI等。

2. 算法流程

该算法通过在搜索空间中创建一个节点集来实现。

• 先将起点加入节点集。
• 从节点集中选取离起点最近的节点，计算其相邻节点的路径距离，如果路径距离加上该节点到起点的距离小于该相邻节点到起点的距离，那么更新该相邻节点到起点的距离，并将该节点加入节点集。
• 重复步骤2，直到到达终点或搜索完所有节点。

3. 代码实现

该算法实现中，需定义地图和节点对象。

//定义地图对象
var map = {
    width: 10,
    height: 10,
    obstacles: [{x:3,y:3},{x:4,y:3},{x:5,y:3},{x:4,y:4}]
};

//定义节点对象
function node(x, y, endX, endY) {
    this.x = x; //节点横坐标
    this.y = y; //节点纵坐标
    this.g = 0; //起点到当前节点的距离
    this.h = Math.abs(endX - x) + Math.abs(endY - y); //当前节点到终点的估算距离
    this.f = this.g + this.h; //节点综合评价函数
    this.parent = null; //当前节点的父节点
}

以上实现是一个简单示例，地图的width和height分别为地图的宽度和高度，obstacles表示地图上的障碍物，使用数组形式存储，每个障碍物包含x和y属性表示该障碍物在地图上的位置信息。节点对象包括x、y、g、h、f和parent属性。其中g表示起点到当前节点的距离，h表示当前节点到终点的估算距离，f表示g和h的综合评价函数，parent表示当前节点的父节点。

在实现中需要定义开始节点和结束节点，调用寻路函数进行搜索。

//开始节点
var start = new node(0, 0, 9, 9);

//结束节点
var end = new node(9, 9, 9, 9);

//寻路函数
function findPath(start, end) {
    var openList = [start]; //节点集合（初始状态只包含起点）
    var closedList = []; //已处理节点集合

    while (openList.length > 0) {
        //找到f值最小的节点
        var node = openList[0];
        for (var i = 1; i < openList.length; i++) {
            if (openList[i].f < node.f) {
                node = openList[i];
            }
        }

        //将该节点从节点集中删除并加入已处理集合
        openList.splice(openList.indexOf(node), 1);
        closedList.push(node);

        //如果该节点为终点
        if (node.x === end.x && node.y === end.y) {
            var path = [];
            while (node.parent) {
                path.push(node);
                node = node.parent;
            }
            return path.reverse();
        }

        //找到该节点相邻的节点，并计算路径距离
        var neighbors = getNeighbors(node, end);
        for (var j = 0; j < neighbors.length; j++) {
            var neighbor = neighbors[j];

            //如果该节点已在已处理集合中则跳过
            if (closedList.indexOf(neighbor) > -1) {
                continue;
            }

            //计算路径距离
            var g = node.g + (neighbor.x === node.x || neighbor.y === node.y ? 10 : 14);

            //如果路径距离加上该节点到终点的距离小于该相邻节点到起点的距离，则更新节点并加入节点集中
            if (g + neighbor.h < neighbor.f) {
                neighbor.g = g;
                neighbor.f = neighbor.g + neighbor.h;
                neighbor.parent = node;
                if (openList.indexOf(neighbor) === -1) {
                    openList.push(neighbor);
                }
            }
        }
    }

    //如果没有找到路径
    return null;
}

//计算当前节点相邻的节点
function getNeighbors(node, end) {
    var neighbors = [];
    var x = node.x,
        y = node.y;

    //左
    if (x > 0 && !(map.obstacles.filter(function(item){return item.x===x-1 && item.y===y}).length>0)){
        neighbors.push(new node(x - 1, y, end.x, end.y));
    }

    //右
    if (x < map.width - 1 && !(map.obstacles.filter(function(item){return item.x===x+1 && item.y===y}).length>0)){
        neighbors.push(new node(x + 1, y, end.x, end.y));
    }

    //上
    if (y > 0 && !(map.obstacles.filter(function(item){return item.x===x && item.y===y-1}).length>0)){
        neighbors.push(new node(x, y - 1, end.x, end.y));
    }

    //下
    if (y < map.height - 1 && !(map.obstacles.filter(function(item){return item.x===x && item.y===y+1}).length>0)){
        neighbors.push(new node(x, y + 1, end.x, end.y));
    }

    //左上
    if (x > 0 && y > 0 && !(map.obstacles.filter(function(item){return item.x===x-1 && item.y===y-1}).length>0)){
        neighbors.push(new node(x - 1, y - 1, end.x, end.y));
    }

    //右上
    if (x < map.width - 1 && y > 0 && !(map.obstacles.filter(function(item){return item.x===x+1 && item.y===y-1}).length>0)){
        neighbors.push(new node(x + 1, y - 1, end.x, end.y));
    }

    //左下
    if (x > 0 && y < map.height - 1 && !(map.obstacles.filter(function(item){return item.x===x-1 && item.y===y+1}).length>0)){
        neighbors.push(new node(x - 1, y + 1, end.x, end.y));
    }

    //右下
    if (x < map.width - 1 && y < map.height - 1 && !(map.obstacles.filter(function(item){return item.x===x+1 && item.y===y+1}).length>0)){
        neighbors.push(new node(x + 1, y + 1, end.x, end.y));
    }

    return neighbors;
}

4. 示例说明

以下是一个示例，以10*10的地图为例，地图中有四个障碍物，起点为左上角，终点为右下角。

0   1   2   3   4   5   6   7   8   9   
1   .   .   .   .   .   .   .   .   .   |   0
2   .   .   .   #   #   #   .   .   .   |   1
3   .   .   .   .   .   .   .   .   .   |   2
4   .   .   .   .   .   .   .   .   .   |   3
5   .   .   .   .   .   .   .   .   .   |   4
6   .   .   .   .   .   .   .   .   .   |   5
7   .   .   .   .   .   .   .   .   .   |   6
8   .   .   .   .   .   .   .   .   .   |   7
9   .   .   .   .   .   .   .   .   .   |   8
                             |  9
      0 1   2   3   4   5   6   7   8   9   

假设障碍物的坐标为对应位置的左上角坐标。

根据以上示例，在调用寻路函数后，实现的输出结果为：

[
    node {x: 9, y: 9, g: 40, h: 0, f: 40, parent: node{x:8,y:8,...}},
    node {x: 8, y: 8, g: 33, h: 2, f: 35, parent: node{x:7,y:7,...}},
    node {x: 7, y: 7, g: 26, h: 4, f: 30, parent: node{x:6,y:6,...}},
    ...
    node {x: 1, y: 1, g: 10, h: 10, f: 20, parent: node{x:0,y:0,...}},
    node {x: 0, y: 0, g: 0, h: 18, f: 18, parent: null}
]

输出结果包含了所有寻找到最短路径的节点。可以从后往前找到起点和终点间所需的节点数，实现路径的绘制。

5. 总结

以上就是本文对 A*寻路算法的完整分析及实现。希望通过阅读本文，读者可以完全了解本算法的实现过程和应用场景。