引言
波函数坍缩（Wave Function Collapse，简称WFC）是一种程序化内容生成算法，最早由Maxim Gumin提出。它借鉴了量子力学中”波函数坍缩”的概念，通过局部约束传播来生成与输入样本风格一致的二维图案。在游戏开发中，WFC被广泛用于程序化地图生成、纹理合成和关卡设计。本文将用Java实现一个简化版的WFC算法，讲解其核心思想：熵最小化选择与约束传播。
算法核心思想
WFC算法的核心流程如下：
- 样本分析：从输入样本中提取所有N×N的瓦片模式（tile patterns），并记录每个模式与相邻模式的兼容关系。
- 初始化：将输出网格中每个格子的”波函数”初始化为所有可能模式的叠加态。
- 观察与坍缩：选择熵最低（可选模式最少）的格子，随机选择一个合法模式使其坍缩。
- 约束传播：当一个格子坍缩后，向其邻居传播约束，排除不兼容的模式。若某邻居因此只剩一种模式，则继续级联传播。
- 重复：重复步骤3-4，直到所有格子都坍缩，或出现矛盾（某格子无可用模式）。
Java实现
import java.util.*;
/**
* 波函数坍缩算法（Wave Function Collapse）简化实现
* 用于程序化二维地图生成
*/
public class WaveFunctionCollapse {
// 模式类：表示一个N×N的瓦片组合
static class Pattern {
int[][] tiles; // 瓦片索引矩阵
int size; // 模式大小（N×N）
int frequency; // 在样本中出现的频次
public Pattern(int[][] tiles, int frequency) {
this.size = tiles.length;
this.tiles = new int[size][size];
for (int i = 0; i < size; i++) {
this.tiles[i] = tiles[i].clone();
}
this.frequency = frequency;
}
// 检查两个模式在指定方向上是否兼容
// dir: 0=上, 1=右, 2=下, 3=左
boolean compatible(Pattern other, int dir) {
// dir表示other相对于this的方向
// 例如dir=0（other在上方），则this的第0行要与other的最后一行匹配
if (dir == 0) { // other在this上方
for (int x = 0; x < size; x++) {
if (tiles[0][x] != other.tiles[size - 1][x]) return false;
}
} else if (dir == 2) { // other在this下方
for (int x = 0; x < size; x++) {
if (tiles[size - 1][x] != other.tiles[0][x]) return false;
}
} else if (dir == 3) { // other在this左方
for (int y = 0; y < size; y++) {
if (tiles[y][0] != other.tiles[y][size - 1]) return false;
}
} else if (dir == 1) { // other在this右方
for (int y = 0; y < size; y++) {
if (tiles[y][size - 1] != other.tiles[y][0]) return false;
}
}
return true;
}
}
// 波单元：表示网格中一个格子的叠加态
static class WaveCell {
Set<Integer> possiblePatterns; // 仍有可能的模式索引集合
boolean collapsed; // 是否已坍缩
int chosenPattern; // 坍缩后选择的模式
public WaveCell(int patternCount) {
this.possiblePatterns = new HashSet<>();
for (int i = 0; i < patternCount; i++) {
this.possiblePatterns.add(i);
}
this.collapsed = false;
this.chosenPattern = -1;
}
double entropy(int[] frequencies, int totalFreq) {
if (collapsed) return -1;
double sum = 0;
for (int p : possiblePatterns) {
double prob = (double) frequencies[p] / totalFreq;
sum += prob;
}
// 使用香农熵的近似：模式数量的对数加上噪声打破平局
return Math.log(sum) + Math.random() * 0.001;
}
}
private List<Pattern> patterns;
private boolean[][][] compatible; // compatible[p][dir][q] = pattern p在dir方向上与pattern q兼容
private int patternSize;
private int[] frequencies;
private int totalFrequency;
public WaveFunctionCollapse(List<Pattern> patterns, int patternSize) {
this.patterns = patterns;
this.patternSize = patternSize;
this.frequencies = new int[patterns.size()];
for (int i = 0; i < patterns.size(); i++) {
frequencies[i] = patterns.get(i).frequency;
totalFrequency += frequencies[i];
}
precomputeCompatibility();
}
// 预计算所有模式之间的兼容性
private void precomputeCompatibility() {
int n = patterns.size();
compatible = new boolean[n][4][n];
for (int p = 0; p < n; p++) {
for (int dir = 0; dir < 4; dir++) {
for (int q = 0; q < n; q++) {
// dir: 0=上, 1=右, 2=下, 3=左
// pattern q 在 pattern p 的 dir 方向
compatible[p][dir][q] = patterns.get(p).compatible(patterns.get(q), dir);
}
}
}
}
// 从样本中提取所有N×N模式
public static List<Pattern> extractPatterns(int[][] sample, int n) {
Map<String, Pattern> patternMap = new HashMap<>();
int rows = sample.length;
int cols = sample[0].length;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
int[][] tiles = new int[n][n];
for (int dy = 0; dy < n; dy++) {
for (int dx = 0; dx < n; dx++) {
int sy = (y + dy) % rows;
int sx = (x + dx) % cols;
tiles[dy][dx] = sample[sy][sx];
}
}
String key = patternToString(tiles);
patternMap.computeIfAbsent(key, k -> new Pattern(tiles, 0)).frequency++;
}
}
return new ArrayList<>(patternMap.values());
}
private static String patternToString(int[][] tiles) {
StringBuilder sb = new StringBuilder();
for (int[] row : tiles) {
for (int v : row) sb.append(v).append(',');
sb.append(';');
}
return sb.toString();
}
// 执行WFC生成
public int[][] generate(int width, int height) {
WaveCell[][] wave = new WaveCell[height][width];
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
wave[y][x] = new WaveCell(patterns.size());
}
}
int[][] result = new int[height][width];
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0, 1, 0};
// 方向对应：0=上, 1=右, 2=下, 3=左
// 反向：opposite[dir] = (dir + 2) % 4
while (true) {
// 找到熵最小且未坍缩的格子
Double minEntropy = null;
int minX = -1, minY = -1;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (!wave[y][x].collapsed) {
double e = wave[y][x].entropy(frequencies, totalFrequency);
if (minEntropy == null || e < minEntropy) {
minEntropy = e;
minX = x;
minY = y;
}
}
}
}
if (minEntropy == null) break; // 全部坍缩完成
// 坍缩选中的格子：按频率加权随机选择
WaveCell cell = wave[minY][minX];
List<Integer> candidates = new ArrayList<>(cell.possiblePatterns);
int chosen = weightedRandomChoice(candidates, frequencies);
cell.collapsed = true;
cell.chosenPattern = chosen;
cell.possiblePatterns.clear();
cell.possiblePatterns.add(chosen);
// 约束传播（BFS）
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{minX, minY});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cx = cur[0], cy = cur[1];
WaveCell curCell = wave[cy][cx];
for (int dir = 0; dir < 4; dir++) {
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
if (wave[ny][nx].collapsed) continue;
// 获取当前格子所有可能模式在dir方向上兼容的模式集合
Set<Integer> allowed = new HashSet<>();
for (int p : curCell.possiblePatterns) {
for (int q = 0; q < patterns.size(); q++) {
if (compatible[p][dir][q]) {
allowed.add(q);
}
}
}
WaveCell neighbor = wave[ny][nx];
Set<Integer> toRemove = new HashSet<>();
for (int q : neighbor.possiblePatterns) {
if (!allowed.contains(q)) {
toRemove.add(q);
}
}
if (!toRemove.isEmpty()) {
neighbor.possiblePatterns.removeAll(toRemove);
if (neighbor.possiblePatterns.isEmpty()) {
throw new RuntimeException("矛盾：无法找到兼容的模式，生成失败");
}
queue.offer(new int[]{nx, ny});
}
}
}
}
// 提取结果（取每个模式中心位置的瓦片）
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
int pIdx = wave[y][x].chosenPattern;
Pattern p = patterns.get(pIdx);
// 使用模式中心作为输出瓦片
result[y][x] = p.tiles[patternSize / 2][patternSize / 2];
}
}
return result;
}
private int weightedRandomChoice(List<Integer> candidates, int[] frequencies) {
int total = 0;
for (int c : candidates) total += frequencies[c];
int r = new Random().nextInt(total);
int sum = 0;
for (int c : candidates) {
sum += frequencies[c];
if (r < sum) return c;
}
return candidates.get(candidates.size() - 1);
}
// 打印地图
public static void printMap(int[][] map) {
char[] symbols = {' ', '#', '~', 'T', '^'};
for (int[] row : map) {
for (int v : row) {
System.out.print(symbols[Math.min(v, symbols.length - 1)]);
}
System.out.println();
}
}
public static void main(String[] args) {
// 样本地图：0=空地, 1=墙, 2=水, 3=树, 4=山
int[][] sample = {
{1,1,1,1,1,1,1,1},
{1,0,0,0,3,0,0,1},
{1,0,2,2,2,0,0,1},
{1,0,2,4,2,0,3,1},
{1,3,2,2,2,0,0,1},
{1,0,0,0,0,0,0,1},
{1,0,3,0,0,3,0,1},
{1,1,1,1,1,1,1,1}
};
int patternSize = 3;
List<Pattern> patterns = extractPatterns(sample, patternSize);
System.out.println("提取模式数量: " + patterns.size());
WaveFunctionCollapse wfc = new WaveFunctionCollapse(patterns, patternSize);
int[][] generated = wfc.generate(32, 16);
System.out.println("\n生成地图:");
printMap(generated);
}
}
复杂度分析
- 模式提取：对于R×C的样本和N×N的模式大小，时间复杂度为O(R·C·N²)。
- 兼容性预计算：若有P个模式，时间复杂度为O(P²·N²)。
- 生成过程：设输出网格为W×H，每次选择最低熵格子为O(W·H)，约束传播的摊还复杂度接近O(W·H·P²)（实际中因早期大量坍缩而远低于此）。
- 空间复杂度：O(W·H·P)用于存储波函数状态，O(P²)用于兼容性表。
总结
波函数坍缩算法通过”观察-坍缩-传播”的循环，将局部约束逐步传播到全局，最终生成风格一致的程序化内容。本文实现的简化版涵盖了WFC的核心机制：模式提取、兼容性预计算、熵最小化选择与级联约束传播。在实际游戏引擎中，可进一步扩展为重叠模型（overlapping model）、多层级生成（hierarchical WFC）以及带权重的定向约束，以生成更复杂、更具艺术感的地图与纹理。
