每日算法 — 使用java实现星际争霸：A*分流与Flocking群体移动算法

引言

《星际争霸》作为经典的实时战略游戏，其AI核心在于大量作战单位的智能移动。当数百个单位同时收到移动指令时，简单的直线路径会导致严重的拥堵和碰撞。本文用Java实现A*分流路径规划与Flocking群体移动算法，让单位既能绕开障碍高效寻路，又能在移动中保持自然编队。

核心算法设计

1. A*分流路径规划

传统A*算法为每个单位独立寻路，在狭窄路口会造成拥堵。分流策略的核心思想是：将地图划分为多个车道，不同单位根据起点终点的相对位置被分配到不同车道，实现并行通过。

2. Flocking群体行为

Craig Reynolds提出的Flocking模型包含三条基本规则：
– 分离（Separation）：避免与邻近单位碰撞
– 对齐（Alignment）：朝向邻近单位的平均方向
– 聚合（Cohesion）：向邻近单位的平均位置靠拢

结合A*的全局路径与Flocking的局部避障，单位既不会撞墙，也不会相互重叠。

完整Java实现

import java.util.*;

/**
 * 星际争霸风格的多单位智能移动系统
 * 结合A*分流路径规划与Flocking群体行为
 */
public class StarCraftMovement {

    static class Vec2 {
        double x, y;
        Vec2(double x, double y) { this.x = x; this.y = y; }
        Vec2 add(Vec2 v) { return new Vec2(x + v.x, y + v.y); }
        Vec2 sub(Vec2 v) { return new Vec2(x - v.x, y - v.y); }
        Vec2 mul(double s) { return new Vec2(x * s, y * s); }
        double len() { return Math.sqrt(x * x + y * y); }
        Vec2 normalize() {
            double l = len();
            return l < 1e-6 ? new Vec2(0, 0) : new Vec2(x / l, y / l);
        }
        double dist(Vec2 v) { return sub(v).len(); }
    }

    // A*节点
    static class Node implements Comparable<Node> {
        int x, y;
        double g, h;
        Node parent;
        Node(int x, int y) { this.x = x; this.y = y; }
        double f() { return g + h; }
        @Override public int compareTo(Node o) { return Double.compare(f(), o.f()); }
        @Override public boolean equals(Object o) {
            if (!(o instanceof Node)) return false;
            Node n = (Node) o;
            return x == n.x && y == n.y;
        }
        @Override public int hashCode() { return x * 131 + y; }
    }

    // 地图：true表示可通过
    private boolean[][] passable;
    private int width, height;

    public StarCraftMovement(boolean[][] passable) {
        this.passable = passable;
        this.height = passable.length;
        this.width = passable[0].length;
    }

