Overview › Code › R60
Code · blind round

R60 · Dijkstra vs A* on a weighted grid

blind round 9/11 local models answered

Every answer below carries the name of the model that wrote it. Blind refers to the scoring: the review was done without knowing which model produced which answer — the published result names them.

2 of the 11 local models delivered nothing through our test harness in this round — for reasons that lie with our setup, not with the models. Those cards are marked DNF like any other, but they are not evidence about those models — the reason is noted on the card itself.

A frontier reference answered the same task (Claude Opus 5) — outside the field and deliberately unscored, further down the page.

Show task 
Create ONE self-contained HTML file (STRICT LIMIT: max 120 lines total) that runs Dijkstra and A* side by side on the SAME randomly weighted 30x20 grid, drawn on one <canvas> split into two panels. Animate the search step by step: colour each cell by its terrain cost, mark visited cells, mark the frontier in a different colour, and draw the final shortest path once found. Show the number of cells each algorithm expanded and the total path cost as live labels — both paths must have the same cost, only the expanded counts may differ. Smooth requestAnimationFrame animation, NO user input, starts immediately and keeps running (restart with a fresh random instance when finished). No external libraries, no comments needed. Output ONLY the HTML file content, nothing else.

The answers

Local models (Brain cluster) — identical prompt, shuffled order (the sequence is not a ranking)
qwen3.5:9bBLANKLIMFORMAT
Show code
```html
<!DOCTYPE html>
<html>
<head><title>Dijkstra vs A*</title></head>
<style>body {display: flex; justify-content: center; align-items: center; height: 100vh; margin: 0; background: #111; color: white;}#container {display: flex; width: 92vw; max-width: 1200px;}canvas {border: 2px solid #444; box-shadow: 0 0 15px rgba(0,0,0,0.5);}#dijkstra {flex: 1;}#astar {flex: 1;}h3 {text-align: center; margin-top: 5px; color: #aaa;}</style>
<body><div id="container"><canvas id="dijkstra"></canvas><canvas id="astar"></canvas></div>
<script>
const C = window.innerWidth * 0.92 / 2 - 40; // Constant for canvas size calculation (adjusted for padding)
let GRID_W = 30;
let GRID_H = 20;
let CANVAS_SIZE = 600;

const cDijkstra = document.getElementById('dijkstra');
const cAstar = document.getElementById('astar');
cDijkstra.width = CANVAS_SIZE;
cDijkstra.height = CANVAS_SIZE;
cAstar.width = CANVAS_SIZE;
cAstar.height = CANVAS_SIZE;

const ctxD = cDijkstra.getContext('2d');
const ctxA = cAstar.getContext('2d');

let grid, start, end;
let isRunning = true;
let stepQueue = [];
let animationFrameId = null;

class PriorityQueue { constructor() { this.heap = []; } isEmpty() { return this.heap.length === 0; } peek() { return this.heap[0]; } pop() { const item = this.heap.shift(); this.heap.pop(); return item; } push(item) { this.heap.push(item); this.heap.sort((a, b) => a.cost - b.cost); }}

function initGrid() {
    grid = Array(GRID_H).fill(0).map(() => Array(GRID_W).fill(0).map(() => Math.floor(Math.random() * 3) + 1));
    start = [1, 1]; end = [GRID_W - 2, GRID_H - 2];
}

function setupVisualization(ctx) {
    const cell = CANVAS_SIZE / GRID_W;
    for (let y = 0; y < GRID_H; y++) {
        for (let x = 0; x < GRID_W; x++) {
            ctx.fillStyle = `hsl(${grid[y][x] * 30}, 70%, ${50 + grid[y][x] * 10}%)`;
            ctx.fillRect(x * cell, y * cell, cell - 1, cell - 1);
        }
    }
}

function getNeighbors(r, c) {
    const n = [];
    [[0, 1], [0, -1], [1, 0], [-1, 0]].forEach(([dr, dc]) => {
        const nr = r + dr;
        const nc = c + dc;
        if (nr >= 0 && nr < GRID_H && nc >= 0 && nc < GRID_W) n.push([nr, nc]);
    });
    return n;
}

function reconstructPath(cameFrom, current) {
    let path = [];
    let temp = [...current];
    while (temp[1] !== start[1] || temp[0] !== start[0]) {
        path.unshift(temp);
        const key = `${temp[0]},${temp[1]}`;
        if (!cameFrom.has(key)) break;
        let next = cameFrom.get(key);
        temp = next;
    }
    path.unshift(start);
    return path;
}

// --- Dijkstra's Algorithm (Uses Priority Queue based on cost) ---
function runDijkstra() {
    const dist = Array(GRID_H).fill(0).map(() => Array(GRID_W).fill(Infinity));
    const cameFrom = new Map();
    const pq = new PriorityQueue();

    dist[start[0]][start[1]] = 0;
    pq.push({ cost: 0, r: start[0], c: start[1] });
    
    let expandedCount = 0;
    let currentPathCost = Infinity;
    stepQueue = [];

    while (!pq.isEmpty()) {
        const { cost, r, c } = pq.pop();
        if (cost > dist[r][c]) continue;

        expandedCount++;
        stepQueue.push({ type: 'expand', r, c, cost, state: { visited: [[r, c]], frontier: [] } });

        if (r === end[0] && c === end[1]) {
            currentPathCost = cost; 
            // Path reconstruction is handled after the loop finishes successfully
            break;
        }
        
        for (const [nr, nc] of getNeighbors(r, c)) {
            const moveCost = grid[nr][nc];
            const newCost = dist[r][c] + moveCost;

            if (newCost < dist[nr][nc]) {
                dist[nr][nc] = newCost;
                cameFrom.set(`${nr},${nc}`, [{ r, c }, { cost: newCost }]); // Store predecessor and path details
                pq.push({ cost: newCost, r: nr, c: nc });
            }
        }
    }

    return { expandedCount: expandedCount, finalCost: dist[end[0]][end[1]], cameFrom, ran: currentPathCost !== Infinity };
}

// --- A* Algorithm (Uses Priority Queue based on f(n) = g(n) + h(n)) ---
function runAStar() {
    const gScore = Array(GRID_H).fill(0).map(() => Array(GRID_W).fill(Infinity));
    const cameFrom = new Map();
    // Priority Queue stores {f: f_cost, r, c}
    const pq = new PriorityQueue();

    gScore[start[0]][start[1]] = 0;
    pq.push({ cost: 0, r: start[0], c: start[1] });

    let expandedCount = 0;
    let currentPathCost = Infinity;
    stepQueue = [];

    const heuristic = (r, c) => Math.abs(r - end[0]) + Math.abs(c - end[1]); // Manhattan distance

    while (!pq.isEmpty()) {
        const { cost: f_cost, r, c } = pq.pop();

        expandedCount++;
        stepQueue.push({ type: 'expand', r, c, cost: f_cost, state: { visited: [[r, c]], frontier: [] } });

        if (r === end[0] && c === end[1]) {
            currentPathCost = gScore[r][c]; 
            break;
        }
        
        for (const [nr, nc] of getNeighbors(r, c)) {
            const moveCost = grid[nr][nc];
            const tentative_gScore = gScore[r][c] + moveCost;

            if (tentative_gScore < gScore[nr][nc]) {
                gScore[nr][nc] = tentative_gScore;
                cameFrom.set(`${nr},${nc}`, [{ r, c }, { cost: tentative_gScore }]);
                const f_score = tentative_gScore + heuristic(nr, nc);
                pq.push({ cost: f_score, r: nr, c: nc });
            }
        }
    }

    return { expandedCount: expandedCount, finalCost: gScore[end[0]][end[1]], cameFrom, ran: currentPathCost !== Infinity };
}


function animate(ctx, pathFinder) {
    if (stepQueue.length === 0 || !isRunning) return;

    const step = stepQueue.shift();
    let currentState = step.state;
    let r = step.r, c = step.c;

    // Clear canvas and redraw costs
    ctx.clearRect(0, 0, CANVAS_SIZE, CANVAS_SIZE);
    setupVisualization(ctx);

    if (step.type === 'expand') {
        // Draw visited cells (black)
        currentState.visited.forEach(([vr, vc]) => {
            const cell = CANVAS_SIZE / GRID_W;
            ctx.fillStyle = '#333';
            ctx.fillRect(vc * cell, vr * cell, cell - 1, cell - 1);
        });

        // Draw frontier (green)
        currentState.frontier.forEach(([fr, fc]) => {
             const cell = CANVAS_SIZE / GRID_W;
            ctx.fillStyle = 'rgba(0, 255, 0, 0.5)';
            ctx.fillRect(fc * cell, fr * cell, cell - 1, cell - 1);
        });

        // Highlight current expanded node (yellow)
        const cell = CANVAS_SIZE / GRID_W;
        ctx.fillStyle = 'rgba(255, 255, 0, 0.8)';
        ctx.fillRect(c * cell, r * cell, cell - 1, cell - 1);
    }

    if (stepQueue.length === 0) {
        // Animation complete for this algorithm
        const results = pathFinder;
        let pathNodes = [];
        if (results.cameFrom && results.ran) {
             // Reconstruct the actual path using the stored sequence data structure
            let temp = [end[0], end[1]]; 
            while (temp[1] !== start[1] || temp[0] !== start[0]) {
                pathNodes.push(temp);
                const key = `${temp[0]},${temp[1]}`;
                if (!results.cameFrom.has(key)) break;
                let nextData = results.cameFrom.get(key);
                temp = [nextData[0][0], nextData[0][1]];
            }
            pathNodes.unshift(start);

            // Draw final path (blue)
            const cell = CANVAS_SIZE / GRID_W;
            ctx.strokeStyle = 'rgba(50, 170, 255, 1)';
            ctx.lineWidth = 3;
            for (let i = 0; i < pathNodes.length - 1; i++) {
                const [r1, c1] = pathNodes[i];
                const [r2, c2] = pathNodes[i+1];
                ctx.beginPath();
                ctx.moveTo(c1 * cell + cell / 2, r1 * cell + cell / 2);
                ctx.lineTo(c2 * cell + cell / 2, r2 * cell + cell / 2);
                ctx.stroke();
            }
        }

        // Final Drawing state: visited cells are marked on the last step of animation
    }


    animationFrameId = requestAnimationFrame(() => animate(ctx, pathFinder));
}

function runAlgorithmCycle(canvasCtx, algorithmFunc) {
    // Reset visualization and queue
    step
qwen3:8bharness
No answer reached us (ERR) — and the reason lies with our setup, not with the model: reasoning consumed the entire token budget and the answer stayed empty; the gateway rejects budgets above 3000 tokens Counted as a did-not-finish, but it is not evidence about this model.
gemma4:26bharness
No answer reached us (THIN) — and the reason lies with our setup, not with the model: reasoning consumed the entire token budget (3 min 28 s, zero characters of answer); larger budgets are refused by the gateway Counted as a did-not-finish, but it is not evidence about this model.
qwen3:14bBLANKLIMFORMAT
Show code
```html
<!DOCTYPE html>
<html>
<head><meta charset="UTF-8"><title>Dijkstra vs A*</title></head>
<style>body{display:flex;align-items:center;height:100vh;margin:0;background:#222}canvas{border:1px solid #444;}</style>
<body><canvas id="canvas" width="600" height="400"></canvas><script>
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

let GRID_W = 30, GRID_H = 20;
let START = {x: 0, y: 0};
let END = {x: GRID_W - 1, y: GRID_H - 1};
let grid = [];

function generateGrid() {
    grid = [];
    for (let i = 0; i < GRID_H; i++) {
        let row = [];
        for (let j = 0; j < GRID_W; j++) {
            row.push({x: j, y: i, cost: Math.floor(Math.random() * 3) + 1});
        }
        grid.push(row);
    }
}

function getNeighbors(r, c) {
    const n = [];
    [[0, 1], [0, -1], [1, 0], [-1, 0]].forEach(([dr, dc]) => {
        const nr = r + dr;
        const nc = c + dc;
        if (nr >= 0 && nr < GRID_H && nc >= 0 && nc < GRID_W) n.push({r: nr, c: nc});
    }); return n;
}

function heuristic(a, b) { return Math.abs(a.x - b.x) + Math.abs(a.y - b.y); }

// Priority Queue implementation (simple array sort/shift for line count efficiency)
class PQ { constructor() { this.items = []; } isEmpty() { return this.items.length === 0; } push(item, priority) { this.items.push({item, priority}); this.items.sort((a, b) => a.priority - b.priority); } pop() { return this.items.shift().item; } }

function solveDijkstra() {
    let dist = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(Infinity));
    let prev = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(null));
    let pq = new PQ();

    dist[START.y][START.x] = 0;
    pq.push({r: START.y, c: START.x}, 0);

    let expandedCount = 0;
    while (!pq.isEmpty()) {
        const {r, c} = pq.pop();
        if (r === END.y && c === END.x) break;

        if (dist[r][c] < Infinity && dist[r][c] > 0) {
            expandedCount++;
        } else if (r !== START.y || c !== START.x) {
             // Only count nodes popped that aren't the start node, and are not already processed
             if (dist[r][c] === Infinity && !(r===START.y&&c===START.x)) continue;
        }


        getNeighbors(r, c).forEach(({r: nr, c: nc}) => {
            const newDist = dist[r][c] + grid[nr][nc].cost;
            if (newDist < dist[nr][nc]) {
                dist[nr][nc] = newDist;
                prev[nr][nc] = {r, c};
                pq.push({r: nr, c: nc}, newDist);
            }
        });
    }

    let path = []; let current = {r: END.y, c: END.x};
    while (current) { path.unshift(current); current = prev[current.r][current.c]); }
    return {path: path, cost: dist[END.y][END.x], expanded: Math.max(1, expandedCount)};
}

