本文介绍一种高效、可扩展的无重复二维坐标对（x, y）随机生成方案，避免传统“重试法”性能退化问题，适用于战舰类游戏中船体自动布放场景。
本文介绍一种高效、可扩展的无重复二维坐标对（x, y）随机生成方案，避免传统“重试法”性能退化问题，适用于战舰类游戏中船体自动布放场景。
在开发类似《BattleShip》的网格类游戏时，一个核心挑战是：如何在有限棋盘（如10×10）上，批量、高效、无冲突地生成多个不重叠的船体位置？ 每艘船由连续的单元格组成（如长度为3的横向或纵向序列），而所有船的单元格坐标（x, y）全局唯一——即任意两个单元格不能拥有完全相同的坐标对。
直接使用 Random.nextInt() 配合循环重试（“generate-then-check-if-used-else-retry”）看似简单，但在棋盘填充率升高时，碰撞概率急剧上升，最坏情况下可能陷入长时阻塞或无限循环，不符合生产级游戏逻辑的确定性与响应性要求。
更优解是采用确定性伪随机映射 + 全局状态管理策略。其核心思想不是“随机选点再验证”，而是将所有合法坐标对线性编号 → 通过可逆/遍历式伪随机置换 → 映射回二维坐标，从而保证：
- 每次调用获取新坐标对，天然不重复；
- 时间复杂度 O(1) 均摊，无重试开销；
- 支持提前预分配全部位置，便于碰撞预检。
以下是一个轻量、实用的实现方案（不依赖外部库，兼容 Java 8+）：
当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。
立即学习“Java免费学习笔记（深入）”；
import java.util.*;
public class NonRepeatingCoordinateGenerator {
private final int width;
private final int height;
private final int totalCells;
private final Random globalRandom;
private final Set<String> used = new HashSet<>(); // 用于快速查重（可选，仅调试/兜底）
// 使用线性同余生成器（LCG）模拟独立随机流 —— 关键优化点
private static final long A = 25214903917L; // JDK Random 的 multiplier
private static final long C = 11L; // JDK Random 的 addend
private static final long M = 1L << 48; // modulus
public NonRepeatingCoordinateGenerator(int width, int height) {
this.width = width;
this.height = height;
this.totalCells = width * height;
this.globalRandom = new Random();
}
// 将 0~(width*height-1) 的索引映射为唯一 (x, y)，通过 LCG 置换打乱顺序
public Cell nextUniqueCell() {
long index = generateNextIndex();
int x = (int) (index % width);
int y = (int) (index / width);
String key = x + "," + y;
if (!used.add(key)) {
throw new IllegalStateException("Unexpected collision in LCG mapping!");
}
return new Cell(x, y);
}
// 使用 LCG 实现“全空间遍历式”伪随机序列（周期 ≈ 2^48）
private long state = 0;
private long generateNextIndex() {
state = (A * state + C) & (M - 1); // 标准 LCG 步进
return state % totalCells; // 投影到有效范围（带轻微偏差，但对游戏完全可接受）
}
// 批量预生成 n 个不重复 Cell（推荐用于整艘船的连续坐标生成）
public List<Cell> nextUniqueCells(int n) {
List<Cell> result = new ArrayList<>(n);
for (int i = 0; i < n && result.size() < n; i++) {
Cell c = nextUniqueCell();
result.add(c);
}
return result;
}
}⚠️ 关键注意事项：
-
不要在每艘船内单独调用
nextUniqueCell()生成首格后“沿方向延伸”——这仍可能导致船体之间重叠（例如船A占(2,3)-(2,4)-(2,5)，船B首格恰好生成(2,4)）。正确做法是：对整艘船所需的所有单元格（如3个连续坐标），统一从nextUniqueCells(3)获取，再校验是否共线且方向一致；或更稳妥地——先随机选首格和方向，再检查该整条路径是否全部未被占用（使用Set<cell></cell>快速判断）。 - 上述 LCG 实现虽非密码学安全，但对游戏逻辑已足够：周期极长、分布均匀、无明显模式。若需更强随机性，可替换为
ThreadLocalRandom.current().nextLong()驱动的 Fisher-Yates 洗牌（需预先构建全坐标列表，内存 O(W×H)）。 - 实际部署时，建议将所有已放置的
Cell存入HashSet<cell></cell>（需确保Cell正确重写equals()和hashCode()），每次生成新船前执行Collections.disjoint(newShipCells, occupiedCells)快速校验。
总结：解决“无重复随机坐标对”问题，本质是将随机采样转化为确定性遍历。通过 LCG 映射或预洗牌，我们摆脱了不可控的重试循环，使布船逻辑兼具高性能、可预测性与可维护性——这才是面向真实游戏场景的工程化答案。
