Java战舰游戏开发：如何生成不重复的随机坐标对

核心思路 #

解决战舰重叠问题的核心是维护已占用坐标集合，每次生成新战舰时先校验是否与已占用区域冲突，冲突则重新生成；或预计算所有合法放置位置，直接随机选取，减少无效尝试。

具体实现步骤 #

1. 完善Cell类的坐标识别逻辑 #

HashSet需要正确识别相同坐标的Cell，因此必须重写equals()和hashCode()方法：

import java.util.Objects;

public class Cell implements Comparable<Cell> {
    private final int x;
    private final int y;

    public int getX() { return x; }
    public int getY() { return y; }

    Cell(int xc, int yc) {
        x = xc;
        y = yc;
    }

    public Cell continueWithDirection(Direction d) {
        switch (d) {
            case ROW -> { return new Cell(x + 1, y); }
            case COLUMN -> { return new Cell(x, y + 1); }
        }
        return new Cell(x, y);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Cell cell = (Cell) o;
        return x == cell.x && y == cell.y;
    }

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

    @Override
    public int compareTo(Cell other) {
        if (this.y != other.y) {
            return Integer.compare(this.y, other.y);
        }
        return Integer.compare(this.x, other.x);
    }
}

2. 基础版：循环重试+冲突检测 #

用HashSet<Cell>存储已占用坐标，每次生成战舰后校验是否冲突，无冲突则保留：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class ShipGenerator {
    private final Random randomizer = new Random();
    private final Set<Cell> occupiedCells = new HashSet<>();
    private int areaWidth;
    private int areaHeight;

    public ShipGenerator(int areaWidth, int areaHeight) {
        this.areaWidth = areaWidth;
        this.areaHeight = areaHeight;
    }

    public Cell[] generateValidShip(int size) {
        while (true) {
            Direction dir = Direction.random();
            int startX, startY;

            // 根据方向计算合法起始坐标范围
            if (dir == Direction.ROW) {
                startX = randomizer.nextInt(areaWidth - size + 1);
                startY = randomizer.nextInt(areaHeight);
            } else {
                startX = randomizer.nextInt(areaWidth);
                startY = randomizer.nextInt(areaHeight - size + 1);
            }

            // 生成战舰所有坐标
            List<Cell> shipCells = new ArrayList<>();
            Cell current = new Cell(startX, startY);
            shipCells.add(current);
            for (int i = 1; i < size; i++) {
                current = current.continueWithDirection(dir);
                shipCells.add(current);
            }

            // 检测是否与已占用坐标冲突
            boolean hasConflict = shipCells.stream().anyMatch(occupiedCells::contains);
            if (!hasConflict) {
                occupiedCells.addAll(shipCells);
                return shipCells.toArray(new Cell[0]);
            }
            // 冲突则循环重试
        }
    }
}

3. 优化版：预计算合法位置 #

当地图剩余空间紧张时，预计算所有可放置战舰的起始点和方向，直接随机选取，避免无效循环：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.AbstractMap.SimpleEntry;

public class OptimizedShipGenerator {
    private final Random randomizer = new Random();
    private final Set<Cell> occupiedCells = new HashSet<>();
    private int areaWidth;
    private int areaHeight;

    public OptimizedShipGenerator(int areaWidth, int areaHeight) {
        this.areaWidth = areaWidth;
        this.areaHeight = areaHeight;
    }

    public Cell[] generateValidShip(int size) {
        List<SimpleEntry<Cell, Direction>> validPositions = getAllValidStartPositions(size);
        if (validPositions.isEmpty()) {
            throw new IllegalStateException("地图已无空间放置该尺寸战舰");
        }

        // 随机选取合法位置
        SimpleEntry<Cell, Direction> selected = validPositions.get(randomizer.nextInt(validPositions.size()));
        Cell start = selected.getKey();
        Direction dir = selected.getValue();

        // 生成战舰坐标并标记为已占用
        List<Cell> shipCells = new ArrayList<>();
        Cell current = start;
        for (int i = 0; i < size; i++) {
            shipCells.add(current);
            current = current.continueWithDirection(dir);
        }
        occupiedCells.addAll(shipCells);
        return shipCells.toArray(new Cell[0]);
    }

    // 预计算所有合法的战舰起始点与方向
    private List<SimpleEntry<Cell, Direction>> getAllValidStartPositions(int size) {
        List<SimpleEntry<Cell, Direction>> validPositions = new ArrayList<>();

        // 横向放置的合法起始点
        for (int y = 0; y < areaHeight; y++) {
            for (int x = 0; x <= areaWidth - size; x++) {
                Cell start = new Cell(x, y);
                if (isPositionAvailable(start, Direction.ROW, size)) {
                    validPositions.add(new SimpleEntry<>(start, Direction.ROW));
                }
            }
        }

        // 纵向放置的合法起始点
        for (int x = 0; x < areaWidth; x++) {
            for (int y = 0; y <= areaHeight - size; y++) {
                Cell start = new Cell(x, y);
                if (isPositionAvailable(start, Direction.COLUMN, size)) {
                    validPositions.add(new SimpleEntry<>(start, Direction.COLUMN));
                }
            }
        }

        return validPositions;
    }

    // 校验某起始点沿指定方向放置战舰是否可用
    private boolean isPositionAvailable(Cell start, Direction dir, int size) {
        Cell current = start;
        for (int i = 0; i < size; i++) {
            if (occupiedCells.contains(current)) {
                return false;
            }
            current = current.continueWithDirection(dir);
        }
        return true;
    }
}

注意事项 #

• 必须重写Cell的equals和hashCode，否则集合无法正确判断坐标是否重复。
• 基础版适合地图空间充足的场景，实现简单；优化版适合战舰数量多、空间紧张的场景，效率更高。
• 需处理地图无剩余空间的异常情况，避免无限循环或程序崩溃。

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