    /**
     * A*寻路算法，返回路径点列表
     */
    public List<Vec2> aStar(Vec2 start, Vec2 goal) {
        int sx = (int) start.x, sy = (int) start.y;
        int gx = (int) goal.x, gy = (int) goal.y;

        PriorityQueue<Node> open = new PriorityQueue<>();
        Set<Node> closed = new HashSet<>();
        Node startNode = new Node(sx, sy);
        startNode.g = 0;
        startNode.h = heuristic(sx, sy, gx, gy);
        open.add(startNode);

        while (!open.isEmpty()) {
            Node cur = open.poll();
            if (cur.x == gx && cur.y == gy) {
                return reconstructPath(cur);
            }
            closed.add(cur);

            for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}) {
                int nx = cur.x + d[0], ny = cur.y + d[1];
                if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
                if (!passable[ny][nx]) continue;

                Node neighbor = new Node(nx, ny);
                if (closed.contains(neighbor)) continue;

                double tentativeG = cur.g + ((d[0] != 0 && d[1] != 0) ? 1.414 : 1.0);

                boolean inOpen = open.stream().anyMatch(n -> n.equals(neighbor));
                if (!inOpen || tentativeG < neighbor.g) {
                    neighbor.g = tentativeG;
                    neighbor.h = heuristic(nx, ny, gx, gy);
                    neighbor.parent = cur;
                    if (!inOpen) open.add(neighbor);
                }
            }
        }
        return Collections.emptyList(); // 无路径
    }

    private double heuristic(int x1, int y1, int x2, int y2) {
        // 欧几里得距离
        return Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    }

    private List<Vec2> reconstructPath(Node end) {
        List<Vec2> path = new ArrayList<>();
        Node cur = end;
        while (cur != null) {
            path.add(new Vec2(cur.x, cur.y));
            cur = cur.parent;
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 分流策略：为每个单位计算偏移后的目标点
     * 根据单位在群体中的相对位置，分配不同的车道
     */
    public Vec2[] computeFlowTargets(Vec2[] units, Vec2 groupGoal) {
        Vec2 center = computeCenter(units);
        Vec2 toGoal = groupGoal.sub(center).normalize();
        Vec2 perpendicular = new Vec2(-toGoal.y, toGoal.x); // 垂直方向

        Vec2[] targets = new Vec2[units.length];
        for (int i = 0; i < units.length; i++) {
            Vec2 offset = units[i].sub(center);
            // 将偏移投影到垂直方向，实现车道分离
            double laneOffset = offset.x * perpendicular.x + offset.y * perpendicular.y;
            // 目标点 = 群体目标 + 个体在编队中的相对偏移
            targets[i] = groupGoal.add(new Vec2(
                perpendicular.x * laneOffset * 0.5,
                perpendicular.y * laneOffset * 0.5
            ));
        }
        return targets;
    }

    private Vec2 computeCenter(Vec2[] units) {
        double cx = 0, cy = 0;
        for (Vec2 u : units) { cx += u.x; cy += u.y; }
        return new Vec2(cx / units.length, cy / units.length);
    }

    // 作战单位
    static class Unit {
        Vec2 pos, vel;
        double maxSpeed = 2.0;
        double maxForce = 0.3;
        List<Vec2> path;
        int pathIndex = 0;

        Unit(double x, double y) {
            this.pos = new Vec2(x, y);
            this.vel = new Vec2(0, 0);
        }
    }

    /**
     * Flocking群体行为计算
     * 返回该单位在当前帧应受到的合力
     */
    public Vec2 flockingForce(Unit unit, List<Unit> allUnits, Vec2 target) {
        Vec2 sep = separation(unit, allUnits);
        Vec2 ali = alignment(unit, allUnits);
        Vec2 coh = cohesion(unit, allUnits);
        Vec2 seek = seek(unit, target);

        // 加权组合
        sep = sep.mul(2.0);   // 分离权重最高，避免碰撞
        ali = ali.mul(1.0);
        coh = coh.mul(1.0);
        seek = seek.mul(1.5); // 寻路权重次高

        return sep.add(ali).add(coh).add(seek);
    }

    // 分离：远离过近的单位
    private Vec2 separation(Unit unit, List<Unit> allUnits) {
        Vec2 steer = new Vec2(0, 0);
        int count = 0;
        double desiredSeparation = 3.0;
        for (Unit other : allUnits) {
            if (other == unit) continue;
            double d = unit.pos.dist(other.pos);
            if (d > 0 && d < desiredSeparation) {
                Vec2 diff = unit.pos.sub(other.pos);
                diff = diff.normalize();
                diff = diff.mul(1.0 / d); // 距离越近，排斥力越大
                steer = steer.add(diff);
                count++;
            }
        }
        if (count > 0) {
            steer = steer.mul(1.0 / count);
            steer = steer.normalize().mul(unit.maxSpeed);
            steer = steer.sub(unit.vel);
            if (steer.len() > unit.maxForce) steer = steer.normalize().mul(unit.maxForce);
        }
        return steer;
    }

    // 对齐：朝向邻居的平均速度方向
    private Vec2 alignment(Unit unit, List<Unit> allUnits) {
        Vec2 sum = new Vec2(0, 0);
        int count = 0;
        double neighborDist = 8.0;
        for (Unit other : allUnits) {
            if (other == unit) continue;
            if (unit.pos.dist(other.pos) < neighborDist) {
                sum = sum.add(other.vel);
                count++;
            }
        }
        if (count > 0) {
            sum = sum.mul(1.0 / count);
            sum = sum.normalize().mul(unit.maxSpeed);
            Vec2 steer = sum.sub(unit.vel);
            if (steer.len() > unit.maxForce) steer = steer.normalize().mul(unit.maxForce);
            return steer;
        }
        return new Vec2(0, 0);
    }

    // 聚合：向邻居的平均位置靠拢
    private Vec2 cohesion(Unit unit, List<Unit> allUnits) {
        Vec2 sum = new Vec2(0, 0);
        int count = 0;
        double neighborDist = 8.0;
        for (Unit other : allUnits) {
            if (other == unit) continue;
            if (unit.pos.dist(other.pos) < neighborDist) {
                sum = sum.add(other.pos);
                count++;
            }
        }
        if (count > 0) {
            sum = sum.mul(1.0 / count);
            return seek(unit, sum);
        }
        return new Vec2(0, 0);
    }

    // 朝向目标点移动
    private Vec2 seek(Unit unit, Vec2 target) {
        Vec2 desired = target.sub(unit.pos);
        desired = desired.normalize().mul(unit.maxSpeed);
        Vec2 steer = desired.sub(unit.vel);
        if (steer.len() > unit.maxForce) steer = steer.normalize().mul(unit.maxForce);
        return steer;
    }

    /**
     * 模拟一帧更新
     */
    public void updateUnits(List<Unit> units, Vec2 groupGoal) {
        // 为每个单位计算独立目标（分流）
        Vec2[] positions = units.stream().map(u -> u.pos).toArray(Vec2[]::new);
        Vec2[] targets = computeFlowTargets(positions, groupGoal);

        for (int i = 0; i < units.size(); i++) {
            Unit u = units.get(i);

            // 若已到达当前路径点，推进到下一个
            if (u.path != null && u.pathIndex < u.path.size()) {
                Vec2 waypoint = u.path.get(u.pathIndex);
                if (u.pos.dist(waypoint) < 1.0) u.pathIndex++;
                if (u.pathIndex < u.path.size()) {
                    targets[i] = u.path.get(u.pathIndex);
                }
            }

            // 计算Flocking合力
            Vec2 force = flockingForce(u, units, targets[i]);

            // 更新速度与位置
            u.vel = u.vel.add(force);
            if (u.vel.len() > u.maxSpeed) u.vel = u.vel.normalize().mul(u.maxSpeed);
            u.pos = u.pos.add(u.vel);
        }
    }

    // 演示主方法
    public static void main(String[] args) {
        // 创建地图
        boolean[][] map = new boolean[60][60];
        for (int y = 0; y < 60; y++) {
            for (int x = 0; x < 60; x++) {
                map[y][x] = true;
                // 设置障碍物
                if (x > 20 && x < 25 && y > 10 && y < 40) map[y][x] = false;
                if (x > 35 && x < 40 && y > 20 && y < 50) map[y][x] = false;
            }
        }

        StarCraftMovement system = new StarCraftMovement(map);

        // 创建20个单位
        List<Unit> units = new ArrayList<>();
        Random rand = new Random(42);
        for (int i = 0; i < 20; i++) {
            units.add(new Unit(5 + rand.nextDouble() * 5, 5 + rand.nextDouble() * 5));
        }

        Vec2 goal = new Vec2(55, 55);

        // 为每个单位规划A*路径
        for (Unit u : units) {
            u.path = system.aStar(u.pos, goal);
        }

        // 模拟100帧
        for (int frame = 0; frame < 100; frame++) {
            system.updateUnits(units, goal);
            if (frame % 20 == 0) {
                double avgDist = 0;
                for (Unit u : units) avgDist += u.pos.dist(goal);
                System.out.printf("Frame %d: avg dist to goal = %.2f%n", frame, avgDist / units.size());
            }
        }
    }
}

算法复杂度分析

其中N为单位数量。Flocking的O(N²)可通过均匀网格（Uniform Grid）或KD树优化至O(N)。

扩展思考

1. 流场（Flow Field）寻路：为终点预计算整个地图的方向场，单位只需查表即可获得移动方向，适合超大规模单位群。
2. RVO/ORCA避障：在Flocking基础上引入速度障碍概念，保证单位间绝对无碰撞。
3. 阵型保持：引入编队模板（如矩形、楔形），单位按模板位置移动而非完全自由聚集。