solver.js
/**
* 波函数坍缩求解器 —— 整个工程的核心，与页面里跑的是同一份逻辑。
* ---------------------------------------------------------------------------
* 输入是"每种地形能挨着谁"的规则表和一个随机种子；
* 输出是**每一格被观测（坍缩）的顺序**，而不是一次性地给出一张地图。
*
* 为什么要把顺序返回出去
* 标准 WFC 是"求解即成品"，用户只看到结果。但这个作品想让人看见"坍缩"本身，
* 所以求解和播放被拆开：求解阶段爱怎么回溯、重试都行，播放阶段按记录好的顺序
* 一格一格点亮。动画因此永远跑得完 —— 失败的尝试根本不会进入播放列表。
*/
/* ---------------------------------------------------------------- 基础工具 */
/** 32 位确定性随机数（mulberry32）—— 同一个种子永远得到同一座岛 */
export function mulberry32(a){
return function(){
a = (a + 0x6D2B79F5) | 0;
let t = Math.imul(a ^ (a >>> 15), 1 | a);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
/** 位置哈希 → [0,1)。用于"每格固定"的扰动：同一格每次渲染的抖动都一样，不会闪 */
export function hash01(x, y, s){
let h = (Math.imul(x | 0, 374761393) + Math.imul(y | 0, 668265263) + Math.imul(s | 0, 1274126177)) | 0;
h = (h ^ (h >>> 13)) | 0;
h = Math.imul(h, 1274126177) | 0;
h = (h ^ (h >>> 16)) >>> 0;
return h / 4294967296;
}
/* ------------------------------------------------------------ 地形与约束 */
export const VOID = 0, WATER = 1, SAND = 2, GRASS = 3, FOREST = 4, ROCK = 5;
/**
* 相邻兼容表：key 的地形可以和数组里的地形紧挨着。
* 这张表就是整个工程的"规则"—— 求解器只负责在这套规则下找一组自洽的填法。
*
* water 能挨 grass → 内陆可以出现湖
* sand 能挨 rock → 海边可以立礁石
* water 不能挨 forest/rock → 海岸线保留结构，不会糊成一团
* void 只挨 void/water → 岛的外缘一定是水，于是自然形成"环水的岛"
*/
export const ADJ_TEXT = {
void: ['void','water'],
water: ['void','water','sand','grass'],
sand: ['water','sand','grass','rock'],
grass: ['water','sand','grass','forest'],
forest: ['grass','forest','rock'],
rock: ['sand','forest','rock'],
};
/** 兼容表编译成位掩码：ADJ[a] 的第 b 位 = 1 表示 a 与 b 可相邻 */
export const ADJ = new Uint8Array(6);
for (let a = 0; a < 6; a++){
let m = 1 << a;
for (let b = 0; b < 6; b++){
if (ADJ_TEXT[LEVEL_KEYS[a]].indexOf(LEVEL_KEYS[b]) >= 0) m |= 1 << b;
}
ADJ[a] = m;
}
// 强制对称 —— 手写兼容表很容易写成单向，在这里一次性兜住
for (let a = 0; a < 6; a++){
for (let b = 0; b < 6; b++){
if ((ADJ[a] >> b) & 1) ADJ[b] |= 1 << a;
}
}
export const LEVEL_KEYS = ['void','water','sand','grass','forest','rock'];
/* --------------------------------------------------------------- 权重模型 */
/** 基准权重：草地与水是主体，岩石最少 —— 决定岛的整体地貌比例 */
export const BASE_W = [0, 62, 34, 72, 48, 24];
function gauss(x, mu, sigma){
const d = (x - mu) / sigma;
return Math.exp(-0.5 * d * d);
}
/**
* 位置权重：按"离岛心的距离"给每种地形加权。高斯峰位大致是
* 中心岩石 → 林地 → 草地 → 沙滩 → 外围水域。
*
* 这不是事后修改地形（那会破坏局部一致性），而是 WFC 里的标准做法：
* 只改"随机挑一个候选"时的倾向，约束传播该拦的照样拦。
* 没有它，环带会整齐得像同心圆；配上逐格抖动，同一个规则也能长出千变万化的岛。
*/
export function biasFor(v, r, jitter){
let b = 1;
switch (v){
case WATER: b = 0.14 + 3.20 * gauss(r, 1.00, 0.18); break;
case SAND: b = 0.30 + 3.80 * gauss(r, 0.78, 0.16); break;
case GRASS: b = 0.30 + 1.75 * gauss(r, 0.56, 0.26); break;
case FOREST: b = 0.16 + 2.60 * gauss(r, 0.34, 0.20); break;
case ROCK: b = 0.05 + 4.60 * gauss(r, 0.06, 0.30); break;
}
return b * (0.62 + 0.76 * jitter);
}
/* -------------------------------------------------------------- 求解器本体 */
const DIRS = [[1,0],[-1,0],[0,1],[0,-1]];
export class Solver {
/** @param n 网格边长 @param seed 随机种子 */
constructor(n, seed){
this.n = n;
this.seed = seed | 0;
this.rng = mulberry32(this.seed);
this.total = n * n;
this.cand = new Uint8Array(this.total); // 候选地形位掩码
this.fixed = new Uint8Array(this.total); // 1 = 已确定
this.lv = new Int8Array(this.total); // 确定后的地形
this.w = new Float32Array(this.total * 6); // 每格每地形的权重
this.lastIdx = -1; this.lastLv = 0; this.lastEnt = 0;
}
idx(x, z){ return z * this.n + x; }
/**
* 掩码 + 权重。
* 圆外的格子被**钉成深渊**（掩码只剩 void、标记为已确定），
* 圆内按到岛心的距离铺一套倾向权重。岛的轮廓半径被三组不同频率的正弦扰动，
* 所以每个种子给出不同的岛形 —— 但振幅刻意压小，太大就会把岛撕成条带。
*/
init(){
const n = this.n, c = (n - 1) / 2, s = this.seed;
const FULL = 0b111110; // level 1..5
for (let z = 0; z < n; z++){
for (let x = 0; x < n; x++){
const i = this.idx(x, z);
const dx = (x - c) / c, dz = (z - c) / c;
const rad = Math.sqrt(dx * dx + dz * dz);
const ang = Math.atan2(dz, dx);
const edge = 0.850
+ 0.070 * Math.sin(ang * 3 + s * 0.73)
+ 0.042 * Math.sin(ang * 5 - s * 1.31)
+ 0.026 * Math.sin(ang * 8 + s * 2.17);
if (rad > edge){
this.cand[i] = 1 << VOID;
this.fixed[i] = 1;
this.lv[i] = VOID;
} else {
this.cand[i] = FULL;
}
// 用"实际半径 / 岛缘半径"归一化，岛的胖瘦才不会影响地貌比例
const r = Math.min(1, rad / edge);
const jit = hash01(x, z, s + 13);
for (let v = 1; v <= 5; v++){
this.w[i * 6 + v] = BASE_W[v] * biasFor(v, r, jit);
}
}
}
}
/** 把已确定的格子全部推进约束队列，跑一次全量传播 */
seedPropagate(){
const stack = [];
for (let i = 0; i < this.total; i++) if (this.fixed[i]) stack.push(i);
return this.propagate(stack);
}
/**
* 约束传播（AC-3 风格）：
* 取出队列里的格子，算出"它的邻居们还允许保留哪些地形"，与邻居的候选求交；
* 交集变了就把邻居也推进队列继续传播。交集为空 = 这组填法矛盾，整轮作废。
*
* 这是 WFC 和"随机刷格子"的根本区别：改一格会连带收紧一整片邻居。
*/
propagate(stack){
const n = this.n;
while (stack.length){
const i = stack.pop();
const ci = this.cand[i];
if (!ci) return false;
const x = i % n, z = (i / n) | 0;
for (let d = 0; d < 4; d++){
const nx = x + DIRS[d][0], nz = z + DIRS[d][1];
if (nx < 0 || nx >= n || nz < 0 || nz >= n) continue; // 出界 = 无约束
const j = this.idx(nx, nz);
let allowed = 0;
for (let b = 0; b < 6; b++) if (ci & (1 << b)) allowed |= ADJ[b];
const nc = allowed & this.cand[j];
if (!nc) return false;
if (nc !== this.cand[j]){
this.cand[j] = nc;
stack.push(j);
}
}
}
return true;
}
/** 香农熵：候选集合越"杂"熵越高。求解器永远先啃熵最低的那一格 */
entropy(i){
let sum = 0, logsum = 0;
const base = i * 6;
for (let v = 1; v <= 5; v++){
if (this.cand[i] & (1 << v)){
const w = this.w[base + v] || 1e-4;
sum += w; logsum += w * Math.log(w);
}
}
if (sum <= 0) return 0;
return Math.log(sum) - logsum / sum;
}
/**
* 观测一格：在所有"熵最低"的格子里随机挑一个，按权重掷出一种地形。
* 只剩一个候选的格子熵记作 -1 —— 它其实已经确定了，优先处理掉。
*/
step(){
let best = Infinity, ties = [];
for (let i = 0; i < this.total; i++){
if (this.fixed[i]) continue;
const c = this.cand[i];
const e = (c & (c - 1)) === 0 ? -1 : this.entropy(i);
if (e < best - 1e-9){ best = e; ties.length = 0; ties.push(i); }
else if (e <= best + 1e-9) ties.push(i);
}
if (!ties.length) return false; // 全部观测完毕
const i = ties[(this.rng() * ties.length) | 0];
this.lastEnt = this.entropy(i);
const base = i * 6;
let total = 0;
for (let v = 1; v <= 5; v++) if (this.cand[i] & (1 << v)) total += this.w[base + v];
let pick = 1, acc = this.rng() * total;
for (let v = 1; v <= 5; v++){
if (this.cand[i] & (1 << v)){
acc -= this.w[base + v];
if (acc <= 0){ pick = v; break; }
}
}
this.cand[i] = 1 << pick;
this.fixed[i] = 1;
this.lv[i] = pick;
this.lastIdx = i;
this.lastLv = pick;
return this.propagate([i]) ? true : 'fail';
}
}
/**
* 求解并返回坍缩顺序。
* 失败就叫下一个种子重试 —— 规则很宽松，实测几乎总是一次就过；
* 重试之所以必要，是因为"矛盾"在 WFC 里是原理性的，不是 bug。
*
* @returns {{n:number, order:{i:number,lv:number,ent:number}[], cells:Int8Array, seed:number}|null}
*/
export function solve(n, seed){
for (let attempt = 0; attempt < 90; attempt++){
const s = (seed + attempt * 7919) | 0;
const solver = new Solver(n, s);
solver.init();
if (!solver.seedPropagate()) continue;
const order = [];
let ok = true;
for (;;){
const r = solver.step();
if (r === false) break;
if (r === 'fail'){ ok = false; break; }
order.push({ i: solver.lastIdx, lv: solver.lastLv, ent: solver.lastEnt });
}
if (ok && order.length) return { n, order, cells: solver.lv, seed: s };
}
return null;
}