function solveAStar() {
    let gScore = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(Infinity)); // Cost from start
    let fScore = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(Infinity)); // Estimated total cost
    let prev = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(null));
    let pq = new PQ();

    gScore[START.y][START.x] = 0;
    fScore[START.y][START.x] = heuristic(START, END);
    pq.push({r: START.y, c: START.x}, fScore[START.y][START.x]);

    let expandedCount = 0;
    while (!pq.isEmpty()) {
        const {r, c} = pq.pop();
        if (r === END.y && c === END.x) break;

        if (gScore[r][c] < Infinity && gScore[r][c] > 0 || (r===START.y&&c===START.x)) {
             expandedCount++;
        }


        getNeighbors(r, c).forEach(({r: nr, c: nc}) => {
            const tentative_gScore = gScore[r][c] + grid[nr][nc].cost;
            if (tentative_gScore < gScore[nr][nc]) {
                prev[nr][nc] = {r, c};
                gScore[nr][nc] = tentative_gScore;
                fScore[nr][nc] = tentative_gScore + heuristic({x: nc, y: nr}, END);
                pq.push({r: nr, c: nc}, fScore[nr][nc]);
            }
        });
    }

    let path = []; let current = {r: END.y, c: END.x};
    while (current) { path.unshift(current); current = prev[current.r][current.c]); }
    return {path: path, cost: gScore[END.y][END.x], expanded: Math.max(1, expandedCount)};
}

let dijkstraState = { dist: Array.from({length: GRID_H}, () => new Array(GRID_W).fill(Infinity)), prev: [], pq: new PQ(), openSet: new Set(), visited: new Set(), currentPath: [] };
let aStarState = { gScore: Array.from({length: GRID_H}, () => new Array(GRID_W).fill(Infinity)), prev: [], pq: new PQ(), openSet: new Set(), visited: new Set(), currentPath: [] };

function initStates() {
    dijkstraState.prev = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(null));
    aStarState.prev = Array.from({length: GRID_H}, () => new Array(GRID_W).fill(null));

    // Initialize Dijkstra state
    dijkstraState.dist[START.y][START.x] = 0;
    dijkstraState.pq = new PQ();
    dijkstraState.pq.push({r: START.y, c: START.x}, 0);

    // Initialize A* state
    aStarState.gScore[START.y][START.x] = 0;
    aStarState.pq = new PQ();
    aStarState.pq.push({r: START.y, c: START.x}, heuristic(START, END));

    dijkstraState.visited.clear();
    aStarState.visited.clear();
}


function drawGrid() {
    const cellSize = 20;
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    for (let i = 0; i < GRID_H; i++) {
        for (let j = 0; j < GRID_W; j++) {
            const x = j * cellSize;
            const y = i * cellSize;
            ctx.fillStyle = `rgb(${15 + grid[i][j].cost * 20}, ${150 - grid[i][j].cost * 10}, ${15 + grid[i][j].cost * 20})`;
            ctx.fillRect(x, y, cellSize, cellSize);
        }
    }
}

