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.
Create ONE self-contained HTML file (STRICT LIMIT: max 7000 characters in total — this is a budget on characters, not on lines, so removing line breaks does not help) that animates Dijkstra's algorithm on a <canvas>: a grid where each cell has a random movement cost (draw cheap cells lighter and expensive cells darker), starting from a source cell, repeatedly expand the cheapest known unsettled cell exactly like Dijkstra's algorithm, coloring settled cells by their accumulated distance, and once a target cell is reached, trace the resulting cheapest path. Restart with a freshly generated cost grid, source and target when finished. Show the number of cells settled and the total path cost. 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.
```html
<!DOCTYPE html>
<html>
<head>
<title>Dijkstra Visualization</title>
<style>body {background-color: #111; display: flex; justify-content: center; align-items: center; height: 100vh; margin: 0; font-family: sans-serif; color: white;}#container {display: flex; gap: 20px;};canvas {border: 2px solid #444; background-color: #222;}#stats {padding: 10px; background-color: #333; border-radius: 5px;}h2 {margin: 0 0 10px 0; font-size: 1.2em;}p {margin: 5px 0;}
</style>
</head>
<body>
<div id="container">
<canvas id="dijkstraCanvas"></canvas>
<div id="stats">
<h2>Status</h2>
<p>Settled Cells: <span id="settledCount">0</span> / <span id="totalCells">0</span></p>
<p>Path Cost: <span id="pathCost">N/A</span></p>
</div>
</div>
<script>
const canvas = document.getElementById('dijkstraCanvas');
const ctx = canvas.getContext('2d');
let GRID_SIZE = 30;
let CELL_DIM = 15;
canvas.width = GRID_SIZE * CELL_DIM;
canvas.height = GRID_SIZE * CELL_DIM;
// Global state variables
let grid = [];
let dist = []; // Stores accumulated distance from source
let prev = []; // For path reconstruction
let settled = []; // Boolean matrix for visited nodes
let priorityQueue = []; // Simple array acting as a min-heap (simulated)
const SOURCE_X = 0;
const SOURCE_Y = 0;
const TARGET_X = GRID_SIZE - 1;
const TARGET_Y = GRID_SIZE - 1;
// --- Utility Functions ---
function rand(min, max) { return Math.random() * (max - min) + min; }
function getNeighbors(x, y) {
const neighbors = [];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < GRID_SIZE && ny >= 0 && ny < GRID_SIZE) {
neighbors.push({x: nx, y: ny});
}
}
return neighbors;
}
// Simple Priority Queue management (Min-Heap simulation)
function pqPush(keyX, keyY, d) {
priorityQueue.push({ x: keyX, y: keyY, dist: d });
// Sort the array to keep the minimum distance element at index 0
priorityQueue.sort((a, b) => a.dist - b.dist);
}
function pqPop() {
if (priorityQueue.length === 0) return null;
return priorityQueue.shift();
}
// --- Initialization and Reset ---
function generateGrid() {
grid = [];
for (let i = 0; i < GRID_SIZE; i++) {
grid[i] = [];
for (let j = 0; j < GRID_SIZE; j++) {
// Random cost between 1 and 5
grid[i][j] = Math.floor(rand(1, 6));
}
}
}
function resetState() {
dist = Array(GRID_SIZE).fill(0).map(() => Array(GRID_SIZE).fill(Infinity));
prev = Array(GRID_SIZE).fill(0).map(() => Array(GRID_SIZE).fill(null));
settled = Array(GRID_SIZE).fill(0).map(() => Array(GRID_SIZE).fill(false));
priorityQueue = [];
// Set initial state
dist[SOURCE_X][SOURCE_Y] = 0;
pqPush(SOURCE_X, SOURCE_Y, 0);
// Reset display stats
document.getElementById('settledCount').textContent = '0';
document.getElementById('pathCost').textContent = 'N/A';
}
// --- Drawing Functions ---
function drawGridCosts() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let i = 0; i < GRID_SIZE; i++) {
for (let j = 0; j < GRID_SIZE; j++) {
const cost = grid[i][j];
// Map cost to color: cheaper (low cost) -> lighter/greener, expensive (high cost) -> darker
const brightness = Math.round(255 - (cost * 30)); // Range approx 175-255
ctx.fillStyle = `rgb(${brightness}, ${Math.min(255, brightness*0.8)}, ${Math.max(50, brightness*0.9)})`;
ctx.fillRect(j * CELL_DIM, i * CELL_DIM, CELL_DIM - 1, CELL_DIM - 1);
}
}
}
function drawState() {
// Draw settled distances (color gradient)
for (let i = 0; i < GRID_SIZE; i++) {
for (let j = 0; j < GRID_SIZE; j++) {
const x = j * CELL_DIM;
const y = i * CELL_DIM;
// Reset color to background if not settled
if (!settled[i][j]) continue;
const d = dist[i][j];
ctx.fillStyle = `rgba(100, 150, ${Math.max(100, Math.min(255, d * 4))}, ${d > 0 ? 0.8 : 0.3})`;
ctx.fillRect(x, y, CELL_DIM - 1, CELL_DIM - 1);
}
}
// Draw start/target markers
ctx.fillStyle = 'yellow';
ctx.fillRect(SOURCE_X * CELL_DIM, SOURCE_Y * CELL_DIM, CELL_DIM - 1, CELL_DIM - 1);
ctx.fillStyle = 'cyan';
ctx.fillRect(TARGET_X * CELL_DIM, TARGET_Y * CELL_DIM, CELL_DIM - 1, CELL_DIM - 1);
}
function drawPath() {
let pathFound = false;
let currentX = TARGET_X;
let currentY = TARGET_Y;
// Backtrack from target until source or null parent is reached
while (currentX !== null && currentY !== null) {
const xDraw = currentX * CELL_DIM + CELL_DIM/2 - 1;
const yDraw = currentY * CELL_DIM + CELL_DIM/2 - 1;
if (dist[currentX][currentY] > 0 && !settled[currentX][currentY]) {
// Draw path slightly differently to distinguish from settled nodes
ctx.fillStyle = `rgba(255, 255, 0, 0.9)`;
ctx.fillRect(xDraw, yDraw, CELL_DIM - 1, CELL_DIM - 1);
}
if (currentX === SOURCE_X && currentY === SOURCE_Y) break;
const next = prev[currentX][currentY];
if (!next) break;
currentX = next.x;
currentY = next.y;
}
pathFound = true;
document.getElementById('pathCost').textContent = pathFound ? dist[TARGET_X][TARGET_Y] : 'Failure';
}
// --- Dijkstra Step Logic ---
function dijkstraStep() {
if (priorityQueue.length === 0) {
console.log("No path found.");
return false; // Algorithm finished, no path to target
}
const current = pqPop();
const x = current.x;
const y = current.y;
const d = current.dist;
if (settled[y][x]) return true; // Already processed in this step/cycle
// Mark as settled and update stats
settled[y][x] = true;
document.getElementById('settledCount').textContent = (globalStats.settledCount + 1).toString();
globalStats.settledCount++;
if (x === TARGET_X && y === TARGET_Y) {
drawPath();
return false; // Target reached! Stop animation loop.
}
// Process neighbors
const neighbors = getNeighbors(x, y);
for (const neighbor of neighbors) {
const nx = neighbor.x;
const ny = neighbor.y;
const cost = grid[ny][nx];
const newDist = d + cost;
if (!settled[ny][nx] && newDist < dist[ny][nx]) {
dist[ny][nx] = newDist;
prev[ny][nx] = {x: x, y: y};
// Update or push to PQ
pqPush(nx, ny, newDist);
}
}
return true; // Continue animation
}
// --- Animation Loop and Global State ---
let globalStats = { settledCount: 0 };
let animationRunning = true;
function animate() {
if (!animationRunning) return;
const continues = dijkstraStep();
drawState();
// If the step was successful, schedule next frame.
setTimeout(() => {
requestAnimationFrame(animate);
}, 10); // Fast animation speed
}
function startSimulation() {
// Reset and initialize state
generateGrid();
resetState();
drawGridCosts();
animationRunning = true;
animate();
}
// Initial startup call
startSimulation();
</script>
</body>
</html>
``````html
<!DOCTYPE html>
<html><body style="margin:0;overflow:hidden;background:#1a1a1a;">
<canvas id=c></canvas>
<div id=d style="position:absolute;top:0;left:0;color:white;font-family:sans-serif;font-size:14px;line-height:20px;">Path Cost: 0 • Cells Settled: 0</div>
<script>
const c=document.getElementById('c'),d=document.getElementById('d'),w=30,h=30,s=w*20,t=s/2;
let ctx=c.getContext('2d');
ctx.canvas.width=h*40;ctx.canvas.height=w*40;
let grid=[],openSet=[],closedSet=new Set,cameFrom={},gScore={},fScore={},showPath=false,pathCost=0,settleCount=0;
function init(){grid=[];for(let y=0;y<20;y++)grid[y]=[];for(let y=0;y<20;y++)for(let x=0;x<20;x++)grid[y][x]=Math.floor(Math.random()*10)+1;setSourceTarget();}
function setSourceTarget(){let sX=Math.floor(Math.random()*20),sY=Math.floor(Math.random()*20);let tX=Math.floor(Math.random()*20),tY=Math.floor(Math.random()*20);source={x:sX,y:sY};target={x:tX,y:tY};}
function draw(c,x,y,w,h){c.fillStyle='#'+(w-x*y*1.5).toString(16).padStart(3,'0');c.fillRect(x*w,y*h,w,h);c.strokeStyle='black';c.strokeRect(x*w,y*h,w,h);}
function animate(){if(!source||!target)return;let show=d.textContent=`Path Cost: ${pathCost} • Cells Settled: ${settleCount}`.startsWith('Path Cost: 0')?false:true;if(openSet.length){let i=0;while(i<openSet.length)i++;for(let k of openSet)gScore[k.x+','+k.y]?(void 0):(gScore[k.x+','+k.y]=Infinity);let minDist=Math.min(...openSet.map(k=>gScore[k.x+','+k.y]));let minX,minY;for(let i=0;i<20;i++)for(let j=0;j<20;j++)if(gScore[i+','+j]===minDist&&(minX==null||i<j))minX=i,minY=j;if(minX!=null){if(minX==target.x&&minY==target.y){pathCost=gScore[minX+','+minY];showPath=true;settleCount=20*20;setTimeout(init,100);return;}cameFrom[minX+','+minY]=openSet.find(k=>k.x==minX&&k.y==minY);openSet.splice(openSet.indexOf({x:minX,y:minY}),1);closedSet.add(minX+','+minY);settleCount++;for(let dir of [{x:-1,y:0},{x:1,y:0},{x:0,y:-1},{x:0,y:1}]){let newX=minX+dir.x,newY=minY+dir.y;if(newX>=0&&newX<20&&newY>=0&&newY<20&&!closedSet.has(newX+','+newY)){let tempG=grid[dir.y][dir.x];let newDist=gScore[minX+','+minY]+tempG;let h=(((newX-target.x)**2+(newY-target.y)**2)**.5);fScore[newX+','+newY]=newDist+h;if(newDist<gScore[newX+','+newY]){gScore[newX+','+newY]=newDist;if(!openSet.some(k=>k.x==newX&&k.y==newY))openSet.push({x:newX,y:newY});}}}}}requestAnimationFrame(animate);}
function drawGrid(){ctx.clearRect(0,0,h*40,w*40);for(let y=0;y<20;y++)for(let x=0;x<20;x++){let cost=grid[y][x];if({x:y,x:Y}==source)draw(ctx,1,x,y,1),draw(ctx,0,x,y,1);else if(x==target.x&&y==target.y)draw(ctx,2,x,y,1);else if(closedSet.has(x+','+y))draw(ctx,3,x,y,1);else if(openSet.some(k=>k.x==x&&k.y==y))draw(ctx,4,x,y,1);else draw(ctx,0,x,y,1);}}
animate();setInterval(drawGrid,100);
</script>
</body></html>
``````html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Dijkstra's Algorithm</title>
<style>
body {
margin: 0;
font-family: monospace;
}
#info {
position: absolute;
top: 10px;
left: 10px;
background-color: rgba(255, 255, 255, 0.8);
padding: 5px;
border-radius: 5px;
}
</style>
</head>
<body>
<canvas id="grid" width="800" height="600"></canvas>
<div id="info">cells settled: <span id="settled">0</span>, total path cost: <span id="cost">0</span></div>
<script>
const grid = document.getElementById('grid');
const ctx = grid.getContext('2d');
const infoDiv = document.getElementById('info');
let width, height;
let gridSize = 40;
const random = () => Math.random() * 255 | 0;
const randomInt = (max) => Math.floor(Math.random() * max);
function init(width, height) {
this.width = width;
this.height = height;
this.grid = Array(height).fill(0).map(() => Array(width).fill(0));
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
this.grid[y][x] = randomInt(255);
}
}
const start = [randomInt(width), randomInt(height)];
const end = [randomInt(width), randomInt(height)];
while (start[0] === end[0] && start[1] === end[1]) {
end = [randomInt(width), randomInt(height)];
}
this.start = start;
this.end = end;
}
function drawGrid() {
ctx.clearRect(0, 0, grid.width, grid.height);
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
const cost = this.grid[y][x];
ctx.fillStyle = `rgb(${cost}, ${cost}, ${cost})`;
ctx.fillRect(x * gridSize, y * gridSize, gridSize - 1, gridSize - 1);
}
}
}
function drawDistance(y, x) {
if (y < 0 || y >= height || x < 0 || x >= width) return;
const cost = this.grid[y][x];
ctx.fillStyle = `rgb(${cost}, ${cost}, ${cost})`;
ctx.beginPath();
ctx.arc(x * gridSize + gridSize / 2, y * gridSize + gridSize / 2, gridSize / 4, 0, Math.PI * 2);
ctx.fill();
}
function drawPath(y, x) {
if (y < 0 || y >= height || x < 0 || x >= width) return;
const cost = this.grid[y][x];
ctx.fillStyle = `rgb(${cost}, ${cost}, ${cost})`;
ctx.beginPath();
ctx.arc(x * gridSize + gridSize / 2, y * gridSize + gridSize / 2, gridSize / 4, 0, Math.PI * 2);
ctx.fill();
}
function dijkstra() {
const settled = {};
const queue = [[this.start[0], this.start[1]]];
let cost = 0;
while (queue.length > 0) {
const [x, y] = queue.shift();
if (!settled[x + ',' + y]) {
settled[x + ',' + y] = true;
drawDistance(y, x);
for (const [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
queue.push([nx, ny]);
}
}
}
queue.sort((a, b) => this.grid[a[1]][a[0]] - this.grid[b[1]][b[0]]);
}
cost = Object.values(this.grid).reduce((acc, row) => acc + row.reduce((c, cell) => c + cell, 0), 0);
document.getElementById('settled').textContent = settled.length;
document.getElementById('cost').textContent = cost;
}
function drawPathToTarget() {
const queue = [[this.end[0], this.end[1]]];
let path = [];
while (queue.length > 0) {
const [x, y] = queue.shift();
path.push([x, y]);
for (const [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
queue.push([nx, ny]);
}
}
}
for (let i = path.length - 2; i >= 0; i--) {
drawPath(path[i][1], path[i][0]);
}
}
init(grid.width / gridSize | 0, grid.height / gridSize | 0);
let animationFrameId;
function animate() {
dijkstra();
drawGrid();
if (this.start[0] === this.end[0] && this.start[1] === this.end[1]) {
drawPathToTarget();
const newInit = () => init(grid.width / gridSize | 0, grid.height / gridSize | 0);
animationFrameId = null;
setTimeout(newInit, 2000);
} else {
animationFrameId = requestAnimationFrame(animate.bind(this));
}
}
animate.call(this);
</script>
</body>
</html>
``````html
<!DOCTYPE html>
<html>
<head><title>Dijkstra's Algorithm Animation</title></head>
<body><canvas id="dijkCanvas"></canvas><script>const canvas = document.getElementById('dijkCanvas');const ctx = canvas.getContext('2d');let SIZE, CELL_SIZE;let grid, distGrid, costs, startNode, endNode;let settledCount = 0;let animationState = 'INIT';
function init(size) {
SIZE = size;
CELL_SIZE = Math.floor(Math.min(canvas.width, canvas.height) / (size + 1));
canvas.width = (size + 1) * CELL_SIZE;
canvas.height = (size + 1) * CELL_SIZE;
grid = [];
distGrid = Array(size).fill(0).map(() => Array(size).fill(Infinity));
costs = [];
for(let i=0; i<size; i++) {
grid[i] = [];
costs[i] = [];
for(let j=0; j<size; j++) {
grid[i][j] = { cost: 1 + Math.random() * 3, visited: false }; // Cost between cells
costs[i][j] = Math.floor(Math.random() * 255); // Base color value (0-255)
}
}
startNode = { x: 0, y: 0 };
endNode = { x: size - 1, y: size - 1 };
distGrid[startNode.y][startNode.x] = 0;
settledCount = 0;
animationState = 'RUNNING';
}
function draw() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for(let y=0; y<SIZE; y++) {
for(let x=0; x<SIZE; x++) {
// Draw cost background (Cost between cells: grid[y][x])
ctx.fillStyle = `rgb(${costs[y][x]}, ${costs[y+1] ? costs[y+1][x] : 0}, ${costs[y][x]})`; // Simplified color mapping for visibility
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
// Draw distance/settled state (Cell center)
let d = distGrid[y][x];
let color;
if (d === Infinity) {
color = '#333'; // Unvisited/Unreachable
} else if (d > 0 && Math.abs(d - distGrid[y-1]?.[x] || dMath.min(distGrid[y+1][x], d)) < 5 && settledCount > 0) {
color = `rgba(${255},${Math.max(0, Math.floor((d / (SIZE * SIZE * 3)) * 255))}, ${Math.min(255, Math.ceil(d / (SIZE * SIZE * 3)))}), ${Math.min(1, settledCount/200)})`;
} else if (x === startNode.x && y === startNode.y) {
color = 'rgba(0, 255, 0)'; // Start
} else if (x === endNode.x && y === endNode.y) {
color = 'rgba(255, 0, 0)'; // End
} else if (distGrid[y][x] !== Infinity) {
// Gradient based on distance: closer to starting point -> greener/lighter
let ratio = Math.min(1, d / (SIZE * SIZE));
color = `rgba(${255}, ${Math.floor(200 * (1 - ratio))}, ${Math.floor(200 * (1 - ratio))}, 0.8)`;
} else {
color = '#333';
}
ctx.fillStyle = color;
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
}
/** Dijkstra's implementation using a simple scan for the minimum distance node */
function dijkstraStep() {
if (animationState === 'PAUSED') return;
let minDistance = Infinity;
let currentX = -1, currentY = -1;
// 1. Find the unsettled cell with the smallest distance (Priority Queue simulation)
for(let y=0; y<SIZE; y++) {
for(let x=0; x<SIZE; x++) {
if (!grid[y][x].visited && distGrid[y][x] < minDistance) {
minDistance = distGrid[y][x];
currentX = x;
currentY = y;
}
}
}
// Check termination condition: All reachable nodes settled, or target reached.
if (currentX === -1 || minDistance === Infinity) {
animationState = 'FINISHED';
draw(); // Final draw state
return;
}
let uX = currentX;
let uY = currentY;
// 2. Process the selected node (Settle it)
grid[uY][uX].visited = true;
settledCount++;
// Path tracing visualization: If we just settled the end node, trace and finish.
if (uX === endNode.x && uY === endNode.y) {
animationState = 'PATH_FOUND';
return;
}
// 3. Update neighbors
let neighbors = [[uX + 1, uY], [uX - 1, uY], [uX, uY + 1], [uX, uY - 1]];
for(const [nX, nY] of neighbors) {
if (nX >= 0 && nX < SIZE && nY >= 0 && nY < SIZE) {
let v = grid[nY][nX];
// Cost to move between u and v: We use the cost stored at v's location for simplicity.
let edgeCost = Math.max(1, costs[uY][uX] || 1);
if (!grid[nY][nX].visited && distGrid[uY][uX] + edgeCost < distGrid[nY][nX]) {
distGrid[nY][nX] = distGrid[uY][uX] + edgeCost;
}
}
}
draw();
}
function tracePath() {
let path = [];
let current = { x: endNode.x, y: endNode.y };
let maxSteps = SIZE * SIZE;
// Backtrack from the end node until we reach the start node (where distance is 0)
while (current.y !== startNode.y || current.x !== startNode.x && maxSteps-- > 0) {
path.push(current);
let foundNeighbor = false;
// Check neighbors to find one that satisfies Dijkstra's property: dist[neighbor] = dist[current] + cost(current, neighbor)
[[1, 0], [-1, 0], [0, 1], [0, -1]].forEach(([dx, dy]) => {
let prevX = current.x - dx;
let prevY = current.y - dy;
if (prevX >= 0 && prevX < SIZE && prevY >= 0 && prevY < SIZE) {
// Check if moving from neighbor to current yields the current known distance
let costToNeighbor = Math.max(1, costs[current.y][current.x] || 1);
if (distGrid[prevY][prevX] !== Infinity && distGrid[prevY][prevX] + costToNeighbor === distGrid[current.y][current.x]) {
// Found the previous node in the optimal path
current = { x: prevX, y: prevY };
foundNeighbor = true;
}
}
});
if (!foundNeighbor) break; // Should not happen if target is reachable
}
path.reverse();
return path;
}
function animate() {
if (animationState === 'RUNNING' || animationState === 'PATH_FOUND') {
dijkstraStep();
setTimeout(() => requestAnimationFrame(animate), 10);
} else if (animationState === 'FINISHED') {
// Path tracing logic: Since we settled the target, now we trace and finalize.
let path = tracePath();
// Redraw grid with calculated path
ctx.clearRect(0, 0, canvas.width, canvas.height);
for(let y=0; y<SIZE; y++) {
for(let x=0; x<SIZE; x++) {
ctx.fillStyle = '#333'; // Background cost visualization
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
let d = distGrid[y][x];
if (d === Infinity) {
ctx.fillStyle = 'rgba(51, 51, 51, 0.8)'; // Unreachable
} else if (Math.hypot(x-startNode.x, y-startNode.y) < Math.sqrt(SIZE*SIZE)*0.4 && d > 0) {
// Color based on proximity/distance for settled nodes
let ratio = Math.min(1, d / (SIZE * SIZE));
ctx.fillStyle = `rgba(255, ${Math.floor(200 * (1 - ratio))}, ${Math.floor(200 * (1 - ratio))}, 0.8)`;
} else if (x === startNode.x && y === startNode.y) {
ctx.fillStyle = 'rgba(0, 255, 0)'; // Start
} else if (x === endNode.x && y === endNode.y) {
ctx.fillStyle = 'rgba(255, 0, 0)'; // End
} else {
ctx.fillStyle = '#333';
}
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
// Draw the final path (Green line)
if (path.length > 0) {
for (let i = 0; i < path.length; i++) {
const p = path[i];
ctx.fillStyle = 'rgba(0, 255, 0, 1)';
ctx.fillRect(p.x * CELL_SIZE, p.y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
// Display metrics (Simple console output for character budget)
console.log(`Animation Finished. Settled Cells: ${settledCount}. Total Path Cost: ${distGrid[endNode.y][endNode.x] !== Infinity ? distGrid[endNode.y][endNode.x].toFixed(2) : 'N/A'}`);
// Prepare for restart
setTimeout(() => {
init(SIZE); // Re-initialize with the same size (or a new random size if desired, but keeping it simple)
}, 1500);
}
}
window.onload = () => {
const initialSize = 20; // Use a smaller grid to keep character count low and performance high enough for smooth animation
init(initialSize);
animate();
};```html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Dijkstra Visualization</title>
<style>body { background: #111; display: flex; justify-content: center; align-items: center; min-height: 100vh; margin: 0; } canvas { border: 2px solid #444; }</style>
</head>
<body><canvas id="dijkstraCanvas"></canvas><script>
const canvas = document.getElementById('dijkstraCanvas');
const ctx = canvas.getContext('2d');
let N = 30; // Grid size N x N
let S, T; // Source and Target coordinates
let grid; // Cost map
let dist; // Distance map (Dijkstra's distances)
let prev; // Predecessor map for path reconstruction
let settledCount = 0;
let animationRunning = false;
canvas.width = N * 15;
canvas.height = N * 15;
function generateGrid() {
grid = [];
dist = Array(N).fill(0).map(() => Array(N).fill(Infinity));
prev = Array(N).fill(0).map(() => Array(N).fill(-1));
for (let i = 0; i < N; i++) {
grid[i] = [];
for (let j = 0; j < N; j++) {
// Generate cost between 1 and 9, scaled for color visualization
grid[i][j] = Math.floor(Math.random() * 8) + 2;
}
}
S = { x: 2, y: 2 };
T = { x: N - 3, y: N - 3 };
// Initialize source distance and set grid costs for visualization (1-9).
dist[S.y][S.x] = 0;
}
function drawGrid() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
const cellSize = 15;
for (let y = 0; y < N; y++) {
for (let x = 0; x < N; x++) {
let colorValue = grid[y][x] / 9; // Normalize cost for lightness mapping (0 to 1)
// Darker background for higher costs, lighter for lower costs.
let r = Math.floor(50 + (colorValue * 80));
let g = Math.floor(50 + (colorValue * 80));
let b = Math.floor(50 + (colorValue * 80));
ctx.fillStyle = `rgb(${r},${g},${b})`;
ctx.fillRect(x * cellSize, y * cellSize, cellSize - 1, cellSize - 1);
// Draw cell labels/costs (optional but helpful)
ctx.fillStyle = '#AAA';
ctx.font = '10px Arial';
ctx.fillText(grid[y][x], x * cellSize + 2, y * cellSize + 12);
}
}
// Highlight S and T
ctx.fillStyle = 'green';
ctx.fillRect(S.x * 15 - 1, S.y * 15 - 1, 15, 15);
ctx.fillStyle = 'red';
ctx.fillRect(T.x * 15 - 1, T.y * 15 - 1, 15, 15);
}
function getNeighbors(y, x) {
const neighbors = [];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
for (const [dy, dx] of directions) {
const ny = y + dy;
const nx = x + dx;
if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
neighbors.push({ nX: nx, nY: ny });
}
}
return neighbors;
}
/**
* Dijkstra's Core Step
* Finds the minimum distance unsettled node (Simulated Min-Priority Queue using linear scan).
*/
function findMinUnsettled() {
let minD = Infinity;
let bestNode = null;
for (let y = 0; y < N; y++) {
for (let x = 0; x < N; x++) {
// Check if settled or if distance is still Infinity (unvisited)
if (dist[y][x] !== Infinity && dist[y][x] > 0 && !settled[y][x]) {
if (dist[y][x] < minD) {
minD = dist[y][x];
bestNode = { x: x, y: y };
}
}
}
}
return bestNode;
}
let settled = Array(N).fill(0).map(() => Array(N).fill(false));
function dijkstraStep() {
if (settledCount >= N * N) return true; // Grid fully processed
const current = findMinUnsettled();
if (!current || dist[current.y][current.x] === Infinity) {
// Cannot reach any more nodes or all reachable nodes are settled
return true;
}
const { x: cx, y: cy } = current;
// Check if target reached (or close enough to stop animation/path tracing)
if (x === T.x && y === T.y) {
animatingPath(true);
return true;
}
// 1. Settle the node
settled[cy][cx] = true;
const currentDist = dist[cy][cx];
settledCount++;
// 2. Visualization: Color the settled cell by its distance cost
drawDistance(cy, cx, currentDist);
// 3. Update neighbors
getNeighbors(cy, cx).forEach(({ nX, nY }) => {
if (!settled[nY][nX]) {
const cost = grid[nY][nX];
const newDist = currentDist + cost;
if (newDist < dist[nY][nX]) {
dist[nY][nX] = newDist;
prev[nY][nX] = { x: cx, y: cy };
}
}
});
return false; // Still running
}
function drawDistance(y, x, d) {
const cellSize = 15;
// Use a color gradient based on distance (e.g., blue -> purple/red for higher cost)
let intensity = Math.min(255, Math.floor(d / 3)); // Scale down large distances to fit RGB palette
let r = Math.max(0, 100 + (Math.random() * 50));
let g = Math.max(0, 100 - (intensity * 0.5));
let b = Math.min(255, 100 + (d / 6));
// Fade out the color slightly over time to simulate settling
ctx.globalAlpha = 0.8;
ctx.fillStyle = `rgba(${r},${g},${b}, 0.7)`;
ctx.fillRect(x * cellSize, y * cellSize, cellSize - 1, cellSize - 1);
ctx.globalAlpha = 1.0;
}
function drawPath() {
const path = [];
let current = T;
while (current) {
path.push({ x: current.x, y: current.y });
if (current.x === S.x && current.y === S.y) break;
current = prev[current.y][current.x];
}
const cellSize = 15;
ctx.beginPath();
path.forEach((p, i) => {
if (i === 0) ctx.moveTo(p.x * cellSize + cellSize / 2, p.y * cellSize + cellSize / 2);
else ctx.lineTo(p.x * cellSize + cellSize / 2, p.y * cellSize + cellSize / 2);
});
ctx.strokeStyle = 'lime';
ctx.lineWidth = Math.max(3, N/10);
ctx.stroke();
}
function animatingPath(isFinal) {
if (!isFinal) return;
const totalCost = dist[T.y][T.x];
drawPath();
// Display stats overlay (simplified text output for character saving)
let statText = `Settled: ${settledCount}/${N*N} | Total Cost: ${totalCost}`;
ctx.fillStyle = 'white';
ctx.font = '16px monospace';
ctx.fillText(statText, 10, N * 15 - 10);
// Set the flag to stop the main loop after a delay
setTimeout(() => {
animationRunning = false;
drawGrid(); // Redraw grid state before restart
restartSimulation();
}, 1500);
}
let lastTime = 0;
function animate(time) {
if (!animationRunning) return;
const deltaTime = time - lastTime;
lastTime = time;
// Animation speed control (e.g., limit steps to ~30 FPS visual update rate)
if (deltaTime < 50) requestAnimationFrame(animate);
return;
const finished = dijkstraStep();
if (finished) {
requestAnimationFrame(() => animatingPath(true));
} else {
animationRunning = true;
requestAnimationFrame(animate);
}
}
function restartSimulation() {
settledCount = 0;
for(let y=0; y<N; y++) settled[y].fill(false);
generateGrid();
drawGrid();
animationRunning = true;
requestAnimationFrame(animate);
}
// Start immediately on load
restartSimulation();
</script></body></html>
``````html
<!DOCTYPE html><html><head><title>Dijkstra Animation</title></head><body><canvas id="c" width="640" height="480"></canvas><div>Settled: <span id="settled">0</span>, Path Cost: <span id="cost">0</span></div><script>
const c=document.getElementById('c'),ctx=c.getContext('2d'),size=32,w=640,h=480,cols=w/size,rows=h/size;
let grid=[],source,target,distances=[],heap=[],settledCount=0,pathCost=0,running=false;
function initGrid(){
grid=[];
for(let y=0;y<rows;y++){
let row=[];for(let x=0;x<cols;x++)row.push({x:x,y:y,cost:Math.floor(Math.random()*5)+1,neighbors:[],distance:Infinity,settlement:false,path:false});
grid.push(row);
}
source={x:2,y:2};target={x:cols-3,y:rows-3};
}
function getDistance(x,y){return y*cols+x;}
function rebuildGrid(){
for(let y=0;y<rows;y++){
for(let x=0;x<cols;x++){
grid[y][x].distance=Infinity;
grid[y][x].settlement=false;
grid[y][x].path=false;
}
}
heap=[];
distances={};
settledCount=0;
pathCost=0;
}
function buildNeighbors(){
for(let y=0;y<rows;y++){
for(let x=0;x<cols;x++){
let neighbors=[];const current=getDistance(x,y);
if(y>0){neighbors.push(getDistance(x,y-1))}
if(y<rows-1){neighbors.push(getDistance(x,y+1))}
if(x>0){neighbors.push(getDistance(x-1,y))}
if(x<cols-1){neighbors.push(getDistance(x+1,y))}
grid[y][x].neighbors=neighbors;
}
}
}
function updateDisplay(){document.getElementById('settled').textContent=settledCount;document.getElementById('cost').textContent=pathCost.toFixed(2);}
function drawGrid(){
ctx.fillStyle='white';ctx.fillRect(0,0,w,h);
for(let y=0;y<rows;y++){
for(let x=0;x<cols;x++){
let cell=grid[y][x];
ctx.fillStyle=`hsl(${255-cell.cost*40},100%,${cell.cost/6*80}%)`;
if(cell.settlement)ctx.fillStyle='rgba(0,255,0,.3)';
if(cell.path)ctx.fillStyle='rgba(255,0,0,.5)';
ctx.fillRect(x*size+1,y*size+1,size-2,size-2);
}
}
}
function drawPath(){
let current=target;
while(current!=source){
grid[current.y][current.x].path=true;
let minDist=Infinity;let minX=-1;let minY=-1;
for(let neighbor of grid[current.y][current.x].neighbors){
let y=Math.floor(neighbor/cols);let x=neighbor%cols;
if(grid[y][x].distance<minDist&&grid[y][x].settlement){
minDist=grid[y][x].distance;minX=x;minY=y;
}
}
current={x:minX,y:minY};
}
}
function animate(i){
requestAnimationFrame(animate);
if(heap.length==0||heap[0].distance==Infinity||!running){
running=false;if(i==0){return;}drawGrid();updateDisplay();
setTimeout(()=>{
initGrid();rebuildGrid();distances={};grid[source.y][source.x].distance=0;heap.push({index:getDistance(source.x,source.y),distance:0});
while(heap.length>0){
heap.sort((a,b)=>b.distance-a.distance);
let current=heap.pop();
if(grid[current.y][current.x].settlement)continue;
grid[current.y][current.x].settlement=true;settledCount++;
if(current.index==getDistance(target.x,target.y)){
pathCost=current.distance;drawPath();running=false;break;
}
for(let neighbor of grid[current.y][current.x].neighbors){
let y=Math.floor(neighbor/cols);let x=neighbor%cols;
if(!grid[y][x].settlement&&grid[y][x].distance>current.distance+grid[y][x].cost){
grid[y][x].distance=current.distance+grid[y][x].cost;
distances[neighbor]=grid[y][x].distance;
heap.push({index:neighbor,distance:grid[y][x].distance,y:y,x:x});
}
}
}
running=true;if(i==0){animate(1);return;}
},250);
}else{
drawGrid();
}
}
initGrid();rebuildGrid();distances={};heap.push({index:getDistance(source.x,source.y),distance:0});running=true;
</script></body></html>
```<think>
Okay, let's tackle this problem. The user wants an HTML file that animates Dijkstra's algorithm on a canvas. Hmm, I need to create a self-contained HTML file with all the code inside. Let me break down the requirements step by step.
First, the canvas needs a grid with random movement costs. Each cell's color should be lighter for cheaper costs and darker for expensive ones. So, generating a 2D array for the grid with random numbers between 1 and maybe 10? I'll have to think about the range. The user said movement cost, so probably higher numbers mean it's more expensive. So lighter cells (like white) for lower costs and darker for higher. Maybe a grayscale color based on the cost normalized.
Next, Dijkstra's algorithm steps: starting from a source, expanding to the cheapest unsettled cell each time. The settled cells need to be colored by their accumulated distance. The target should be reached, and then the path traced back. After finishing, it should restart with a new grid, source, and target.
Animation should use requestAnimationFrame for smoothness. No user input, it starts immediately and loops. The file must be under 7000 characters. Let's see how to structure this.
I'll need a canvas element, script that initializes everything. Let's outline the steps in code:
1. Set up the canvas and context.
2. Define grid size, maybe 50x50? That's manageable and not too big for a canvas.
3. Initialize the grid with random costs. Maybe between 1 and 10. The color for each cell is a shade of gray where cost 1 is white (rgb(255,255,255)), and higher costs get darker. So, for a cost of 10, it would be darker. Wait, maybe it's better to have lower costs (cheaper) as lighter. So higher cost means darker. Let me think: cost ranges from 1 to 10. So color value for a cell can be (255 - cost * 25.5) to make it darker as cost increases. Wait, but 1 would be 255 -25.5 = 229.5, which is still light. Maybe better to invert it. Like (255 - (cost/max)*255). So max cost is say 10, so cost/max gives a 0-1 value, subtracted from 1, then scaled to 255. Hmm, perhaps (cost * 25.5) but capped. Maybe for simplicity, just scale the cost to the color. For example, if cost is between 1 and 10, then colorValue = 255 - (cost-1)*25.5. So 1 is 255, 10 would be 255 -25.5*9=255-229.5=25.5. That way lower costs are brighter. That works.
Then, each cell in the grid has a cost, and we need to store their distance and whether they're settled.
The algorithm steps:
- Initialize a grid of distances, all set to infinity except the source which is 0.
- Keep a priority queue of unsettled cells, ordered by current distance. The priority queue needs to be able to find the minimum. Since JavaScript doesn't have a built-in priority queue, perhaps we can manage it with an array and find the minimum each time. But for efficiency, maybe use an array and each step pick the minimum among the unsettled.
Wait, but with 50x50 grid, that's 2500 cells max. Even with O(n) each step, it might be manageable as the animation is on screen. Let's see.
Alternatively, for each step, iterate through all cells to find the next minimum. Since each step picks the next cheapest, we can do that with a loop over all cells, checking if they are settled yet and if their distance is the current minimum. That should be okay.
Structure variables:
- grid: 2D array of costs.
- distances: 2D array of distances from source. Initially infinity except source.
- settled: 2D array of booleans.
- previous: 2D array to track path.
The algorithm loop would be:
1. Find the unsettled cell with the smallest distance (Dijkstra's step).
2. If this cell is the target, then break and trace back the path.
3. Otherwise, mark it as settled.
4. For each of its neighbors, check if they are within bounds, not settled. Update their distance if the path through current is better.
5. Repeat until target is found.
Once the path is found, trace back from target to source using previous pointers.
Then, after finishing, restart by generating a new grid and new source/target positions.
The animation should be smooth using requestAnimationFrame. Each frame should represent a step in the algorithm.
Wait, but Dijkstra's steps might need to be animated step by step. So each frame, we perform one iteration (i.e., process the next cell). That way, the animation can show the expansion of settled cells.
But how to handle the animation loop:
- The main loop (requestAnimationFrame) calls a function that steps through the algorithm.
- When the algorithm is done (target found), it restarts everything and continues.
So variables need to track the current state (e.g., whether processing, which frame is being drawn, etc.)
Implementing this in JavaScript:
First, variables:
const size = 50; // grid size
let grid = [];
let distances = [];
let settled = [];
let previous = [];
let source = {x:0,y:0};
let target = {x:49,y:49}; // or random positions
let path = [];
let settledCount = 0;
let pathCost = 0;
These need to be initialized each time the grid is reset.
The setup function would generate a new grid, set source and target randomly (maybe to opposite corners or random positions). Then initialize the algorithm's variables.
Now, the drawing functions:
The canvas needs to be redrawn each frame. The settled cells should be colored based on their distance. The settled cells are drawn in a color that represents their distance. Maybe the distance can be scaled to the color, but perhaps using a gradient. Alternatively, the distance can be mapped to a color scale. Since distance can be large, maybe modulo some value to get a color.
Alternatively, the path can be drawn in green, settled cells in a gradient based on their distance.
Hmm, but Dijkstra's uses the distance as the accumulated cost. To show that, maybe each cell's color is proportional to its distance. For example, the closer to the source, the lighter. Or the darker as distance increases? Wait, maybe using a gradient where lower distances are lighter and higher darker. Since distance is the accumulated cost, maybe a blue-to-red gradient? Or just a grayscale where the distance is scaled to a color value. Let's think: for a distance of 100 (assuming a maximum possible distance), we can take (distance/maxDistance)*255 and set the color accordingly. But max distance could be up to grid size squared? Not sure. Alternatively, use a simple scale where distance is used directly, but scaled down. For example, (distance % 256) as the color value. So, the color is a grayscale where the distance mod 255 determines the shade.
Alternatively, to have a clear visual: settled cells can be colored with a gradient from the source to darker shades as the distance increases. Maybe just (distance * (255 / (maxPossibleDistance))) as the color. But without knowing the max distance, perhaps just use distance modulo, but it's tricky. Alternatively, the distance can be represented by a color value that's a scaled version. Let's say the maximum distance in the grid would be (size * maxCost) * size. Since each step adds at least 1, the max possible is (size^2)*10, but that's too big. Maybe just use a fixed scaling factor, like 255 / (size * maxCost). Alternatively, just use (distance % 256) as the red component. Hmm, perhaps the simplest way is to set the cell's color to a grayscale where the distance is scaled. For example:
colorValue = (distance * 255) / (size * maxCost);
But since maxCost is 10, and size 50, that would be 255/(50*10)=0.51. So distance*0.51, but that might not be enough. Maybe just use distance mod 255. Or just take distance as the color value, but cap it at 255. Wait, but distance can be up to 50*10*50? Maybe it's better to just use the distance value directly for the grayscale, but scaled. Alternatively, use the distance divided by some factor. Maybe (distance * 4) mod 255? Not sure. Alternatively, use the distance as the color's lightness in HSL. But maybe simpler to just set the color to something like 255 - distance * (255 / maxDistance). But without knowing maxDistance, perhaps just use distance * 2. Because 50x50 grid, the maximum distance can be up to 50*50 (if all steps are cost 1, but moving diagonally isn't allowed?), so maybe 2500? Hmm, that's too big. Alternatively, just use distance as the color component but mod 255. Let me think of a quick way: let's set the color to (distance % 256) for red component, so it cycles. Or maybe (distance * 1.5) mod 255. Alternatively, perhaps just use the distance as a value, and map it to a grayscale where lower distance is brighter. Wait, but distance starts at 0 (source), so the source is white, and as the distance increases, they get darker. So the cell's color could be (255 - (distance * 255) / maxPossibleDistance). But maxPossibleDistance is unknown. Alternatively, just use distance multiplied by a scaling factor, say 2. So for distance 100, it would be 200, which is over 255, but that's okay. Maybe use distance % 256 as the color value. That way, cells with higher distances cycle back to lighter colors. Maybe that's confusing, but it's better than nothing.
Alternatively, use distance values for green component. But maybe for simplicity, the color can be (distance) mapped to a color with R = distance, G = distance, B = distance. But the distance can be up to, say, 500, so when distance exceeds 255, it wraps around. Hmm, but maybe that's okay.
Alternatively, for the settled cell color, use (distance * 1) % 255 as the grayscale. So:
ctx.fillStyle = 'rgb(' + (distance * 2) + ',' + (distance * 2) + ',' + (distance * 2) + ')';
Wait, but if distance is 100, that would be 200, but if distance is 150, then 300%255=45, so it would be light again. Hmm, that might look like a wave pattern. Not ideal, but perhaps better than nothing.
Alternatively, maybe just use the distance to set the color channel, but with a fixed scaling factor. Let's choose 255 / (maxPossible distance). But how to compute max possible distance? Since the grid is 50x50, and each step can have a cost up to 10, the max possible distance is (50*2-2) * 10 (since the farthest is diagonally opposite, but moving via adjacent cells). Wait, the maximum path is the Manhattan distance between opposite corners: 49+49=98 steps. Each step can have a cost of 10, so max distance is 98*10= 980. So 980 would be the maximum possible distance. To scale that down to 255, multiply by 255/980 ≈0.26. So for a distance of d, the color value would be d * 0.26. So 980*0.26≈255. So that would give a gradient from 0 (white) to 255 (black). But in code, perhaps using:
var color = Math.min(d * 255 / 980, 255);
But 980 is arbitrary, but maybe that's okay. Alternatively, let's just use (d * 2) % 255, but that might loop. Hmm. Alternatively, for the color, the distance is used as the grayscale value, even if it's over 255, but the browser will clamp it to 255. So, for distance 300, it would be 255, for 400 it's still 255. That would make the highest distances all black. That might be okay.
Alternatively, maybe just use the distance as the value and let it overflow. So:
ctx.fillStyle = 'rgb(' + (distance * 2) + ',' + (distance * 2) + ',' + (distance * 2) + ')';
So that 0 is black (wait, no: 0*2 is 0, so RGB(0,0,0) is black. But the source is 0, so that would be black, which is bad. Hmm, that's a problem. So maybe invert it. Let's think again. The source has distance 0. To have the source be white, maybe:
colorValue = 255 - (distance * scalingFactor);
Scaling factor such that max distance (say 1000) would be 255. Let's say scalingFactor is 0.25, then 1000*0.25 is 250. So colorValue would be 5. That might not be enough. Hmm.
Alternatively, for distance 0 (source), set to white. Then, higher distances get darker:
colorValue = 255 - (distance * 255 / maxDistanceEstimate). But without knowing maxDistanceEstimate, perhaps just use:
colorValue = 255 - (distance * 0.5);
So for distance 500, that would be 255 - 250 = 5, which is dark. But for distance 255*2=510, it would be negative so 0. So capped at 0.
Thus, in code:
var g = Math.max(255 - (distance * 0.5), 0);
Then the color is rgb(g,g,g). That way, the source (distance 0) is 255 (white), and higher distances get darker. Even if the distance exceeds 510, it'll be 0 (black). That might work.
Okay, moving on.
The next step: setting up the grid. Each cell's cost is a random integer between 1 and 10, maybe. So in setup:
function init() {
grid = [];
distances = [];
settled = [];
previous = [];
source = {x: Math.floor(Math.random() * size), y: Math.floor(Math.random() * size)};
// pick target somewhere else, maybe opposite corner or random
target = {x: Math.floor(Math.random() * size), y: Math.floor(Math.random() * size)};
// make sure source and target are different
while (target.x == source.x && target.y == source.y) {
target.x = Math.floor(Math.random() * size);
target.y = Math.floor(Math.random() * size);
}
// generate grid
for (let y =0; y<size; y++) {
grid[y] = [];
distances[y] = [];
settled[y] = [];
previous[y] = [];
for (let x=0; x<size; x++) {
grid[y][x] = Math.floor(Math.random() * 10) + 1; // 1-10
distances[y][x] = Infinity;
settled[y][x] = false;
previous[y][x] = null;
}
}
distances[source.y][source.x] = 0;
settledCount = 0;
pathCost = 0;
// reset path
path = [];
// start algorithm
// maybe a flag running to indicate if it's processing
}
Then, the main function that runs Dijkstra's step by step. Since each frame is a step, we need to process one cell per frame.
The algorithm steps:
In each step, find the cell with the smallest distance among the unsettled cells.
Once found, mark it as settled, then check its neighbors.
But how to do this step by step?
Perhaps in code:
function step() {
let minDist = Infinity;
let current = null;
// find the unsettled cell with smallest distance
for (let y=0; y<size; y++) {
for (let x=0; x<size; x++) {
if (!settled[y][x] && distances[y][x] < minDist) {
minDist = distances[y][x];
current = {x, y};
}
}
}
if (current === null) return; // no more cells, maybe target wasn't reachable. But we choose source and target as different, so should reach.
// mark as settled
settled[current.y][current.x] = true;
settledCount++;
// if this is the target, done
if (current.x == target.x && current.y == target.y) {
// trace path
path = [];
let temp = current;
while (temp !== null) {
path.push([temp.x, temp.y]);
temp = previous[temp.y][temp.x];
}
pathCost = distances[current.y][current.x];
// done, so start new init when animation completes?
// but need to wait until the animation ends
return; // exit step function, so next frame will trigger another step (but since we are done, need to stop)
}
// check neighbors
const dirs = [[-1,0], [1,0], [0,-1], [0,1]]; // up, down, left, right
for (const [dx, dy] of dirs) {
const nx = current.x + dx;
const ny = current.y + dy;
if (nx >=0 && nx < size && ny >=0 && ny < size) {
const newDist = distances[current.y][current.x] + grid[ny][nx]; // assuming moving to (nx, ny) has cost grid[ny][nx]
if (newDist < distances[ny][nx]) {
distances[ny][nx] = newDist;
previous[ny][nx] = current;
}
}
}
}
Wait, but in Dijkstra's algorithm, you usually have a priority queue to efficiently find the next cell. However, doing a linear search here is O(n^2) per step, which might be manageable for a 50x50 grid (2500 cells per step). Each step is one frame (like 1/60th of a second), but 2500 iterations per frame might be slow. 2500 * 50 steps (if the path is 50 steps) would take about 50 frames. Maybe manageable?
Alternatively, to make it faster, use a priority queue, but that complicates the code. Since the user asked to create it, perhaps proceed with the linear search, even if it's less efficient.
Alternatively, maybe set the grid size to 20x20 for better performance. Let me check: the original problem didn't specify size, so maybe 25x25? Let's see. Let me adjust the size in the code to 25 instead of 50. So size = 25.
Wait, but the user didn't specify, so perhaps proceed with 50, but maybe that's too slow. Hmm. Let me see:
In the code, if size is 50, then each step requires 50*50=2500 iterations to find the current node. Then, for each of those, checking 4 directions. But in the step function, the loop to find current is the main cost.
Alternatively, to optimize, pre-process:
Once a cell is settled, it can be ignored. So in the step function, perhaps keep track of all unsettled cells in an array, and iterate through those. That would reduce the search time.
But for simplicity, perhaps proceed with the basic approach, and hope it's manageable.
Now, the drawing function.
The drawing function will loop through each cell and color it based on its state:
- If the cell is the source: bright green or something
- Target: red
- Settled cells: their distance-based gray
- Unsettled: their cost's color (maybe the cost's random color?)
Wait, the original grid has each cell's cost (1-10). Maybe color the cells based on their cost. For example, cost 1 is light gray, 10 is dark gray. So for each cell (x,y), its base color is based on grid[y][x].
So in the drawing function:
function draw() {
ctx.clearRect(0,0, canvas.width, canvas.height);
const cellWidth = canvas.width / size;
const cellHeight = canvas.height / size;
for (let y=0; y<size; y++) {
for (let x=0; x<size; x++) {
ctx.fillStyle = 'rgb(' + (grid[y][x]*25.5) + ',' + (grid[y][x]*25.5) + ',' + (grid[y][x]*25.5) + ')';
// so cost 1 is 25.5 brightness, up to 255 for cost 10 (10*25.5=255). But since JS uses integers, maybe use grid[y][x]*25
ctx.fillStyle = 'rgb(' + (grid[y][x]*25) + ',' + (grid[y][x]*25) + ',' + (grid[y][x]*25) + ')';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
if (settled[y][x]) {
const d = distances[y][y][x]; // Wait, no, distances[y][x]
const g = Math.max(255 - (d * 0.5), 0);
ctx.fillStyle = 'rgb(' + g + ',' + g + ',' + g + ')';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
// highlight source and target
if (x === source.x && y === source.y) {
ctx.fillStyle = 'green';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
if (x === target.x && y === target.y) {
ctx.fillStyle = 'red';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
// draw path
if (path.length >0) {
// path is array of [x,y] in reverse order (since we traced back from target)
for (const [px, py] of path) {
if (x === px && y === py) {
ctx.fillStyle = 'yellow';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
}
}
}
}
}
Wait, but the settled cells are overwritten by their distance color, which might be better to draw on top. Maybe the settled cells should be drawn after the base color, so that their gray overrides the cost's base color.
Also, the path is drawn in yellow, so that should be on top of everything.
Also, the source and target colors (green and red) need to be on top as well.
The order in the loop for each cell is important:
1. Base color (cost)
2. Settled color (distance)
3. Source/Target colors
4. Path color
Wait, but path is part of the settled path, so maybe the settled color is under the path. Hmm.
Alternatively, the path can be drawn last.
Alternatively, reorganize:
First draw base cost colors.
Then, for settled cells, draw their distance-based gray. This will overwrite the base color for settled cells.
Then draw source and target (green and red) which will overwrite the settled color if they are the source or target.
Then draw the path in yellow, which will overwrite both.
Wait, but the path is composed of settled cells, so when we draw the settled color, then the path is drawn on top.
Alternatively, maybe:
- Base color for all cells
- For settled cells, draw their distance gray (over base)
- For path cells, draw yellow (over all)
- Source and target colors (over everything?)
Hmm, perhaps better to first draw base colors, then settled colors, then source and target, then path.
Alternatively, the path should be the last to draw.
Also, the settled cells include the path, so perhaps the path is part of the settled cells, but needs to stand out.
Alternatively, the settled cells are drawn in their gray, then the path is drawn in yellow on top.
The source and target are also on top.
This seems okay.
Another point: the cellWidth and cellHeight calculations. The canvas should have a size that's a multiple of the grid size, or it can just use scaling.
Let me think the canvas is, say, 500x500, and grid size 25, so each cell is 20x20.
But in code, perhaps set the canvas width and height to 500.
Now, putting all together.
The overall structure:
HTML:
<canvas id="myCanvas"></canvas>
JS:
const canvas = document.getElementById('myCanvas');
const ctx = canvas.getContext('2d');
let size = 25; // grid size
canvas.width = 500;
canvas.height = 500;
var running = false;
var currentStep = 0;
function init() { ... } // as above
function step() { ... } // as above
function draw() { ... } // as above
function animate() {
if (running) {
step();
draw();
requestAnimationFrame(animate);
}
}
// Start the animation after init
init();
animate();
Wait, but the problem is that the step function only processes one step, and then the next frame will process another step. However, the step function as currently written will process one cell per frame, which might be manageable. The animation loop would call step() and draw() each frame.
However, in the step function, after finding the current cell, it checks if it's the target, and if so, computes the path. After that, it needs to stop running so that the animation doesn't continue. But the animation loop is controlled by the 'running' flag. Wait, the 'running' flag is not set here. So perhaps in the init(), set running = true, and when step() finds the target, set running = false, so that the animation stops.
Wait, in the current step function, when the target is reached, it computes the path and then returns. But the animation loop continues to call animate(), so need to set running = false.
So need to adjust:
In step function:
if (x === target.x ...) {
pathCost = ...
running = false; // stop further steps
return;
}
Alternatively, after computing the path, set running = false.
Also, in the init() function, after setting up variables, need to set running = true.
Wait, let me rework the code with these changes.
Full code outline:
const canvas = document.getElementById('myCanvas');
const ctx = canvas.getContext('2d');
let size = 25;
canvas.width = 500;
canvas.height = 500;
let source = {x: 0, y: 0}; // example, but better to pick randomly or fixed
let target = {x: size-1, y: size-1};
let grid = []; // 2D array of costs (1-10)
let distances = []; // 2D array for Dijkstra's
let previous = []; // 2D array for tracking path
let path = [];
let pathCost = 0;
let running = false;
function init() {
source.x = 0;
source.y = 0;
target.x = size -1;
target.y = size -1;
// Initialize grid with random costs 1-10
grid = [];
for (let y = 0; y < size; y++) {
grid[y] = [];
for (let x = 0; x < size; x++) {
grid[y][x] = Math.floor(Math.random() * 10) +1; // 1-10
}
}
// Initialize distances and previous
distances = [];
previous = [];
for (let y = 0; y < size; y++) {
distances[y] = new Array(size).fill(Infinity);
previous[y] = new Array(size).fill(null);
}
distances[source.y][source.x] = 0;
// Reset path and cost
path = [];
pathCost = 0;
running = true;
}
function step() {
if (!running) return;
// Find the node with the smallest distance that is not yet settled
let minDist = Infinity;
let current = null;
for (let y = 0; y < size; y++) {
for (let x = 0; x < size; x++) {
if (distances[y][x] < minDist && previous[y][x] === null) { // not settled yet
minDist = distances[y][x];
current = {x, y};
}
}
}
if (!current) {
// No path found?
running = false;
return;
}
// Mark current as settled by setting previous to something?
// Or just proceed.
// Then check if current is target
if (current.x === target.x && current.y === target.y) {
// Found the target
// Trace back path
let temp = current;
path = [];
while (temp !== null) {
path.push({x: temp.x, y: temp.y});
temp = previous[temp.y][temp.x];
}
path.reverse(); // to go from source to target
pathCost = distances[current.y][current.x];
running = false;
return;
}
// Process neighbors
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
for (const [dx, dy] of dirs) {
const nx = current.x + dx;
const ny = current.y + dy;
if (nx >=0 && nx < size && ny >=0 && ny < size) {
const newDist = distances[current.y][current.x] + grid[ny][nx];
if (newDist < distances[ny][nx]) {
distances[ny][nx] = newDist;
previous[ny][nx] = current; // store pointer to previous node
}
}
}
}
function draw() {
ctx.clearRect(0,0,canvas.width,canvas.height);
const cellWidth = canvas.width / size;
const cellHeight = canvas.height / size;
// Draw grid cells
for (let y = 0; y < size; y++) {
for (let x = 0; x < size; x++) {
// Base color based on grid
const cost = grid[y][x];
const baseColor = Math.floor(cost * 25.5); // 1-255, but better as integers
ctx.fillStyle = `rgb(${baseColor}, ${baseColor}, ${baseColor})`;
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
// Settled cells (distance-based gray)
if (previous[y][x] !== null) { // settled
const dist = distances[y][x];
let gray = Math.max(255 - (dist * 0.5), 0);
ctx.fillStyle = `rgb(${gray}, ${gray}, ${gray})`;
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
// Draw source and target
if (x === source.x && y === source.y) {
ctx.fillStyle = 'green';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
if (x === target.x && y === target.y) {
ctx.fillStyle = 'red';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
// Draw path
if (path.length > 0) {
const cell = {x: x, y: y};
if (path.some(p => p.x === x && p.y === y)) {
ctx.fillStyle = 'yellow';
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
}
}
}
}
function animate() {
if (running) {
step();
}
draw();
requestAnimationFrame(animate);
}
init();
animate();
Wait, but in the step function, the current node is selected as the one with minimum distance and not settled yet (previous[y][x] === null). However, in Dijkstra's algorithm, settled nodes are those that have been processed, so perhaps we should have a separate array to track settled nodes. Because in the current setup, previous[y][x] is set when the node is updated, but not necessarily settled.
Hmm, this might be an error. The previous array is used to track the path, but not to indicate whether the node has been settled (i.e., processed). So perhaps need a separate 'settled' array.
Let me revise the step function:
Add a 2D array called settled.
Initialize:
settled = [];
for (let y =0; y < size; y++) {
settled[y] = new Array(size).fill(false);
}
Then in step:
let minDist = Infinity;
let current = null;
for (let y =0; y < size; y++) {
for (let x =0; x < size; x++) {
if (!settled[y][x] && distances[y][x] < minDist) {
minDist = distances[y][x];
current = {x, y};
}
}
}
Then after choosing current:
settled[current.y][current.x] = true;
This way, once a node is processed, it's marked as settled and won't be considered again.
Also, in the draw function, to check if settled:
if (settled[y][x]) {
So, adjusting the code accordingly.
Also, in the initialization of previous array, previous should be set to null for all nodes, except maybe source?
Yes.
Additionally, in the step function, after selecting current, before processing neighbors, we need to mark it as settled.
These changes are important to track settled nodes properly.
Let me adjust the code:
Adding 'settled' array:
Initialize in init():
settled = [];
for (let y =0; y < size; y++) {
settled[y] = new Array(size).fill(false);
}
step function:
function step() {
if (!running) return;
// Find the node with the smallest distance that is not yet settled
let minDist = Infinity;
let current = null;
for (let y = 0; y < size; y++) {
for (let x = 0; x < size; x++) {
if (!settled[y][x] && distances[y][x] < minDist) {
minDist = distances[y][x];
current = {x, y};
}
}
}
if (!current) {
// No path found
running = false;
return;
}
// Mark as settled
settled[current.y][current.x] = true;
// Check if current is target
if (current.x === target.x && current.y === target.y) {
// Trace path
let temp = current;
path = [];
while (temp !== null) {
path.push({x: temp.x, y: temp.y});
temp = previous[temp.y][temp.x];
}
path.reverse();
pathCost = distances[current.y][current.x];
running = false;
return;
}
// Process neighbors
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
for (const [dx, dy] of dirs) {
const nx = current.x + dx;
const ny = current.y + dy;
if (nx >=0 && nx < size && ny >=0 && ny < size) {
const newDist = distances[current.y][current.x] + grid[ny][nx];
if (newDist < distances[ny][nx]) {
distances[ny][nx] = newDist;
previous[ny][nx] = current; // Store the previous node
}
}
}
}
Also, in the draw function, to check settled[y][x]:
// Settled cells (distance-based gray)
if (settled[y][x]) { // settled nodes are those processed
const dist = distances[y][x];
let gray = Math.max(255 - (dist * 0.5), 0);
ctx.fillStyle = `rgb(${gray}, ${gray}, ${gray})`;
ctx.fillRect(x * cellWidth, y * cellHeight, cellWidth, cellHeight);
}
This should fix the issue where nodes were not properly tracked as settled.
Now, with these changes, the code should work correctly.
Testing the code, when the path is found, the path should be highlighted in yellow, and the settled nodes in gray.
Also, the source is green, target red.
Possible issues:
- The path tracing might have an off-by-one error or incorrect direction. In the while loop:
temp = previous[temp.y][temp.x]; // but previous is storing the previous node, so when temp is current, the next is previous of that.
Wait, in the step function, when we set previous[ny][nx] = current; // So previous of ny,nx is current.
So when tracing back from target:
temp starts at target node.
previous[target.y][target.x] would be the previous node that led to it.
So the loop:
temp = current (the target node)
then temp = previous[temp.y][temp.x]
Yes, that's correct.
Testing this should correctly trace back to the source.
Another possible issue: in the draw function's path check:
if (path.some(p => p.x === x && p.y === y)) {
This will loop through the path array every cell, which could be inefficient for large grids, but for 25x25 it's okay.
Alternatively, could use a hash map.
But for simplicity, this is acceptable.
Lastly, in the initial setup:
source is at (0,0), target at (size-1, size-1).
The grid initialization uses Math.floor(Math.random() *10)+1, which gives 1-10 (since Math.random() *10 is 0-10, floor gives 0-9, plus1 becomes 1-10). That's correct.
Testing the code with these changes should work.
Therefore, the final code is as above.<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Dijkstra's Algorithm Animation</title>
<style>
body {
background: black;
}
canvas{
image-rendering: pixelated;
}
</style>
</head>
<body>
<canvas id="grid" width="600px" height="600px"></canvas>
<script>
const grid = document.getElementById("grid");
// The canvas context with image smoothing disabled
const ctx = grid.getContext("2d", {willReadFrequently: true});
// Size of the canvas and each cell in pixels (must be square)
const cellSizePx = 10;
const widthCells = Math.round(grid.width / cellSizePx);
const heightCells = Math.round(grid.height / cellSizePx);
// The number of cells
const numCells = widthCells * heightCells;
let gridCosts = new Array(numCells).fill(100);
// Randomize the costs from 50 to 250
for (let i=0;i<gridCosts.length;i++){
gridCosts[i] = Math.round(Math.random() * 200) + 50;
}
// The start and end cells, each is an array of two elements [x, y] where x and y are the cell indices in the flat list
const sourceCell = [1,1];
let targetCell = [];
// Colors for settled and unsettled nodes
const colorUnsettledNode = "#808080";
const colorSettledNodeStart = "#C0504D";
const colorSettledNodeTarget = "#FF7F50";
// An array of distances to the start cell, same shape as gridCosts. Initialized with Infinity everywhere except for the starting node's distance which is set to 0
let dists = new Array(numCells).fill(Infinity);
dists[sourceCell[0] + sourceCell[1]*widthCells] = 0;
// An array of booleans indicating whether a cell has been settled or not. Same shape as gridCosts, initialized with false everywhere except for the start node which is set to true
let settled = new Array(numCells).fill(false);
settled[sourceCell[0] + sourceCell[1]*widthCells] = true;
// The number of cells currently settled and total path cost
const numSettled = document.createElement("p");
const pathCost = document.createElement("p");
grid.parentNode.appendChild(numSettled);
grid.parentNode.appendChild(pathCost);
// Define colors for different costs
const colorMap = [ "#228B22", "#3CB371", "#40E0D0", "#6495ED", "#4B0082", "#FF7F50" ];
// Function to get the RGB value from a given index using colorMap array
function getColor(i) {
return colorMap[Math.min(colorMap.length - 1, Math.round(i / (gridCosts.length/colorMap.length)))];
}
// Function to draw a single cell at specified coordinates with given cost value and boolean settled flag
function drawCell(x, y, c, s) {
// Get the current color based on cost
const color = getColor(c);
// Set the fill style and stroke style for the cell
ctx.fillStyle = s ? (targetCell[0] == x && targetCell[1] == y ? colorSettledNodeTarget : colorSettledNodeStart) : color;
ctx.strokeStyle = "#FFFFFF";
const rect = new Path2D();
rect.rect(x * cellSizePx, y * cellSizePx, cellSizePx - 0.5, cellSizePx - 0.5);
ctx.fill(rect);
ctx.stroke(rect);
}
// Function to draw the entire grid based on the current state
function drawGrid() {
ctx.clearRect(0, 0, grid.width, grid.height);
for (let y = 0; y < heightCells; y++) {
for (let x = 0; x < widthCells; x++) {
const i = x + y * widthCells;
drawCell(x,y,gridCosts[i],settled[i]);
}
}
}
// Function to update the grid after each step
function update() {
// Find the index of next cheapest unsettled cell
let nextCheapestIx = Infinity;
for (let y=0;y<heightCells;y++){
for(let x=0;x<widthCells;x++){
const i = x + y * widthCells;
if (!settled[i] && dists[i]<nextCheapestIx){
nextCheapestIx = dists[i];
}
}
}
// If there are no more unsettled nodes, the algorithm is finished and we can start over with a fresh instance
if (isNaN(nextCheapestIx)){
gridCosts = new Array(numCells).fill(100);
for (let i=0;i<gridCosts.length;i++){
gridCosts[i] = Math.round(Math.random() * 200) + 50;
}
dists = new Array(numCells).fill(Infinity);
dists[sourceCell[0] + sourceCell[1]*widthCells] = 0;
settled = new Array(numCells).fill(false);
settled[sourceCell[0] + sourceCell[1]*widthCells] = true;
targetCell = [];
}
// If not, continue with the algorithm and set nextCheapestIx as settled
else{
const nextCheapestX = Math.floor(nextCheapestIx / widthCells);
const nextCheapestY = (nextCheapestIx % widthCells) + 1;
drawCell(nextCheapestX-1,nextCheapestY-1,gridCosts[nextCheapestIx],false);
settled[nextCheapestIx] = true;
}
// If the target has been reached, trace back its path to update cost sums and colors of the nodes on the path. Finish when reaching the source node again.
if (targetCell[0]){
const currentNodeX = Math.floor(nextCheapestIx / widthCells);
const currentNodeY = (nextCheapestIx % widthCells) + 1;
drawCell(currentNodeX-1,currentNodeY-1,gridCosts[nextCheapestIx],true);
// If not at the source node yet
if (!(currentNodeX == sourceCell[0] && currentNodeY == sourceCell[1])){
dists[sourceCell[0] + sourceCell[1]*widthCells - 1] = dists[nextCheapestIx];
drawCell(targetCell[0]-1,targetCell[1]-1,gridCosts[dists[targetCell[0] + targetCell[1]*widthCells-1]],true);
}
}
// If a new target node has been reached (the algorithm is still running) or the previous one was removed from the settled list due to being pruned by shorter paths
else if ((nextCheapestX == targetCell[0] && nextCheapestY == targetCell[1]) || !settled[targetCell[0] + targetCell[1]*widthCells-1]){
drawCell(nextCheapestX,nextCheapestY,gridCosts[nextCheapestIx],true);
dists[sourceCell[0] + sourceCell[1]*widthCells - 1] = dists[nextCheapestIx];
targetCell = [nextCheapestX, nextCheapestY];
}
// Update the number of settled cells and path cost counters in the DOM
numSettled.innerHTML = `Number of Settled Cells: ${settled.filter(x=>x).length}`;
if (targetCell[0]){
const totalCost = dists[sourceCell[0] + sourceCell[1]*widthCells - 1];
pathCost.innerHTML = `Total Path Cost: ${totalCost}`;
}
// Call the draw function to render the updated state and then recursively call this update function again with requestAnimationFrame (if animation is still running)
drawGrid();
requestAnimationFrame(update);
}
// Run the algorithm once at startup
update();
</script>
</body>
</html>| Model | Blind score | Latency | Status |
|---|---|---|---|
| gemma4:26b | — | — | harness |
| qwen3:14b | — | 36.6 s | OK |
| deepseek-r1:14b | — | 50.8 s | OK |
| qwen3:8b | — | — | harness |
| llama3.1:8b | — | 159.2 s | OK |
| qwen3-coder:30b | — | 38.8 s | OK |
| qwen3.5:9b | — | 58.0 s | OK |
| mistral-small:24b | — | — | DNF |
| deepseek-r1:32b | — | 88.2 s | OK |
| qwq:32b | — | 259.3 s | OK |
| command-r:35b | — | 123.5 s | OK |