design-procedural-gen

程序化内容生成

用途

通过程序化内容生成提升可重玩性，生成地图、地牢、战利品、地形、NPC 行为变化和世界构造。与游戏类型无关，适用于 Roguelike、生存游戏、放置游戏、开放世界游戏，或任何能从生成内容中获益的游戏。

适用场景

触发词：程序化生成、地牢生成、地图生成、战利品表、世界种子、噪声地形、BSP、波函数坍缩、随机化、种子随机、Perlin 噪声、Simplex 噪声、生成内容、Roguelike、可重玩性

前置条件

• game-economy-design — 战利品平衡与奖励曲线
• postgres-game-schema — 缓存生成内容、种子存储

核心原则

Will Wright：“我对替玩家做事的游戏不感兴趣。我想创建一个能响应玩家的模拟世界。”——简单规则产生的涌现，是程序化生成的核心。

Derek Yu（Spelunky）：“程序化生成的魔力不在于随机性，而在于受约束的随机性。约束就是设计。”

Tarn Adams（Dwarf Fortress）：“先模拟世界，再让故事自然涌现。”

Rogue 的原始开发者（Michael Toy、Glenn Wichman）：“每次游玩都应该有所不同，但每次游玩都应该公平。”

1. 为所有内容设置种子——相同种子 = 相同结果；便于调试、分享、复现 Bug 和确定性重放
2. 将生成与验证分开——先自由生成，再验证约束；切勿在紧密循环中反复生成并检查，以免陷入无限循环
3. 用 BSP（二叉空间分割）生成地牢房间——密度均衡且易于控制；递归地将空间拆分为叶节点，并在叶节点中放置房间
4. 用 Perlin/Simplex 噪声实现连续变化——适用于地形、天气、环境变化和资源密度；始终保持连贯平滑
5. 用加权随机表生成战利品——不要使用纯随机；通过权重、保底机制和保证掉落控制方差（交叉参考 game-economy-design）
6. 用波函数坍缩生成基于图块的世界——定义图块之间的邻接规则，从熵最低的单元开始坍缩；生成连贯且遵守规则的布局
7. 生成前先设定预算约束——在生成前设置房间数量、敌人密度、物品数量和路径长度的最小值/最大值；预算就是设计
8. 分层生成——先生成宏观结构（世界 → 区域 → 地带），再生成微观细节（房间 → 家具 → 物品）；每一层都会约束下一层
9. 缓存或重新生成，二选一，不要两者兼用——按内容类型决定：存入数据库（生成成本高、很少变化）或按需重新生成（成本低、由种子决定结果）
10. 确保不同环境下保持确定性——使用已知的 PRNG 算法（mulberry32、xoshiro128），绝不要使用 Math.random()；不同 JS 引擎中的 Math.random() 存在差异，会导致跨平台种子失效

分步说明

1. 定义种子和 RNG 策略

选择带种子的 PRNG。绝不要使用 Math.random()——它无法设置种子，且在不同引擎中的表现各异。

// mulberry32 — fast, deterministic, 32-bit state
const mulberry32 = (seed: number): (() => number) => {
  let s = seed | 0;
  return () => {
    s = (s + 0x6d2b79f5) | 0;
    let t = Math.imul(s ^ (s >>> 15), 1 | s);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
};

从世界种子派生各系统的种子：

const deriveSubSeed = (worldSeed: string, system: string, id: string): number => {
  const str = `${worldSeed}:${system}:${id}`;
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (Math.imul(31, hash) + str.charCodeAt(i)) | 0;
  }
  return hash >>> 0;
};

2. 选择生成算法

内容类型	算法	适用场景
地牢房间/走廊	BSP 树	带房间和走廊的网格关卡
开放地形、高度图	Perlin/Simplex 噪声	连续、平滑的景观
基于图块的世界	波函数坍缩	带邻接规则的图块集
战利品、掉落物、奖励	加权随机表	任何物品分布系统
洞穴系统	元胞自动机	有机的洞穴状形态
城市布局、道路网络	L 系统 / Voronoi	结构化但自然的布局

3. 定义预算约束

运行任何生成流程前，都要定义硬性限制：

interface GenerationBudget {
  minRooms: number;
  maxRooms: number;
  minEnemies: number;
  maxEnemies: number;
  minItems: number;
  maxItems: number;
  maxRetries: number; // CRITICAL: prevent infinite loops
}

4. 生成、验证、重试

