关键词

js+ajax实现的A*游戏路径算法整理

关于“js+ajax实现的A*游戏路径算法整理”的完整攻略,以下是详细介绍(注意,为了方便阅读,带有代码块的内容使用了代码语法高亮):

什么是A*算法?

A*算法是一种基于图形、搜索和启发式运算的寻路算法,通常用于从起点到目标点的最优路径搜索。

A*算法的要点

A*算法将费用(距离、代价)与启发式函数两者结合,来评估当前节点到目标点路径的可能代价大小。其中启发式函数具有预测未来路径代价的功能。

  • 当问题没有特殊限制时,最好采用A算法进行搜索,而像树状图,网格状图等结构问题,A算法可以简单快速地处理。
  • 一般情况下,用A*算法所得到的解决答案是最优解。但有时会出现因方向不同而产生的误差,故也不一定保证绝对最优解。

A*算法伪代码

1.置入起始点。
2.置起始点的f=0,算法对已处理的部分为0,未处理部分为无限制。
3.若终止则结束。
4.选取“未处理”状态中f值最小的点做为当前节点。
5.将当前节点从“未处理”中删除,放入“已处理”中。
6.扩展当前节点。
7.若候选节点中已存在于已处理表,或未处理表f值比当前节点要小,则删除该节点。
8.将本次扩展得到的所有节点按f值排序后,加入未处理节点。

实现A*算法的示例

示例#1:A*算法在地图寻路中的应用

下面是一段基于A*算法的JavaScript代码,实现了地图寻路的功能,具体实现过程详见注释:

// 定义地图类
class Map {
    constructor() {
        this.map = mapData; // 初始化地图数据
        this.start = null; // 起点
        this.end = null; // 终点
    }

    // 计算当前点到终点的曼哈顿距离
    calcManhattan(point) {
        const dx = Math.abs(point.x - this.end.x);
        const dy = Math.abs(point.y - this.end.y);
        return dx + dy;
    }

    // 查找当前点的八个相邻节点
    findNeighbor(point) {
        const w = this.map[0].length;
        const h = this.map.length;
        const neighbor = [];

        for (let i = point.x - 1; i <= point.x + 1; i++) {
            for (let j = point.y - 1; j <= point.y + 1; j++) {
                if (i >= 0 && i < h && j >= 0 && j < w && (i != point.x || j != point.y) && this.map[i][j] != 1) {
                    neighbor.push({x: i, y: j});
                }
            }
        }

        return neighbor;
    }

    //寻路
    findPath() {
        let openList = [];
        let closedList = [];

        openList.push(this.start); // 起点放入openList

        while (openList.length) { // 当openList不为空时
            let minIndex = 0;
            // 找到f(n)=g(n)+h(n)最小的节点作为当前节点
            for (let i = 0; i < openList.length; i++) {
                if (openList[i].f < openList[minIndex].f) {
                    minIndex = i;
                }
            }

            const currentNode = openList[minIndex];  // 当前节点
            // 当前节点为终点时
            if (currentNode.x === this.end.x && currentNode.y === this.end.y) {
                let path = [];
                let node = currentNode;
                while (node) {
                    path.push(node);
                    node = node.parent;
                }
                return path.reverse();
            }

            // 将当前点从`openList`转移到`closedList`
            openList.splice(minIndex, 1);
            closedList.push(currentNode);

            // 扩展相邻节点
            let neighbors = this.findNeighbor(currentNode);
            for (let i = 0; i < neighbors.length; i++) {
                const neighbor = neighbors[i];

                // 如果邻居节点已被访问过或被加入到开启列表中,则继续下一个节点的遍历
                if (closedList.some(v => v.x === neighbor.x && v.y === neighbor.y)
                    || openList.some(v => v.x === neighbor.x && v.y === neighbor.y)) {
                    continue;
                }

                let g = currentNode.g + 1;  // 到达邻居节点的实际代价
                // 确认邻居节点代价是否最优
                let isInOpenList = openList.some(v => v.x === neighbor.x && v.y === neighbor.y);
                let isInClosedList = closedList.some(v => v.x === neighbor.x && v.y === neighbor.y);
                let h = this.calcManhattan(neighbor);  // 当前节点到终点的曼哈顿距离
                let f = g + h; // 总代价

                if (!isInOpenList && !isInClosedList) {
                    openList.push({
                        x: neighbor.x,
                        y: neighbor.y,
                        g,
                        f,
                        parent: currentNode
                    });
                } else if (isInOpenList && g < neighbor.g) {
                    const index = openList.findIndex(v => v.x === neighbor.x && v.y === neighbor.y);
                    openList[index].g = g;
                    openList[index].f = f;
                    openList[index].parent = currentNode;
                } else if (isInClosedList && g < neighbor.g) {
                    const index = closedList.findIndex(v => v.x === neighbor.x && v.y === neighbor.y);
                    closedList[index].g = g;
                    closedList[index].f = f;
                    closedList[index].parent = currentNode;
                    openList.push(closedList[index]);
                    closedList.splice(index, 1);
                }
            }
        }

        return null;
    }
}

