Experimental
MAZE SOLVER
Paste maze data or load a file to see how different algorithms find the optimal path. Visualize the search frontier and final route.
Size: -
Explored: 0
Path: 0 steps
Status: Ready
Developer Reference
Core Algorithm & Standalone Script
Standalone, zero-dependency JavaScript implementation powering this tool. Free to inspect, copy, and build upon.
const canvas = document.getElementById('mazeCanvas');
const ctx = canvas.getContext('2d');
const solveBtn = document.getElementById('solveBtn');
const stopBtn = document.getElementById('stopBtn');
const btnText = document.getElementById('btnText');
let maze = null;
let isSolving = false;
let exploredCount = 0;
let pixelBFSState = null; // holds { bin, w, h, lft, top, rgt, bot } for pixel-BFS
class Maze {
constructor(data) {
this.width = data.width;
this.height = data.height;
this.grid = data.grid.map(row => row.map(cell => ({
walls: cell.w,
visited: false,
parent: null,
g: Infinity,
f: Infinity
})));
this.maxW = 800;
this.cellSize = Math.max(4, Math.floor(this.maxW / Math.max(this.width, this.height)));
this.wallWeight = Math.max(1, Math.floor(this.cellSize / 5));
}
drawWall(x, y, colorWall = '#ff2200', colorPath = '#0a0a0a') {
const px = x * this.cellSize;
const py = y * this.cellSize;
const cell = this.grid[y][x];
ctx.fillStyle = colorPath;
ctx.fillRect(px, py, this.cellSize, this.cellSize);
ctx.strokeStyle = colorWall;
ctx.lineWidth = this.wallWeight;
ctx.lineCap = 'square';
if (cell.walls.top) { ctx.beginPath(); ctx.moveTo(px, py); ctx.lineTo(px + this.cellSize, py); ctx.stroke(); }
if (cell.walls.right) { ctx.beginPath(); ctx.moveTo(px + this.cellSize, py); ctx.lineTo(px + this.cellSize, py + this.cellSize); ctx.stroke(); }
if (cell.walls.bottom) { ctx.beginPath(); ctx.moveTo(px + this.cellSize, py + this.cellSize); ctx.lineTo(px, py + this.cellSize); ctx.stroke(); }
if (cell.walls.left) { ctx.beginPath(); ctx.moveTo(px, py + this.cellSize); ctx.lineTo(px, py); ctx.stroke(); }
}
reset() {
for (let y = 0; y < this.height; y++) {
for (let x = 0; x < this.width; x++) {
const cell = this.grid[y][x];
cell.visited = false;
cell.parent = null;
cell.g = Infinity;
cell.f = Infinity;
}
}
}
drawGrid() {
canvas.width = this.width * this.cellSize;
canvas.height = this.height * this.cellSize;
for (let y = 0; y < this.height; y++) {
for (let x = 0; x < this.width; x++) {
this.drawWall(x, y);
}
}
// Highlight start and end
this.highlightCell(0, 0, '#00ff00'); // Start
this.highlightCell(this.width - 1, this.height - 1, '#ff0000'); // End
}
highlightCell(x, y, color) {
const px = x * this.cellSize;
const py = y * this.cellSize;
const offset = this.wallWeight;
ctx.fillStyle = color;
ctx.fillRect(px + offset, py + offset, this.cellSize - offset*2, this.cellSize - offset*2);
}
}
async function solveMaze() {
if (isSolving) return;
const algo = document.getElementById('algorithm').value;
const speed = parseInt(document.getElementById('speed').value);
const expColor = document.getElementById('expColor').value;
const solColor = document.getElementById('solColor').value;
// ── Pixel BFS mode: operates directly on the uploaded image ──────────
if (algo === 'pixelbfs') {
if (!uploadedImage) {
alert("Pixel BFS requires an uploaded image. Please upload a maze image first."); return;
}
isSolving = true;
solveBtn.disabled = true;
btnText.innerText = "Solving...";
stopBtn.style.display = 'block';
exploredCount = 0;
document.getElementById('statExplored').innerHTML = `Explored: <b>0</b>`;
document.getElementById('statSteps').innerHTML = `Path: <b>0 steps</b>`;
document.getElementById('statStatus').innerHTML = `Status: <b>Running...</b>`;
const pathFound = await runPixelBFS(uploadedImage, manualThreshold, speed, expColor, solColor);
if (!pathFound) alert("No path found! Try adjusting the threshold or choosing start/end points near open passages.");
finishSolving();
return;
}
// ── JSON / wall-graph modes ───────────────────────────────────────────
const input = document.getElementById('mazeInput').value;
if (!input) { alert("Please paste maze JSON first (or select Pixel BFS to solve directly from an image)."); return; }
try {
const data = JSON.parse(input);
maze = new Maze(data);
maze.reset();
maze.drawGrid();
} catch (e) {
alert("Invalid JSON format."); return;
}
document.getElementById('statSize').innerHTML = `Size: <b>${maze.width}x${maze.height}</b>`;
document.getElementById('statExplored').innerHTML = `Explored: <b>0</b>`;
document.getElementById('statSteps').innerHTML = `Path: <b>0 steps</b>`;
isSolving = true;
solveBtn.disabled = true;
btnText.innerText = "Solving...";
stopBtn.style.display = 'block';
exploredCount = 0;
const start = { x: 0, y: 0 };
const end = { x: maze.width - 1, y: maze.height - 1 };
maze.grid[start.y][start.x].visited = true;
maze.grid[start.y][start.x].g = 0;
let pathFound = false;
if (algo === 'bfs') pathFound = await runBFS(start, end, speed, expColor);
else if (algo === 'dfs') pathFound = await runDFS(start, end, speed, expColor);
else if (algo === 'astar') pathFound = await runAStar(start, end, speed, expColor);
else if (algo === 'dijkstra') pathFound = await runDijkstra(start, end, speed, expColor);
if (pathFound) {
await drawPath(end, solColor);
document.getElementById('statStatus').innerHTML = `Status: <b>Solved!</b>`;
} else {
alert("No path found!");
}
finishSolving();
}
// ── Pixel-space BFS ──────────────────────────────────────────────────────
// Works directly on the binary pixel array — no grid conversion needed.
// Start = first passable pixel near top-left corner of the maze bounding box.
// End = first passable pixel near bottom-right corner.
// Passable pixel = bin[y*w+x] === 0 (path, not wall).
// Explores 4-connected neighbors. Downsamples by pixelStep to stay fast.
async function runPixelBFS(img, userThreshold, speed, expColor, solColor) {
const { bin, w, h, lft, top, rgt, bot } = getBinaryData(img, userThreshold);
const mw = rgt - lft + 1, mh = bot - top + 1;
// Draw image onto canvas so we can overlay the path
canvas.width = mw;
canvas.height = mh;
const imgCanvas = document.createElement('canvas');
imgCanvas.width = w; imgCanvas.height = h;
imgCanvas.getContext('2d').drawImage(img, 0, 0);
ctx.drawImage(imgCanvas, lft, top, mw, mh, 0, 0, mw, mh);
document.getElementById('statSize').innerHTML = `Size: <b>${mw}×${mh}px</b>`;
// Downsample step — larger = faster but less accurate.
// Aim for ~300px in the shorter dimension.
const pixelStep = Math.max(1, Math.floor(Math.min(mw, mh) / 300));
// Find start: scan inward from top-left corner for first passable pixel
const findPassable = (x0, y0, dx, dy) => {
for (let d = 0; d < Math.max(mw, mh); d++) {
const px = x0 + dx * d, py = y0 + dy * d;
if (px < lft || px > rgt || py < top || py > bot) break;
if (!bin[py * w + px]) return { x: px - lft, y: py - top };
}
return null;
};
// Try corner-searching in 4 directions to find open start/end
const startPx = findPassable(lft, top, 1, 0)
|| findPassable(lft, top, 0, 1)
|| findPassable(lft + Math.floor(mw*0.1), top, 0, 1);
const endPx = findPassable(rgt, bot, -1, 0)
|| findPassable(rgt, bot, 0, -1)
|| findPassable(rgt - Math.floor(mw*0.1), bot, 0, -1);
if (!startPx || !endPx) return false;
// Mark start and end visually
ctx.fillStyle = '#00ff00'; ctx.fillRect(startPx.x - 3, startPx.y - 3, 6, 6);
ctx.fillStyle = '#ff0000'; ctx.fillRect(endPx.x - 3, endPx.y - 3, 6, 6);
// BFS on downsampled pixels
const visited = new Uint8Array(mw * mh);
const parentX = new Int32Array(mw * mh).fill(-1);
const parentY = new Int32Array(mw * mh).fill(-1);
const idx = (x, y) => y * mw + x;
const sx = startPx.x - (startPx.x % pixelStep);
const sy = startPx.y - (startPx.y % pixelStep);
const ex = endPx.x - (endPx.x % pixelStep);
const ey = endPx.y - (endPx.y % pixelStep);
visited[idx(sx, sy)] = 1;
const queue = [sx, sy]; // flat array queue for speed
let qi = 0;
const dirs = [[pixelStep, 0], [-pixelStep, 0], [0, pixelStep], [0, -pixelStep]];
const expRGB = hexToRGB(expColor);
let frameCount = 0;
const batchSize = speed >= 95 ? 10000 : speed >= 80 ? 1000 : speed >= 50 ? 200 : 50;
let found = false;
while (qi < queue.length && isSolving) {
const x = queue[qi++], y = queue[qi++];
exploredCount++;
frameCount++;
if (x === ex && y === ey) { found = true; break; }
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || ny < 0 || nx >= mw || ny >= mh) continue;
if (visited[idx(nx, ny)]) continue;
// Check if all pixels in the step are passable (wall-free)
let blocked = false;
for (let s = 1; s <= pixelStep && !blocked; s++) {
const cx = x + Math.round(dx * s / pixelStep);
const cy = y + Math.round(dy * s / pixelStep);
if (bin[(top + cy) * w + (lft + cx)]) blocked = true;
}
if (blocked) continue;
visited[idx(nx, ny)] = 1;
parentX[idx(nx, ny)] = x;
parentY[idx(nx, ny)] = y;
queue.push(nx, ny);
}
// Batch canvas updates for performance
if (frameCount >= batchSize) {
frameCount = 0;
// Paint explored batch
const imgData = ctx.getImageData(0, 0, mw, mh);
for (let bi = Math.max(0, qi - batchSize * 2); bi < qi; bi += 2) {
const bx = queue[bi], by = queue[bi + 1];
if (bx === undefined) continue;
const p = (by * mw + bx) * 4;
imgData.data[p] = expRGB[0];
imgData.data[p+1] = expRGB[1];
imgData.data[p+2] = expRGB[2];
imgData.data[p+3] = 180;
}
ctx.putImageData(imgData, 0, 0);
document.getElementById('statExplored').innerHTML = `Explored: <b>${exploredCount}</b>`;
if (speed < 95) await new Promise(r => setTimeout(r, Math.round((100 - speed) * 0.5)));
}
}
if (!found) return false;
// Trace and draw path
const solRGB = hexToRGB(solColor);
let cx = ex, cy = ey, steps = 0;
const pathImgData = ctx.getImageData(0, 0, mw, mh);
while (cx !== -1 && cy !== -1) {
for (let py = cy; py < cy + pixelStep && py < mh; py++) {
for (let px = cx; px < cx + pixelStep && px < mw; px++) {
const p = (py * mw + px) * 4;
pathImgData.data[p] = solRGB[0];
pathImgData.data[p+1] = solRGB[1];
pathImgData.data[p+2] = solRGB[2];
pathImgData.data[p+3] = 255;
}
}
steps++;
const pi = idx(cx, cy);
const nx = parentX[pi], ny = parentY[pi];
cx = nx; cy = ny;
if (steps % 50 === 0) {
ctx.putImageData(pathImgData, 0, 0);
document.getElementById('statSteps').innerHTML = `Path: <b>${steps} steps</b>`;
await new Promise(r => setTimeout(r, 8));
}
}
ctx.putImageData(pathImgData, 0, 0);
document.getElementById('statSteps').innerHTML = `Path: <b>${steps} steps</b>`;
document.getElementById('statExplored').innerHTML = `Explored: <b>${exploredCount}</b>`;
document.getElementById('statStatus').innerHTML = `Status: <b>Solved!</b>`;
return true;
}
function hexToRGB(hex) {
const h = hex.replace('#', '');
return [parseInt(h.slice(0,2),16), parseInt(h.slice(2,4),16), parseInt(h.slice(4,6),16)];
}
async function runBFS(start, end, speed, color) {
const queue = [start];
maze.grid[start.y][start.x].visited = true;
while (queue.length > 0 && isSolving) {
const current = queue.shift();
exploredCount++;
document.getElementById('statExplored').innerHTML = `Explored: <b>${exploredCount}</b>`;
if (current.x === end.x && current.y === end.y) return true;
maze.highlightCell(current.x, current.y, color);
const neighbors = getValidNeighbors(current);
for (const next of neighbors) {
if (!maze.grid[next.y][next.x].visited) {
maze.grid[next.y][next.x].visited = true;
maze.grid[next.y][next.x].parent = current;
queue.push(next);
}
}
if (speed < 100) await new Promise(r => setTimeout(r, 101 - speed));
}
return false;
}
async function runDFS(start, end, speed, color) {
const stack = [start];
maze.grid[start.y][start.x].visited = true;
while (stack.length > 0 && isSolving) {
const current = stack.pop();
exploredCount++;
document.getElementById('statExplored').innerHTML = `Explored: <b>${exploredCount}</b>`;
if (current.x === end.x && current.y === end.y) return true;
maze.highlightCell(current.x, current.y, color);
const neighbors = getValidNeighbors(current);
for (const next of neighbors) {
if (!maze.grid[next.y][next.x].visited) {
maze.grid[next.y][next.x].visited = true;
maze.grid[next.y][next.x].parent = current;
stack.push(next);
}
}
if (speed < 100) await new Promise(r => setTimeout(r, 101 - speed));
}
return false;
}
async function runAStar(start, end, speed, color) {
const openSet = [start];
maze.grid[start.y][start.x].g = 0;
maze.grid[start.y][start.x].f = heuristic(start, end);
while (openSet.length > 0 && isSolving) {
// Find node in openSet with lowest f
let lowIdx = 0;
for (let i = 0; i < openSet.length; i++) {
if (maze.grid[openSet[i].y][openSet[i].x].f < maze.grid[openSet[lowIdx].y][openSet[lowIdx].x].f) {
lowIdx = i;
}
}
const current = openSet.splice(lowIdx, 1)[0];
exploredCount++;
document.getElementById('statExplored').innerHTML = `Explored: <b>${exploredCount}</b>`;
if (current.x === end.x && current.y === end.y) return true;
maze.highlightCell(current.x, current.y, color);
const neighbors = getValidNeighbors(current);
for (const next of neighbors) {
const tentativeG = maze.grid[current.y][current.x].g + 1;
if (tentativeG < maze.grid[next.y][next.x].g) {
maze.grid[next.y][next.x].parent = current;
maze.grid[next.y][next.x].g = tentativeG;
maze.grid[next.y][next.x].f = tentativeG + heuristic(next, end);
if (!openSet.some(p => p.x === next.x && p.y === next.y)) {
openSet.push(next);
}
}
}
if (speed < 100) await new Promise(r => setTimeout(r, 101 - speed));
}
return false;
}
// ── Min-heap for Dijkstra ────────────────────────────────────────────────
class MinHeap {
constructor() { this.h = []; }
push(item) {
this.h.push(item);
this._up(this.h.length - 1);
}
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length > 0) { this.h[0] = last; this._down(0); }
return top;
}
get size() { return this.h.length; }
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p].dist <= this.h[i].dist) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p;
}
}
_down(i) {
const n = this.h.length;
while (true) {
let s = i, l = 2*i+1, r = 2*i+2;
if (l < n && this.h[l].dist < this.h[s].dist) s = l;
if (r < n && this.h[r].dist < this.h[s].dist) s = r;
if (s === i) break;
[this.h[s], this.h[i]] = [this.h[i], this.h[s]]; i = s;
}
}
}
async function runDijkstra(start, end, speed, color) {
const dist = Array.from({ length: maze.height }, () => new Array(maze.width).fill(Infinity));
dist[start.y][start.x] = 0;
maze.grid[start.y][start.x].g = 0;
const pq = new MinHeap();
pq.push({ dist: 0, x: start.x, y: start.y });
while (pq.size > 0 && isSolving) {
const { dist: d, x, y } = pq.pop();
// Skip stale entries
if (d > dist[y][x]) continue;
exploredCount++;
document.getElementById('statExplored').innerHTML = `Explored: <b>${exploredCount}</b>`;
if (x === end.x && y === end.y) return true;
maze.highlightCell(x, y, color);
for (const next of getValidNeighbors({ x, y })) {
const newDist = dist[y][x] + 1;
if (newDist < dist[next.y][next.x]) {
dist[next.y][next.x] = newDist;
maze.grid[next.y][next.x].g = newDist;
maze.grid[next.y][next.x].parent = { x, y };
pq.push({ dist: newDist, x: next.x, y: next.y });
}
}
if (speed < 100) await new Promise(r => setTimeout(r, 101 - speed));
}
return false;
}
function heuristic(a, b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
function getValidNeighbors(p) {
const neighbors = [];
const cell = maze.grid[p.y][p.x];
if (!cell.walls.top) neighbors.push({ x: p.x, y: p.y - 1 });
if (!cell.walls.right) neighbors.push({ x: p.x + 1, y: p.y });
if (!cell.walls.bottom) neighbors.push({ x: p.x, y: p.y + 1 });
if (!cell.walls.left) neighbors.push({ x: p.x - 1, y: p.y });
return neighbors;
}
async function drawPath(end, color) {
let current = end;
let steps = 0;
while (current) {
maze.highlightCell(current.x, current.y, color);
current = maze.grid[current.y][current.x].parent;
steps++;
document.getElementById('statSteps').innerHTML = `Path: <b>${steps} steps</b>`;
await new Promise(r => setTimeout(r, 10));
}
}
function finishSolving() {
isSolving = false;
solveBtn.disabled = false;
btnText.innerText = "Solve Maze";
stopBtn.style.display = 'none';
}
stopBtn.onclick = () => { isSolving = false; finishSolving(); };
solveBtn.onclick = solveMaze;
function loadSample() {
const sample = {"width":20,"height":20,"grid":[[{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":true,"left":false}}],[{"w":{"top":false,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":false,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":false,"right":true,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":false,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":false,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":false,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":0,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":true,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":0,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":true}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":false,"bottom":false,"left":false}},{"w":{"top":true,"right":true,"bottom":false,"left":false}}],[{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":true}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":false,"bottom":true,"left":false}},{"w":{"top":false,"right":true,"bottom":true,"left":false}}],[{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":true}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":false,"bottom":true,"left":false}},{"w":{"top":true,"right":true,"bottom":true,"left":false}}]]};
document.getElementById('mazeInput').value = JSON.stringify(sample);
alert("Sample maze loaded! Click 'Solve Maze' to see it in action.");
}
function exportSolution() {
if (!maze) return;
const link = document.createElement('a');
link.download = `maze_solution_${maze.width}x${maze.height}.png`;
link.href = canvas.toDataURL();
link.click();
}
let uploadedImage = null;
let analysisMode = 'diagonal'; // 'diagonal' | 'standard'
let manualThreshold = null; // null = auto Otsu
function setAnalysisMode(mode) {
analysisMode = mode;
const diagBtn = document.getElementById('modeDiagBtn');
const stdBtn = document.getElementById('modeStdBtn');
const desc = document.getElementById('modeDesc');
if (mode === 'diagonal') {
diagBtn.style.border = '1px solid var(--accent)';
diagBtn.style.background = 'rgba(255,34,0,0.15)';
diagBtn.style.color = 'var(--accent)';
stdBtn.style.border = '1px solid var(--border)';
stdBtn.style.background = 'transparent';
stdBtn.style.color = 'var(--muted)';
desc.textContent = 'Reads pixels diagonally. Uses cell hypotenuse \u221A(w\u00B2+h\u00B2) to count grid blocks.';
} else {
stdBtn.style.border = '1px solid var(--accent)';
stdBtn.style.background = 'rgba(255,34,0,0.15)';
stdBtn.style.color = 'var(--accent)';
diagBtn.style.border = '1px solid var(--border)';
diagBtn.style.background = 'transparent';
diagBtn.style.color = 'var(--muted)';
desc.textContent = 'Projects wall pixels onto X/Y axes to detect cell grid dimensions.';
}
}
function onThresholdChange(val) {
const v = parseInt(val);
manualThreshold = v === 0 ? null : v;
document.getElementById('threshLabel').textContent = v === 0 ? 'Auto (Otsu)' : v;
if (uploadedImage) updateBWPreview();
}
function updateBWPreview() {
if (!uploadedImage) return;
const { dataURL, thresh } = getBWPreview(uploadedImage, manualThreshold);
document.getElementById('bwPreview').src = dataURL;
if (manualThreshold === null)
document.getElementById('threshLabel').textContent = `Auto \u2192 ${thresh}`;
}
function handleFileUpload(file) {
if (!file) return;
if (file.type.startsWith('image/')) {
const reader = new FileReader();
reader.onload = e => {
const img = new Image();
img.onload = () => {
uploadedImage = img;
document.getElementById('uploadPreview').src = img.src;
document.getElementById('threshSlider').value = 0;
manualThreshold = null;
updateBWPreview();
document.getElementById('pngControls').style.display = 'block';
};
img.src = e.target.result;
};
reader.readAsDataURL(file);
return;
}
const reader = new FileReader();
reader.onload = e => {
document.getElementById('mazeInput').value = e.target.result;
document.getElementById('pngControls').style.display = 'none';
alert("JSON file loaded!");
};
reader.readAsText(file);
}
// ── Shared: build binary data from image ────────────────────────────────
function computeOtsu(brightArr) {
const hist = new Array(256).fill(0);
for (const b of brightArr) hist[b]++;
const total = brightArr.length;
let sumAll = 0;
for (let t = 0; t < 256; t++) sumAll += t * hist[t];
let sumB = 0, wB = 0, best = 0, threshold = 128;
for (let t = 0; t < 256; t++) {
wB += hist[t]; if (!wB) continue;
const wF = total - wB; if (!wF) break;
sumB += t * hist[t];
const between = wB * wF * ((sumB / wB) - (sumAll - sumB) / wF) ** 2;
if (between > best) { best = between; threshold = t; }
}
return threshold;
}
function getBinaryData(img, userThreshold) {
const oc = document.createElement('canvas');
oc.width = img.width;
oc.height = img.height;
const oCtx = oc.getContext('2d');
oCtx.drawImage(img, 0, 0);
const w = oc.width, h = oc.height;
const pixels = oCtx.getImageData(0, 0, w, h).data;
const bright = new Uint8Array(w * h);
for (let i = 0; i < w * h; i++)
bright[i] = Math.round((pixels[i*4] + pixels[i*4+1] + pixels[i*4+2]) / 3);
const thresh = (userThreshold != null) ? userThreshold : computeOtsu(bright);
const cornerAvg = (bright[0] + bright[w-1] + bright[(h-1)*w] + bright[h*w-1]) / 4;
const wallsAreBright = cornerAvg > thresh;
const bin = new Uint8Array(w * h);
for (let i = 0; i < w * h; i++)
bin[i] = wallsAreBright ? (bright[i] > thresh ? 1 : 0) : (bright[i] <= thresh ? 1 : 0);
let top = 0, bot = h-1, lft = 0, rgt = w-1;
o1: for (let y=0;y<h;y++) for (let x=0;x<w;x++) if (bin[y*w+x]) { top=y; break o1; }
o2: for (let y=h-1;y>=0;y--) for (let x=0;x<w;x++) if (bin[y*w+x]) { bot=y; break o2; }
o3: for (let x=0;x<w;x++) for (let y=0;y<h;y++) if (bin[y*w+x]) { lft=x; break o3; }
o4: for (let x=w-1;x>=0;x--) for (let y=0;y<h;y++) if (bin[y*w+x]) { rgt=x; break o4; }
return { bin, w, h, thresh, top, bot, lft, rgt };
}
// ── B&W preview ─────────────────────────────────────────────────────────
function getBWPreview(img, userThreshold) {
const { bin, w, h, thresh } = getBinaryData(img, userThreshold);
const pc = document.createElement('canvas');
pc.width = w; pc.height = h;
const pCtx = pc.getContext('2d');
const id = pCtx.createImageData(w, h);
for (let i = 0; i < w * h; i++) {
const v = bin[i] ? 0 : 255;
id.data[i*4] = v;
id.data[i*4+1] = v;
id.data[i*4+2] = v;
id.data[i*4+3] = 255;
}
pCtx.putImageData(id, 0, 0);
return { dataURL: pc.toDataURL(), thresh };
}
// ── 1D projection cell-count (standard mode) ────────────────────────────
// Uses proper local-maxima peak-finding instead of a fixed ratio threshold.
// Steps:
// 1. Smooth the projection with a small box filter to suppress single-pixel noise.
// 2. Find local maxima peaks — each peak is a wall column/row.
// 3. Merge peaks that are too close together (sub-pixel duplicates).
// 4. Cell count = number of wall peaks - 1.
function detectCellCount(projection) {
const size = projection.length;
if (size < 3) return 1;
// 1. Box-filter smooth (window = ~1% of size, min 3)
const win = Math.max(3, Math.round(size * 0.01)) | 1; // force odd
const half = (win - 1) >> 1;
const smooth = new Float32Array(size);
let acc = 0;
for (let i = 0; i < win; i++) acc += projection[i];
for (let i = 0; i < size; i++) {
smooth[i] = acc / win;
const drop = i - half;
const add = i + half + 1;
if (drop >= 0) acc -= projection[drop];
if (add < size) acc += projection[add];
}
const maxVal = Math.max(...smooth);
if (!maxVal) return 1;
// Adaptive noise floor: peaks must be at least 15% of the max
const noiseFloor = maxVal * 0.15;
// 2. Collect local maxima above noise floor
const peaks = [];
for (let i = 1; i < size - 1; i++) {
if (smooth[i] > noiseFloor && smooth[i] >= smooth[i-1] && smooth[i] >= smooth[i+1]) {
// Refine peak position with parabolic interpolation
const denom = smooth[i-1] - 2*smooth[i] + smooth[i+1];
const pos = denom !== 0 ? i - 0.5*(smooth[i+1]-smooth[i-1])/denom : i;
peaks.push(pos);
}
}
// Edge peaks
if (smooth[0] > noiseFloor && smooth[0] > smooth[1]) peaks.unshift(0);
if (smooth[size-1] > noiseFloor && smooth[size-1] > smooth[size-2]) peaks.push(size-1);
if (peaks.length < 2) return 1;
// 3. Merge peaks closer than minGap (estimated cell width / 4)
const estCellWidth = size / Math.max(peaks.length - 1, 1);
const minGap = Math.max(2, estCellWidth * 0.25);
const merged = [peaks[0]];
for (let i = 1; i < peaks.length; i++) {
if (peaks[i] - merged[merged.length-1] >= minGap) merged.push(peaks[i]);
}
return Math.max(1, merged.length - 1);
}
// ── Diagonal hypotenuse-based cell detection ────────────────────────────
//
// Scans several parallel diagonals (primary TL→BR and anti TR→BL, plus
// perpendicular offsets) to count wall↔path transitions.
//
// K = median_transitions / 2 → cells crossed by the diagonal.
// For an M×N maze: K = M+N−gcd(M,N).
//
// Recover (cols, rows) via integer search over candidate row counts,
// using aspect ratio r = mw/mh ≈ cols/rows (assumes square cells).
// This correctly handles non-square mazes — the old cellHyp/√2 formula
// only worked for square mazes where K=M=N.
//
// Examples:
// K=20, r=1 → rows=20, cols=20, gcd=20, fit=20 ✓ (20×20)
// K=40, r=2/3 → rows=30, cols=20, gcd=10, fit=40 ✓ (20×30)
function gcd(a, b) { while (b) { const t = b; b = a % b; a = t; } return a; }
function solveGridDimensions(K, r) {
// Score by combined K-fit error + weighted aspect-ratio error.
// Pure K-fit isn't unique: e.g. K=40 is satisfied by both (8,33) and
// (10,40) when r=0.25 — aspect error resolves such ties correctly.
let bestCols = 1, bestRows = 1, bestScore = Infinity;
for (let rows = 1; rows <= K * 2; rows++) {
const cols = Math.max(1, Math.round(rows * r));
const fit = cols + rows - gcd(cols, rows);
const errK = Math.abs(fit - K);
const errR = Math.abs(cols / rows - r) / Math.max(r, 1e-6);
const score = errK + errR * K * 0.3;
if (score < bestScore) { bestScore = score; bestCols = cols; bestRows = rows; }
}
return { cols: bestCols, rows: bestRows };
}
function detectByDiagonal(bin, lft, top, rgt, bot, w) {
const mw = rgt - lft + 1;
const mh = bot - top + 1;
const diagLen = Math.sqrt(mw * mw + mh * mh);
const countTransitions = (x0, y0, x1, y1) => {
const nSamples = Math.ceil(diagLen);
let prev = -1, trans = 0;
for (let i = 0; i < nSamples; i++) {
const t = i / (nSamples - 1);
const px = Math.max(lft, Math.min(rgt, Math.round(x0 + (x1 - x0) * t)));
const py = Math.max(top, Math.min(bot, Math.round(y0 + (y1 - y0) * t)));
const v = bin[py * w + px];
if (v !== prev && prev !== -1) trans++;
prev = v;
}
return trans;
};
const shorter = Math.min(mw, mh);
const offFracs = [-0.25, -0.1, 0, 0.1, 0.25];
const transCounts = [];
for (const frac of offFracs) {
const shift = Math.round(frac * shorter);
const ox = Math.round(-mh * shift / diagLen);
const oy = Math.round( mw * shift / diagLen);
const x0p = lft + ox, y0p = top + oy;
const x1p = rgt + ox, y1p = bot + oy;
if (x0p >= lft && x0p <= rgt && y0p >= top && y0p <= bot &&
x1p >= lft && x1p <= rgt && y1p >= top && y1p <= bot)
transCounts.push(countTransitions(x0p, y0p, x1p, y1p));
const x0a = rgt - ox, y0a = top + oy;
const x1a = lft - ox, y1a = bot + oy;
if (x0a >= lft && x0a <= rgt && y0a >= top && y0a <= bot &&
x1a >= lft && x1a <= rgt && y1a >= top && y1a <= bot)
transCounts.push(countTransitions(x0a, y0a, x1a, y1a));
}
transCounts.push(countTransitions(lft, top, rgt, bot));
transCounts.push(countTransitions(rgt, top, lft, bot));
const valid = transCounts.filter(t => t > 1).sort((a, b) => a - b);
const medianTrans = valid.length ? valid[Math.floor(valid.length / 2)] : 4;
const K = Math.max(1, Math.round(medianTrans / 2));
const r = mw / mh;
const { cols, rows } = solveGridDimensions(K, r);
return { cols, rows, K, cellHyp: diagLen / K };
}
// ── Build maze JSON from cell grid ──────────────────────────────────────
function buildMazeJSON(bin, w, lft, top, rgt, bot, cols, rows) {
const mw = rgt - lft + 1, mh = bot - top + 1;
const cellW = mw / cols, cellH = mh / rows;
const hasWall = (x1, y1, x2, y2, n = 16) => {
let count = 0;
for (let i = 0; i < n; i++) {
const t = (i + 0.5) / n;
const px = Math.max(0, Math.min(w-1, Math.round(x1 + (x2-x1)*t)));
const py = Math.max(0, Math.min(Math.floor(bin.length/w)-1, Math.round(y1 + (y2-y1)*t)));
if (bin[py * w + px]) count++;
}
return count > n / 2;
};
const grid = [];
for (let gy = 0; gy < rows; gy++) {
const row = [];
for (let gx = 0; gx < cols; gx++) {
const cx = lft + (gx + 0.5) * cellW;
const cy = top + (gy + 0.5) * cellH;
const hw = cellW * 0.3, hh = cellH * 0.3;
row.push({ v: false, w: {
top: hasWall(cx-hw, cy-cellH*0.5, cx+hw, cy-cellH*0.5),
bottom: hasWall(cx-hw, cy+cellH*0.5, cx+hw, cy+cellH*0.5),
left: hasWall(cx-cellW*0.5, cy-hh, cx-cellW*0.5, cy+hh),
right: hasWall(cx+cellW*0.5, cy-hh, cx+cellW*0.5, cy+hh),
}});
}
grid.push(row);
}
return { width: cols, height: rows, grid };
}
// ── Main analysis entry point ────────────────────────────────────────────
function analyzeImage() {
if (!uploadedImage) return;
const { bin, w, h, thresh, top, bot, lft, rgt } = getBinaryData(uploadedImage, manualThreshold);
const mw = rgt - lft + 1, mh = bot - top + 1;
let cols, rows, infoText;
if (analysisMode === 'diagonal') {
// ── Diagonal hypotenuse method ──────────────────────────────
const diag = detectByDiagonal(bin, lft, top, rgt, bot, w);
cols = diag.cols;
rows = diag.rows;
// Cross-validate with 1D projections
const colProj = new Float32Array(mw);
const rowProj = new Float32Array(mh);
for (let y = top; y <= bot; y++)
for (let x = lft; x <= rgt; x++)
if (bin[y*w+x]) { colProj[x-lft]++; rowProj[y-top]++; }
const projCols = detectCellCount(colProj);
const projRows = detectCellCount(rowProj);
if (Math.abs(projCols - cols) / Math.max(cols, 1) < 0.30) cols = projCols;
if (Math.abs(projRows - rows) / Math.max(rows, 1) < 0.30) rows = projRows;
infoText = `Diagonal: K=${diag.K} cells crossed · cellHyp ≈ ${diag.cellHyp.toFixed(1)}px · thresh ${thresh}`;
} else {
// ── Standard 1D projection method ──────────────────────────
const colProj = new Float32Array(mw);
const rowProj = new Float32Array(mh);
for (let y = top; y <= bot; y++)
for (let x = lft; x <= rgt; x++)
if (bin[y*w+x]) { colProj[x-lft]++; rowProj[y-top]++; }
cols = detectCellCount(colProj);
rows = detectCellCount(rowProj);
infoText = `Projection: ${cols}×${rows} detected · thresh ${thresh}`;
}
const result = buildMazeJSON(bin, w, lft, top, rgt, bot, cols, rows);
document.getElementById('mazeInput').value = JSON.stringify(result);
document.getElementById('statStatus').innerHTML = `Status: <b>Parsed ${cols}\u00D7${rows}</b>`;
const info = document.getElementById('analysisInfo');
info.textContent = infoText;
info.style.display = 'block';
document.getElementById('pngControls').style.display = 'none';
}
const dz = document.getElementById('dropZone');
dz.addEventListener('dragover', e => { e.preventDefault(); dz.classList.add('dragover'); });
dz.addEventListener('dragleave', () => dz.classList.remove('dragover'));
dz.addEventListener('drop', e => { e.preventDefault(); dz.classList.remove('dragover'); handleFileUpload(e.dataTransfer.files[0]); });
window.onload = () => {
const stored = localStorage.getItem('toolpad_maze_data');
if (stored) {
document.getElementById('mazeInput').value = stored;
// Don't auto-solve, just alert
alert("Maze data loaded from Generator! Click 'Solve Maze' to begin.");
localStorage.removeItem('toolpad_maze_data');
}
};