const generateWithValidation = <T>(
  generator: (rng: () => number) => T,
  validator: (result: T) => boolean,
  seed: number,
  maxRetries: number,
): T | null => {
  for (let attempt = 0; attempt < maxRetries; attempt++) {
    const rng = mulberry32(seed + attempt);
    const result = generator(rng);
    if (validator(result)) return result;
  }
  return null; // Budget exhausted — loosen constraints or fix generator
};

5. 缓存生成内容

对于开销较大的生成操作（完整的地牢布局、世界地图），按种子缓存：

// Store in DB via postgres-game-schema
const cacheKey = `${generatorVersion}:${seed}`;
// Regenerate on demand for cheap content (loot rolls, NPC names)

有关活动会话期间的临时种子缓存，请交叉参考 redis-game-patterns。

代码示例

BSP 地牢生成

完整的基于 BSP 的地牢生成器参见 boilerplate/dungeon-generator.ts。用法：

import { DungeonGenerator } from './dungeon-generator';

const generator = new DungeonGenerator();
const dungeon = generator.generate('my-seed-123', {
  width: 80,
  height: 60,
  minRooms: 5,
  maxRooms: 12,
  minRoomSize: 4,
  maxRoomSize: 10,
  corridorWidth: 1,
});

// dungeon.rooms — array of placed rooms
// dungeon.corridors — connections between rooms
// dungeon.entrance — starting point
// dungeon.exits — exit points
// dungeon.grid — 2D cell array for rendering

加权战利品表

使用 Vose 别名法的加权战利品表参见 boilerplate/loot-table.ts。用法：

import { LootTable } from './loot-table';

const table = new LootTable<string>()
  .add('Common Sword', 60)
  .add('Rare Shield', 25)
  .add('Epic Staff', 10)
  .add('Legendary Crown', 4)
  .add('Mythic Amulet', 1)
  .withGuaranteed('Health Potion');

const drops = table.roll(3, seededRng); // 3 weighted rolls + guaranteed item

交叉参考

• game-economy-design — 战利品平衡、奖励曲线、掉落率调整
• postgres-game-schema — 在 DB 中缓存生成内容、种子存储
• redis-game-patterns — 临时种子缓存、按会话范围生成的内容
• game-backend-architecture — 服务端生成、权威地牢状态

陷阱与反模式

• 无限重试循环 — 预算限制过严会导致生成-验证循环无限执行；始终使用 maxRetries 限制重试次数，并优雅地处理失败
• 大规模场景下的种子冲突 — 32 位种子约有 40 亿个取值；每天生成 1 万个种子时，大约在累计 6.5 万个种子时就会遇到生日悖论；大型游戏应使用 64 位种子或字符串种子
• 不同 JS 引擎之间存在非确定性 — V8、SpiderMonkey 和 JavaScriptCore 的 Math.random() 实现各不相同；始终使用显式的 PRNG
• 在紧密循环中生成 — 在 while(true) 中生成后立即丢弃会耗尽 CPU；应批量尝试、限制重试次数并记录失败率
• 同时存储生成内容和种子 — 二选一；同时存储会浪费空间，并在生成器版本变化时引发同步错误
• WFC 约束过多 — 邻接规则过多会导致无法完成坍缩；从宽松规则开始，再逐步收紧
• 忘记对生成器进行版本管理 — 修改算法后，旧种子会产生不同结果；应为生成器添加版本号，并将版本与种子一起存储

设计师理念

Will Wright（《SimCity》《Spore》）：最佳的程序化系统会产生涌现效果——简单规则相互作用，生成复杂且难以预测的结果。生成器应该让你感到惊喜。如果你能预测每一种输出，系统就不够复杂；如果每一种输出都是混乱的，约束就不够严格。

Derek Yu（《Spelunky》）：程序化生成不能替代设计。每个生成的房间、放置的敌人和掉落的物品，都应该让人觉得经过了精心设计。生成器是一种工具，能大规模实现你的设计意图——它需要明确的规则、严格的约束和细致的调整。

Tarn Adams（《Dwarf Fortress》）：进行深入模拟。最丰富的程序化内容源自分层模拟——历史生成派系，派系引发冲突，冲突生成任务。每一层都会为下一层提供内容。

来源

• 《Procedural Content Generation in Games》—— Noor Shaker、Julian Togelius、Mark J. Nelson
• 《Spelunky》—— Derek Yu（Boss Fight Books）
• 《The Art of Game Design》—— Jesse Schell，关于随机性的一章
• 《Wave Function Collapse》—— Maxim Gumin（原始算法）
• GDC 演讲：《Building Worlds with Noise》（2018 年）、《Procedural Generation in No Man's Sky》（2017 年）