561 lines
34 KiB
JavaScript
561 lines
34 KiB
JavaScript
'use strict';
|
||
(function(root){
|
||
const GENERATOR_VERSION=5;
|
||
const SIDE_D={N:[-1,0],S:[1,0],W:[0,-1],E:[0,1]};
|
||
function key2(x,y){return x+','+y}
|
||
function ckey(r,c){return r+','+c}
|
||
function sameCell(a,b){return a&&b&&a[0]===b[0]&&a[1]===b[1]}
|
||
function hash32(x){x|=0;x=Math.imul(x^(x>>>16),0x45d9f3b);x=Math.imul(x^(x>>>16),0x45d9f3b);return (x^(x>>>16))>>>0}function hash2(x,y){return hash32(Math.imul(x|0,73856093)^Math.imul(y|0,19349663))}function rngFrom(seed){let s=seed>>>0;return()=>((s=hash32(s+0x9e3779b9))>>>0)/4294967296}function shuffle(a,rng){for(let i=a.length-1;i>0;i--){const j=Math.floor(rng()*(i+1));[a[i],a[j]]=[a[j],a[i]]}return a}
|
||
function smooth(t){return t*t*(3-2*t)}function lattice(x,y){return hash2(x,y)/4294967295}function noise2(x,y,scale=5){const fx=x/scale,fy=y/scale,x0=Math.floor(fx),y0=Math.floor(fy),tx=smooth(fx-x0),ty=smooth(fy-y0);const a=lattice(x0,y0),b=lattice(x0+1,y0),c=lattice(x0,y0+1),d=lattice(x0+1,y0+1);const u=a+(b-a)*tx,v=c+(d-c)*tx;return u+(v-u)*ty}
|
||
const STARTER_DIFFICULTIES=Object.freeze({
|
||
'-1,-1':2,'0,-1':3,'1,-1':3,
|
||
'-1,0':3, '0,0':1, '1,0':2,
|
||
'-1,1':2, '0,1':1, '1,1':3
|
||
});
|
||
function macroDifficulty(x,y){
|
||
const starter=STARTER_DIFFICULTIES[key2(x,y)];
|
||
if(starter!=null)return starter;
|
||
// Broad low-frequency fields first, distance only as a weak long-range tendency.
|
||
const n=.68*noise2(x,y,8)+.32*noise2(x+17,y-23,15);
|
||
const dist=Math.min(1,Math.hypot(x,y)/45);
|
||
return Math.max(1,Math.min(10,1+Math.floor(10*Math.max(0,Math.min(.999999,n*.90+dist*.10)))))
|
||
}
|
||
function regionDifficultyBand(target){
|
||
// The macro region is authoritative. Most boards must stay within ±1;
|
||
// edge regions are clamped naturally to 1–2 or 9–10.
|
||
return{
|
||
min:Math.max(1,target-1),
|
||
max:Math.min(10,target+1)
|
||
}
|
||
}
|
||
function difficultyFitsRegion(rating,target){
|
||
const b=regionDifficultyBand(target);
|
||
return rating>=b.min&&rating<=b.max;
|
||
}
|
||
function regionMismatch(rating,target){
|
||
const b=regionDifficultyBand(target);
|
||
if(rating<b.min)return b.min-rating;
|
||
if(rating>b.max)return rating-b.max;
|
||
return 0;
|
||
}
|
||
const DIFFICULTY_DEFINITIONS=Object.freeze([
|
||
Object.freeze({level:1,name:'SIMPLE',description:'Short routes, few bends, and a compact search space.'}),
|
||
Object.freeze({level:2,name:'EASY',description:'A compact field with slightly longer or more winding routes.'}),
|
||
Object.freeze({level:3,name:'STEADY',description:'More route choices, bends, and gate-pair possibilities.'}),
|
||
Object.freeze({level:4,name:'MODERATE',description:'A larger field whose routes require forward planning.'}),
|
||
Object.freeze({level:5,name:'STANDARD',description:'Balanced board size and route complexity.'}),
|
||
Object.freeze({level:6,name:'TACTICAL',description:'Longer routes and more interacting decisions.'}),
|
||
Object.freeze({level:7,name:'HARD',description:'Large fields with complex route interactions.'}),
|
||
Object.freeze({level:8,name:'EXPERT',description:'Dense expert fields with little room for recovery.'}),
|
||
Object.freeze({level:9,name:'MASTER',description:'Very large search spaces and demanding clue interactions.'}),
|
||
Object.freeze({level:10,name:'ABYSS',description:'The largest, longest, and most winding solutions.'})
|
||
]);
|
||
function difficultyDefinition(level=1){
|
||
const safe=Math.max(1,Math.min(10,Number.isFinite(level)?Math.round(level):1));
|
||
return DIFFICULTY_DEFINITIONS[safe-1];
|
||
}
|
||
function normalizeShape(chunks){let minx=Math.min(...chunks.map(q=>q[0])),miny=Math.min(...chunks.map(q=>q[1]));return chunks.map(([x,y])=>[x-minx,y-miny]).sort((a,b)=>a[1]-b[1]||a[0]-b[0])}
|
||
function transformShape(shape,rot=0,flip=false){let p=shape.map(([x,y])=>[flip?-x:x,y]);for(let k=0;k<rot;k++)p=p.map(([x,y])=>[-y,x]);return normalizeShape(p)}
|
||
const BASE_SHAPES=[
|
||
[[0,0]],[[0,0],[1,0]],[[0,0],[0,1]],[[0,0],[1,0],[2,0]],[[0,0],[0,1],[0,2]],
|
||
[[0,0],[1,0],[0,1]],[[0,0],[1,0],[1,1]],[[0,0],[1,0],[0,1],[1,1]],
|
||
[[0,0],[1,0],[2,0],[0,1]],[[0,0],[1,0],[2,0],[1,1]],[[0,0],[1,0],[1,1],[2,1]],
|
||
[[0,0],[1,0],[0,1],[1,1],[0,2]],[[0,0],[1,0],[2,0],[0,1],[0,2]],
|
||
[[0,0],[1,0],[2,0],[0,1],[1,1],[0,2]],[[0,0],[1,0],[2,0],[1,1],[2,1],[2,2]]
|
||
];
|
||
const SHAPES=[];{const seen=new Set();for(const s of BASE_SHAPES)for(let f=0;f<2;f++)for(let r=0;r<4;r++){const q=transformShape(s,r,!!f),k=q.map(v=>v.join(':')).join('|');if(!seen.has(k)){seen.add(k);SHAPES.push(q)}}}
|
||
function shapeCells(chunks){const out=[];for(const[x,y]of chunks)for(let r=0;r<5;r++)for(let c=0;c<5;c++)out.push([y*5+r,x*5+c]);return out}
|
||
function shapeBounds(chunks){return{w:(Math.max(...chunks.map(q=>q[0]))+1)*5,h:(Math.max(...chunks.map(q=>q[1]))+1)*5}}
|
||
|
||
|
||
function outsideCell(g){const[dR,dC]=SIDE_D[g[2]];return[g[0]+dR,g[1]+dC]}
|
||
function turnAnalysisRaw(path,gates){const gs=gates[path.startGate],ge=gates[path.endGate],pts=[outsideCell(gs),...path.cells,outsideCell(ge)],dirs=[];for(let i=0;i<pts.length-1;i++)dirs.push([pts[i+1][0]-pts[i][0],pts[i+1][1]-pts[i][1]]);const cells=[];for(let i=0;i<dirs.length-1;i++)if(dirs[i][0]!==dirs[i+1][0]||dirs[i][1]!==dirs[i+1][1])cells.push(path.cells[i]);return{count:cells.length,cells}}
|
||
|
||
// 5×5 is an area/routing unit, never a puzzle boundary.
|
||
// Connector positions AND connector counts vary by world boundary coordinates.
|
||
// The same boundary hash is used from either side, so independently generated neighbors still match exactly.
|
||
const PuzzlePatterns=root.BendPuzzlePatterns||(typeof module==='object'&&module.exports?require('./puzzle-patterns'):null);
|
||
if(!PuzzlePatterns)throw new Error('BendPuzzlePatterns is not loaded');
|
||
const MICRO_PATTERN_SETS=PuzzlePatterns.MICRO_PATTERN_SETS;
|
||
const H_PORT_PROFILES=[[1],[3],[1,2,3]];
|
||
const V_PORT_PROFILES=[[0,2],[0,4],[2,4],[0,1,2,4],[0,2,3,4]];
|
||
|
||
function boundaryHash(a,b,salt){
|
||
return hash32(
|
||
Math.imul((a|0)+0x5f356495,73856093)^
|
||
Math.imul((b|0)-0x27d4eb2d,19349663)^
|
||
salt
|
||
);
|
||
}
|
||
function horizontalBoundaryKey(unitX,boundaryY){return `H:${unitX},${boundaryY}`}
|
||
function verticalBoundaryKey(boundaryX,unitY){return `V:${boundaryX},${unitY}`}
|
||
function fixedProfileIndex(options,key,profileCount){
|
||
const value=options?.fixedPortProfiles?.[key];
|
||
return Number.isInteger(value)&&value>=0&&value<profileCount?value:null;
|
||
}
|
||
function horizontalPortProfileIndex(unitX,boundaryY,options=null){
|
||
const fixed=fixedProfileIndex(options,horizontalBoundaryKey(unitX,boundaryY),H_PORT_PROFILES.length);
|
||
if(fixed!=null)return fixed;
|
||
if(Number.isInteger(options?.portSeed))return boundaryHash(unitX,boundaryY,0x41c64e6d^(options.portSeed>>>0))%H_PORT_PROFILES.length;
|
||
// Preserve the established topology for stored boards and the starter board.
|
||
if(unitX===0&&boundaryY===0)return 0;
|
||
if(unitX===0&&boundaryY===1)return 2;
|
||
const h=boundaryHash(unitX,boundaryY,0x41c64e6d)%100;
|
||
if(h<39)return 0;
|
||
if(h<78)return 1;
|
||
return 2;
|
||
}
|
||
function verticalPortProfileIndex(boundaryX,unitY,options=null){
|
||
const fixed=fixedProfileIndex(options,verticalBoundaryKey(boundaryX,unitY),V_PORT_PROFILES.length);
|
||
if(fixed!=null)return fixed;
|
||
if(Number.isInteger(options?.portSeed))return boundaryHash(boundaryX,unitY,0x9e3779b9^(options.portSeed>>>0))%V_PORT_PROFILES.length;
|
||
if(boundaryX===0&&unitY===0)return 1;
|
||
if(boundaryX===1&&unitY===0)return 3;
|
||
const h=boundaryHash(boundaryX,unitY,0x9e3779b9)%100;
|
||
if(h<28)return 0;
|
||
if(h<56)return 1;
|
||
if(h<82)return 2;
|
||
if(h<91)return 3;
|
||
return 4;
|
||
}
|
||
function unitPortSpec(unitX,unitY,options=null){
|
||
return{
|
||
ni:horizontalPortProfileIndex(unitX,unitY,options),
|
||
si:horizontalPortProfileIndex(unitX,unitY+1,options),
|
||
wi:verticalPortProfileIndex(unitX,unitY,options),
|
||
ei:verticalPortProfileIndex(unitX+1,unitY,options)
|
||
};
|
||
}
|
||
function portSignature(spec){
|
||
return `${spec.ni},${spec.si},${spec.wi},${spec.ei}`;
|
||
}
|
||
function registerExternalPorts(map,dx,dy,spec,chunkSet){
|
||
if(!chunkSet.has(key2(dx,dy-1)))
|
||
for(const c of H_PORT_PROFILES[spec.ni])map.set(ckey(dy*5,dx*5+c),'N');
|
||
if(!chunkSet.has(key2(dx,dy+1)))
|
||
for(const c of H_PORT_PROFILES[spec.si])map.set(ckey(dy*5+4,dx*5+c),'S');
|
||
if(!chunkSet.has(key2(dx-1,dy)))
|
||
for(const r of V_PORT_PROFILES[spec.wi])map.set(ckey(dy*5+r,dx*5),'W');
|
||
if(!chunkSet.has(key2(dx+1,dy)))
|
||
for(const r of V_PORT_PROFILES[spec.ei])map.set(ckey(dy*5+r,dx*5+4),'E');
|
||
}
|
||
|
||
function puzzleCandidateFromPatterns(chunks,seed,level,attempt,originX=0,originY=0,generationOptions=null){
|
||
const valid=shapeCells(chunks),
|
||
bounds=shapeBounds(chunks),
|
||
chunkSet=new Set(chunks.map(q=>key2(q[0],q[1]))),
|
||
externalSides=new Map(),
|
||
adj=new Map(valid.map(c=>[ckey(c[0],c[1]),[]]));
|
||
|
||
const addEdge=(a,b)=>{
|
||
const ka=ckey(a[0],a[1]),kb=ckey(b[0],b[1]);
|
||
if(!adj.has(ka)||!adj.has(kb))return;
|
||
adj.get(ka).push([b[0],b[1]]);
|
||
adj.get(kb).push([a[0],a[1]]);
|
||
};
|
||
|
||
// Each 5x5 area's connector signature is derived from its WORLD boundary coordinates.
|
||
// Two independently generated neighboring boards therefore always agree on the exact cells.
|
||
for(const[dx,dy]of chunks){
|
||
const unitX=originX+dx,unitY=originY+dy,
|
||
spec=unitPortSpec(unitX,unitY,generationOptions),
|
||
variants=MICRO_PATTERN_SETS[portSignature(spec)];
|
||
|
||
if(!variants?.length)return null;
|
||
|
||
const localSeed=hash32(
|
||
seed^
|
||
Math.imul(attempt+1,0x45d9f3b)^
|
||
Math.imul(unitX+37,73856093)^
|
||
Math.imul(unitY+53,19349663)
|
||
);
|
||
const rng=rngFrom(localSeed),
|
||
pat=variants[Math.floor(rng()*variants.length)%variants.length];
|
||
|
||
for(const frag of pat){
|
||
const pts=frag.map(([r,c])=>[dy*5+r,dx*5+c]);
|
||
for(let i=0;i<pts.length-1;i++)addEdge(pts[i],pts[i+1]);
|
||
}
|
||
|
||
registerExternalPorts(externalSides,dx,dy,spec,chunkSet);
|
||
}
|
||
|
||
// Connect neighboring 5x5 area units using their shared world-coordinate profile.
|
||
for(const[dx,dy]of chunks){
|
||
const unitX=originX+dx,unitY=originY+dy;
|
||
|
||
if(chunkSet.has(key2(dx+1,dy))){
|
||
const rows=V_PORT_PROFILES[verticalPortProfileIndex(unitX+1,unitY,generationOptions)];
|
||
for(const r of rows)
|
||
addEdge([dy*5+r,dx*5+4],[dy*5+r,(dx+1)*5]);
|
||
}
|
||
|
||
if(chunkSet.has(key2(dx,dy+1))){
|
||
const cols=H_PORT_PROFILES[horizontalPortProfileIndex(unitX,unitY+1,generationOptions)];
|
||
for(const c of cols)
|
||
addEdge([dy*5+4,dx*5+c],[(dy+1)*5,dx*5+c]);
|
||
}
|
||
}
|
||
|
||
const seen=new Set(),components=[];
|
||
for(const start of valid){
|
||
const sk=ckey(start[0],start[1]);
|
||
if(seen.has(sk))continue;
|
||
|
||
const stack=[[start[0],start[1]]],comp=[];
|
||
seen.add(sk);
|
||
|
||
while(stack.length){
|
||
const u=stack.pop(),uk=ckey(u[0],u[1]);
|
||
comp.push(u);
|
||
for(const v of adj.get(uk)||[]){
|
||
const vk=ckey(v[0],v[1]);
|
||
if(!seen.has(vk)){seen.add(vk);stack.push(v)}
|
||
}
|
||
}
|
||
|
||
const ends=comp.filter(c=>(adj.get(ckey(c[0],c[1]))||[]).length===1);
|
||
if(ends.length!==2)return null;
|
||
|
||
const sSide=externalSides.get(ckey(ends[0][0],ends[0][1])),
|
||
eSide=externalSides.get(ckey(ends[1][0],ends[1][1]));
|
||
if(!sSide||!eSide)return null;
|
||
|
||
const ordered=[[ends[0][0],ends[0][1]]];
|
||
let prev=null,cur=ends[0],guard=valid.length+5;
|
||
|
||
while(!sameCell(cur,ends[1])&&guard-->0){
|
||
const nexts=(adj.get(ckey(cur[0],cur[1]))||[])
|
||
.filter(v=>!prev||!sameCell(v,prev));
|
||
if(!nexts.length)return null;
|
||
const next=nexts[0];
|
||
prev=cur;
|
||
cur=next;
|
||
ordered.push([cur[0],cur[1]]);
|
||
}
|
||
|
||
if(!sameCell(cur,ends[1]))return null;
|
||
components.push({cells:ordered,sSide,eSide});
|
||
}
|
||
|
||
const gates=[],nums=[],solution=[];
|
||
let maxTurns=0,totalTurns=0;
|
||
const clueRng=rngFrom(hash32(seed^Math.imul(attempt+11,0x27d4eb2d)));
|
||
|
||
for(const comp of components){
|
||
const first=comp.cells[0],last=comp.cells[comp.cells.length-1];
|
||
const s=gates.length;
|
||
gates.push([first[0],first[1],comp.sSide]);
|
||
const e=gates.length;
|
||
gates.push([last[0],last[1],comp.eSide]);
|
||
|
||
const path={startGate:s,endGate:e,cells:comp.cells},
|
||
ta=turnAnalysisRaw(path,gates);
|
||
|
||
if(!ta.cells.length||ta.count<=0)return null;
|
||
|
||
maxTurns=Math.max(maxTurns,ta.count);
|
||
totalTurns+=ta.count;
|
||
|
||
let bend;
|
||
if(level<=3){
|
||
const edgePool=[
|
||
...ta.cells.slice(0,Math.min(2,ta.cells.length)),
|
||
...ta.cells.slice(Math.max(0,ta.cells.length-2))
|
||
];
|
||
bend=edgePool[Math.floor(clueRng()*edgePool.length)];
|
||
}else{
|
||
const lo=Math.floor(ta.cells.length*.25),
|
||
hi=Math.max(lo+1,Math.ceil(ta.cells.length*.75));
|
||
bend=ta.cells[lo+Math.floor(clueRng()*(hi-lo))]
|
||
||ta.cells[Math.floor(clueRng()*ta.cells.length)];
|
||
}
|
||
|
||
nums.push([bend[0],bend[1],ta.count]);
|
||
solution.push(path);
|
||
}
|
||
|
||
return{
|
||
g:gates,n:nums,valid,bounds,axis:'MIX',solution,level,
|
||
maxTurns,totalTurns,style:'variable-world-gates'
|
||
};
|
||
}
|
||
|
||
function solutionComplexity(p){
|
||
const areaUnits=Math.max(1,p.valid.length/25),
|
||
paths=Array.isArray(p.solution)?p.solution:[],
|
||
lineCount=Math.max(1,paths.length||p.n.length),
|
||
turns=paths.length
|
||
?paths.map(path=>turnAnalysisRaw(path,p.g).count)
|
||
:p.n.map(n=>n[2]),
|
||
lengths=paths.length?paths.map(path=>path.cells.length):[p.valid.length/lineCount],
|
||
totalTurns=turns.reduce((sum,value)=>sum+value,0),
|
||
avgTurns=totalTurns/lineCount,
|
||
maxTurns=Math.max(0,...turns),
|
||
avgLength=lengths.reduce((sum,value)=>sum+value,0)/lineCount,
|
||
maxLength=Math.max(0,...lengths);
|
||
|
||
// This is intentionally independent of the requested world region. It measures
|
||
// the solution we actually generated:
|
||
// board area + longest/average bend load + longest/average route + pair count.
|
||
const score=
|
||
1+
|
||
1.35*Math.log2(areaUnits)+
|
||
.32*Math.max(0,maxTurns-3)+
|
||
.22*Math.max(0,avgTurns-2.5)+
|
||
.09*Math.max(0,maxLength-8)+
|
||
.12*Math.max(0,avgLength-5)+
|
||
.08*Math.max(0,lineCount-5);
|
||
const rating=Math.max(1,Math.min(10,Math.floor(score+.15)));
|
||
return{rating,score,areaUnits,lineCount,totalTurns,avgTurns,maxTurns,avgLength,maxLength};
|
||
}
|
||
function clueConstrainedDifficulty(p,rating){
|
||
if(rating<=5)return rating;
|
||
const clues=(p.n||[]).map(clue=>Number(clue[2])||0),demanding=clues.filter(value=>value>=4).length;
|
||
// A single short branch should not collapse an otherwise large, demanding
|
||
// board to level 5. Cap only when the board has no meaningful bend load.
|
||
return !clues.length||Math.max(...clues)<4||demanding<Math.max(1,Math.ceil(clues.length*.25))?5:rating;
|
||
}
|
||
|
||
function solverDifficulty(p,targetLevel=null){
|
||
const raw=clueConstrainedDifficulty(p,solutionComplexity(p).rating);
|
||
const target=Number.isInteger(targetLevel)?Math.max(1,Math.min(10,targetLevel)):null;
|
||
if(target==null)return raw;
|
||
// Generation patterns are selected from the regional target. Retain the raw
|
||
// complexity for diagnostics, but classify the playable board at the
|
||
// region's authoritative level so valid level 6-10 boards are not discarded
|
||
// merely because the size-based estimator saturates at an extreme.
|
||
if(raw<=5&&target>=7)return raw;
|
||
return target;
|
||
}
|
||
function generatePuzzle(chunks,seed,level,originX=0,originY=0,generationOptions=null){
|
||
// Macro geography is primary: first search only within the region's allowed band.
|
||
// Among valid candidates, prefer the exact regional target.
|
||
let bestInBand=null,bestInBandScore=Infinity;
|
||
let closest=null,closestScore=Infinity;
|
||
const tries=level<=2?96:level<=5?64:48;
|
||
|
||
for(let attempt=0;attempt<tries;attempt++){
|
||
const p=puzzleCandidateFromPatterns(chunks,seed,level,attempt,originX,originY,generationOptions);
|
||
if(!p)continue;
|
||
|
||
const complexity=solutionComplexity(p),rawRating=clueConstrainedDifficulty(p,complexity.rating),rating=solverDifficulty(p,level);complexity.rawRating=rawRating;complexity.rating=rating;
|
||
p.portSeed=Number.isInteger(generationOptions?.portSeed)?generationOptions.portSeed>>>0:null;
|
||
p.complexity=complexity;
|
||
p.difficulty=rating;
|
||
const linePenalty=p.solution.length<3?6:0;
|
||
const targetDistance=Math.abs(rating-level);
|
||
const intrinsicTie=Math.abs(complexity.score-(level+.25));
|
||
|
||
const score=targetDistance*80+linePenalty+intrinsicTie;
|
||
|
||
if(difficultyFitsRegion(rating,level)&&score<bestInBandScore){
|
||
bestInBand=p;
|
||
bestInBandScore=score;
|
||
}
|
||
|
||
const mismatch=regionMismatch(rating,level);
|
||
const fallbackScore=mismatch*1000+targetDistance*80+linePenalty+intrinsicTie;
|
||
if(fallbackScore<closestScore){
|
||
closest=p;
|
||
closestScore=fallbackScore;
|
||
}
|
||
}
|
||
|
||
if(bestInBand){
|
||
bestInBand.level=bestInBand.difficulty;
|
||
bestInBand.regionalTarget=level;
|
||
return bestInBand;
|
||
}
|
||
|
||
// Keep searching before accepting a regional outlier.
|
||
for(let attempt=tries;attempt<420;attempt++){
|
||
const p=puzzleCandidateFromPatterns(chunks,seed,level,attempt,originX,originY,generationOptions);
|
||
if(!p)continue;
|
||
const complexity=solutionComplexity(p),rawRating=clueConstrainedDifficulty(p,complexity.rating),rating=solverDifficulty(p,level);complexity.rawRating=rawRating;complexity.rating=rating;
|
||
p.portSeed=Number.isInteger(generationOptions?.portSeed)?generationOptions.portSeed>>>0:null;
|
||
p.complexity=complexity;
|
||
p.difficulty=rating;
|
||
|
||
if(difficultyFitsRegion(rating,level)){
|
||
p.level=rating;
|
||
p.regionalTarget=level;
|
||
return p;
|
||
}
|
||
|
||
const mismatch=regionMismatch(rating,level);
|
||
const score=mismatch*1000+Math.abs(rating-level)*80;
|
||
if(score<closestScore){
|
||
closest=p;
|
||
closestScore=score;
|
||
}
|
||
}
|
||
|
||
// This should be rare; caller may reject this shape and try another one.
|
||
if(closest){
|
||
closest.level=closest.difficulty;
|
||
closest.regionalTarget=level;
|
||
closest.regionalOutlier=true;
|
||
return closest;
|
||
}
|
||
throw new Error('Unable to compose routing puzzle for shape');
|
||
}
|
||
const UNIQUENESS_RULE_VERSION=2;
|
||
function textHash(text){let value=0x811c9dc5;for(let index=0;index<text.length;index++){value^=text.charCodeAt(index);value=Math.imul(value,0x01000193)}return hash32(value)}
|
||
function puzzleSignature(puzzle){
|
||
const special=puzzle?.specialCells||{};
|
||
return`${GENERATOR_VERSION}:${UNIQUENESS_RULE_VERSION}:${textHash(JSON.stringify({
|
||
g:puzzle?.g||[],n:puzzle?.n||[],valid:puzzle?.valid||[],obstacles:puzzle?.obstacles||[],
|
||
crossings:special.crossings||[],warps:special.warps||[],locks:special.locks||[],internalGates:special.internalGates||[]
|
||
})).toString(16)}`;
|
||
}
|
||
function physicalEdgeKey(a,b){const left=ckey(...a),right=ckey(...b);return left<right?`${left}|${right}`:`${right}|${left}`}
|
||
function warpPairKey(a,b){return`warp:${physicalEdgeKey(a,b)}`}
|
||
function solutionGridEdges(puzzle){
|
||
const warpKeys=new Set((puzzle?.specialCells?.warps||[]).map(pair=>warpPairKey(pair.a,pair.b))),result=new Set();
|
||
for(const path of puzzle?.solution||[])for(let index=1;index<path.cells.length;index++){
|
||
const a=path.cells[index-1],b=path.cells[index],key=physicalEdgeKey(a,b);
|
||
if(Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1])===1)result.add(key);
|
||
else if(!warpKeys.has(warpPairKey(a,b)))return null;
|
||
}
|
||
return result;
|
||
}
|
||
function routeTurnCount(route,gates,warpKeys,internalGateIndexes=new Set()){
|
||
const start=gates[route.startGate],end=gates[route.endGate],points=[...(internalGateIndexes.has(route.startGate)?[]:[outsideCell(start)]),...route.cells,...(internalGateIndexes.has(route.endGate)?[]:[outsideCell(end)])],directions=[];
|
||
for(let index=1;index<points.length;index++){
|
||
const previous=points[index-1],cell=points[index],distance=Math.abs(previous[0]-cell[0])+Math.abs(previous[1]-cell[1]);
|
||
directions.push(distance===1?[cell[0]-previous[0],cell[1]-previous[1]]:warpKeys.has(warpPairKey(previous,cell))?null:null);
|
||
}
|
||
let turns=0;for(let index=0;index<directions.length-1;index++){const before=directions[index],after=directions[index+1];if(before&&after&&(before[0]!==after[0]||before[1]!==after[1]))turns++}
|
||
return turns;
|
||
}
|
||
function solutionSpecialUsage(puzzle){
|
||
const paths=puzzle?.solution||[],special=puzzle?.specialCells||{},warpPairs=special.warps||[],locks=special.locks||[],crossings=special.crossings||[],internalGates=special.internalGates||[];
|
||
let usedCrossings=0,usedWarps=0,usedLocks=0,usedInternalGates=0;
|
||
for(const cell of crossings){
|
||
const axes=[];for(const path of paths){const index=path.cells?.findIndex(candidate=>sameCell(candidate,cell))??-1;if(index<0)continue;
|
||
const previous=path.cells[index-1],next=path.cells[index+1];if(!previous||!next)continue;
|
||
const horizontal=previous[0]===cell[0]&&next[0]===cell[0],vertical=previous[1]===cell[1]&&next[1]===cell[1];if(horizontal||vertical)axes.push(horizontal?'H':'V');
|
||
}
|
||
if(axes.includes('H')&&axes.includes('V'))usedCrossings++;
|
||
}
|
||
for(const pair of warpPairs)if(paths.some(path=>path.cells?.some((cell,index)=>index>0&&(sameCell(path.cells[index-1],pair.a)&&sameCell(cell,pair.b)||sameCell(path.cells[index-1],pair.b)&&sameCell(cell,pair.a)))))usedWarps++;
|
||
for(const lock of locks)if(paths.some(path=>{const keyIndex=path.cells?.findIndex(cell=>sameCell(cell,lock.key))??-1,doorIndex=path.cells?.findIndex(cell=>sameCell(cell,lock.door))??-1;return keyIndex>=0&&doorIndex>keyIndex}))usedLocks++;
|
||
for(const pair of internalGates)if(paths.some(path=>path.startGate===pair?.a||path.endGate===pair?.a)&&paths.some(path=>path.startGate===pair?.b||path.endGate===pair?.b))usedInternalGates++;
|
||
return{total:crossings.length+warpPairs.length+locks.length+internalGates.length,used:usedCrossings+usedWarps+usedLocks+usedInternalGates,usedCrossings,usedWarps,usedLocks,usedInternalGates};
|
||
}
|
||
function interactionQuality(puzzle,stats,analysis={}){
|
||
const paths=puzzle.solution||[],totalLength=paths.reduce((sum,path)=>sum+(path.cells?.length||0),0),maxLength=Math.max(0,...paths.map(path=>path.cells?.length||0)),
|
||
usage=solutionSpecialUsage(puzzle),specials=usage.total,
|
||
forcedRatio=stats.nodeCount?Math.min(1,stats.rootForced/stats.nodeCount):0,branchPenalty=Math.min(30,Math.log2(Math.max(1,stats.searchNodes))*3),
|
||
monotonyPenalty=Math.max(0,maxLength-Math.max(18,totalLength*.45))*.55,
|
||
redundantClues=Math.max(0,analysis.redundantClues||0),redundantSpecials=Math.max(0,analysis.redundantSpecials??Math.max(0,specials-usage.used)),
|
||
contributingSpecials=Math.max(0,analysis.contributingSpecials??usage.used),unknownQualityChecks=Math.max(0,analysis.unknownQualityChecks||0),
|
||
score=Math.max(0,Math.min(100,48+forcedRatio*24+Math.min(12,contributingSpecials*3)-branchPenalty-monotonyPenalty-redundantClues*5-redundantSpecials*8-unknownQualityChecks));
|
||
return{score,totalLength,maxLength,rootForced:stats.rootForced,searchNodes:stats.searchNodes,maxCandidates:stats.maxCandidates,firstBranchDepth:stats.firstBranchDepth,
|
||
specialCount:specials,specialsUsed:usage.used,contributingSpecials,redundantClues,redundantSpecials,unknownQualityChecks,accepted:score>=20&&redundantSpecials===0};
|
||
}
|
||
function verifyPuzzleUniqueness(puzzle,{maxMs=450,nodeCap=250000,analyzeQuality=true,allowMissingClues=false}={}){
|
||
const started=Date.now(),signature=puzzleSignature(puzzle),finish=(status,extra={})=>({status,signature,ruleVersion:UNIQUENESS_RULE_VERSION,elapsedMs:Date.now()-started,...extra});
|
||
try{
|
||
if(!puzzle||!Array.isArray(puzzle.valid)||!puzzle.valid.length||!Array.isArray(puzzle.g)||!puzzle.g.length||puzzle.g.length%2||!Array.isArray(puzzle.n))return finish('invalid');
|
||
const validSet=new Set(),gateByCell=new Map(),crossings=new Set((puzzle.specialCells?.crossings||[]).map(cell=>ckey(...cell)));
|
||
for(const cell of puzzle.valid){if(!Array.isArray(cell)||cell.length!==2||!Number.isInteger(cell[0])||!Number.isInteger(cell[1])||validSet.has(ckey(...cell)))return finish('invalid');validSet.add(ckey(...cell))}
|
||
for(let index=0;index<puzzle.g.length;index++){const gate=puzzle.g[index],key=ckey(gate?.[0],gate?.[1]);if(!validSet.has(key)||gateByCell.has(key)||crossings.has(key)||!SIDE_D[gate?.[2]])return finish('invalid');gateByCell.set(key,index)}
|
||
const internalGateIndexes=new Set();for(const pair of puzzle.specialCells?.internalGates||[]){const a=pair?.a,b=pair?.b,ga=puzzle.g[a],gb=puzzle.g[b];if(!Number.isInteger(a)||!Number.isInteger(b)||a===b||!ga||!gb||internalGateIndexes.has(a)||internalGateIndexes.has(b))return finish('invalid');const da=SIDE_D[ga[2]],db=SIDE_D[gb[2]];if(Math.abs(ga[0]-gb[0])+Math.abs(ga[1]-gb[1])!==1||ga[0]+da[0]!==gb[0]||ga[1]+da[1]!==gb[1]||gb[0]+db[0]!==ga[0]||gb[1]+db[1]!==ga[1])return finish('invalid');internalGateIndexes.add(a);internalGateIndexes.add(b)}
|
||
const nodes=[],cellNodes=new Map(),addNode=(cell,axis=null)=>{
|
||
const index=nodes.length,key=ckey(...cell);nodes.push({cell:[cell[0],cell[1]],axis,target:axis?2:gateByCell.has(key)?1:2,edges:[],fixed:[]});return index;
|
||
};
|
||
for(const cell of puzzle.valid){const key=ckey(...cell);if(crossings.has(key))cellNodes.set(key,{H:addNode(cell,'H'),V:addNode(cell,'V')});else cellNodes.set(key,{N:addNode(cell,null)})}
|
||
const nodeFor=(cell,axis)=>{const entry=cellNodes.get(ckey(...cell));return entry&&(axis==='H'?entry.H??entry.N:axis==='V'?entry.V??entry.N:entry.N)};
|
||
const edges=[],edgeSeen=new Set(),preferred=solutionGridEdges(puzzle);if(!preferred)return finish('invalid');
|
||
const addEdge=(a,b,axis)=>{
|
||
const physical=physicalEdgeKey(a,b);if(edgeSeen.has(physical))return;edgeSeen.add(physical);
|
||
const left=nodeFor(a,axis),right=nodeFor(b,axis);if(!Number.isInteger(left)||!Number.isInteger(right))return;
|
||
const index=edges.length;edges.push({a:left,b:right,physical,preferred:preferred.has(physical)});nodes[left].edges.push(index);nodes[right].edges.push(index);
|
||
};
|
||
for(const cell of puzzle.valid){const right=[cell[0],cell[1]+1],down=[cell[0]+1,cell[1]];if(validSet.has(ckey(...right)))addEdge(cell,right,'H');if(validSet.has(ckey(...down)))addEdge(cell,down,'V')}
|
||
const warpKeys=new Set();
|
||
for(const pair of puzzle.specialCells?.warps||[]){
|
||
const left=nodeFor(pair?.a),right=nodeFor(pair?.b);if(!Number.isInteger(left)||!Number.isInteger(right)||left===right)return finish('invalid');
|
||
const key=warpPairKey(pair.a,pair.b);if(warpKeys.has(key))return finish('invalid');warpKeys.add(key);nodes[left].fixed.push(right);nodes[right].fixed.push(left);
|
||
}
|
||
for(const lock of puzzle.specialCells?.locks||[])if(!validSet.has(ckey(...(lock?.key||[])))||!validSet.has(ckey(...(lock?.door||[]))))return finish('invalid');
|
||
const state=new Int8Array(edges.length);state.fill(-1);const degreeOn=new Int16Array(nodes.length),unknown=new Int16Array(nodes.length);
|
||
for(let index=0;index<nodes.length;index++){degreeOn[index]=nodes[index].fixed.length;unknown[index]=nodes[index].edges.length;if(degreeOn[index]>nodes[index].target||degreeOn[index]+unknown[index]<nodes[index].target)return finish('invalid')}
|
||
const trail=[],assign=(edgeIndex,value)=>{
|
||
const current=state[edgeIndex];if(current!==-1)return current===value;
|
||
state[edgeIndex]=value;trail.push(edgeIndex);const edge=edges[edgeIndex];
|
||
unknown[edge.a]--;unknown[edge.b]--;if(value){degreeOn[edge.a]++;degreeOn[edge.b]++}return true;
|
||
},rollback=mark=>{while(trail.length>mark){const edgeIndex=trail.pop(),edge=edges[edgeIndex],value=state[edgeIndex];if(value){degreeOn[edge.a]--;degreeOn[edge.b]--}unknown[edge.a]++;unknown[edge.b]++;state[edgeIndex]=-1}};
|
||
const propagate=()=>{
|
||
let changed=true;
|
||
while(changed){changed=false;for(let nodeIndex=0;nodeIndex<nodes.length;nodeIndex++){
|
||
const node=nodes[nodeIndex],need=node.target-degreeOn[nodeIndex];if(need<0||need>unknown[nodeIndex])return false;
|
||
if(!unknown[nodeIndex]||need!==0&&need!==unknown[nodeIndex])continue;const value=need===unknown[nodeIndex]?1:0;
|
||
for(const edgeIndex of node.edges)if(state[edgeIndex]===-1){if(!assign(edgeIndex,value))return false;changed=true}
|
||
}}
|
||
return true;
|
||
};
|
||
const gateByNode=new Map();for(const[key,gateIndex]of gateByCell){const node=nodeFor(key.split(',').map(Number));if(!Number.isInteger(node))return finish('invalid');gateByNode.set(node,gateIndex)}
|
||
const validateSolution=()=>{
|
||
const adjacency=nodes.map(node=>[...node.fixed]);for(let index=0;index<edges.length;index++)if(state[index]===1){const edge=edges[index];adjacency[edge.a].push(edge.b);adjacency[edge.b].push(edge.a)}
|
||
const visited=new Set(),routes=[],routeByNode=new Map();
|
||
for(const[startNode,startGate]of gateByNode){if(visited.has(startNode))continue;let previous=-1,current=startNode,guard=nodes.length+2;const routeNodes=[],cells=[];
|
||
while(guard-->0){if(visited.has(current)&¤t!==startNode)return null;visited.add(current);routeByNode.set(current,routes.length);routeNodes.push(current);cells.push([...nodes[current].cell]);
|
||
if(current!==startNode&&gateByNode.has(current)){const endGate=gateByNode.get(current),forward=startGate<=endGate,routedCells=forward?cells:[...cells].reverse();routes.push({startGate:Math.min(startGate,endGate),endGate:Math.max(startGate,endGate),cells:routedCells,nodes:forward?routeNodes:[...routeNodes].reverse()});break}
|
||
const next=adjacency[current].filter(node=>node!==previous);if(next.length!==1)return null;previous=current;current=next[0];
|
||
}
|
||
if(!routes.length||routes[routes.length-1].nodes.indexOf(startNode)<0)return null;
|
||
}
|
||
if(visited.size!==nodes.length||routes.length*2!==puzzle.g.length)return null;
|
||
for(const cellKey of crossings){const pair=cellNodes.get(cellKey);if(routeByNode.get(pair.H)===routeByNode.get(pair.V))return null}
|
||
const cluesByRoute=routes.map(()=>[]);
|
||
for(const clue of puzzle.n){const entry=cellNodes.get(ckey(clue[0],clue[1])),routeIds=new Set(Object.values(entry||{}).map(node=>routeByNode.get(node)).filter(Number.isInteger));if(routeIds.size!==1)return null;cluesByRoute[[...routeIds][0]].push(clue)}
|
||
for(let index=0;index<routes.length;index++){if(cluesByRoute[index].length>1||!allowMissingClues&&cluesByRoute[index].length!==1)return null;const clue=cluesByRoute[index][0];if(!clue)continue;const route=routes[index],turns=routeTurnCount(route,puzzle.g,warpKeys,internalGateIndexes);if(turns!==clue[2])return null}
|
||
for(const lock of puzzle.specialCells?.locks||[]){const keyEntry=cellNodes.get(ckey(...lock.key)),doorEntry=cellNodes.get(ckey(...lock.door)),keyRoutes=new Set(Object.values(keyEntry||{}).map(node=>routeByNode.get(node))),doorRoutes=new Set(Object.values(doorEntry||{}).map(node=>routeByNode.get(node)));if(![...keyRoutes].some(id=>doorRoutes.has(id)))return null}
|
||
return routes.sort((left,right)=>left.startGate-right.startGate||left.endGate-right.endGate).map(route=>`${route.startGate}-${route.endGate}:${route.cells.map(cell=>ckey(...cell)).join(';')}`).join('|');
|
||
};
|
||
let searchNodes=0,timedOut=false,maxCandidates=0,firstBranchDepth=null,rootForced=0;const canonical=new Set();
|
||
if(!propagate())return finish('unsolved',{solutions:0,nodes:0});rootForced=trail.length;
|
||
const search=depth=>{
|
||
if(canonical.size>=2)return;if(++searchNodes>nodeCap||((searchNodes&1023)===0&&Date.now()-started>maxMs)){timedOut=true;return}
|
||
if(!propagate())return;
|
||
let chosen=-1,bestUnknown=Infinity;
|
||
for(let nodeIndex=0;nodeIndex<nodes.length;nodeIndex++){const need=nodes[nodeIndex].target-degreeOn[nodeIndex];if(need<=0||!unknown[nodeIndex])continue;if(unknown[nodeIndex]<bestUnknown){bestUnknown=unknown[nodeIndex];chosen=nodes[nodeIndex].edges.find(edgeIndex=>state[edgeIndex]===-1&&edges[edgeIndex].preferred);if(chosen==null||chosen<0)chosen=nodes[nodeIndex].edges.find(edgeIndex=>state[edgeIndex]===-1);if(bestUnknown===1)break}}
|
||
if(chosen<0){const key=validateSolution();if(key)canonical.add(key);return}
|
||
if(firstBranchDepth==null)firstBranchDepth=depth;maxCandidates=Math.max(maxCandidates,bestUnknown);const mark=trail.length,order=edges[chosen].preferred?[1,0]:[0,1];
|
||
for(const value of order){if(assign(chosen,value))search(depth+1);rollback(mark);if(canonical.size>=2||timedOut)break}
|
||
};
|
||
search(0);
|
||
if(canonical.size>=2)return finish('multiple',{solutions:2,nodes:searchNodes});
|
||
if(timedOut)return finish('timeout',{solutions:canonical.size,nodes:searchNodes});
|
||
if(!canonical.size)return finish('unsolved',{solutions:0,nodes:searchNodes});
|
||
const stats={nodeCount:nodes.length,rootForced,searchNodes,maxCandidates,firstBranchDepth:firstBranchDepth??0};
|
||
let qualityAnalysis={};
|
||
if(analyzeQuality){
|
||
const usage=solutionSpecialUsage(puzzle),remaining=()=>Math.max(0,maxMs-(Date.now()-started)),checks=[];
|
||
for(let index=0;index<Math.min(4,puzzle.n.length);index++)checks.push({type:'clue',index});
|
||
for(let index=0;index<Math.min(2,puzzle.specialCells?.locks?.length||0);index++)checks.push({type:'lock',index});
|
||
let redundantClues=0,redundantSpecials=Math.max(0,usage.total-usage.used),contributingSpecials=usage.used,unknownQualityChecks=0;
|
||
for(let checkIndex=0;checkIndex<checks.length;checkIndex++){
|
||
const budget=Math.min(70,Math.floor(remaining()/Math.max(1,checks.length-checkIndex)));if(budget<12){unknownQualityChecks+=checks.length-checkIndex;break}
|
||
const check=checks[checkIndex],relaxed=JSON.parse(JSON.stringify(puzzle));
|
||
if(check.type==='clue')relaxed.n.splice(check.index,1);
|
||
else relaxed.specialCells.locks.splice(check.index,1);
|
||
const result=verifyPuzzleUniqueness(relaxed,{maxMs:budget,nodeCap:Math.min(30000,nodeCap),analyzeQuality:false,allowMissingClues:check.type==='clue'});
|
||
if(result.status==='timeout'||result.status==='invalid')unknownQualityChecks++;
|
||
else if(result.status==='unique'){
|
||
if(check.type==='clue')redundantClues++;
|
||
else{redundantSpecials++;contributingSpecials=Math.max(0,contributingSpecials-1)}
|
||
}
|
||
}
|
||
qualityAnalysis={redundantClues,redundantSpecials,contributingSpecials,unknownQualityChecks,checksRun:checks.length-unknownQualityChecks};
|
||
}
|
||
const quality=interactionQuality(puzzle,stats,qualityAnalysis);
|
||
return finish('unique',{solutions:1,nodes:searchNodes,quality});
|
||
}catch(error){return finish('invalid',{error:error?.message||String(error)})}
|
||
}
|
||
const api=Object.freeze({GENERATOR_VERSION,UNIQUENESS_RULE_VERSION,key2,ckey,sameCell,hash32,rngFrom,shuffle,macroDifficulty,difficultyFitsRegion,DIFFICULTY_DEFINITIONS,difficultyDefinition,SHAPES,H_PORT_PROFILES,V_PORT_PROFILES,horizontalBoundaryKey,verticalBoundaryKey,solutionComplexity,solverDifficulty,generatePuzzle,puzzleSignature,verifyPuzzleUniqueness});
|
||
root.BendPuzzle=api;if(typeof module==='object'&&module.exports)module.exports=api;
|
||
})(typeof self!=='undefined'?self:globalThis);
|