// 示例#1的应用
const mapData = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
];
const map = new Map();
map.start = { x: 0, y: 0 }; // 起点
map.end = { x: 3, y: 4 }; // 终点
console.log(map.findPath());

示例#2:A*算法的通用实现

下面演示如何用A*算法实现通用的寻路:

class PathFinding {
    constructor() {
        // 地图大小
        this._size = {
            x: 0,
            y: 0
        };
        // 障碍物数组
        this._barriers = [];
    }

    // 初始化地图和障碍物数组
    init(size, barriers) {
        this._size = size;
        this._barriers = barriers;
    }

    //判断是否是障碍物
    isBarrier(x, y) {
        let isBarrier = false;
        for (let i = 0; i < this._barriers.length; i++) {
            if (this._barriers[i].x === x && this._barriers[i].y === y) {
                isBarrier = true;
                break;
            }
        }
        return isBarrier;
    }

    // 计算曼哈顿距离
    calcManhattan(from, to) {
        return Math.abs(to.x - from.x) + Math.abs(to.y - from.y);
    }

    // 查找路径
    findPath(src, dest) {
        let openList = [];
        let closedList = [];
        let startNode = {
            x: src.x,
            y: src.y,
            g: 0, // 实际代价
            h: this.calcManhattan(src, dest), // 估测代价
            f: this.calcManhattan(src, dest), // 总代价
            parent: null
        };
        openList.push(startNode);

        while (openList.length > 0) { // 当openList不为空时
            // 从openList中取出f(n)值最小的作为当前节点
            let currentIndex = 0;
            for (let i = 1; i < openList.length; i++) {
                if (openList[i].f < openList[currentIndex].f) {
                    currentIndex = i;
                }
            }
            let currentNode = openList[currentIndex];

            // 如果找到目标,则返回路径
            if (currentNode.x === dest.x && currentNode.y === dest.y) {
                let path = [];
                let node = currentNode;
                while (node) {
                    path.push(node);
                    node = node.parent;
                }
                return path.reverse();
            }

            // 从openList删除当前节点,加入到closedList
            openList.splice(currentIndex, 1);
            closedList.push(currentNode);

            // 扩展节点
            for (let i = currentNode.x - 1; i <= currentNode.x + 1; i++) {
                for (let j = currentNode.y - 1; j <= currentNode.y + 1; j++) {
                    if (i >= 0 && i < this._size.x && j >= 0 && j < this._size.y 
                        && (i != currentNode.x || j != currentNode.y) && !this.isBarrier(i, j)) {
                        let g = currentNode.g + 1; // 实际代价
                        let h = this.calcManhattan({ x: i, y: j }, dest); // 估测代价
                        let f = g + h; // 总代价
                        let isExistInClosedList = false;
                        for (let k = 0; k < closedList.length; k++) {
                            if (closedList[k].x === i && closedList[k].y === j) {
                                isExistInClosedList = true;
                                break;
                            }
                        }

                        let isExistInOpenList = false;
                        for (let k = 0; k < openList.length; k++) {
                            if (openList[k].x === i && openList[k].y === j) {
                                isExistInOpenList = true;
                                break;
                            }
                        }

                        if (!isExistInClosedList && !isExistInOpenList) {
                            openList.push({
                                x: i,
                                y: j,
                                g,
                                h,
                                f,
                                parent: currentNode
                            })
                        } else if (isExistInOpenList && g < openList[currentIndex].g) {
                            let index = openList.findIndex((value) => value.x === i && value.y === j);
                            openList[index].g = g;
                            openList[index].h = h;
                            openList[index].f = f;
                            openList[index].parent = currentNode;
                        }
                    }
                }
            }
        }
    }
};

// 示例#2的应用
// 定义地图大小和障碍物数组
let size = {x: 6, y: 3};
let barriers = [
    {x: 1, y: 0},
    {x: 1, y: 1},
    {x: 3, y: 0},
    {x: 3, y: 1},
    {x: 4, y: 1},
    {x: 5, y: 1},
];
// 初始化并进行寻路
const pf = new PathFinding();
pf.init(size, barriers);
console.log(pf.findPath({x: 0, y: 0}, {x: 5, y: 2}));

以上是关于js+ajax实现的A*游戏路径算法整理的详细攻略,希望能够帮到你!

本文链接:http://task.lmcjl.com/news/11837.html

展开阅读全文