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 the A* search algorithm on a <canvas>: a grid with randomly placed obstacle cells, a start and a goal, expanding the frontier as small squares colored by their f-score, and once the goal is reached, tracing the final shortest path in a distinct color. Restart with a freshly generated grid, start and goal when finished or when no path exists. Show the number of nodes expanded and the path length. 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>
<canvas id=c width=600 height=400></canvas>
<div id=i style="position:absolute;top:10px;left:10px;color:black;"></div>
<script>
let c=document.getElementById('c'), ctx=c.getContext('2d');
const cols=25, rows=25, cellSize=17;
let start,end,path=openSet=closedSet=new Set;metrics=document.getElementById('i');
let grid=null,nodesExpanded=0,pathLength=0,isDone=false,isSearching=true;
function setup(){grid=new Array(cols).fill().map(_=>new Array(rows).fill(0));
start={x:Math.floor(Math.random()*cols),y:Math.floor(Math.random()*rows)};end={...start};
while(end.x==start.x||end.y==start.y){end.y=Math.floor(Math.random()*rows)}
for(let i=0;i<cols;i++)for(let j=0;j<rows;j++)grid[i][j]=Math.random()<0.3?1:0;
runAStar();}
function runAStar(){
if(isDone||isSearching&&!openSet.size){setup();return;}
nodesExpanded++;
let f=();
return;
for(let x=start.x-1;x<=start.x+1;x++) for(let y=start.y-1;y<=start.y+1;y++) { ... }
}
</script>
</head>
<body style="background:#f0f0f0;"></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>A\* Search Algorithm Animation</title>
<style>
body {
margin: 0;
}
#canvas {
border: 1px solid black;
}
</style>
</head>
<body>
<script>
const canvas = document.createElement('canvas');
document.body.appendChild(canvas);
const ctx = canvas.getContext('2d');
let gridWidth = 50;
let gridHeight = 20;
let gridSize = Math.min(window.innerWidth, window.innerHeight) * 0.8 / gridWidth;
canvas.width = gridWidth * gridSize;
canvas.height = gridHeight * gridSize;
let grid = [];
for (let i = 0; i < gridHeight; i++) {
let row = [];
for (let j = 0; j < gridWidth; j++) {
row.push(Math.random() < 0.2 ? 'obstacle' : 'free');
}
grid.push(row);
}
function generateGoal() {
return [Math.floor(Math.random() * gridHeight), Math.floor(Math.random() * gridWidth)];
}
let start = generateGoal();
while (start[1] === grid[start[0]][start[1]]) {
start = generateGoal();
}
let goal = start;
while (goal[1] === grid[goal[0]][goal[1]] || goal[1] === start[1]) {
goal = [Math.floor(Math.random() * gridHeight), Math.floor(Math.random() * gridWidth)];
}
function drawGrid() {
ctx.fillStyle = 'white';
ctx.fillRect(0, 0, canvas.width, canvas.height);
for (let i = 0; i < gridHeight; i++) {
for (let j = 0; j < gridWidth; j++) {
if (grid[i][j] === 'obstacle') {
ctx.fillStyle = 'black';
} else if (i === start[0] && j === start[1]) {
ctx.fillStyle = 'red';
} else if (i === goal[0] && j === goal[1]) {
ctx.fillStyle = 'green';
}
ctx.fillRect(j * gridSize, i * gridSize, gridSize, gridSize);
}
}
}
const openList = [];
const cameFrom = new Map();
openList.push({ x: start[1], y: start[0], fScore: Math.sqrt((start[0] - goal[0]) ** 2 + (start[1] - goal[1]) ** 2) });
function heuristic(a, b) {
return Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2);
}
let totalExpanded = 0;
let pathLength = 0;
function animate() {
requestAnimationFrame(animate);
if (!openList.length && start[1] !== goal[1]) {
drawGrid();
ctx.font = '16px Arial';
ctx.fillStyle = 'black';
ctx.textAlign = 'left';
ctx.textBaseline = 'top';
ctx.fillText(`No path found. Press F5 to restart.` , 10, 10);
return;
}
if (openList.length && openList[0].y === goal[0] && openList[0].x === goal[1]) {
let reconstructedPath = [];
let current = [goal[1], goal[0]];
while (cameFrom.has(`${current[0]},${current[1]}`)) {
reconstructedPath.push(current);
current = cameFrom.get(`${current[0]},${current[1]}`);
}
const path = reconstructedPath.concat([[start[1], start[0]]]).reverse();
for (let i = 0; i < path.length - 1; i++) {
let cellX = path[i][1];
let cellY = path[i][0];
ctx.fillStyle = 'blue';
ctx.fillRect(cellX * gridSize, cellY * gridSize, gridSize, gridSize);
pathLength++;
}
drawGrid();
ctx.font = '16px Arial';
ctx.fillStyle = 'black';
ctx.textAlign = 'left';
ctx.textBaseline = 'top';
ctx.fillText(`Path length: ${pathLength}. Press F5 to restart.` , 10, 10);
return;
}
openList.sort((a, b) => a.fScore - b.fScore);
let current = openList.shift();
totalExpanded++;
for (let i = Math.max(0, current.y - 1); i <= Math.min(gridHeight - 1, current.y + 1); i++) {
for (let j = Math.max(0, current.x - 1); j <= Math.min(gridWidth - 1, current.x + 1); j++) {
if (grid[i][j] !== 'obstacle' && !cameFrom.has(`${j},${i}`)) {
let newFScore = current.fScore + heuristic({ x: j, y: i }, goal);
openList.push({ x: j, y: i, fScore: newFScore });
cameFrom.set(`${j},${i}`, [current.x, current.y]);
}
}
}
drawGrid();
ctx.font = '16px Arial';
ctx.fillStyle = 'black';
ctx.textAlign = 'left';
ctx.textBaseline = 'top';
ctx.fillText(`Expanded nodes: ${totalExpanded}.`, 10, 30);
}
animate();
setInterval(() => {
start = generateGoal();
while (start[1] === grid[start[0]][start[1]]) {
start = generateGoal();
}
}, 30000);
setInterval(() => {
goal = [Math.floor(Math.random() * gridHeight), Math.floor(Math.random() * gridWidth)];
while (goal[1] === grid[goal[0]][goal[1]] || goal[1] === start[1]) {
goal = [Math.floor(Math.random() * gridHeight), Math.floor(Math.random() * gridWidth)];
}
}, 30000);
</script>
</body>
</html>
``````html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>A* Search Visualization</title>
<style>
body { background: #222; display: flex; justify-content: center; align-items: center; height: 100vh; margin: 0; font-family: Arial, sans-serif; color: white; }
#container { display: flex; padding: 20px; background: #111; border-radius: 8px; box-shadow: 0 0 15px rgba(0, 255, 0, 0.3); }
canvas { border: 4px solid #4CAF50; background: #0d0d0d; }
#stats { margin-left: 20px; padding: 10px; background: #222; border-radius: 5px; min-width: 180px; }
h3 { margin-top: 0; color: #4CAF50; }
</style>
</head>
<body>
<div id="container">
<canvas id="aStarCanvas"></canvas>
<div id="stats">
<h3>Stats</h3>
<p>Nodes Expanded: <span id="expandedCount">0</span></p>
<p>Path Length: <span id="pathLength">N/A</span></p>
</div>
</div>
<script>
const canvas = document.getElementById('aStarCanvas');
const ctx = canvas.getContext('2d');
// --- Configuration ---
const COLS = 35;
const ROWS = 25;
const CELL_SIZE = 20;
canvas.width = COLS * CELL_SIZE;
canvas.height = ROWS * CELL_SIZE;
let grid = [];
let startNode = { x: 1, y: 1 };
let goalNode = { x: COLS - 2, y: ROWS - 2 };
// --- State Variables ---
let openList = new Set();
let closedSet = new Set();
let gScore = Array(ROWS).fill(0).map(() => Array(COLS).fill(Infinity));
let fScore = Array(ROWS).fill(0).map(() => Array(COLS).fill(Infinity));
let cameFrom = Array(ROWS).fill(0).map(() => Array(COLS).fill(null));
// Visualization state
let isRunning = false;
let nodesExpandedCount = 0;
let animationFrameId = null;
let visualizationQueue = []; // Stores coordinates (x, y) to color/process next
let pathFound = false;
/** Initializes or resets the grid and state variables. */
function setupGrid() {
grid = Array(ROWS).fill(0).map(() => Array(COLS).fill(false));
openList.clear();
closedSet.clear();
gScore = Array(ROWS).fill(0).map(() => Array(COLS).fill(Infinity));
fScore = Array(ROWS).fill(0).map(() => Array(COLS).fill(Infinity));
cameFrom = Array(ROWS).fill(0).map(() => Array(COLS).fill(null));
nodesExpandedCount = 0;
pathFound = false;
visualizationQueue = [];
// Generate random obstacles (approx 25% coverage)
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if ((c === startNode.x && r === startNode.y) || (c === goalNode.x && r === goalNode.y)) {
grid[r][c] = false; // Start/Goal are never obstacles
} else if (Math.random() < 0.25) {
grid[r][c] = true; // Obstacle
} else {
grid[r][c] = false;
}
}
}
// Reset scores/paths
for(let r=0; r<ROWS; r++) for(let c=0; c<COLS; c++) {
gScore[r][c] = Infinity;
fScore[r][c] = Infinity;
cameFrom[r][c] = null;
}
// Initialize A* start state
gScore[startNode.y][startNode.x] = 0;
fScore[startNode.y][startNode.x] = Math.abs(startNode.x - goalNode.x) + Math.abs(startNode.y - goalNode.y); // Heuristic (Manhattan)
openList.add(`${startNode.x},${startNode.y}`);
// Start the search process
runAStarStep();
}
/** Finds neighbors and returns them as coordinates {x, y}. */
function getNeighbors(node) {
const neighbors = [];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // N, S, E, W
for (const [dy, dx] of directions) {
const newY = node.y + dy;
const newX = node.x + dx;
if (newY >= 0 && newY < ROWS && newX >= 0 && newX < COLS && !grid[newY][newX]) {
neighbors.push({ x: newX, y: newY });
}
}
return neighbors;
}
/** Core A* step logic (Non-visualized part). */
function runAStarStep() {
if (!openList.size) return false;
// 1. Find the node with the lowest F Score in the open list
let currentKey = null;
let minF = Infinity;
for (const key of openList) {
const [x, y] = key.split(',').map(Number);
if (fScore[y][x] < minF) {
minF = fScore[y][x];
currentKey = key;
}
}
if (!currentKey) return false; // Should not happen if openList is populated
const [currentX, currentY] = currentKey.split(',').map(Number);
// 2. Process the current node (Move it from Open to Closed)
openList.delete(currentKey);
closedSet.add(`${currentX},${currentY}`);
nodesExpandedCount++;
if (currentX === goalNode.x && currentY === goalNode.y) {
pathFound = true;
return false; // Goal reached, stop search loop
}
// 3. Check neighbors
const neighbors = getNeighbors({ x: currentX, y: currentY });
for (const neighbor of neighbors) {
const nKey = `${neighbor.x},${neighbor.y}`;
if (closedSet.has(nKey)) continue; // Skip if already processed
// Calculate Tentative G Score
const newGScore = gScore[currentY][currentX] + 1;
let existingNodeInOpen = openList.has(nKey);
let updateNeeded = false;
if (!existingNodeInOpen) {
updateNeeded = true; // New node found
} else if (newGScore < gScore[neighbor.y][neighbor.x]) {
updateNeeded = true; // Found better path to existing open node
}
if (updateNeeded) {
// Update scores and parent
cameFrom[neighbor.y][neighbor.x] = { x: currentX, y: currentY };
gScore[neighbor.y][neighbor.x] = newGScore;
const h = Math.abs(neighbor.x - goalNode.x) + Math.abs(neighbor.y - goalNode.y);
fScore[neighbor.y][neighbor.x] = newGScore + h;
if (!existingNodeInOpen) {
openList.add(nKey);
}
}
}
return true; // Search continues
}
/** Renders the current state of the search (frontier expansion). */
function drawVisualization() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
// Draw Obstacles and Grid base
for (let y = 0; y < ROWS; y++) {
for (let x = 0; x < COLS; x++) {
if (grid[y][x]) {
ctx.fillStyle = '#333'; // Dark obstacle
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
} else if ((x === startNode.x && y === startNode.y) || (x === goalNode.x && y === goalNode.y)) {
// Start and Goal
ctx.fillStyle = (x === startNode.x && y === startNode.y) ? '#0f0' : '#ff0';
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
} else {
// Normal cell background
ctx.fillStyle = '#1a1a1a';
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
}
// Draw expanded/closed nodes (Visited)
for (let y = 0; y < ROWS; y++) {
for (let x = 0; x < COLS; x++) {
if (!grid[y][x] && !(x === startNode.x && y === startNode.y)) {
const key = `${x},${y}`;
let color = null;
// Closed nodes (already processed)
if (closedSet.has(key)) {
color = 'rgba(100, 100, 255, 0.3)'; // Blue/Purple for closed
}
// Open nodes (frontier - color by f-score)
else if (openList.has(key)) {
const f = Math.round(fScore[y][x]);
// Color gradient based on F score (lower f = brighter green/yellow)
const maxF = Math.max(2 * COLS, 2 * ROWS); // Estimate max possible f
const intensity = Math.min(1, (Math.abs(f - 1) / maxF));
color = `rgba(${Math.floor(100 + intensity * 155)}, ${Math.floor(255 * (1-intensity))}, ${Math.floor(50 + intensity * 200)}, 0.7)`;
}
if (color) {
ctx.fillStyle = color;
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
}
}
}
/** Main animation loop driver. */
function animate() {
if (!isRunning) return;
// 1. Draw the current state before running the step
drawVisualization();
// 2. Perform one A* search step
const success = runAStarStep();
// 3. Update stats and handle termination
document.getElementById('expandedCount').textContent = nodesExpandedCount;
if (pathFound) {
//<!DOCTYPE html>
<html>
<head>
<title>A* Search Visualization</title>
<style>body { background: #111; display: flex; justify-content: center; align-items: center; height: 100vh; margin: 0; } canvas { border: 2px solid #777; }</style>
</head>
<body>
<canvas id="aStarCanvas"></canvas>
<script>
const CANVAS = document.getElementById('aStarCanvas');
const CTX = CANVAS.getContext('2d');
let GRID_SIZE = 30; // N x N grid
let CELL_SIZE = 20;
CANVAS.width = GRID_SIZE * CELL_SIZE;
CANVAS.height = GRID_SIZE * CELL_SIZE;
// Global state variables
let grid = [];
let startNode, goalNode;
let openList = []; // Priority Queue simulation
let closedList = new Set();
let currentPath = [];
let expandedNodes = 0;
let animationFrameId = null;
let isRunning = true;
// --- Utility Functions ---
function generateGrid() {
grid = [];
for (let y = 0; y < GRID_SIZE; y++) {
grid[y] = [];
for (let x = 0; x < GRID_SIZE; x++) {
if (Math.random() > 0.7) { // 30% chance of obstacle
grid[y][x] = 'O';
} else {
grid[y][x] = '.';
}
}
}
startNode = { x: Math.floor(Math.random() * GRID_SIZE), y: Math.floor(Math.random() * GRID_SIZE) };
goalNode = { x: Math.floor(Math.random() * GRID_SIZE), y: Math.floor(Math.random() * GRID_SIZE) };
// Ensure start and goal are not obstacles or on top of each other
while (grid[startNode.y][startNode.x] === 'O' || grid[goalNode.y][goalNode.x] === 'O' ||
(Math.abs(startNode.x - goalNode.x) < 3 && Math.abs(startNode.y - goalNode.y) < 3)) {
startNode = { x: Math.floor(Math.random() * GRID_SIZE), y: Math.floor(Math.random() * GRID_SIZE) };
goalNode = { x: Math.floor(Math.random() * GRID_SIZE), y: Math.floor(Math.random() * GRID_SIZE) };
}
// Reset state
openList = [];
closedList = new Set();
currentPath = [];
expandedNodes = 0;
}
function heuristic(a, b) { // Manhattan distance
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
// Node structure for A*
class Node {
constructor(x, y, g = Infinity, h = 0, parent = null) {
this.x = x;
this.y = y;
this.g = g; // Cost from start
this.h = h; // Heuristic cost to goal
this.f = g + h; // Total estimated cost
this.parent = parent;
}
}
function getNeighbors(current) {
const neighbors = [];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
for (const [dx, dy] of directions) {
const nx = current.x + dx;
const ny = current.y + dy;
if (nx >= 0 && nx < GRID_SIZE && ny >= 0 && ny < GRID_SIZE && grid[ny][nx] !== 'O') {
neighbors.push(new Node(nx, ny));
}
}
return neighbors;
}
// Simple Priority Queue implementation (Min-Heap based on f-score)
function priorityQueueInsert(queue, node) {
let added = false;
for (let i = 0; i < queue.length; i++) {
if (node.x === queue[i].x && node.y === queue[i].y) return false; // Already exists
}
queue.push(node);
// Simple sorting for visualization/efficiency tradeoff in JS environment
queue.sort((a, b) => a.f - b.f);
return true;
}
function getOrCreateNode(x, y, currentOpenList, parent) {
let existing = currentOpenList.find(n => n.x === x && n.y === y);
if (existing) return existing;
return new Node(x, y);
}
// --- Main A* Logic Step ---
function aStarStep() {
if (!openList.length || openList[0].g === Infinity) {
// No more nodes to check in the frontier
if (currentPath.length > 0) {
triggerSuccess();
} else if (closedList.size > 0) {
triggerFailure();
}
return false; // Stop animation
}
const current = openList.shift(); // Simulate pop minimum f-score node
if (current.x === goalNode.x && current.y === goalNode.y) {
console.log("Goal reached!");
currentPath = reconstructPath(current);
return false; // Stop animation, path found
}
closedList.add(`${current.x},${current.y}`);
expandedNodes++;
// Check neighbors
const neighbors = getNeighbors(current);
for (let n of neighbors) {
const key = `${n.x},${n.y}`;
if (closedList.has(key)) continue;
const newG = current.g + 1; // Assuming uniform cost of 1
// Check if neighbor is already in open list or needs update
let isInOpen = openList.some(n2 => n2.x === n.x && n2.y === n.y);
if (!isInOpen || newG < n.g) {
n.parent = current;
n.g = newG;
n.h = heuristic(n, goalNode);
n.f = n.g + n.h;
if (!isInOpen) {
priorityQueueInsert(openList, n);
} else {
// Update existing node's score (simulated by resorting or finding and updating)
const indexToUpdate = openList.findIndex(n2 => n2.x === n.x && n2.y === n.y);
if (indexToUpdate !== -1) {
openList[indexToUpdate].g = newG;
openList[indexToUpdate].h = n.h;
openList[indexToUpdate].f = n.f;
}
}
}
}
return true; // Continue animation
}
function reconstructPath(goal) {
let temp = goal;
while (temp !== null) {
temp = temp.parent;
}
// Re-run path reconstruction from the final node back to start
let path = [];
let curr = goal;
while(curr) {
path.unshift({x: curr.x, y: curr.y});
curr = curr.parent;
}
return path;
}
// --- Drawing and Animation ---
function draw() {
CTX.clearRect(0, 0, CANVAS.width, CANVAS.height);
for (let y = 0; y < GRID_SIZE; y++) {
for (let x = 0; x < GRID_SIZE; x++) {
const color = grid[y][x] === 'O' ? '#333' : '#1a1a1a';
CTX.fillStyle = color;
CTX.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
// Draw the open list (Frontier) - colored by f-score
openList.forEach(node => {
const intensity = Math.min(255, 100 + Math.ceil(node.f / GRID_SIZE)); // Scale color based on f
CTX.fillStyle = `rgba(${intensity}, ${Math.max(0, 255 - node.f * 2)}, 0, 0.6)`;
CTX.fillRect(node.x * CELL_SIZE, node.y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
});
// Draw the closed list (Expanded)
closedList.forEach(key => {
const [x, y] = key.split(',').map(Number);
CTX.fillStyle = 'rgba(50, 50, 50, 0.8)';
CTX.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
});
// Draw obstacles (already done above)
// Highlight Start and Goal
drawCell(startNode.x, startNode.y, '#00ff00'); // Green Start
drawCell(goalNode.x, goalNode.y, '#ff0000'); // Red Goal
// Draw the final path (if found)
if (currentPath.length > 0) {
CTX.strokeStyle = '#ffff00'; // Yellow Path
CTX.lineWidth = CELL_SIZE * 0.8;
CTX.beginPath();
for (let i = 0; i < currentPath.length; i++) {
const node = currentPath[i];
const x = node.x * CELL_SIZE + CELL_SIZE / 2;
const y = node.y * CELL_SIZE + CELL_SIZE / 2;
if (i === 0) CTX.moveTo(x, y);
else CTX.lineTo(x, y);
}
CTX.stroke();
}
// Display Stats
const stats = document.getElementById('stats');
if (!stats) {
const div = document.createElement('div');
div.id = 'stats';
div.style.cssText = 'position: absolute; top: 10px; color: white; font-family: monospace; background: rgba(0,0,0,0.5); padding: 10px; border-radius: 5px;';
document.body.appendChild(div);
}
const statDiv = document.getElementById('stats');
statDiv.innerHTML = `Nodes Expanded: ${expandedNodes}<br>Frontier Size: ${openList.length}`;
}
function drawCell(x, y, color) {
CTX.fillStyle = color;
CTX.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
// --- State Machine Control ---
function triggerSuccess() {
console.log("Path found!");
currentPath.forEach((node, index) => {
if (index > 0 && index < currentPath.length - 1) {
drawCell(node.x, node.y, '#ffff00'); // Highlight path nodes
}
});
const statDiv = document.getElementById('stats');
statDiv.innerHTML += `<br>Goal Reached! Path Length: ${currentPath.length - 1}`;
setTimeout(resetSimulation, 2500);
}
function triggerFailure() {
console.log("No path found!");
const statDiv = document.getElementById('stats');
statDiv.innerHTML += `<br>Failure! No path exists.`;
setTimeout(resetSimulation,```html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>A* Search Algorithm Animation</title>
<style>
body { margin: 0; overflow: hidden; }
canvas { display: block; }
</style>
</head>
<body>
<canvas id="canvas"></canvas>
<script>
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
function randomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.g = Infinity;
this.h = 0;
this.f = Infinity;
this.parent = null;
}
}
function heuristic(a, b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
function getNeighbors(node, grid) {
const neighbors = [];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const dir of directions) {
const nx = node.x + dir[0];
const ny = node.y + dir[1];
if (nx >= 0 && nx < grid.width && ny >= 0 && ny < grid.height && !grid.grid[nx][ny].obstacle) {
neighbors.push(grid.grid[nx][ny]);
}
}
return neighbors;
}
function reconstructPath(cameFrom, current) {
const totalPath = [current];
while (cameFrom[current]) {
current = cameFrom[current];
totalPath.unshift(current);
}
return totalPath;
}
class Grid {
constructor(width, height) {
this.width = width;
this.height = height;
this.grid = [];
for (let x = 0; x < width; x++) {
const row = [];
for (let y = 0; y < height; y++) {
row.push(new Node(x, y));
}
this.grid.push(row);
}
this.obstacles = randomInt(10, 50);
while (this.obstacles > 0) {
const x = randomInt(0, width - 1);
const y = randomInt(0, height - 1);
if (!this.grid[x][y].obstacle) {
this.grid[x][y].obstacle = true;
this.obstacles--;
}
}
this.start = new Node(randomInt(0, width - 1), randomInt(0, height - 1));
while (this.grid[this.start.x][this.start.y].obstacle) {
this.start = new Node(randomInt(0, width - 1), randomInt(0, height - 1));
}
this.goal = new Node(randomInt(0, width - 1), randomInt(0, height - 1));
while (this.grid[this.goal.x][this.goal.y].obstacle || (this.start.x === this.goal.x && this.start.y === this.goal.y)) {
this.goal = new Node(randomInt(0, width - 1), randomInt(0, height - 1));
}
}
draw() {
const cellSize = Math.min(canvas.width / this.width, canvas.height / this.height);
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let x = 0; x < this.width; x++) {
for (let y = 0; y < this.height; y++) {
const node = this.grid[x][y];
if (node.obstacle) {
ctx.fillStyle = 'black';
} else if (node === this.start) {
ctx.fillStyle = 'green';
} else if (node === this.goal) {
ctx.fillStyle = 'red';
} else if (node.f !== Infinity) {
const fColor = Math.floor(255 * (1 - node.f / 90));
ctx.fillStyle = `rgb(${fColor}, ${255 - fColor}, 0)`;
} else {
ctx.fillStyle = 'white';
}
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
}
}
astar() {
const openSet = [];
const cameFrom = {};
const gScore = {};
const fScore = {};
for (const node of this.flattenGrid()) {
gScore[node] = Infinity;
fScore[node] = Infinity;
}
gScore[this.start] = 0;
fScore[this.start] = heuristic(this.start, this.goal);
openSet.push(this.start);
let nodesExpanded = 0;
while (openSet.length > 0) {
openSet.sort((a, b) => fScore[a] - fScore[b]);
const current = openSet.shift();
if (current === this.goal) {
return { cameFrom, pathLength: reconstructPath(cameFrom, current).length };
}
nodesExpanded++;
for (const neighbor of getNeighbors(current, this)) {
const tentativeGScore = gScore[current] + 1;
if (tentativeGScore < gScore[neighbor]) {
cameFrom[neighbor] = current;
gScore[neighbor] = tentativeGScore;
fScore[neighbor] = tentativeGScore + heuristic(neighbor, this.goal);
if (!openSet.includes(neighbor)) {
openSet.push(neighbor);
}
}
}
}
return { nodesExpanded };
}
flattenGrid() {
const flatArray = [];
for (const row of this.grid) {
for (const node of row) {
flatArray.push(node);
}
}
return flatArray;
}
animateAstar() {
let frame = 0;
function drawFrame() {
if (!animationRunning) return;
ctx.clearRect(0, 0, canvas.width, canvas.height);
this.draw();
const result = aStarResults[frame];
if (result) {
for (const node of result.openSet) {
node.f = frame;
}
for (const node of result.closedSet) {
node.f = Infinity;
}
if (result.pathFound && result.goalNode === this.goal) {
const pathLength = result.path.length;
ctx.font = '24px Arial';
ctx.fillStyle = 'black';
ctx.fillText(`Nodes Expanded: ${nodesExpanded}`, 10, canvas.height - 50);
ctx.fillText(`Path Length: ${pathLength}`, 10, canvas.height - 20);
}
}
frame++;
if (frame < aStarResults.length) {
requestAnimationFrame(drawFrame);
} else {
setTimeout(() => this.animateAstar(), 3000);
}
}
drawFrame();
}
}
const grid = new Grid(20, 15);
function runAstar() {
const openSet = [];
let nodesExpanded = 0;
const aStarResults = [];
for (const node of grid.flattenGrid()) {
node.g = Infinity;
node.f = Infinity;
}
grid.start.g = 0;
grid.start.f = heuristic(grid.start, grid.goal);
openSet.push(grid.start);
while (openSet.length > 0) {
openSet.sort((a, b) => a.f - b.f);
const current = openSet.shift();
if (current === grid.goal) {
const path = reconstructPath(cameFrom, current);
aStarResults.push({ openSet, closedSet: [], pathFound: true, goalNode: current });
return { nodesExpanded, pathLength: path.length };
}
nodesExpanded++;
for (const neighbor of getNeighbors(current, grid)) {
const tentativeGScore = current.g + 1;
if (tentativeGScore < neighbor.g) {
cameFrom[neighbor] = current;
neighbor.g = tentativeGScore;
neighbor.f = tentativeGScore + heuristic(neighbor, grid.goal);
if (!openSet.includes(neighbor)) {
openSet.push(neighbor);
}
}
}
aStarResults.push({ openSet });
}
return { nodesExpanded };
}
const animationRunning = true;
let aStarResults = [];
aStarResults.push(runAstar());
grid.animateAstar();
</script>
</body>
</html>
``````html
<!DOCTYPE html>
<html lang="en"><head><meta charset="UTF-8"/><title>A* Search Visualization</title><style>body{background:#222;color:white;font-family:sans-serif;display:flex;flex-direction:column;align-items:center;margin:0;padding:10px;}canvas{border:1px solid #444;background:#333;margin-bottom:15px;}</style></head><body id="container"><canvas id="aStarCanvas"></canvas><p>Nodes Expanded: <span id="expandedCount">0</span> | Path Length: <span id="pathLength">N/A</span></p><script>
const canvas = document.getElementById('aStarCanvas');
const ctx = canvas.getContext('2d');
const expandedSpan = document.getElementById('expandedCount');
const pathLengthSpan = document.getElementById('pathLength');
// Configuration
const COLS = 40;
const ROWS = 30;
const CELL_SIZE = 18; // Use a relatively small size for detail
canvas.width = COLS * CELL_SIZE;
canvas.height = ROWS * CELL_SIZE;
let grid = [];
let startNode, goalNode;
let openList = [];
let closedSet = new Set();
let pathFound = false;
let expandedNodesCount = 0;
let currentPath = [];
// Helper class for coordinates and node data
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.g = Infinity; // Cost from start
this.h = 0; // Heuristic cost to end
this.f = Infinity; // Total cost (g + h)
this.isObstacle = false;
this.parent = null;
}
equals(other) { return this.x === other.x && this.y === other.y; }
}
function initGrid() {
grid = [];
for (let i = 0; i < ROWS; i++) {
grid[i] = [];
for (let j = 0; j < COLS; j++) {
const node = new Node(j, i);
node.isObstacle = Math.random() > 0.8 ? true : false; // ~20% obstacles
grid[i][j] = node;
}
}
// Set Start and Goal (must be non-obstacle)
startNode = grid[Math.floor(ROWS * 0.1)][5];
goalNode = grid[Math.floor(ROWS * 0.9)][COLS - 6];
if (startNode.isObstacle || goalNode.isObstacle) {
// Fallback attempt if random generation failed to place start/goal correctly
startNode = grid[5][5];
goalNode = grid[ROWS - 5][COLS - 5];
}
expandedNodesCount = 0;
currentPath = [];
pathFound = false;
// Reset all node states
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const n = grid[r][c];
n.g = Infinity;
n.h = 0;
n.f = Infinity;
n.parent = null;
}
}
// Setup start node
startNode.g = 0;
startNode.h = Math.hypot(goalNode.x - startNode.x, goalNode.y - startNode.y);
startNode.f = startNode.h; // f = g + h
openList = [startNode];
closedSet.clear();
}
/** Heuristic function (Manhattan distance is sufficient and fast) */
function heuristic(a, b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
function getNeighbors(node) {
const neighbors = [];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // Cardinal directions only (no diagonals for simplicity/speed)
for (const [dx, dy] of directions) {
const nx = node.x + dx;
const ny = node.y + dy;
if (nx >= 0 && nx < COLS && ny >= 0 && ny < ROWS) {
const neighbor = grid[ny][nx];
if (!neighbor.isObstacle) {
neighbors.push(neighbor);
}
}
}
return neighbors;
}
function aStarSearch() {
if (pathFound) return false; // Already completed
openList = [startNode];
closedSet.clear();
while (openList.length > 0 && !pathFound) {
// Find node with the lowest F score (Optimization: instead of sorting every time, we iterate)
let bestIndex = 0;
for(let i = 1; i < openList.length; i++) {
if (openList[i].f < openList[bestIndex].f) {
bestIndex = i;
}
}
const currentNode = openList.splice(bestIndex, 1)[0]; // Get and remove the best node
// Check for goal reached
if (currentNode.equals(goalNode)) {
pathFound = true;
let temp = [];
let curr = currentNode;
while (curr) {
temp.push(curr);
curr = curr.parent;
}
currentPath = temp.reverse();
return true;
}
closedSet.add(currentNode);
expandedNodesCount++;
// Explore neighbors
const neighbors = getNeighbors(currentNode);
for (const neighbor of neighbors) {
if (closedSet.has(neighbor)) continue;
// Cost calculation: g_new = g_current + cost_to_move
const tentativeGScore = currentNode.g + 1; // Assume uniform cost of 1
let isNewNode = true;
let existingIndex = openList.findIndex(n => n.equals(neighbor));
if (existingIndex !== -1) {
isNewNode = false;
const existingNeighbor = openList[existingIndex];
// If we found a better path to an already open node
if (tentativeGScore >= existingNeighbor.g) continue;
}
// Update scores
neighbor.parent = currentNode;
neighbor.g = tentativeGScore;
neighbor.h = heuristic(neighbor, goalNode);
neighbor.f = neighbor.g + neighbor.h;
if (isNewNode || tentativeGScore < openList[existingIndex].g) {
if (!openList.includes(neighbor)) {
openList.push(neighbor);
} else {
// If it was already in the list, we updated its parent/score above
}
}
}
}
return false; // Path not found
}
function draw() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
// Draw Grid (Obstacles)
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const n = grid[r][c];
ctx.fillStyle = n.isObstacle ? '#555' : '#333';
ctx.fillRect(c * CELL_SIZE, r * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
// Draw Open List (Frontier) - F-score visualization
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const n = grid[r][c];
if (openList.includes(n) && !n.equals(startNode) && !n.equals(goalNode)) {
// Use f-score to determine color intensity/shade
let alpha = Math.min(1, n.f / 30); // Normalize F score for visible coloring
ctx.fillStyle = `rgba(60, 150, ${20 + (n.h * 1)}*, ${alpha})`;
ctx.fillRect(c * CELL_SIZE, r * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
}
// Draw Closed Set (Visited)
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const n = grid[r][c];
if (!n.equals(startNode) && !n.equals(goalNode) && closedSet.has(n)) {
ctx.fillStyle = 'rgba(150, 50, 50, 0.6)'; // Dark red/gray for visited
ctx.fillRect(c * CELL_SIZE, r * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
}
// Draw Path (If found)
if (currentPath.length > 0 && !pathFound) { // This handles drawing the path only when the search finishes
for(let i = 1; i < currentPath.length - 1; i++) {
const node = currentPath[i];
ctx.fillStyle = 'rgba(255, 200, 0, 0.9)'; // Gold path color
ctx.fillRect(node.x * CELL_SIZE, node.y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}
}
// Draw Start and Goal
[startNode, goalNode].forEach(n => {
ctx.fillStyle = n === startNode ? '#00FF00' : '#FF0000'; // Green/Red
ctx.fillRect(n.x * CELL_SIZE, n.y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
});
// Update Stats
expandedSpan.textContent = expandedNodesCount;
}
function animateSearch() {
if (!pathFound) {
const success = aStarSearch();
draw();
if (success) {
// Path found, keep animating the final state for a moment
// We don't need to run A* again, just draw the result and wait.
} else if (!pathFound && openList.length === 0) {
// No path possible
}
}
if (pathFound) {
// If path was found, we simply redraw the final state repeatedly until restart condition is triggered externally or loop timeout happens.
draw();
}
requestAnimationFrame(animateSearch);
}
function runSimulation() {
initGrid();
// Clear previous path visualization before starting a new search
currentPath = [];
pathFound = false;
expandedNodesCount = 0;
pathLengthSpan.textContent = 'N/A';
animateSearch();
}
// Initial execution and continuous loop management
let animationFrameId = null;
window.addEventListener('load', () => {
runSimulation();
});
</script></body></html>
``````html
<!DOCTYPE html><html><body style="margin:0;display:flex;justify-content:center;background:#000;font-family:Arial;height:100vh"><canvas id=c width=500 height=500></canvas><div style="color:#fff;padding:20px">Nodes Expanded: <span id=n>0</span><br>Path Length: <span id=p>∞</span></div><script>
var n=5,c=document.getElementById('c'),N=100,obs=.3,start={},goal={},nodes=[],path=[],queue=[];function init(){start={x:Math.floor(Math.random()*N),y:Math.floor(Math.random()*N)};goal={x:(start.x+Math.floor(Math.random()*4)+1)%N,y:(start.y+Math.floor(Math.random()*4)+1)%N};obstacles=new Array(N*N).fill().map((v,i)=>i%Math.random()>obs);nodes=new Array(N).fill().map(v=>new Array(N));path=[];queue=[];resetGrid();animateSearch()}function resetGrid(){for(let i=0;i<N;i++)for(let j=0;j<N;j++){if(i==start.x&&j==start.y||i==goal.x&&j==goal.y)nodes[i][j]={f:Infinity,g:0,parent:{x:i,y:j}};else nodes[i][j]=obstacles[i*N+j]?null:{f:Infinity,g:Infinity,parent:null}}}function drawGrid(){c.fillStyle='#000';c.fillRect(0,0,c.width,c.height);c.strokeStyle='#333';for(let i=1;i<N;i++){let x=i*n;let y=i*n;c.beginPath();c.moveTo(x,0);c.lineTo(x,c.height);c.stroke();c.beginPath();c.moveTo(0,y);c.lineTo(c.width,y);c.stroke()}}function drawNode(x,y,color){x=x*n+2;y=y*n+2;c.fillStyle=color||'#fff';c.fillRect(x,y,n-4,n-4)}function drawStartGoal(){drawNode(start.x,start.y,'#0ff');drawNode(goal.x,goal.y,'#f00')}function drawPath(){path.forEach(p=>drawNode(p.x,p.y,'#0f0'));drawStartGoal()}function animateSearch(f=0){nodesExpanded=document.getElementById('n').textContent;let found=false;if(queue.length>0){let node=queue.shift();if(node.pos.x==goal.x&&node.pos.y==goal.y){found=true}else{let neighbors=[[1,0],[-1,0],[0,1],[0,-1]];for(let [dx,dy] of neighbors){let nx=node.pos.x+dx;let ny=node.pos.y+dy;if(nx<0||nx>=N||ny<0||ny>=N)continue;if(obstacles[nx*N+ny])continue;if(nodes[nx][ny].g>node.g+1){nodes[nx][ny].g=node.g+1;n=parseInt(nodesExpanded)+1;document.getElementById('n').textContent=n;nodes[nx][ny].parent={x:node.pos.x,y:node.pos.y};nodes[nx][ny].f=nodes[nx][ny].g+Math.abs(nx-goal.x)+Math.abs(ny-goal.y);queue.push({pos:{x:nx,y:ny},f:nodes[nx][ny].f});queue.sort((a,b)=>a.f-b.f)}}}drawGrid();if(!found){for(let i=0;i<N;i++)for(let j=0;j<N;j++){let node=nodes[i][j];if(node!=null&&node.g<Infinity)drawNode(i,j,'#'+(15-Math.min(Math.floor(node.f/10),15)).toString(16)+(15-Math.min(Math.floor((node.f-Math.abs(i-goal.x)-Math.abs(j-goal.y))/10),15)).toString(16)+2)}drawStartGoal()}else{path=[];let current=goal;while(current.x!=start.x||current.y!=start.y){path.push({x:current.x,y:current.y});current=nodes[current.x][current.y].parent}path.reverse();drawPath();document.getElementById('p').textContent=path.length+1}if(!found&&queue.length>0)requestAnimationFrame(animateSearch);else{resetGrid();init()}}init();
</script></body></html>
```<think>
Okay, so I need to create an HTML file that animates the A* search algorithm on a canvas. The user specified it should be self-contained, strict limit of 7000 characters, no external libraries, and no comments. Let me start by breaking down the requirements.
First, the HTML structure. It should have a canvas element, and some text elements to display the nodes expanded and path length. Maybe use divs for the text. The canvas needs some styling to be centered and visible.
Then, the JavaScript part. I need to set up the grid, with obstacles, start and goal points. The grid should be randomly generated each time. The A* algorithm needs to be implemented with pathfinding. The animation should use requestAnimationFrame for smoothness. Also, when the path is found or it's impossible, it should restart with a new grid.
Let me think about the grid structure. Each cell can be an object with position, f-score, g-score, h-score, parent, and whether it's an obstacle. The grid can be a 2D array. The obstacles can be set with a certain probability, say 25%, but not on start or goal.
The A* algorithm steps: initialize the open list, start node's g=0, h=heuristic. Then, in a loop, pick the node with the lowest f-score, check if it's the goal. If so, backtrack the path. Otherwise, add neighbors to the open list. Need to track visited nodes (closed list). The neighbors can be up, down, left, right (no diagonals, I think? Probably, since the user didn't specify otherwise).
The animation: each step, draw the grid, color the nodes by their f-score or by state (open, closed, path). The frontier should expand as small squares. Maybe color the current node being processed, then the open nodes with their f-score gradient. The path at the end should be in a distinct color.
Displaying the number of expanded nodes and path length. These can be updated as the algorithm progresses.
Restarting: when the algorithm finishes (either path found or no path), after some delay, generate a new grid, reset all variables, and start again.
So the steps for the code:
1. Set up canvas and ctx.
2. Define grid size, maybe 40x40. The cell size can be computed based on canvas size.
3. Generate grid with random obstacles, start and goal positions (maybe top-left and bottom-right).
4. Implement A* algorithm with functions to handle open list (maybe using a priority queue, but since it's JS, perhaps just an array and find the min each time).
5. Animation loop with requestAnimationFrame. Each frame, process one step of A*, then render.
6. When done, render the path, show numbers, wait, then restart.
Potential issues:
- Performance: with 40x40 grid, it's manageable but need to make sure the animation is smooth. Maybe process one node per frame to prevent it from going too fast.
- Obstacle generation: ensure start and goal are not obstacles and are accessible.
- Pathfinding: correctly calculating the heuristic (manhattan or euclidean?), but Manhattan is easier. Let's use Manhattan distance for h.
- Drawing: Need to fill the cells with appropriate colors. Maybe gradient for f-score, or different colors for open/closed nodes.
- Restarting when no path exists: After a certain number of steps if the open list is empty, then restart.
Implementing the priority queue: Since in each step of A*, we need the node with the lowest f-score, maybe each frame, we find the node with the lowest f in the open list. That's O(n) each time, but for 40x40 grid, that's 1600 nodes. Maybe manageable? Or perhaps optimize with a min-heap later, but first go with the simplest approach.
Let me outline the code structure:
HTML:
<!DOCTYPE html>
<html>
<head>
<style>
body { margin: 0; display: flex; flex-direction: column; align-items: center; padding: 20px; }
canvas { border: 1px solid black; }
div { margin: 5px; }
</style>
</head>
<body>
<canvas id="canvas"></canvas>
<div id="expanded">Nodes Expanded: 0</div>
<div id="pathLength">Path Length: 0</div>
<script>
// JS code here
</script>
</body>
</html>
Now the JavaScript part.
First, variables:
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const gridWidth = 40;
const gridHeight = 40;
let cellSize = 15; // initial, will adjust based on canvas size
But we might need to set canvas size based on grid dimensions. Let's set canvas width and height after grid size is determined.
Wait, maybe better to set canvas to have a fixed size? Like 600x600, which would give cellSize of 15 (600/40). Let me see: 40 cells per side, 15px each. 40*15 = 600. That works. So set canvas to 600x600.
So in HTML:
<canvas id="canvas" width="600" height="600"></canvas>
Then in JS:
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const gridWidth = 40, gridHeight = 40;
const cellSize = 15;
Then the grid array:
let grid = Array(gridHeight).fill(0).map(() => Array(gridWidth).fill({})); // need to initialize each cell properly
Wait, better to create each cell with properties:
Each cell will be an object like:
{
x: column, y: row,
f: 0, g: 0, h: 0,
isObstacle: false,
visited: false,
parent: null
}
Wait, but in the grid, maybe a 2D array where each element is such an object. So first, create the grid:
function resetGrid() {
grid = Array(gridHeight).fill().map(() => Array(gridWidth));
// initialize each cell
for (let y=0; y<gridHeight; y++) {
for (let x=0; x<gridWidth; x++) {
grid[y][x] = {
x: x,
y: y,
g: Infinity,
h: 0,
f: Infinity,
isObstacle: Math.random() < 0.25 ? true : false, // 25% chance obstacle
visited: false,
parent: null
};
}
}
// place start and goal
startNode = { x: 0, y: 0 };
goalNode = { x: gridWidth-1, y: gridHeight-1 };
// ensure they are not obstacles
grid[startNode.y][startNode.x].isObstacle = false;
grid[goalNode.y][goalNode.x].isObstacle = false;
}
Wait, but the start and goal positions could be randomized. The user didn't specify, so maybe just place them at the corners? Or better to randomize their positions each time but not on an obstacle.
Alternatively, set startNode to (0,0), goal to (gridWidth-1, gridHeight-1), but make sure they are not obstacles.
But when generating obstacles, they might already be non-obstacle? The line 'isObstacle: Math.random() < 0.25 ? true : false' could have them as obstacles. So after generating, set both start and goal to not be obstacles.
So in resetGrid(), after initializing all cells, set:
grid[startNode.y][startNode.x].isObstacle = false;
Same for goalNode.
Also, maybe the start and goal should be placed randomly but not in obstacle cells.
Alternatively, maybe choose start and goal positions randomly but not on obstacle. Hmm, maybe it's better to set them in corners but ensure they aren't obstacles.
Proceeding with that.
Now, variables needed for A*:
let openList = [];
let closedList = [];
let path = null;
let nodesExpanded = 0;
let pathLength = 0;
let isRunning = false;
Variables for the current step. Maybe in the animation loop, each frame processes one step of the algorithm.
Wait, the A* algorithm is step-based, so each frame, we do one iteration.
Hmm, but the A* algorithm is a loop that continues until the open list is empty or the goal is found. To animate this, we need to break it into steps, so each frame processes part of the loop.
Alternatively, in each frame, process one iteration of the main loop (selecting the best node, expanding it, adding neighbors to open list, etc.)
Wait, the standard A* loop is:
Initialize open list with start node.
While open list is not empty:
current = node in open list with lowest f-score
if current is goal, build path and exit
remove current from open list, add to closed list
for each neighbor:
if neighbor is goal, set parent and exit
if neighbor is obstacle or in closed list, skip
tempG = current.g + 1 (assuming movement cost is 1)
if neighbor not in open list, add to open list, set parent and g and h
else if tempG < neighbor.g, update parent and g
update f and h (h is heuristic)
Wait, the heuristic is the estimated distance from neighbor to goal. Using Manhattan distance: Math.abs(neighbor.x - goal.x) + Math.abs(neighbor.y - goal.y)
Hmm, okay.
So, to make this step-based, perhaps:
Each frame, we process one node from the open list. That way, each frame does a single node's expansion, which can be animated.
So, the main processing would be in a function like stepAStar(), which does one step, and then calls requestAnimationFrame again.
But to structure this, maybe have a function that runs the algorithm step by step.
Now, the animation loop:
function animate() {
if (isRunning) {
stepAStar();
}
render();
requestAnimationFrame(animate);
}
But stepAStar() needs to perform one step of the algorithm.
So, let's structure the algorithm in a way that can be done in steps.
The variables:
let current;
let openList = new MinPriorityQueue(); // but without a library, we can manage as array and find min each time.
Alternatively, we can have an array openList, and each time find the node with lowest f.
Wait, but in each step, we want to process the next node. So, in the step function:
function stepAStar() {
if (openList.length === 0) {
// no path found, wait and restart
isRunning = false;
setTimeout(() => resetGrid(), 2000); // after 2 seconds
return;
}
// get current node (min f-score)
current = getMinFromOpenList();
openList = openList.filter(node => node !== current);
closedList.push(current);
nodesExpanded++;
if (current.x === goalNode.x && current.y === goalNode.y) {
// found path, build path and stop
buildPath(current);
isRunning = false;
setTimeout(() => resetGrid(), 2000); // after showing path for 2 seconds
return;
}
// process neighbors
const neighbors = getNeighbors(current);
for (const neighbor of neighbors) {
if (neighbor.isObstacle || closedList.some(n => n.x === neighbor.x && n.y === neighbor.y)) continue;
const tentativeG = current.g + 1; // movement cost is 1
if (tentativeG < neighbor.g) {
neighbor.parent = current;
neighbor.g = tentativeG;
neighbor.f = neighbor.g + neighbor.h;
if (!openList.some(n => n.x === neighbor.x && n.y === neighbor.y)) {
openList.push(neighbor);
}
}
}
}
Wait, but this is all in one step, which might take too long for one frame. So perhaps split processing each neighbor into steps?
Alternatively, process one neighbor per step? That would make it very slow but animate each move.
Alternatively, process the current node's expansion in one step, but process all neighbors at once. The animation would then need to show the current node being processed, and the neighbors added to the open list.
Hmm, maybe the step function can be structured to process the current node, then the next step processes the next node.
But how to track the state? Perhaps the algorithm is in a state machine. Maybe the step function does one iteration of the loop.
Alternatively, have a flag that indicates whether the algorithm is running, and in each frame step, it does one iteration.
Alternatively, the A* loop can be broken into steps, with each step doing one iteration. Let's try:
In the stepAStar function:
if (openList is empty) { reset }
current = find node with smallest f.
remove from open list, add to closed list.
if current is goal:
build path, schedule reset.
else:
process each neighbor:
but process all neighbors at once, since each step would take too much time otherwise.
Wait, but neighbors can be many. So maybe process one neighbor per step?
That would take a lot of steps, but could make the animation more detailed.
Alternatively, process the current node's expansion (neighbors) all at once, but only do one step of the algorithm per frame.
Wait, perhaps it's better to have the A* algorithm run in steps so that each frame does one expansion step (i.e., selects the next node and processes it), but the neighbor processing is done in full. That way the animation can show the frontier expanding step by step.
Alternatively, the problem is that processing all neighbors in one step would not allow the animation to show them. To have smooth animation, each neighbor addition could be a step, but that would require storing the neighbors to process one by one.
This is getting complicated. Maybe to simplify, in each frame, process one node from the open list, and process all its neighbors in that step. This way, each frame shows the current node being expanded and all its neighbors added. The animation would still be manageable as the grid isn't too big.
Alternatively, in the stepAStar function, process one node and all its neighbors, then the next frame processes the next node.
I think that's manageable.
Now, functions:
function getMinFromOpenList() {
let min = openList[0];
for (let node of openList) {
if (node.f < min.f || (node.f === min.f && node.h < min.h)) {
min = node;
}
}
return min;
}
But since openList is an array, we can loop through it each time to find the minimum.
The neighbors function:
function getNeighbors(node) {
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
return dirs.map(([dx, dy]) => {
const x = node.x + dx;
const y = node.y + dy;
if (x >=0 && x < gridWidth && y >=0 && y < gridHeight) {
return grid[y][x];
}
return null;
}).filter(n => n !== null);
}
Wait, the grid is as grid[y][x], so need to make sure the indices are correct.
Now, building the path:
function buildPath(endNode) {
path = [];
let current = endNode;
while (current.parent) {
path.unshift(current);
current = current.parent;
}
path.unshift(current); // add start node
pathLength = path.length - 1; // since steps between nodes
// update the display
}
Now, the initial setup:
Reset the grid, set openList to startNode, and start the algorithm.
When starting, after resetting, set openList to startNode, and start the animation loop.
Let me structure the setup:
let startNode, goalNode, grid, openList, closedList, path, pathLength, nodesExpanded, isRunning;
function reset() {
resetGrid();
nodesExpanded = 0;
pathLength = 0;
openList = [];
closedList = [];
const startCell = grid[startNode.y][startNode.x];
startCell.g = 0;
startCell.h = heuristic(startCell);
startCell.f = startCell.g + startCell.h;
openList.push(startCell);
path = null;
isRunning = true;
}
function heuristic(node) {
return Math.abs(node.x - goalNode.x) + Math.abs(node.y - goalNode.y);
}
function startAlgorithm() {
reset();
requestAnimationFrame(animate);
}
So when the page loads, call startAlgorithm().
Wait, but in the script, we need to initialize and start.
Putting all together, in the script section:
(function() {
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const gridWidth = 40, gridHeight = 40;
const cellSize = 15; // 40*15=600
canvas.width = gridWidth * cellSize;
canvas.height = gridHeight * cellSize;
let grid = [];
let startNode, goalNode;
let openList = [];
let closedList = [];
let path = null;
let nodesExpanded = 0;
let pathLength = 0;
let isRunning = false;
function resetGrid() {
grid = [];
for (let y=0; y<gridHeight; y++) {
grid[y] = [];
for (let x=0; x<gridWidth; x++) {
const isObstacle = Math.random() < 0.25;
grid[y][x] = {
x, y,
g: Infinity,
h: 0,
f: Infinity,
isObstacle: isObstacle,
visited: false,
parent: null
};
}
}
startNode = grid[0][0];
startNode.isObstacle = false;
goalNode = grid[gridHeight-1][gridWidth-1];
goalNode.isObstacle = false;
}
function reset() {
resetGrid();
nodesExpanded = 0;
pathLength = 0;
openList = [];
closedList = [];
const startCell = grid[startNode.y][startNode.x];
startCell.g = 0;
startCell.h = heuristic(startCell);
startCell.f = startCell.g + startCell.h;
openList.push(startCell);
path = null;
isRunning = true;
}
function heuristic(node) {
return Math.abs(node.x - goalNode.x) + Math.abs(node.y - goalNode.y);
}
function getMinFromOpenList() {
let minNode = openList[0];
for (const node of openList) {
if (node.f < minNode.f ||
(node.f === minNode.f && node.h < minNode.h)) {
minNode = node;
}
}
return minNode;
}
function getNeighbors(node) {
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
return dirs.map(([dx, dy]) => {
const x = node.x + dx;
const y = node.y + dy;
if (x >=0 && x < gridWidth && y >=0 && y < gridHeight) {
return grid[y][x];
}
return null;
}).filter(n => n !== null);
}
function buildPath(endNode) {
path = [];
let current = endNode;
while (current.parent) {
path.unshift(current);
current = current.parent;
}
path.unshift(current);
pathLength = path.length - 1; // steps between nodes
}
function stepAStar() {
if (openList.length === 0) {
isRunning = false;
setTimeout(reset, 2000);
return;
}
const current = getMinFromOpenList();
openList = openList.filter(node => node !== current);
closedList.push(current);
nodesExpanded++;
if (current.x === goalNode.x && current.y === goalNode.y) {
buildPath(current);
isRunning = false;
setTimeout(reset, 2000);
return;
}
const neighbors = getNeighbors(current);
for (const neighbor of neighbors) {
if (neighbor.isObstacle || closedList.some(n => n.x === neighbor.x && n.y === neighbor.y)) continue;
const tentativeG = current.g + 1;
if (tentativeG < neighbor.g) {
neighbor.parent = current;
neighbor.g = tentativeG;
neighbor.h = heuristic(neighbor);
neighbor.f = neighbor.g + neighbor.h;
if (!openList.some(n => n.x === neighbor.x && n.y === neighbor.y)) {
openList.push(neighbor);
}
}
}
}
function animate() {
if (isRunning) stepAStar();
render();
requestAnimationFrame(animate);
}
function render() {
ctx.clearRect(0,0,canvas.width, canvas.height);
for (let y=0; y<gridHeight; y++) {
for (let x=0; x<gridWidth; x++) {
const node = grid[y][x];
let color;
if (node.isObstacle) {
color = '#000';
} else if (closedList.includes(node)) {
color = '#888';
} else if (openList.includes(node)) {
color = '#0f0';
} else {
color = '#fff';
}
ctx.fillStyle = color;
ctx.fillRect(x*cellSize, y*cellSize, cellSize, cellSize);
}
}
if (path) {
ctx.strokeStyle = '#f00';
ctx.lineWidth = 2;
ctx.beginPath();
path.forEach((node, i) => {
if (i === 0) {
ctx.moveTo(node.x*cellSize + cellSize/2, node.y*cellSize + cellSize/2);
} else {
ctx.lineTo(node.x*cellSize + cellSize/2, node.y*cellSize + cellSize/2);
}
});
ctx.stroke();
}
// UI Elements
ctx.fillStyle = '#000';
ctx.font = '12px Arial';
ctx.fillText(`Nodes Expanded: ${nodesExpanded}`, 10, 20);
ctx.fillText(`Path Length: ${pathLength}`, 10, 40);
}
window.addEventListener('load', function() {
reset();
animate();
});
})();
Wait, but in the animate function, we have to make sure that the initial call to animate starts the animation loop. The window.load event listener calls reset() and then animate(). But in the animate function, requestAnimationFrame is called each time, so that should start the loop.
Hmm, but in the code above, the animate function is called once from the load event, then inside it calls requestAnimationFrame(animate), which should keep it going.
Potential issues:
- The reset() function doesn't clear path, but in buildPath it's handled.
- The heuristic is properly calculated.
- The neighbors are correctly fetched from grid.
- The getMinFromOpenList is O(n) each time, which is okay for small grids (40x40 is manageable).
Testing in imagination: when the grid is reset, the open list has the start node. The first step selects it, processes it, and adds neighbors to the open list. The animation shows the start node as closed (gray), and neighbors in open (green).
When the algorithm completes, the path is drawn in red.
Path is built correctly.
Potential optimizations: precompute the goalNode position, etc.
But this should work.
Now, the HTML part:
The user provided just the script, but in the HTML, the canvas must be present. However, since the code is encapsulated in a function, it should work if the canvas is in the page with id 'canvas'.
So, the final code includes a canvas element and the script.
Putting all together:
The full HTML would be something like:
<!DOCTYPE html>
<html>
<head>
<title>A* Animation</title>
</head>
<body>
<canvas id="canvas"></canvas>
<script>
// the code above
</script>
</body>
</html>
But since the user's question is to create the code, I'll present the JavaScript part as the answer.
Wait, the problem says "Create a JavaScript program that..." and the user just needs to provide the code.
So the final answer is the JavaScript code wrapped in a self-invoking function, handling the canvas and animation.
Looking back, I think I have all the necessary parts. The only thing missing is the initial start, but since the window.load event calls reset() and animate(), it should work.
I'll now present the code.<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>A* Search Visualization</title>
<style>
body {
margin: 0;
overflow: hidden;
}
button {
position: absolute;
top: 10px;
right: 10px;
z-index: 999;
}
</style>
</head>
<body>
<button id="restartButton">Restart</button>
<canvas id="aStarCanvas"></canvas>
<script>
const canvas = document.getElementById("aStarCanvas");
const ctx = canvas.getContext("2d");
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
let restartButton = document.getElementById("restartButton");
function restart() {
generateMaze();
drawGrid();
}
restartButton.addEventListener('click', restart);
const gridSize = 20;
const cellSize = Math.floor(canvas.width / gridSize);
canvas.height = cellSize * gridSize;
let maze = [];
let start, goal;
let openList = [];
let closedList = [];
let path = [];
let nodesExpanded = 0;
let pathLength = 0;
function generateMaze() {
maze = Array.from({ length: gridSize }, () =>
Array.from({ length: gridSize }, () => ({
isWall: Math.random() < 0.2, // Adjust for different wall densities
fScore: Infinity,
gScore: Infinity,
hScore: Infinity,
parent: null,
}))
);
start = { x: Math.floor(Math.random() * gridSize), y: Math.floor(Math.random() * gridSize) };
goal = { x: Math.floor(Math.random() * gridSize), y: Math.floor(Math.random() * gridSize) };
maze[start.x][start.y].isWall = false;
maze[goal.x][goal.y].isWall = false;
}
function heuristic(a, b) {
const dx = Math.abs(a.x - b.x);
const dy = Math.abs(a.y - b.y);
return Math.sqrt(dx * dx + dy * dy);
}
function getNeighbors(cell) {
const neighbors = [];
for (let x = cell.x - 1; x <= cell.x + 1; x++) {
for (let y = cell.y - 1; y <= cell.y + 1; y++) {
if (!(x === cell.x && y === cell.y) && x >= 0 && y >= 0 && x < gridSize && y < gridSize && !maze[x][y].isWall) {
neighbors.push({ x, y });
}
}
}
return neighbors;
}
function drawGrid() {
ctx.fillStyle = "#444";
for (let i = 0; i <= gridSize; i++) {
ctx.fillRect(i * cellSize, 0, 1, canvas.height);
ctx.fillRect(0, i * cellSize, canvas.width, 1);
}
restartButton.style.display = "none"; // Hide the button when drawing starts
}
function drawCell(x, y) {
const color = maze[x][y].isWall ? "#CCC" : "#FFF";
ctx.fillStyle = color;
ctx.strokeStyle = "#000";
if (openList.includes({ x, y })) {
ctx.fillStyle = "rgba(255, 240, 168)"; // Highlight open cells
} else if (closedList.includes({ x, y })) {
ctx.fillStyle = "#78D3F9"; // Highlight closed cells
}
ctx.fillRect(x * cellSize + 1, y * cellSize + 1, cellSize - 2, cellSize - 2);
ctx.strokeRect(x * cellSize + 1, y * cellSize + 1, cellSize - 2, cellSize - 2);
}
function drawPath() {
path.forEach((cell) => {
ctx.fillStyle = "#0F0"; // Highlight the path in green
ctx.strokeStyle = "#090";
drawCell(cell.x, cell.y);
});
}
function astar() {
openList.push({ x: start.x, y: start.y });
while (openList.length > 0) {
let currentCell = openList[0];
for (let i = 1; i < openList.length; i++) {
const cell = openList[i];
if (cell.fScore < currentCell.fScore || cell.fScore === currentCell.fScore && cell.hScore < currentCell.hScore) {
currentCell = cell;
}
}
nodesExpanded++;
openList = openList.filter((cell) => cell !== currentCell);
closedList.push(currentCell);
if (currentCell.x === goal.x && currentCell.y === goal.y) {
pathLength = currentCell.gScore;
let cellToDraw = currentCell;
while (cellToDraw.parent) {
drawCell(cellToDraw.x, cellToDraw.y);
const newPath = [];
newPath.push({ x: cellToDraw.x, y: cellToDraw.y });
path = [...new Set([...path, ...newPath])]; // Update the path array
cellToDraw = cellToDraw.parent;
}
setTimeout(() => {
restart(); // Restart after a delay to showcase the full path
}, 100);
}
getNeighbors(currentCell).forEach((neighbor) => {
const gScore = currentCell.gScore + 1;
const hScore = heuristic({ x: neighbor.x, y: neighbor.y }, goal);
if (
!closedList.includes({ x: neighbor.x, y: neighbor.y }) &&
maze[neighbor.x][neighbor.y].isWall === false &&
gScore + hScore < openList.filter((cell) => cell.x === neighbor.x && cell.y === neighbor.y)[0]?.fScore
) {
const newPath = [];
newPath.push({ x: currentCell.x, y: currentCell.y });
maze[neighbor.x][neighbor.y].gScore = gScore;
maze[neighbor.x][neighbor.y].hScore = hScore;
maze[neighbor.x][neighbor.y].fScore = gScore + hScore;
maze[neighbor.x][neighbor.y].parent = currentCell;
openList.push({ x: neighbor.x, y: neighbor.y });
}
});
}
}
function animate() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let i = 0; i < gridSize; i++) {
for (let j = 0; j < gridSize; j++) {
drawCell(i, j);
}
}
if (!path.length) {
astar();
} else {
drawPath();
const text = `Nodes Expanded: ${nodesExpanded}\nPath Length: ${Math.round(pathLength)}`;
ctx.fillStyle = "rgba(0, 0, 0, 0.5)"; // Semi-transparent black background for text
ctx.font = `${cellSize / 4}px Arial`;
ctx.fillText(text, 20, cellSize * gridSize - (cellSize / 8));
}
requestAnimationFrame(animate);
}
animate();
</script>
</body>
</html>| Model | Blind score | Latency | Status |
|---|---|---|---|
| qwen3:8b | — | — | harness |
| deepseek-r1:14b | — | 60.1 s | OK |
| llama3.1:8b | — | 18.3 s | OK |
| qwen3.5:9b | — | 74.2 s | OK |
| qwen3:14b | — | 40.7 s | OK |
| mistral-small:24b | — | 60.7 s | OK |
| gemma4:26b | — | — | harness |
| qwen3-coder:30b | — | 38.6 s | OK |
| deepseek-r1:32b | — | 82.8 s | OK |
| qwq:32b | — | 136.4 s | OK |
| command-r:35b | — | 131.1 s | OK |