Java中BFS算法实现游戏地图范围寻敌异常问题求助

核心问题1：遗漏邻接Unit #

你的代码中使用欧几里得距离计算六边形Tile间的距离，但六边形网格的斜向相邻Tile欧几里得距离约为1.414，当attackRange=1时会被判定为超出范围，导致遗漏这些Tile上的Unit。

修复：替换为六边形网格专属距离公式 #

根据你使用的六边形偏移坐标规则（假设是偶行偏移，即偶数行的列偏移半个单位），修改HexTile.distanceFromTarget方法：

public int distanceFromTarget(HexTile target) {
    int dx = this.getRow() - target.getRow();
    int dy = this.getCol() - target.getCol();
    
    // 根据网格偏移规则调整列差，若为奇行偏移请反向调整
    if ((this.getRow() % 2) == 0) {
        dy -= dx / 2;
    } else {
        dy += (dx + 1) / 2;
    }
    
    // 六边形网格标准距离公式
    return (Math.abs(dx) + Math.abs(dx + dy) + Math.abs(dy)) / 2;
}

如果你的网格是轴向坐标，可改用Math.max(Math.abs(dx), Math.max(Math.abs(dy), Math.abs(-dx-dy)))计算距离。

核心问题2：程序崩溃与其他隐患 #

2.1 列表未清空导致数据累积 #

unitsWithinRange是成员变量，每次调用findUnitsWithinRange前未清空，多次调用会累积旧数据，甚至加入null元素引发空指针异常。

2.2 未判断Unit是否为null #

aux.getUnitOnTile()可能返回null，直接加入列表会导致后续使用时出现空指针异常。

2.3 BFS效率低下 #

使用ArrayList.contains()判断是否访问过Tile，时间复杂度为O(n)，地图较大时性能极差。

修复：优化BFS逻辑与边界检查 #

class Unit {
    private ArrayList<Unit> unitsWithinRange = new ArrayList<>();

    private void findUnitsWithinRange(HexTile currentTile, int attackRange) {
        // 每次调用前清空列表
        unitsWithinRange.clear();
        // 边界检查：避免传入无效参数
        if (currentTile == null || attackRange < 0) {
            return;
        }

        Queue<HexTile> queue = new LinkedList<>();
        // 用Map同时记录Tile的访问状态与距离，兼顾效率与功能
        Map<HexTile, Integer> tileDistance = new HashMap<>();

        queue.add(currentTile);
        tileDistance.put(currentTile, 0);

        while (!queue.isEmpty()) {
            HexTile current = queue.poll();
            int distance = tileDistance.get(current);

            // BFS特性保证后续Tile距离只会更大，超出范围直接跳过
            if (distance > attackRange) {
                continue;
            }

            // 仅添加非null的Unit
            Unit unitOnTile = current.getUnitOnTile();
            if (unitOnTile != null) {
                unitsWithinRange.add(unitOnTile);
            }

            // 遍历邻居，仅处理未访问且距离未超范围的Tile
            for (HexTile neighbor : current.getNeighbours()) {
                if (neighbor != null && !tileDistance.containsKey(neighbor)) {
                    int newDistance = distance + 1;
                    if (newDistance <= attackRange) {
                        tileDistance.put(neighbor, newDistance);
                        queue.add(neighbor);
                    }
                }
            }
        }
    }
}

额外优化：给HexTile重写equals()和hashCode()（基于row和col），确保HashMap能正确识别相同Tile：

class HexTile {
    static final int MAX_NEIGHBOURS = 6;
    private HexTile[] neighbours;
    private int row;
    private int col;

    // 构造方法初始化行列
    public HexTile(int row, int col) {
        this.row = row;
        this.col = col;
        this.neighbours = new HexTile[MAX_NEIGHBOURS];
    }

    public HexTile[] getNeighbours() {
        return this.neighbours;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        HexTile hexTile = (HexTile) o;
        return row == hexTile.row && col == hexTile.col;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, col);
    }

    // 修复后的距离方法
    public int distanceFromTarget(HexTile target) {
        int dx = this.row - target.row;
        int dy = this.col - target.col;
        
        if ((this.row % 2) == 0) {
            dy -= dx / 2;
        } else {
            dy += (dx + 1) / 2;
        }
        
        return (Math.abs(dx) + Math.abs(dx + dy) + Math.abs(dy)) / 2;
    }
}

额外注意事项 #

• 确保HexTile的neighbours数组已正确初始化，所有相邻Tile的引用都已赋值（非null位置对应实际相邻Tile）。
• 如果你的六边形网格是奇行偏移，需调整distanceFromTarget中的列差计算逻辑。

内容的提问来源于stack exchange，提问作者AlexandrosS