[CocosCreator]游戏里最好用的寻路算法——Theta*

时间：2024-10-24 18:53:26

 ＃1024程序员节｜征文＃

一.前言

        在游戏开发领域，算法是不可或缺的重要组成部分。无论是基础的数据处理还是复杂的游戏AI，都依赖各种经典算法的应用，如排序算法、路径规划算法等。尤其在大规模多人在线游戏（MMORPG）中，路径寻路算法显得尤为关键。Theta算法作为A算法的改进，因其高效的路径优化能力，广泛应用于游戏中的NPC行为模拟和玩家角色移动优化。本文将深入探讨Theta*算法的原理及其在游戏开发中的应用，带你更好地理解其在实际场景中的价值。

二.广告

        欢迎喜欢或者从事CocosCreator开发的小伙伴请加入我的大家庭CocosCreator游戏开发Q群:26855530

三.什么是Theta*

        Theta*（Theta Star）是A星算法的优化版本，它完全集成了A星算法的所有优点，解决了A中必须沿网格边走的问题，通过允许节点之间的对角线直接相连，从而缩短路径。换句通俗易懂的话就是，他解决了Ａ星算法的各种无意义的弯弯绕绕的路劲，以两点距离最近的直线路劲的启发式寻路算法．这里借助Ｂ站某主的视频，给大伙对比下两种算法的不同：

A*与Lazy Theta*路径规划算法对比

四.实现Theta*

        接下来我就带大家，在CocosCreator里如何实现Theta*寻路．

        １．定义节点类

        首先，我们需要定义节点的基本结构，包括它的坐标、父节点、g值（从起点到该节点的代价）、h值（启发式估计从该节点到终点的代价）和f值（g+h，用来评估路径的总代价）。

class Node {
    public x: number;
    public y: number;
    public parent: Node | null;
    public g: number;
    public h: number;
    public f: number;

    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
        this.parent = null;
        this.g = Infinity;
        this.h = 0;
        this.f = Infinity;
    }
}

        • x 和 y 是节点的坐标。

        • parent 表示节点的父节点，用来跟踪路径。

        • g 是从起点到该节点的路径代价，初始设为无穷大。

        • h 是从该节点到目标节点的启发式估计。

        • f = g + h 用来评估节点的优先级。

        ２．计算启发式函数h值

        Theta*通常使用欧几里得距离（直线距离）作为启发式函数来估计节点到目标的代价。

function heuristic(node: Node, endNode: Node): number {
    const dx = node.x - endNode.x;
    const dy = node.y - endNode.y;
    return Math.sqrt(dx * dx + dy * dy);
}

        启发函数heuristic计算节点与终点之间的直线距离 

        ３．初始化开放列表和封闭列表

        Theta*需要两个列表：

                • openList：存储将要处理的节点。

                • closedList：存储已经处理过的节点。

const openList: Node[] = [];
const closedList: Set<Node> = new Set();

        ４．检查直线可见性

        Theta*的核心在于检查两个节点之间是否有障碍物。如果两个节点之间没有障碍，则可以直接连接而不需要经过中间节点。

function lineOfSight(grid: number[][], node1: Node, node2: Node): boolean {
    const x0 = node1.x;
    const y0 = node1.y;
    const x1 = node2.x;
    const y1 = node2.y;

    const dx = Math.abs(x1 - x0);
    const dy = Math.abs(y1 - y0);
    const sx = (x0 < x1) ? 1 : -1;
    const sy = (y0 < y1) ? 1 : -1;
    let err = dx - dy;

    let x = x0;
    let y = y0;

    while (x !== x1 || y !== y1) {
        if (grid[y][x] === 1) {
            return false; // 1 表示障碍物
        }
        const e2 = 2 * err;
        if (e2 > -dy) {
            err -= dy;
            x += sx;
        }
        if (e2 < dx) {
            err += dx;
            y += sy;
        }
    }
    return true;
}

        lineOfSight函数使用Bresenham算法检查两个节点之间是否有障碍物。 

        ５．主算法流程

        接下来，实现Theta*的主要逻辑。包括从开放列表中选取代价最低的节点、检查直线可见性并更新节点的父节点等操作。

function thetaStar(grid: number[][], startNode: Node, endNode: Node): Node | null {
    startNode.g = 0;
    startNode.f = heuristic(startNode, endNode);
    openList.push(startNode);

    while (openList.length > 0) {
        // 从 openList 中取出 f 值最小的节点
        openList.sort((a, b) => a.f - b.f);
        const currentNode = openList.shift() as Node;

        if (currentNode.x === endNode.x && currentNode.y === endNode.y) {
            return currentNode; // 找到终点，返回路径
        }

        closedList.add(currentNode);

        const neighbors = getNeighbors(grid, currentNode);

        for (const neighbor of neighbors) {
            if (closedList.has(neighbor)) continue;

            if (!openList.includes(neighbor)) {
                openList.push(neighbor);
            }

            let tentativeG = currentNode.g + heuristic(currentNode, neighbor);

            // 检查是否可以直接连接父节点与邻居
            if (currentNode.parent && lineOfSight(grid, currentNode.parent, neighbor)) {
                const parentG = currentNode.parent.g + heuristic(currentNode.parent, neighbor);
                if (parentG < tentativeG) {
                    neighbor.parent = currentNode.parent;
                    tentativeG = parentG;
                }
            } else {
                neighbor.parent = currentNode;
            }

            if (tentativeG < neighbor.g) {
                neighbor.g = tentativeG;
                neighbor.f = neighbor.g + heuristic(neighbor, endNode);
            }
        }
    }

    return null; // 找不到路径
}

代码解释：

1. 初始化起点 startNode 的 g 和 f 值，并将其加入 openList。

2. 循环从 openList 中取出 f 值最小的节点进行处理。

3. 对每个邻居节点，首先检查是否已经在 closedList 中，如果在就跳过。

4. 如果邻居节点可以通过父节点的直线相连，使用 lineOfSight 检查，并更新父节点和代价。

5. 如果代价比之前记录的小，更新该节点的 g 和 f 值。

6. 当终点节点被处理时，算法结束。

        ６．获取邻居节点

function getNeighbors(grid: number[][], node: Node): Node[] {
    const neighbors: Node[] = [];
    const directions = [
        [0, 1], [1, 0], [0, -1], [-1, 0], // 上下左右
        [1, 1], [1, -1], [-1, 1], [-1, -1] // 四个对角
    ];

    for (const [dx, dy] of directions) {
        const x = node.x + dx;
        const y = node.y + dy;
        if (x >= 0 && x < grid[0].length && y >= 0 && y < grid.length && grid[y][x] === 0) {
            neighbors.push(new Node(x, y));
        }
    }
    return neighbors;
}

        getNeighbors函数返回相邻的非障碍物节点，包括上下左右和对角方向。 

        ７．重建路径

        当找到终点时，可以通过递归获取路径：

function reconstructPath(endNode: Node): Node[] {
    const path: Node[] = [];
    let currentNode: Node | null = endNode;
    while (currentNode) {
        path.push(currentNode);
        currentNode = currentNode.parent;
    }
    return path.reverse(); // 从起点到终点的路径
}

        通过这几步，Theta*算法能够有效缩短路径，减少不必要的转弯。 

五.总结

         Theta*实现起来并不难，只要理解Ａ*的话我相信各位小伙伴都能完全掌握的，我们下期再见吧～

相关文章