Java A* 寻路实现

对于 A* 其实就是需要将整体游戏地图网格化(Grids), 很多人都戏称这种方式为 “刷格子”

网格化之后地图寻路操作其实就像是五子棋连线即可, 其中棋盘上不可获取就是障碍物列表和网格最大值.

一般寻路系统只需要做二维处理即可

对于网格化默认都是以地图左下最初地方设置为 (0,0) 起始点, 后续需要确定整个地图的最大定点值, 这部分代码如下:

import java.util.*;

/**
 * A* 寻路算法实现
 */
public class AStarPathFinder {


    /**
     * 平面
     */
    protected final Vec2 maxAxis;

    /**
     * 障碍物列表
     */
    protected final List<Vec2> obstacles;

    /**
     * 构造方法
     */
    public AStarPathFinder(final Vec2 maxAxis, final List<Vec2> obstacles) {
        this.maxAxis = maxAxis;
        // 声明内部不修改内部列表的 list
        // 有的设计会将障碍物坐标系列表拷贝放到类里面, 但是考虑到障碍物坐标系列表其实是很庞大且已经保证不会变动, 不建议直接拷贝使用
        this.obstacles = Collections.unmodifiableList(obstacles);
    }

    /**
     * 坐标数据对象, 代表 {x,y} 二维坐标
     */
    public record Vec2(float x, float y) {

        /**
         * 需要对坐标对象做比较处理
         */
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;

            // 浮点坐标缩小误差范围, 容错 1e-6 避免精度问题
            Vec2 vec = (Vec2) obj;
            return Math.abs(vec.x - x) < 1e-6 && Math.abs(vec.y - y) < 1e-6;
        }

        @Override
        public int hashCode() {
            return Objects.hash(Math.round(x), Math.round(y));
        }