function drawState(state, isDijkstra) {
    const ctxToUse = canvas; // Using one context for simplicity, drawing the two halves manually
    const cellSize = 20;
    let offset_x = isDijkstra ? 0 : canvas.width / 2 - (GRID_W * cellSize);

    // Draw background cost map first
    for (let i = 0; i < GRID_H; i++) {
        for (let j = 0; j < GRID_W; j++) {
            const x = j * cellSize + offset_x;
            const y = i * cellSize;
            ctx.fillStyle = `rgb(${15 + grid[i][j].cost * 20}, ${150 - grid[i][j].cost * 10}, ${15 + grid[i][j].cost * 20})`;
            ctx.fillRect(x, y, cellSize, cellSize);
        }
    }

    // Draw visited cells (Darker)
    for (let i = 0; i < GRID_H; i++) {
        for (let j = 0; j < GRID_W; j++) {
            if (state.visited.has(`${i},${j}`)) {
                const x = j * cellSize + offset_x;
                const y = i * cellSize;
                ctx.fillStyle = 'rgba(50, 50, 150, 0.6)';
                ctx.fillRect(x, y, cellSize, cellSize);
            }
        }
    }

    // Draw frontier/open set (Cyan)
    for (let i = 0; i < GRID_H; i++) {
        for (let j = 0; j < GRID_W; j++) {
            if (state.openSet.has(`${i},${j}`)) {
                const x = j * cellSize + offset_x;
                const y = i * cellSize;
                ctx.fillStyle = 'rgba(0, 255, 255, 0.4)';
                ctx.fillRect(x, y, cellSize, cellSize);
            }
        }
    }

    // Draw path (Green)
    for (const pos of state.currentPath) {
        if (!isDijkstra && pos[1] === START.y && pos[0] === START.x) continue; // Skip start node drawing on A* side if it is the start cell
        const x = pos[1] * cellSize + offset_x;
        const y = pos[0] * cellSize;
        ctx.fillStyle = 'rgba(0, 255, 0, 0.8)';
        ctx.fillRect(x, y, cellSize, cellSize);
    }

    // Draw Start/End
    const sX = START.x * cellSize + offset_x;
    const sY = START.y * cellSize;
    ctx.fillStyle = 'red'; ctx.fillRect(sX, sY
qwen3-coder:30bERRBLANKLIMFORMAT
Show code
```html
<!DOCTYPE html>
<html><head><title>Dijkstra vs A*</title></head><style>body{display:flex;justify-content:center;align-items:center;height:100vh;margin:0;background:#333;}#container{display:flex;gap:20px;}canvas{border:1px solid #ccc;background:#fff;}#stats{width:250px;color:#eee;font-family:monospace;}h3{margin-top:0;border-bottom:1px solid #444;}span{display:block;margin-bottom:5px;}</style></head><body><div id="container"><canvas id="canvas" width="600" height="480"></canvas><div id="stats"><h3>Dijkstra</h3><span id="d_exp">Exp: 0</span><span id="d_cost">Cost: N/A</span><h3>A*</h3><span id="a_exp">Exp: 0</span><span id="a_cost">Cost: N/A</span></div></div><script>
const C=document.getElementById('canvas');
const ctx=C.getContext('2d');
const W=30,H=20;
const CELL_W=C.width/W,CELL_H=C.height/H;

let grid=[],start=[1,1],end=[W-2,H-2];
let dijkstraState={cost:Infinity,expanded:0,visited:{},frontier:[{c,p},{c,p}],pathFound:false};
let aStarState={cost:Infinity,expanded:0,visited:{},frontier:[{c,p}],pathFound:false};

function init() {
    grid=[];for(let y=0;y<H;y++)grid[y]=[...Array(W)].map(()=>Math.floor(Math.random()*3)+1);
    dijkstraState={cost:Infinity,expanded:0,visited:{},frontier:[{c:start[0],p:start[1]},{c:end[0],p:end[1]}],pathFound:false};
    aStarState={cost:Infinity,expanded:0,visited:{},frontier:[{c:start[0],p:start[1]},{c:end[0],p:end[1]}],pathFound:false};
}

function draw() {
    ctx.clearRect(0,0,C.width,C.height);
    for(let y=0;y<H;y++)for(let x=0;x<W;x++){
        let color = '#9ccc65'; // Default terrain cost
        if (dijkstraState.visited[x]?dijkstraState.visited[x].y===y && dijkstraState.visited[x].x<=x:false) {
             color='#a2c1ad'; // Visited
        } else if (dijkstraState.frontier.some(f=>f.c===x&&f.p===y)) {
            color='#6aa84f'; // Frontier (Dijkstra)
        } else if (aStarState.visited[x]?aStarState.visited[x].y===y && aStarState.visited[x].x<=x:false) {
             color='#a2c1ad';
        } else if (aStarState.frontier.some(f=>f.c===x&&f.p===y)) {
            color='#6aa84f'; // Frontier (A*)
        }
        ctx.fillStyle = color;
        ctx.fillRect(x*CELL_W, y*CELL_H, CELL_W, CELL_H);

        // Draw Path (Simplification: path is only drawn when successful)
        if (dijkstraState.path && dijkstraState.path[y]===x) ctx.fillStyle='#0982c3';
        else if (aStarState.path && aStarState.path[y]===x) ctx.fillStyle='#cc6600';
        ctx.fillRect(x*CELL_W, y*CELL_H, CELL_W, CELL_H);
    }
    if (dijkstraState.path) {
         for(let y=0;y<H;y++)for(let x=0;x<W;x++){
            if (dijkstraState.path[y]===x) ctx.fillStyle='#0982c3'; // Path color
        }
    }
     if (aStarState.path) {
         for(let y=0;y<H;y++)for(let x=0;x<W;x++){
            if (aStarState.path[y]===x) ctx.fillStyle='#cc6600'; // Path color
        }
    }

    // Labels
    document.getElementById('d_exp').innerText=`Exp: ${dijkstraState.expanded}`;
    document.getElementById('d_cost').innerText=`Cost: ${Math.round(dijkstraState.cost)}`;
    document.getElementById('a_exp').innerText=`Exp: ${aStarState.expanded}`;
    document.getElementById('a_cost').innerText=`Cost: ${Math.round(aStarState.cost)}`;
}

function getNeighbors(x,y) {
    let n = [];
    [[0,1],[-1,1],[1,1],[0,-1],[0,1]].forEach(([dx,dy])=>{
        let nx=x+dx;let ny=y+dy;
        if (nx>=0&&nx<W&&ny>=0&&ny<H)n.push({c:nx,p:ny,cost:grid[ny][nx]});
    });
    return n;
}

function processDijkstra(queue){
    let current={c:-1,p:-1};
    if (queue.length === 0) return false;

    current = queue.shift();
    const {c:cx,p:cy}={c:current.c,p:current.p};

    dijkstraState.visited[cx] = {y:cy,x:cx}; // Mark visited (simple representation)
    dijkstraState.frontier.push({c:cx,p:cy});

    if (cx === end[0] && cy === end[1]) {
        dijkstraState.pathFound = true;
        // Reconstruct path (omitted complexity for line limit, assume path is found)
        return false; 
    }

    let neighbors=getNeighbors(cx,cy);

    for(const n of neighbors){
        if (!dijkstraState.visited[n.c] || (dijkstraState.visited[n.c].y !== n.p || dijkstraState.visited[n.c].x !== n.c)) {
            let newCost = dijkstraState.cost + n.cost; // Simplified cost tracking for animation
             if (!dijkstraState.frontier.some(f=>f.c===n.c&&f.p===n.p)) {
                dijkstraState.frontier.push({c:n.c,p:n.p});
            }
        }
    }
    dijkstraState.expanded++;
    return true;
}

function processAStar(queue){
    let current={c:-1,p:-1};
    if (queue.length === 0) return false;

    current = queue.shift();
    const {c:cx,p:cy}={c:current.c,p:current.p};

    aStarState.visited[cx] = {y:cy,x:cx}; // Mark visited
    aStarState.frontier.push({c:cx,p:cy});

     if (cx === end[0] && cy === end[1]) {
        aStarState.pathFound = true;
        return false; 
    }

    let neighbors=getNeighbors(cx,cy);
    for(const n of neighbors){
         // A* logic requires heuristic and cost updates (simplified for brevity)
    }
    aStarState.expanded++;
    return true;
}


function animate() {
    if (!dijkstraState.pathFound && dijkstraState.frontier.length > 0) {
        let nextD = [...dijkstraState.frontier];
        nextD.sort((a,b)=>1); // Simulate PQ extraction (simplification)
        processDijkstra(nextD);
    } else if (!dijkstraState.pathFound && dijkstraState.expanded > 50){
        // Force completion state for visualization when stuck in animation loop steps
        dijkstraState.cost=20; 
        dijkstraState.path = Array(H).fill(null); djkstraState.path[1][1]=1; dijkstraState.path[H-2][W-2]=1;
    }

     if (!aStarState.pathFound && aStarState.frontier.length > 0) {
        let nextA = [...aStarState.frontier];
        nextA.sort((a,b)=>1); // Simulate PQ extraction (simplification)
        processAStar(nextA);
    } else if (!aStarState.pathFound && aStarState.expanded > 50){
         dijkstraState.cost=20; 
         aStarState.cost = 20;
         aStarState.path = Array(H).fill(null); aStarState.path[1][1]=1; aStarState.path[H-2][W-2]=1;
    }


    draw();

    if (!dijkstraState.pathFound && !aStarState.pathFound) {
        setTimeout(()=>requestAnimationFrame(animate), 50);
    } else {
        // Loop restart on completion/stalling
        setTimeout(()=>{init();requestAnimationFrame(animate);},1500);
    }
}

init();
requestAnimationFrame(animate);
</script></body></html>
```
llama3.1:8bERRBLANKLIMFORMAT
Show code
```html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Dijkstra & A* Comparison</title>
<style>
  canvas {
    border: 1px solid black;
  }
  #dijkstra-panel, #a-star-panel {
    float: left;
    width: 49%;
    height: 500px;
  }
  .visited {
    fill: blue;
  }
  .frontier {
    fill: yellow;
  }
</style>
</head>
<body>
<canvas id="grid" width="980"></canvas>
<script>
  const grid = document.getElementById('grid');
  const ctx1 = grid.getContext('2d');
  const ctx2 = grid.getContext('2d', {offsetWidth: 490, offsetHeight: 500});
  let gridData = [];
  for (let i = 0; i < 30; i++) {
    gridData.push([]);
    for (let j = 0; j < 20; j++) {
      gridData[i].push(Math.random());
    }
  }
  const dijkstraExpanded = (count) => document.getElementById('dijkstra-expanded').textContent = `Dijkstra Expanded: ${count}`;
  const aStarExpanded = (count) => document.getElementById('a-star-expanded').textContent = `A* Expanded: ${count}`;
  let dijkstraCount = 0;
  let aStarCount = 0;
  let pathFound = false;
  function drawGrid() {
    ctx1.clearRect(0, 0, grid.width, grid.height);
    ctx2.clearRect(0, 0, grid.width, grid.height);
    const scale = 20 / Math.min(grid.width, grid.height);
    for (let i = 0; i < 30; i++) {
      for (let j = 0; j < 20; j++) {
        const cellX = j * scale;
        const cellY = i * scale;
        const terrainCost = gridData[i][j];
        ctx1.fillStyle = 'rgba(255, 128, 0, 0.5)'; // terrain cost
        ctx1.fillRect(cellX, cellY, scale, scale);
        if (pathFound && path[i][j] === 1) {
          ctx2.strokeStyle = 'black';
          ctx2.lineWidth = 2;
          ctx2.beginPath();
          ctx2.moveTo((j - path[0][j]) * scale + cellX, (i - path[0][i]) * scale + cellY);
          for (let k = 1; k < 20 * 30; k++) {
            const pI = Math.floor(k / 20);
            const pJ = k % 20;
            ctx2.lineTo((pJ - path[pI][pJ]) * scale + cellX, (pI - path[pI][pI]) * scale + cellY);
          }
          ctx2.stroke();
        }
      }
    }
  }
  function dijkstra() {
    const start = [0, 0];
    const end = [29, 19];
    const distances = Array(30).fill().map(() => Array(20).fill(Infinity));
    const cameFrom = Array(30).fill().map(() => Array(20).fill(null));
    const priorityQueue = [];
    let dijkstraCount = 0;
    distances[0][0] = gridData[0][0];
    priorityQueue.push([gridData[0][0], start]);
    while (priorityQueue.length > 0) {
      let [currentDistance, currentNode] = priorityQueue.shift();
      if (dijkstraCount !== dijkstraExpanded(dijkstraCount)) return;
      for (let i = -1; i <= 1; i++) {
        for (let j = -1; j <= 1; j++) {
          const neighborX = currentNode[0] + i;
          const neighborY = currentNode[1] + j;
          if (neighborX >= 0 && neighborX < 30 && neighborY >= 0 && neighborY < 20) {
            const newDistance = currentDistance + gridData[neighborX][neighborY];
            if (newDistance < distances[neighborX][neighborY]) {
              distances[neighborX][neighborY] = newDistance;
              cameFrom[neighborX][neighborY] = currentNode;
              priorityQueue.push([newDistance, [neighborX, neighborY]]);
              dijkstraCount++;
            }
          }
        }
      }
    }
    const shortestPath = [];
    let currentNode = end;
    while (currentNode) {
      shortestPath.unshift(currentNode);
      currentNode = cameFrom[currentNode[0]][currentNode[1]];
    }
    pathFound = true;
    return shortestPath;
  }
  function aStar() {
    const start = [0, 0];
    const end = [29, 19];
    const distances = Array(30).fill().map(() => Array(20).fill(Infinity));
    const cameFrom = Array(30).fill().map(() => Array(20).fill(null));
    const priorityQueue = [];
    let aStarCount = 0;
    distances[0][0] = gridData[0][0];
    priorityQueue.push([gridData[0][0], start]);
    while (priorityQueue.length > 0) {
      let [currentDistance, currentNode] = priorityQueue.shift();
      if (aStarCount !== aStarExpanded(aStarCount)) return;
      for (let i = -1; i <= 1; i++) {
        for (let j = -1; j <= 1; j++) {
          const neighborX = currentNode[0] + i;
          const neighborY = currentNode[1] + j;
          if (neighborX >= 0 && neighborX < 30 && neighborY >= 0 && neighborY < 20) {
            const heuristic = Math.abs(neighborX - end[0]) + Math.abs(neighborY - end[1]);
            const newDistance = currentDistance + gridData[neighborX][neighborY] + heuristic;
            if (newDistance < distances[neighborX][neighborY]) {
              distances[neighborX][neighborY] = newDistance;
              cameFrom[neighborX][neighborY] = currentNode;
              priorityQueue.push([newDistance, [neighborX, neighborY]]);
              aStarCount++;
            }
          }
        }
      }
    }
    const shortestPath = [];
    let currentNode = end;
    while (currentNode) {
      shortestPath.unshift(currentNode);
      currentNode = cameFrom[currentNode[0]][currentNode[1]];
    }
    pathFound = true;
    return shortestPath;
  }
  function drawStep(path, color) {
    ctx2.fillStyle = color;
    for (let i = 0; i < path.length; i++) {
      const x = path[i][1] * scale + cellX;
      const y = path[i][0] * scale + cellY;
      ctx2.fillRect(x, y, scale, scale);
    }
  }
  function drawVisited(color) {
    for (let i = 0; i < 30; i++) {
      for (let j = 0; j < 20; j++) {
        const x = j * scale;
        const y = i * scale;
        ctx1.fillStyle = color;
        ctx1.fillRect(x, y, scale, scale);
      }
    }
  }
  function drawFrontier(color) {
    for (let i = 0; i < 30; i++) {
      for (let j = 0; j < 20; j++) {
        const x = j * scale;
        const y = i * scale;
        ctx2.fillStyle = color;
        ctx2.fillRect(x, y, scale, scale);
      }
    }
  }
  let path = [];
  drawGrid();
  function animation() {
    if (dijkstraCount < dijkstraExpanded(dijkstraCount)) {
      dijkstra();
    }
    if (aStarCount < aStarExpanded(aStarCount)) {
      aStar();
    }
    if (!pathFound) return requestAnimationFrame(animation);
    const shortestPath = dijkstra();
    const aStarPath = aStar();
    path = shortestPath;
    for (let i = 0; i < 30; i++) {
      for (let j = 0; j < 20; j++) {
        const x = j * scale + cellX;
        const y = i * scale + cellY;
        if (path[i][j] === 1) {
          ctx2.fillStyle = 'black';
          ctx2.fillRect(x, y, scale, scale);
        }
      }
    }
    drawStep(path, 'red');
    let currentNode = path[0];
    while (currentNode) {
      const neighborX = currentNode[0];
      const neighborY = currentNode[1];
      if (neighborX >= 0 && neighborX < 30 && neighborY >= 0 && neighborY < 20) {
        ctx2.fillStyle = 'black';
        ctx2.fillRect(neighborY * scale + cellX, neighborX * scale + cellY, scale, scale);
      }
      currentNode = cameFrom[neighborX][neighborY];
    }
    drawVisited('blue');
    for (let i = 0; i < path.length - 1; i++) {
      const point1 = path[i];
      const point2 = path[i + 1];
      ctx2.strokeStyle = 'black';
      ctx2.lineWidth = 3;
      ctx2.beginPath();
      ctx2.moveTo((point1[1] - point1[0]) * scale + cellX, (point1[0] - point1[1]) * scale + cellY);
      ctx2.lineTo((point2[1] - point2[0]) * scale + cellX, (point2[0] - point2[1]) * scale + cellY);
      ctx2.stroke();
    }
    document.getElementById('cost').textContent = `Path Cost: ${distances[29][19]}`
    requestAnimationFrame(animation);
  };
  animation();
  for (let i = 0; i < 30; i++) {
    gridData[i].push(...gridData[i]);
  }
  for (let j = 0; j < 20 * 2; j++) {
    const row = [...gridData[j % 30]];
    gridData.push(row);
  }
  drawGrid();
</script>
<canvas id="dijkstra-panel" width="490"></canvas>
<div id="stats">
  <div id="cost">Path Cost: ?</div>
  <div id="dijkstra-expanded">Dijkstra Expanded: 0</div>
  <div id="a-star-expanded">A* Expanded: 0</div>
</div>
<canvas id="a-star-panel" width="490"></canvas>
```
deepseek-r1:14bERRBLANKMINIFIEDFORMAT
Show code
```html
<!DOCTYPE html>
<html><body style="margin:0;overflow:hidden;">
<canvas id="c" width="600" height="300"></canvas>
<script>
let w=30,h=20,start=(0,0),end=(w-1,h-1);let c=document.getElementById('c').getContext('2d');let scale=2;let terrain={};function initGrid(){for(let y=0;y<h;y++)for(let x=0;x<w;x++)terrain[x+w*y]=Math.floor(Math.random()*10+1)}initGrid();class PriorityQueue{constructor(){this.heap=[]}insert(node){heap.push(node)}extractMin(){return heap.shift()}}let D={open:new Set(),closed:new Set()},A={open:new Set(),closed:new Set()};function dijkstra(){let q=new PriorityQueue;startCost=0;q.insert({x:0,y:0,cost:0,parentNode:null});while(q.heap.length>0){let u=q.extractMin();if(u.x==w-1&&u.y==h-1)break;if(D.closed.has(`${u.x},${u.y}`))continue;D.closed.add(`${u.x},${u.y}`);for(let dir of [[1,0],[-1,0],[0,1],[0,-1]]){let x2=u.x+dir[0],y2=u.y+dir[1];if(x2<0||x2>=w||y2<0||y2>=h)continue;if(!D.open.has(`${x2},${y2}`)&&!D.closed.has(`${x2},${y2}`)){let cost=u.cost+terrain[x2+h*y2];q.insert({x:x2,y:y2,cost,parentNode:u});D.open.add(`${x2},${y2}`)}}}}function aStar(){let q=new PriorityQueue;startCost=0;q.insert({x:0,y:0,cost:0,heuristic:19*5 + terrain[0],parentNode:null});while(q.heap.length>0){let u=q.extractMin();if(u.x==w-1&&u.y==h-1)break;if(A.closed.has(`${u.x},${u.y}`))continue;A.closed.add(`${u.x},${u.y}`);for(let dir of [[1,0],[-1,0],[0,1],[0,-1]]){let x2=u.x+dir[0],y2=u.y+dir[1];if(x2<0||x2>=w||y2<0||y2>=h)continue;if(!A.open.has(`${x2},${y2}`)&&!A.closed.has(`${x2},${y2}`)){let cost=u.cost+terrain[x2+h*y2];heuristic= (w-1-x2)+(h-1-y2)*5; q.insert({x:x2,y:y2,cost,parentNode:u,heuristic:cost + heuristic});A.open.add(`${x2},${y2}`)}}}}function draw(){c.clearRect(0,0,c.canvas.width,c.canvas.height);for(let y=0;y<h;y++)for(let x=0;x<w;x++){let i=x+w*y; c.fillStyle=c(x<10||x>20||y>10?'#ff0000':'#00ffff');}c.font='12px sans-serif';c.fillText(`Dijkstra: ${dExpanded} nodes, cost: ${dCost}`,0,30);c.fillText(`A*: ${aExpanded} nodes, cost: ${aCost}`,0,45);c.stroke();}}function animate(){if(!dFinished||!aFinished)draw();else{initGrid();dijkstra();aStar();requestAnimationFrame(animate)}}let dExpanded=0,aExpanded=0,dCost=0,aCost=0,dFinished=aFinished=false;requestAnimationFrame(animate);
</script>
</body></html>
```
mistral-small:24bSTATFORMAT
Show code
```html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Dijkstra vs A*</title>
<style>
body { display: flex; justify-content: center; align-items: center; height: 100vh; margin: 0; background-color: #f0f0f0; }
canvas { border: 1px solid black; }
#info { position: absolute; top: 10px; left: 10px; color: white; font-family: Arial, sans-serif; }
</style>
</head>
<body>
<canvas id="canvas" width="640" height="480"></canvas>
<div id="info"></div>
<script>
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const cellSize = 10;
const rows = 30;
const cols = 20;
const terrainCosts = Array.from({ length: rows }, () => Array(cols).fill(0));
const dijkstraFrontier = [];
const aStarFrontier = [];
let dijkstraVisited = new Set();
let aStarVisited = new Set();
let dijkstraPath = [];
let aStarPath = [];
let dijkstraExpanded = 0;
let aStarExpanded = 0;

function getRandomCost() {
    return Math.floor(Math.random() * 10) + 5;
}

function drawTerrain() {
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            terrainCosts[r][c] = getRandomCost();
            ctx.fillStyle = `rgb(${terrainCosts[r][c]}, ${255 - terrainCosts[r][c]}, 100)`;
            ctx.fillRect(c * cellSize, r * cellSize, cellSize, cellSize);
        }
    }
}

function drawFrontier(frontier) {
    ctx.strokeStyle = 'yellow';
    frontier.forEach(cell => {
        ctx.strokeRect(cell[1] * cellSize, cell[0] * cellSize, cellSize, cellSize);
    });
}

function djkstraStep() {
    if (dijkstraFrontier.length === 0) return;
    const [r, c] = dijkstraFrontier.shift();
    ctx.fillStyle = 'blue';
    ctx.fillRect(c * cellSize, r * cellSize, cellSize, cellSize);
    dijkstraVisited.add(`${r},${c}`);
    dijkstraExpanded++;

}

function aStarStep() {
    if (aStarFrontier.length === 0) return;
    const [r, c] = aStarFrontier.shift();
    ctx.fillStyle = 'red';
    ctx.fillRect(c * cellSize, r * cellSize, cellSize, cellSize);
    aStarVisited.add(`${r},${c}`);
    aStarExpanded++;
}

function drawPath(path, color) {
    path.forEach(cell => {
        const [r, c] = cell;
        ctx.strokeStyle = color;
        ctx.strokeRect(c * cellSize, r * cellSize, cellSize, cellSize);
    });
}

function animate() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    drawTerrain();
    drawFrontier(dijkstraFrontier);
    drawFrontier(aStarFrontier);

    djkstraStep();
    aStarStep();

    document.getElementById('info').innerHTML = `Dijkstra Expanded: ${dijkstraExpanded} <br> A* Expanded: ${aStarExpanded}`;
}

function init() {
    dijkstraFrontier.push([0, 0]);
    aStarFrontier.push([0, 0]);

    requestAnimationFrame(animate);
}

init();

</script>
</body>
</html>
```
command-r:35bBLANKLIMFORMAT
Show code
```html
<!DOCTYPE html>
<html>
<head>
    <style>
        canvas { border: 1px solid black; }
    </style>
</head>
<body>

    <canvas id="panel1"></canvas>
    <canvas id="panel2"></canvas>
    
    <script>
        function randRange(n, start) {
            return Math.floor(start + (Math.random() * n));
        }

        function neighbours(i, j, w, h) {
            var result = [];
            for (var di=-1; di<=1; di++)
                if (0 <= i+di && i+di < w)
                    for (var dj=-1; dj<=1; dj++)
                        if (!(dj==0 && di==0) && 0 <= j+dj && j+dj < h)
                            result.push({x:i+di, y:j+dj});
            return result;
        }

        function getDistance(a, b) {
            var dx = Math.abs(a.x - b.x);
            var dy = Math.abs(a.y - b.y);
            return dx + dy; // manhattan distance
        }
        
        function dijkstra(grid, start, end) {
            var queue = [{node:start, cost:0}];
            grid[end].cost = Number.POSITIVE_INFINITY;
            while (queue.length > 0) {
                var currentNode = queue.shift();
                if (currentNode.cost != grid[currentNode.node].cost && Math.abs(grid[currentNode.node].cost - currentNode.cost) > 1e-6)
                    continue;

                for (var i=0; i < neighbours(currentNode.node.x, currentNode.node.y, grid.length, grid[0].length).length; i++) {
                    var neighbour = neighbours(currentNode.node.x, currentNode.node.y, grid.length, grid[0].length)[i];

                    if (grid[neighbour.x][neighbour.y].cost != Number.POSITIVE_INFINITY) continue;
                    
                    var newCost = currentNode.cost + 1;
                    if (newCost < grid[neighbour.x][neighbour.y].cost || queue.length == 0) {
                        grid[neighbour.x][neighbour.y].prev = currentNode.node;
                        grid[neighbour.x][neighbour.y].cost = newCost;
                        var idx = findIndexInQueue(queue, neighbour);
                        if (idx != -1)
                            queue.splice(idx, 1);
                        queue.push({node:neighbour, cost:newCost});
                    }
                }
            }

            function findIndexInQueue(queue, node) {
                for (var i=0; i < queue.length; i++)
                    if (JSON.stringify(queue[i].node) == JSON.stringify(node))
                        return i;
                return -1;
            }
        }

        function aStar(grid, start, end) {
            var queue = [{node:start, cost:0}];
            grid[end].cost = Number.POSITIVE_INFINITY;
            while (queue.length > 0) {
                var currentNode = queue.shift();

                if (currentNode.cost != grid[currentNode.node].cost && Math.abs(grid[currentNode.node].cost - currentNode.cost) > 1e-6)
                    continue;
                
                for (var i=0; i < neighbours(currentNode.node.x, currentNode.node.y, grid.length, grid[0].length).length; i++) {
                    var neighbour = neighbours(currentNode.node.x, currentNode.node.y, grid.length, grid[0].length)[i];

                    if (grid[neighbour.x][neighbour.y].cost != Number.POSITIVE_INFINITY) continue;
                    
                    var newCost = currentNode.cost + 1;
                    var priority = newCost + getDistance(neighbour, end);
                    if (newCost < grid[neighbour.x][neighbour.y].cost || queue.length == 0) {
                        grid[neighbour.x][neighbour.y].prev = currentNode.node;
                        grid[neighbour.x][neighbour.y].cost = newCost;
                        var idx = findIndexInQueue(queue, neighbour);
                        if (idx != -1)
                            queue.splice(idx, 1);
                        queue.push({node:neighbour, cost:newCost, priority:priority});
                    }
                }

                function sortByPriority(a, b) { return a.priority < b.priority ? -1 : a.priority > b.priority; }
                queue.sort(sortByPriority);
            }

            function findIndexInQueue(queue, node) {
                for (var i=0; i < queue.length; i++)
                    if (JSON.stringify(queue[i].node) == JSON.stringify(node))
                        return i;
                return -1;
            }
        }

        // MAIN LOOP
        
        var canvas = document.getElementById("panel1");
        var ctx = canvas.getContext("2d");
        canvas = document.getElementById("panel2");
        var ctx_ = canvas.getContext("2d");
        
        function drawGrid(grid, ctx) {
            for (var i=0; i < grid.length; i++)
                for (var j=0; j < grid[i].length; j++)
                    if (typeof grid[i][j] !== 'undefined') {
                        var cost = grid[i][j].cost == Number.POSITIVE_INFINITY ? 1 : grid[i][j].cost > 9 ? 9 : grid[i][j].cost;
                        ctx.fillStyle = "rgb(" + Math.round(250-8*cost) + "," + Math.round(250-8*cost) + ",250)";
                        ctx.fillRect(i*17, j*17, 16, 16);
                    }
        }

        function animate() {
            canvas.width = canvas.width; // clear the canvas

            var grid = [];
            for (var i=0; i < 30; i++)
                grid.push(new Array(20));
            
            drawGrid(grid, ctx);
            
            for (var i=0; i < 30*20; i++) {
                var x = randRange(29,0);
                var y = randRange(19,0);
                while (x == grid[y][0].prev.x && y == grid[y][0].prev.y)
                    y = randRange(19,0);
                
                if (!grid[x] || !grid[x][y]) continue;
                grid[x][y].cost = randRange(5, 1);
            }

            var start_x = randRange(28,0);
            var start_y = randRange(17,0);
            while (start_x == grid[start_y][0].prev.x && start_y == grid[start_y][0].prev.y)
                start_y = randRange(17,0);
            
            var end_x = randRange(2
deepseek-r1:32bBLANKFORMAT
Show code
```html
<!DOCTYPE html>
<html><head><title>Dijkstra vs A*</title></head><body style="background:#f0f0f0;display:flex;height:100vh;margin:0;padding:20px;gap:20px;flex-direction:column;">
<canvas id=c width=800 height=400 style="border:1px solid #ccc;"></canvas>
<div style="display:flex;gap:20px;">
  <div>Dijkstra: expanded <span id=d-expanded>0</span><br>Path cost: <span id=d-cost>0</span></div>
  <div>A*: expanded <span id=a-expanded>0</span><br>Path cost: <span id=a-cost>0</span></div>
</div>
<script>
const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
const cols=30, rows=20;
let grid = Array(cols).fill().map(()=>Array(rows).fill().map(()=>Math.floor(Math.random()*5)+1));
let dijkstraQueue = new PriorityQueue();
let aStarQueue = new PriorityQueue();
let pathDijkstra = [];
let pathAstar = [];
let step=0;

class PriorityQueue {
  constructor() { this.elements = []; }
  add(element, priority) { this.elements.push([element, priority]); }
  extractMin() { 
    let minIdx=0;
    for(let i=1; i<this.elements.length; i++) {
      if(this.elements[i][1] < this.elements[minIdx][1]) minIdx=i;
    }
    return this.elements.splice(minIdx,1)[0];
  }
}

function draw() {
  ctx.fillStyle="#fff"; ctx.fillRect(0,0,canvas.width,canvas.height);
  
  // Left panel (Dijkstra)
  drawGrid(0, 0, 400, 200, 'Dijkstra');
  drawPath(pathDijkstra, 0);
  
  // Right panel (A*)
  drawGrid(400, 0, 400, 200, 'A*');
  drawPath(pathAstar, 400);
}

function drawGrid(x, y, width, height, label) {
  ctx.fillStyle="#ddd"; ctx.font="16px sans-serif";
  ctx.fillText(label, x+width/2-30, y+20);
  
  const cellW = width/cols;
  const cellH = (height-40)/rows;
  
  for(let i=0; i<cols; i++) {
    for(let j=0; j<rows; j++) {
      let val = grid[i][j];
      ctx.fillStyle=`hsl(${val*36},50%,90%)`;
      ctx.fillRect(x+i*cellW, y+40+j*cellH, cellW-1, cellH-1);
    }
  }
  
  // Draw start and end points
  ctx.fillStyle="#0f0"; 
  ctx.beginPath();
  ctx.arc(x + cellW*(cols/2), y + cellH*(rows/2)+20, Math.min(cellW,cellH)/4, 0, Math.PI*2);
  ctx.fill();
}

function drawPath(path, x) {
  if(!path.length) return;
  
  const cellW=400/cols;
  const cellH=200/rows;
  ctx.strokeStyle="#0f0";
  ctx.lineWidth=Math.min(cellW,cellH)/3;
  
  let prev = path[0].map(p => p + [x, 20]);
  ctx.beginPath();
  for(let i=1; i<path.length; i++) {
    let curr = path[i].map(p => p + [x, 20]);
    ctx.moveTo(prev[0], prev[1]);
    ctx.lineTo(curr[0], curr[1]);
    prev=curr;
  }
  ctx.stroke();
}

function heuristic(a,b) {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

function searchAlgo(algorithm) {
  let openSet = algorithm === 'dijkstra' ? dijkstraQueue : aStarQueue;
  if(!openSet.elements.length) return false;

  // Step through queue
  step++;
  for(let i=0; i<2; i++) { // Process two steps per frame
    try {
      let [node, priority] = openSet.extractMin();
      
      // Mark as processed
      if(node.isStart) continue;
      ctx.fillStyle="#ffa"; 
      let x = node.x * (400/cols);
      let y = 20 + node.y * (200/rows);
      ctx.fillRect(x, y, 1, 1);
      
      // Check neighbors
      for(let dir of [[-1,0],[1,0],[0,-1],[0,1]]) {
        let x2=node.x+dir[0], y2=node.y+dir[1];
        if(x2>=0 && x2<cols && y2>=0 && y2<rows)
qwq:32bSTAT
Show code
<think>

Okay, I need to create an HTML file that shows both Dijkstra's and A* algorithms running side by side on a 30x20 grid. The grid should be randomly weighted, and both algorithms should animate their steps. The canvas should be split into two panels, one for each algorithm. The user didn't want any external libraries, so I have to use native JavaScript.

First, I should structure the HTML. The canvas element will be split into two halves. Each panel will display the grid for each algorithm. The grid cells need to show their terrain cost, the visited cells, the frontier (maybe in a different color), and the final path once found. Also, live labels must show the number of cells expanded and the total path cost for both algorithms. Both paths must have the same cost, so the grid's start and end points should be the same for both algorithms.

I need to manage the animation with requestAnimationFrame to keep it smooth. The algorithms should run step by step, so each animation frame should process one step of each algorithm. When both are done, the canvas should restart with a new grid.

Let me think about the grid setup. The grid is 30x20. Each cell can have a random weight between, say, 1 to 10. The start and end points can be fixed, like top-left and bottom-right corners. Or maybe random positions? The user didn't specify, so maybe fixed is better for simplicity.

The canvas needs to be split into two panels. The canvas element's width and height can be calculated based on the grid dimensions. Let's say each grid cell is 20px, so canvas width is 30*20*2 (since two panels side by side) and height 20*20. Wait, no. Wait, the grid is 30 columns and 20 rows. So each panel's width would be 30*cellSize, height 20*cellSize. So if each cell is 20x20, then each panel is 30*20 = 600px wide and 400px tall. Thus, the entire canvas is 1200x400. But maybe a smaller cell size is better for 120 lines. Maybe 10px per cell? 30x10=300px wide per panel, total 600px. Height 20x10=200px. That's manageable.

So setup the canvas with width 600 and height 200. Split into two 300x200 panels. The left is Dijkstra's, right is A*.

Now, the grid cells. Each cell has a cost, so an object array for each panel? Or since they are using the same grid, maybe a single grid array that both algorithms use? Wait, the grid must be the same for both algorithms, as the path costs must be the same. So the grid is a single 30x20 array with cost values. The start and end points are the same for both algorithms.

Each algorithm has its own state: the priority queue, visited cells, path, etc. So I need to implement both algorithms in separate functions, each tracking their own state.

The animation loop will need to step both algorithms, then redraw both panels. Each step processes one expansion step of each algorithm.

First, I need to represent the grid. Let's make a 2D array. The start and end points could be (0,0) and (29,19) or similar. But maybe random? The user says "randomly weighted grid", so the weights are random. The start and end can be fixed for simplicity.

Wait, the user says "randomly weighted grid", but the path's cost must be the same for both algorithms. So as long as the grid is the same for both, the paths will have the same cost. So the grid is created once, and both algorithms use that same grid.

So step by step:

1. Setup the canvas, split into two panels.
2. Generate a random grid with weights between 1 and 10 (or some range).
3. Initialize both algorithms with the same grid, start, and end points.
4. Run the animation loop:

   a. For each algorithm (Dijkstra and A*), process one step (e.g., expand one node)
   
   b. Draw the grid for each algorithm, showing nodes in different states (frontier, visited, path)
   
   c. Update live labels (expanded count and path cost)
   
   d. When both algorithms are done, reset everything and start over.

Implementing Dijkstra's algorithm:

- Uses a priority queue (min-heap) where priority is the total cost from start to current node.
- For each step, extract the node with minimum cost, add to visited, process neighbors, etc.

Implementing A*:

- Similar to Dijkstra's, but the priority also includes a heuristic (e.g., Manhattan distance to end)
- The priority is total cost + heuristic.

For the grid drawing:

Each cell can be colored based on its cost. Maybe a gradient from green to red for low to high cost. Visited nodes can have a transparent overlay. The frontier (current nodes in the queue) can be a different color. The path can be drawn once found.

Drawing steps:

- Clear both panels.
- For each cell in the grid:
   - Fill with a color based on cost (brighter for higher cost)
   - For each algorithm's grid state:
      - If the cell is visited, draw over with a semi-transparent color (like blue)
      - If it's in the frontier, maybe another color (yellow?), or outline
      - The path can be a thicker line in a contrasting color (white)
   - Also draw the start and end points (maybe with a border)

Wait, but the two algorithms are on different panels, so each panel's drawing is independent. So for each panel (left: Dijkstra, right: A*), we need to draw their own visited, frontier, etc.

The key is that both algorithms are operating on the same grid, so their own data structures (like visited nodes, path, etc.) are separate.

The main challenge is implementing both algorithms in a way that they can each be stepped one node at a time (for animation). Since algorithms are often implemented as loops, stepping them one step requires breaking their loops into steps that can be handled per frame.

So for each algorithm, we need a function that, given their current state, processes one step and returns new state. That way, each animation frame can do one step for both algorithms.

Alternatively, use a state machine approach where each algorithm is in a step that can be advanced.

Alternatively, for the animation, each frame calls stepDijkstra and stepAStar, which each process the next step in their algorithms.

Implementing this requires that each algorithm's state is stored in objects that can be updated step by step.

Let me think structure:

- The grid is a 2D array of numbers (costs). Start and end are coordinates.

- Dijkstra's algorithm has:

   - A priority queue (nodes to visit, ordered by current cost)
   - A cameFrom map (to reconstruct the path)
   - A visited set (or maybe part of cameFrom)
   - The current path found (once algorithm is done)

- Similarly for A*, but with a different priority calculation.

The animation loop will process each step, which is:

   For Dijkstra's step:
      - If not done, pop the next node from the queue (the
Outside the Brain cluster — same task, same character budget, collected through their own tooling (response times not comparable)
GPT-5.5 (Codex)frontier referenceOKMINIFIED
Show code
<!doctype html><html><head><meta charset="utf-8"><title>Dijkstra vs A*</title><style>
html,body{margin:0;height:100%;background:#12151c;color:#e8edf2;font:14px system-ui;overflow:hidden}#bar{height:42px;display:flex;gap:28px;align-items:center;justify-content:center;background:#1c2430}b{color:#fff}canvas{display:block;width:100vw;height:calc(100vh - 42px)}
</style></head><body><div id="bar"><span>Dijkstra: <b id="d">0 expanded, cost -</b></span><span>A*: <b id="a">0 expanded, cost -</b></span></div><canvas id="c"></canvas><script>
const W=30,H=20,N=W*H,cv=document.getElementById('c'),x=cv.getContext('2d'),dl=document.getElementById('d'),al=document.getElementById('a');let g,ds,as,last=0,done=0;
function idx(x,y){return y*W+x}function xy(i){return [i%W,(i/W)|0]}function heu(i){let[p,q]=xy(i);return Math.abs(W-1-p)+Math.abs(H-1-q)}
function fresh(){g=Array.from({length:N},(_,i)=>i==0||i==N-1?1:1+Math.floor(Math.random()*9));ds=state(false);as=state(true);done=0;last=0;resize()}
function state(ast){return{ast,open:[0],seen:new Set([0]),vis:new Set,front:new Set([0]),dist:Array(N).fill(1/0),prev:Array(N).fill(-1),path:[],cost:0,exp:0,found:false}}
function pop(s){let bi=0,bv=1/0;for(let i=0;i<s.open.length;i++){let n=s.open[i],v=s.dist[n]+(s.ast?heu(n):0);if(v<bv)bv=v,bi=i}let n=s.open[bi];s.open.splice(bi,1);s.front.delete(n);return n}
function step(s){if(s.found)return;let n=pop(s);s.vis.add(n);s.exp++;if(n==N-1){s.found=true;s.cost=s.dist[n];for(let p=n;p>=0;p=s.prev[p])s.path.push(p);return}let[p,q]=xy(n),nb=[[p+1,q],[p-1,q],[p,q+1],[p,q-1]];for(let [i,j] of nb)if(i>=0&&i<W&&j>=0&&j<H){let m=idx(i,j),nd=s.dist[n]+g[m];if(nd<s.dist[m]){s.dist[m]=nd;s.prev[m]=n;if(!s.seen.has(m)){s.open.push(m);s.seen.add(m);s.front.add(m)}}}}
function resize(){let r=devicePixelRatio||1;cv.width=innerWidth*r;cv.height=(innerHeight-42)*r;x.setTransform(r,0,0,r,0,0);draw()}onresize=resize;
function col(v){let h=125-v*8;return `hsl(${h} 48% ${24+v*4}%)`}
function panel(s,ox,w,name){let cw=w/W,ch=cv.clientHeight/H;x.fillStyle='#111821';x.fillRect(ox,0,w,cv.clientHeight);for(let i=0;i<N;i++){let[p,q]=xy(i);x.fillStyle=col(g[i]);x.fillRect(ox+p*cw,q*ch,cw-1,ch-1)}for(let i of s.vis){let[p,q]=xy(i);x.fillStyle='rgba(73,139,232,.58)';x.fillRect(ox+p*cw,q*ch,cw-1,ch-1)}for(let i of s.front){let[p,q]=xy(i);x.fillStyle='rgba(255,206,82,.78)';x.fillRect(ox+p*cw,q*ch,cw-1,ch-1)}for(let i of s.path){let[p,q]=xy(i);x.fillStyle='#ff4d6d';x.fillRect(ox+p*cw+cw*.18,q*ch+ch*.18,cw*.64,ch*.64)}x.fillStyle='#27e18e';x.fillRect(ox+2,2,cw-4,ch-4);x.fillStyle='#fff';x.fillRect(ox+(W-1)*cw+2,(H-1)*ch+2,cw-4,ch-4);x.fillStyle='rgba(255,255,255,.9)';x.font='16px system-ui';x.fillText(name,ox+10,24)}
function draw(){let w=cv.clientWidth/2;panel(ds,0,w,'Dijkstra');panel(as,w,w,'A*');x.fillStyle='#0c0f14';x.fillRect(w-1,0,2,cv.clientHeight);dl.textContent=`${ds.exp} expanded, cost ${ds.found?ds.cost:'-'}`;al.textContent=`${as.exp} expanded, cost ${as.found?as.cost:'-'}`}
function tick(t){if(t-last>18){for(let k=0;k<8;k++){if(!ds.found)step(ds);if(!as.found)step(as)}draw();last=t;if(ds.found&&as.found&&!done)done=t;if(done&&t-done>1700)fresh()}requestAnimationFrame(tick)}
fresh();requestAnimationFrame(tick);
</script></body></html>
Claude Sonnet 5frontier referenceOK
Show code
<!DOCTYPE html>
<html><head><meta charset="utf-8"><title>Dijkstra vs A*</title>
<style>
html,body{margin:0;background:#111;color:#eee;font-family:monospace;overflow:hidden}
#lbl{position:absolute;top:8px;left:12px;font-size:13px;white-space:pre}
#lbl2{position:absolute;top:8px;left:482px;font-size:13px;white-space:pre}
canvas{display:block;margin:34px auto 0}
</style></head><body>
<div id="lbl"></div><div id="lbl2"></div>
<canvas id="c" width="930" height="340"></canvas>
<script>
const W=30,H=20,N=W*H,CS=15,GX=10,GY=35,PX=480;
const canvas=document.getElementById('c'),ctx=canvas.getContext('2d');
const lbl=document.getElementById('lbl'),lbl2=document.getElementById('lbl2');
let cost=new Float64Array(N);
function xy(i){return [i%W,(i/W)|0];}
function heur(i){const p=xy(i);return Math.abs(W-1-p[0])+Math.abs(H-1-p[1]);}
function neigh(i){const p=xy(i),x=p[0],y=p[1],r=[];if(x>0)r.push(i-1);if(x<W-1)r.push(i+1);if(y>0)r.push(i-W);if(y<H-1)r.push(i+W);return r;}
function newCost(){for(let i=0;i<N;i++)cost[i]=1+Math.floor(Math.random()*9);}
function makeState(useH){return{dist:new Float64Array(N).fill(Infinity),prev:new Int32Array(N).fill(-1),visited:new Uint8Array(N),inOpen:new Uint8Array(N),open:[0],done:false,expanded:0,path:[],cost:0,useH:useH};}
let dij,ast,restarting=false;
function initAll(){newCost();dij=makeState(false);ast=makeState(true);dij.dist[0]=0;ast.dist[0]=0;restarting=false;}
function step(s){
  if(s.done)return;
  if(s.open.length===0){s.done=true;return;}
  let bi=0,bf=Infinity;
  for(let k=0;k<s.open.length;k++){const i=s.open[k],f=s.dist[i]+(s.useH?heur(i):0);if(f<bf){bf=f;bi=k;}}
  const cur=s.open.splice(bi,1)[0];
  s.inOpen[cur]=0;
  if(s.visited[cur])return;
  s.visited[cur]=1;s.expanded++;
  if(cur===N-1){s.done=true;let p=cur,arr=[];while(p!==-1){arr.push(p);p=s.prev[p];}s.path=arr.reverse();s.cost=s.dist[N-1];return;}
  const nb=neigh(cur);
  for(let j=0;j<nb.length;j++){
    const n=nb[j];
    if(s.visited[n])continue;
    const nd=s.dist[cur]+cost[n];
    if(nd<s.dist[n]){s.dist[n]=nd;s.prev[n]=cur;if(!s.inOpen[n]){s.open.push(n);s.inOpen[n]=1;}}
  }
}
function terrain(c){const t=(c-1)/8;return `hsl(${100-t*70},50%,${38+t*12}%)`;}
function drawPanel(s,ox){
  for(let y=0;y<H;y++)for(let x=0;x<W;x++){
    const i=y*W+x;
    ctx.fillStyle=terrain(cost[i]);
    ctx.fillRect(ox+x*CS,GY+y*CS,CS-1,CS-1);
    if(s.visited[i]){ctx.fillStyle='rgba(30,90,230,0.5)';ctx.fillRect(ox+x*CS,GY+y*CS,CS-1,CS-1);}
    else if(s.inOpen[i]){ctx.fillStyle='rgba(255,215,0,0.55)';ctx.fillRect(ox+x*CS,GY+y*CS,CS-1,CS-1);}
  }
  for(let k=0;k<s.path.length;k++){const p=xy(s.path[k]);ctx.fillStyle='#ff3050';ctx.fillRect(ox+p[0]*CS+3,GY+p[1]*CS+3,CS-7,CS-7);}
  ctx.fillStyle='#33ff66';ctx.fillRect(ox+1,GY+1,CS-2,CS-2);
  ctx.fillStyle='#cc33ff';ctx.fillRect(ox+(W-1)*CS+1,GY+(H-1)*CS+1,CS-2,CS-2);
}
function render(){
  ctx.clearRect(0,0,canvas.width,canvas.height);
  drawPanel(dij,GX);
  drawPanel(ast,PX);
  lbl.textContent='Dijkstra   expanded: '+dij.expanded+'   cost: '+(dij.done?dij.cost.toFixed(0):'-');
  lbl2.textContent='A*   expanded: '+ast.expanded+'   cost: '+(ast.done?ast.cost.toFixed(0):'-');
}
function loop(){
  for(let k=0;k<2;k++){if(!dij.done)step(dij);if(!ast.done)step(ast);}
  render();
  if(dij.done&&ast.done&&!restarting){restarting=true;setTimeout(initAll,1600);}
  requestAnimationFrame(loop);
}
initAll();
loop();
</script></body></html>
Claude Haiku 4.5frontier referenceSTATLIM
Show code
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Dijkstra vs A*</title>
<style>
  body { margin: 0; padding: 10px; font-family: monospace; background: #000; color: #0f0; }
  canvas { display: block; margin: 10px auto; background: #111; border: 1px solid #0f0; }
  div { text-align: center; font-size: 12px; }
</style>
</head>
<body>
<canvas id="c" width="800" height="600"></canvas>
<div id="info"></div>
<script>
const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
const w = 800, h = 500;
const gw = 30, gh = 20;
const cw = w / (2 * gw), ch = h / gh;

let grid = [];
for (let i = 0; i < gw * gh; i++) grid[i] = Math.random() * 10 + 1;

const start = { x: 1, y: 1 };
const goal = { x: gw - 2, y: gh - 2 };

function idx(x, y) { return y * gw + x; }
function heur(a, b) { return Math.abs(a.x - b.x) + Math.abs(a.y - b.y); }

function runDijkstra() {
  const visited = new Set(), frontier = [];
  const dist = new Uint32Array(gw * gh);
  dist.fill(1e9);
  dist[idx(start.x, start.y)] = 0;
  frontier.push([0, start.x, start.y]);
  let exp = 0;

  while (frontier.length > 0) {
    frontier.sort((a, b) => a[0] - b[0]);
    const [d, x, y] = frontier.shift();
    if (visited.has(idx(x, y))) continue;
    visited.add(idx(x, y));
    exp++;
    if (x === goal.x && y === goal.y) break;
    for (let [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < gw && ny >= 0 && ny < gh && !visited.has(idx(nx, ny))) {
        const nd = d + grid[idx(nx, ny)];
        if (nd < dist[idx(nx, ny)]) {
          dist[idx(nx, ny)] = nd;
          frontier.push([nd, nx, ny]);
        }
      }
    }
  }
  return { visited: Array.from(visited).map(i => ({ x: i % gw, y: Math.floor(i / gw) })), expanded: exp, cost: dist[idx(goal.x, goal.y)] };
}

function runAStar() {
  const visited = new Set(), frontier = [];
  const dist = new Uint32Array(gw * gh);
  dist.fill(1e9);
  dist[idx(start.x, start.y)] = 0;
  frontier.push([heur(start, goal), 0, start.x, start.y]);
  let exp = 0;

  while (frontier.length > 0) {
    frontier.sort((a, b) => a[0] - b[0]);
    const [_, d, x, y] = frontier.shift();
    if (visited.has(idx(x, y))) continue;
    visited.add(idx(x, y));
    exp++;
    if (x === goal.x && y === goal.y) break;
    for (let [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < gw && ny >= 0 && ny < gh && !visited.has(idx(nx, ny))) {
        const nd = d + grid[idx(nx, ny)];
        if (nd < dist[idx(nx, ny)]) {
          dist[idx(nx, ny)] = nd;
          frontier.push([nd + heur({x:nx, y:ny}, goal), nd, nx, ny]);
        }
      }
    }
  }
  return { visited: Array.from(visited).map(i => ({ x: i % gw, y: Math.floor(i / gw) })), expanded: exp, cost: dist[idx(goal.x, goal.y)] };
}

const dij = runDijkstra();
const astar = runAStar();

function animate() {
  ctx.fillStyle = '#111';
  ctx.fillRect(0, 0, w, h);

  for (let side = 0; side < 2; side++) {
    const ox = side * (w / 2);
    for (let x = 0; x < gw; x++) {
      for (let y = 0; y < gh; y++) {
        const c = Math.floor(grid[idx(x, y)] * 25);
        ctx.fillStyle = `rgb(${c},${c},${c})`;
        ctx.fillRect(ox + x * cw, y * ch, cw, ch);
      }
    }

    const vis = side === 0 ? dij.visited : astar.visited;
    ctx.fillStyle = side === 0 ? '#0f0' : '#f0f';
    for (let p of vis) {
      ctx.fillRect(ox + p.x * cw + 2, p.y * ch + 2, cw - 4, ch - 4);
    }

    ctx.fillStyle = '#ff0';
    ctx.fillRect(ox + start.x * cw + 2, start.y * ch + 2, cw - 4, ch - 4);
    ctx.fillStyle = '#f00';
    ctx.fillRect(ox + goal.x * cw + 2, goal.y * ch + 2, cw - 4, ch - 4);
  }

  ctx.fillStyle = '#0f0';
  ctx.font = '12px monospace';
  ctx.fillText('Dijkstra: ' + dij.expanded + ' cells, cost=' + dij.cost, 10, 520);
  ctx.fillText('A*: ' + astar.expanded + ' cells, cost=' + astar.cost, 400, 520);

  requestAnimationFrame(animate);
}

animate();
</script>
</body>
</html>
Results at a glance— every model in this round with score, response time and status.

Who wrote what

ModelBlind scoreLatencyStatus
qwen3.5:9b —38.4 sOK
qwen3:8b ——harness
gemma4:26b ——harness
qwen3:14b —38.4 sOK
qwen3-coder:30b —35.8 sOK
llama3.1:8b —21.9 sOK
deepseek-r1:14b —138.6 sOK
mistral-small:24b —110.0 sOK
command-r:35b —158.5 sOK
deepseek-r1:32b —152.0 sOK
qwq:32b —152.0 sOK

Frontier reference — outside the blind field

These models answered the identical prompt outside the blind field. They are deliberately not scored and not part of the blind comparison — they are there so you can see where a frontier model lands on the same task.

Collected differently from the blind field: the local models run through a plain API harness, the frontier references through a context-free agent, one shot, no retries. Response times are therefore not comparable and are not shown. On two English tasks the reference answer came back in German — an artefact of that harness, flagged on the affected rounds.
Claude Opus 5frontier reference
Show code
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Dijkstra vs A* on the same weighted grid</title>
<style>
html,body{margin:0;height:100%;background:#0b0f16;color:#e6edf3;display:flex;align-items:center;justify-content:center;
font:13px/1.4 ui-monospace,SFMono-Regular,Menlo,Consolas,monospace}
canvas{background:#141b25;border-radius:12px;box-shadow:0 18px 60px #000a;max-width:98vw;height:auto}
</style>
</head>
<body>
<canvas id="c"></canvas>
<script>
const W=30,H=20,CS=18,N=W*H,PAD=16,TOP=48,PW=W*CS,PH=H*CS,S=0,G=N-1;
const c=document.getElementById('c'),x=c.getContext('2d');
c.width=PAD*3+PW*2;c.height=TOP+PH+PAD+26;
let cost,gmin,A,B,hold=0;
function gen(){
  let f=new Float64Array(N);
  for(let i=0;i<N;i++)f[i]=Math.random();
  for(let p=0;p<2;p++){const g=new Float64Array(N);
    for(let y=0;y<H;y++)for(let X=0;X<W;X++){let s=0,n=0;
      for(let dy=-1;dy<=1;dy++)for(let dx=-1;dx<=1;dx++){const a=X+dx,b=y+dy;
        if(a<0||b<0||a>=W||b>=H)continue;s+=f[b*W+a];n++}
      g[y*W+X]=s/n}
    f=g}
  let mn=1e9,mx=-1e9;for(const v of f){if(v<mn)mn=v;if(v>mx)mx=v}
  cost=new Int32Array(N);
  for(let i=0;i<N;i++)cost[i]=1+Math.round(Math.pow((f[i]-mn)/(mx-mn||1),1.35)*8);
  cost[S]=1;cost[G]=1;gmin=9;for(const v of cost)if(v<gmin)gmin=v;
}
function mk(useH){
  const st={dist:new Float64Array(N).fill(1e18),prev:new Int32Array(N).fill(-1),
    done:new Uint8Array(N),inOpen:new Uint8Array(N),open:[S],exp:0,path:null,fin:false,useH:useH};
  st.dist[S]=0;st.inOpen[S]=1;return st;
}
function hh(n){return (Math.abs(n%W-G%W)+Math.abs((n/W|0)-(G/W|0)))*gmin}
function trace(st){const p=[];let u=G;while(u>=0){p.push(u);u=st.prev[u]}return p.reverse()}
function step(st){
  if(st.fin)return;
  if(!st.open.length){st.fin=true;return}
  let bi=0,bf=1e18;
  for(let i=0;i<st.open.length;i++){const n=st.open[i],f=st.dist[n]+(st.useH?hh(n):0);
    if(f<bf){bf=f;bi=i}}
  const u=st.open[bi];st.open.splice(bi,1);st.inOpen[u]=0;
  if(st.done[u])return;
  st.done[u]=1;st.exp++;
  if(u===G){st.fin=true;st.path=trace(st);return}
  const ux=u%W,uy=u/W|0;
  const nb=[[1,0],[-1,0],[0,1],[0,-1]];
  for(const d of nb){const a=ux+d[0],b=uy+d[1];
    if(a<0||b<0||a>=W||b>=H)continue;
    const v=b*W+a,nd=st.dist[u]+cost[v];
    if(nd<st.dist[v]-1e-9){st.dist[v]=nd;st.prev[v]=u;
      if(!st.done[v]&&!st.inOpen[v]){st.inOpen[v]=1;st.open.push(v)}}}
}
function cell(i){return[(i%W)*CS,(i/W|0)*CS]}
function panel(ox,st,title){
  for(let i=0;i<N;i++){const p=cell(i),px=ox+p[0],py=TOP+p[1],v=cost[i];
    x.fillStyle='hsl('+(142-v*9)+','+(24+v*3)+'%,'+(80-v*6.6)+'%)';
    x.fillRect(px,py,CS-1,CS-1);
    if(st.done[i]){x.fillStyle='rgba(56,139,253,.46)';x.fillRect(px,py,CS-1,CS-1)}
    else if(st.inOpen[i]){x.fillStyle='rgba(255,193,58,.82)';x.fillRect(px,py,CS-1,CS-1)}}
  if(st.path){
    x.lineJoin='round';x.lineCap='round';x.beginPath();
    for(let k=0;k<st.path.length;k++){const p=cell(st.path[k]);
      const px=ox+p[0]+CS/2-.5,py=TOP+p[1]+CS/2-.5;k?x.lineTo(px,py):x.moveTo(px,py)}
    x.strokeStyle='#ff4f6d';x.lineWidth=5;x.stroke();
    x.strokeStyle='rgba(255,255,255,.9)';x.lineWidth=1.6;x.stroke()}
  for(const m of [[S,'#22e08a'],[G,'#ff2f6a']]){const p=cell(m[0]);
    x.fillStyle=m[1];x.fillRect(ox+p[0],TOP+p[1],CS-1,CS-1);
    x.strokeStyle='#fff';x.lineWidth=1.5;x.strokeRect(ox+p[0]+.75,TOP+p[1]+.75,CS-2.5,CS-2.5)}
  x.strokeStyle='rgba(255,255,255,.12)';x.lineWidth=1;
  x.strokeRect(ox-.5,TOP-.5,PW,PH);
  x.fillStyle='#e6edf3';x.font='bold 15px ui-monospace,monospace';x.fillText(title,ox,20);
  x.font='12px ui-monospace,monospace';x.fillStyle='#8fa3b8';
  x.fillText('expanded '+st.exp+'   ·   path cost '+(st.path?st.dist[G]:'…')+
    (st.fin&&!st.path?'  (no path)':''),ox,38);
}
function draw(){
  x.clearRect(0,0,c.width,c.height);
  panel(PAD,A,'Dijkstra');
  panel(PAD*2+PW,B,'A*  (Manhattan × '+gmin+')');
  const y=TOP+PH+19;
  const key=[['#5aa0f5','visited'],['#ffc13a','frontier'],['#ff4f6d','shortest path']];
  let kx=PAD;x.font='12px ui-monospace,monospace';
  for(const k of key){x.fillStyle=k[0];x.fillRect(kx,y-9,10,10);
    x.fillStyle='#8fa3b8';x.fillText(k[1],kx+15,y);kx+=25+x.measureText(k[1]).width}
  const same=A.path&&B.path&&Math.abs(A.dist[G]-B.dist[G])<1e-9;
  x.fillStyle=same?'#22e08a':'#8fa3b8';
  const msg=same?'identical cost '+A.dist[G]+'  ·  A* expanded '+(A.exp-B.exp)+' fewer cells ('+
    Math.round(100-B.exp/A.exp*100)+'% less work)':'searching the same random terrain (cost 1–9)…';
  x.fillText(msg,c.width-PAD-x.measureText(msg).width,y);
}
function frame(){
  requestAnimationFrame(frame);
  if(hold>0){if(--hold===0){gen();A=mk(0);B=mk(1)}}
  else{for(let k=0;k<7;k++){step(A);step(B)}
    if(A.fin&&B.fin)hold=120}
  draw();
}
gen();A=mk(0);B=mk(1);requestAnimationFrame(frame);
</script>
</body>
</html>