        @Override
        public String toString() {
            return String.format("Vector(%.1f, %.1f)", x, y);
        }
    }


    /**
     * A* 的节点封装类型
     */
    public static class Node {

        /**
         * 节点当前坐标
         */
        Vec2 position;

        /**
         * 父节点, 用于回溯上一级路径
         */
        Node parent;

        /**
         * 从起点到当前节点的实际代价
         */
        float g;

        /**
         * 到终点的预估代价
         */
        float h;

        /**
         * f = g + h
         */
        float f;

        /**
         * 构造方法
         */
        public Node(Vec2 position, Node parent, float g, float h) {
            this.position = position;
            this.parent = parent;
            this.g = g;
            this.h = h;
            this.f = g + h;
        }
    }


    /**
     * 检索路径 grid 块
     *
     * @param start 出发点
     * @param end   到达点
     * @return 路径列表
     */
    public List<Vec2> findPath(Vec2 start, Vec2 end) {
        // 边界检查: 如果起点/终点超出地图范围直接返回空
        if (isBounds(start) || isBounds(end)) return Collections.emptyList();

        // 边界检查: 如果起点/终点是障碍物直接返回空
        if (isObstacle(start) || isObstacle(end)) return Collections.emptyList();

        // 起点=终点: 只需要返回起始点
        if (start.equals(end)) return Collections.singletonList(start);

        // 开放列表: 待探索的节点(按 f 值升序排序)
        PriorityQueue<Node> openQueue = new PriorityQueue<>((l, r) -> Float.compare(l.f, r.f));
        Map<Vec2, Node> openMap = new HashMap<>(); // 开放列表缓存(用于快速查找来替代遍历)

        // 关闭列表: 已经探索过的节点
        Set<Vec2> closed = new HashSet<>();

        // 初始化开放节点
        Node startNode = new Node(start, null, 0, heuristic(start, end));
        openQueue.add(startNode);
        openMap.put(start, startNode);


        // 定义8个方向的移动(上下左右 + 四个对角线)
        // 如果游戏相对简单只有上下左右就剔除对应不需要的对角线参数
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        // 开始遍历节点
        while (!openQueue.isEmpty()) {
            // 取出 f 值最小的节点
            Node currentNode = openQueue.poll();
            Vec2 currentPos = currentNode.position;
            openMap.remove(currentPos); // 同步移除缓存

            // 如果当前节点是终点，回溯路径并返回
            if (currentPos.equals(end)) return reconstructPath(currentNode);

            // 将当前节点加入到关闭节点
            closed.add(currentPos);

            // 遍历所有的相邻节点
            for (int[] dir : directions) {

                // 检索 {-1,0} 左边 grid 和 {1,0} 上边相邻区块
                // 其实就是将区块往左上角偏移一下
                float newX = currentPos.x + dir[0];
                float newY = currentPos.y + dir[1];
                Vec2 neighborPos = new Vec2(newX, newY);

                // 这里拆分出来单个解析判断条件: 超出地图边界、是障碍物、已在关闭列表中

                // 判断偏移的坐标超过地图界限: 超过地图边界
                if (isBounds(neighborPos)) continue;

                // 判断偏移的坐标是障碍物: 常见的 "撞墙"
                if (isObstacle(neighborPos)) continue;

                // 判断是否为确认过的不可用节点
                if (closed.contains(neighborPos)) continue;

                // 对角线移动检查: 避免斜穿障碍物
                // 如(0,0)到(1,1) 需要检查 (0,1) 和 (1,0) 是否都是障碍物
                if (dir[0] != 0 && dir[1] != 0) {
                    Vec2 horizontal = new Vec2(currentPos.x + dir[0], currentPos.y);
                    Vec2 vertical = new Vec2(currentPos.x, currentPos.y + dir[1]);

                    // 只要横向/纵向有一个是障碍物，就禁止对角线移动
                    if (isObstacle(horizontal) || isObstacle(vertical)) {
                        continue;
                    }
                }


                // 计算移动代价: 直走代价为1,对角线代价为√2(约1.414)
                // 如果你游戏设计只有四向移动就不需要计算对角线
                float cost = (dir[0] != 0 && dir[1] != 0) ? 1.414f : 1.0f;
                float tentative = currentNode.g + cost; // 计算移动代价


                // 检查邻接节点是否在开放列表中
                Node active = openMap.get(neighborPos);

                // 如果未加入的开放节点加入列表
                if (Objects.isNull(active)) {
                    float h = heuristic(neighborPos, end);
                    Node newNode = new Node(neighborPos, currentNode, tentative, h);
                    openQueue.add(newNode);
                    openMap.put(neighborPos, newNode); // 更新缓存
                } else if (tentative < active.g) {
                    // 确认是否为代价更低的的路径, 如果代价更低直接替换
                    active.parent = currentNode;
                    active.g = tentative;
                    active.f = active.g + active.h;

                    // 重新对队列排序(删除原有的节点, 追加新节点)
                    openQueue.remove(active);
                    openQueue.add(active);
                }
            }
        }

        // 开放列表为空, 未找到路径
        return Collections.emptyList();
    }

    /**
     * 检测坐标是否处于地图界面
     */
    public boolean isBounds(final Vec2 pos) {
        return pos.x < 0 ||
                pos.x > maxAxis.x ||
                pos.y < 0 ||
                pos.y > maxAxis.y;
    }

    /**
     * 检查坐标是否是障碍物
     */
    public boolean isObstacle(final Vec2 pos) {
        return obstacles.contains(pos);
    }

    /**
     * 计算启发函数(曼哈顿距离,适合只允许上下左右移动;欧几里得距离适合对角线移动)
     * 这里使用欧几里得距离,更适合8方向移动
     */
    public float heuristic(final Vec2 cur, final Vec2 end) {
        float dx = end.x() - cur.x();
        float dy = end.y() - cur.y();
        // 欧几里得距离（直线距离）
        return (float) Math.sqrt(dx * dx + dy * dy);
        // 如果是4方向移动，推荐使用曼哈顿距离: return Math.abs(dx) + Math.abs(dy)
    }


    /**
     * 回溯路径(从终点节点反向找到起点, 再反转列表)
     */
    public List<Vec2> reconstructPath(final Node node) {
        List<Vec2> path = new ArrayList<>();
        Node current = node;

        // 从终点回溯到起点
        while (Objects.nonNull(current)) {
            path.add(current.position);
            current = current.parent;
        }

        // 反转列表, 获取到从起点到终点的所有路径
        Collections.reverse(path);
        return path;
    }


    /**
     * 测试运行
     *
     * @param args 参数列表
     */
    public static void main(String[] args) {
        // 假设目前的地图是 20x20 划分的网格
        // 注意: 坐标起始是以 0 开始, 所以需要抵扣 max{y-1,y-1}
        Vec2 map = new Vec2(19, 19);

        // 这里追加障碍物, 障碍物最好采用 {X,Y} 的二维坐标系矩形
        // 这里直接斜线直接就能走过去
        List<Vec2> obstacles = Arrays.asList(
                new Vec2(2, 1),
                new Vec2(4, 2),
                new Vec2(6, 4),
                new Vec2(8, 6),
                new Vec2(12, 8),
                new Vec2(16, 12),
                new Vec2(18, 16)
        );

        // 创建寻路处理器
        AStarPathFinder finder = new AStarPathFinder(map, obstacles);

        // 设置起点与终点
        Vec2 start = new Vec2(0, 0);
        Vec2 end = new Vec2(9, 9);

        //  查找路径
        List<Vec2> paths = finder.findPath(start, end);

        // 确认路径是否存在
        if (paths.isEmpty()) {
            System.err.println("未找到有效路径");
        } else {
            System.out.printf("寻路成功, 共需要移动 %d 个节点: %n", paths.size());
            for (Vec2 pos : paths) {
                System.out.printf(" - (%s,%s)%n", pos.x, pos.y);
            }
        }
    }
}

注意: 上面例子还有最大节点的限制没有加上, 避免地图过大导致遍历大量节点让系统卡顿

这里就是 A* 算法实施步骤, 而对于障碍物之类就需要游戏客户端对地图 “刷格子” 处理:

1. 客户端对地图做网状分块, 可以给单个格子限定 16x16/32x32/64x64(必须要能2整除) 像素等格子

2. 需要设计工具或者按照设计图确认障碍物摆放, 最后导出 JSON 的障碍物(X,Y)列表给客户端/服务端共享

3. 后续就是服务端和客户端共享这份格子表来做寻路判断

服务端最好自己设计或者引用第三方的 Vector2/3 坐标类, 而且最好和客户端的接口保持一致, 后续涉及共享代码可以让客户端编写逻辑

地图规划方面主要看客户端处理, 客户端只需要交付给服务端场景地图ID和障碍物的坐标系列表, 方便在服务端做权威模拟移动.

还有一点: 如果是整数网格(如 16x16 像素/格), 建议改用 int 类型设计网格图从而避免浮点数精度问题节省计算耗费性能问题

在网络游戏当中, 有的游戏点击地址移动会展示 “正在寻路” 就是在等下发路线, 下发完成之后才会执行角色的移动

之前处理过经营类游戏的时候, 大部分格子都是由策划配表处理(策划坐美术旁边像素点级别指挥移动), 这些策划表最后就是客户端/服务端共享

能够出专用的策划工具最好, 毕竟地理分布按照规范来说需要让 “地编” 来设计处理, 为了节约成本只能尽可能单人兼顾多种功能

A* 作为很经典的寻路算法最好理解吃透, 后续无论接触到什么游戏类型都能直接拿来使用, 具体流程如下

• 玩家点击地图 → 客户端:

1. 显示 “正在寻路” UI(避免玩家重复点击上报地址)

2. 像素坐标转网格坐标(GridUtils.pixelToGrid)

3. 校验终点合法性(如是否在地图内, 客户端本地快速过滤无效请求)

4. 向服务端发送寻路请求(Protobuf 序列化：玩家ID + 起点网格 + 终点网格)

• 客户端 → 服务端

1. 权威校验(起点是否和玩家当前AOI位置一致、终点是否是服务端认可的可通行区域)

2. 执行 A* 寻路(带最大节点限制 + 缓存查询)

3. 路径优化(如剔除冗余拐点，减少下发数据量)

4. 下发寻路响应(成功=路径列表; 失败=原因, 如 “路径不可达”)

• 服务端 → 客户端

1. 隐藏 “正在寻路” UI

2. 成功: 执行路径平滑移动(插值计算,避免瞬移)

3. 失败: 显示提示(如“无法到达该位置”)

最后提醒一句: 尽可能采用 int 方式做网格, 事件触发都是基于网格来分布, 避免采用 float 对网格划分, 服务端浮点数来判断计算很浪费

即便是 3D 游戏, 服务端也会将 float 坐标量化为整数网格做碰撞检测和权限校验, 只是客户端表现层保留 float 精度方便平滑处理

如果可以的话, 最好看下商业化的游戏服务端与客户端代码, 商业公司的代码很多都是一线生产处理过的情况; 哪怕编程语言不一样都值得学习参考