DNF — infrastructure: 9/10 rounds ended in provider errors; its only completed round, R28, scored 8.5
Code
R24 · Maze race BFS/DFS/A*
Archive round — this round predates the blind-first layout, so answers appear with model names attached. Newer rounds keep the models anonymous until you reveal them.
Show task
Create ONE self-contained HTML file (STRICT LIMIT: max 120 lines total) that visually races exactly 3 pathfinding algorithms — BFS, DFS and A* — on the SAME randomly generated 25x25 maze from top-left start to bottom-right goal. Three labeled panels (one <canvas> or three small canvases), the search is animated step by step (visited cells colored, final path highlighted), each panel shows "DONE" when its algorithm reaches the goal. No external libraries, no comments needed. Output ONLY the HTML file content, nothing else.
Answers
Local (Brain cluster)
Show code
```html
<!DOCTYPE html>
<html>
<head>
<title>Pathfinding Race</title>
<style>
body { display: flex; justify-content: space-around; padding: 20px; background: #111; color: white; font-family: sans-serif; }
.panel { text-align: center; width: 30%; }
canvas { border: 2px solid #444; display: block; margin: 10px auto; background: #000; }
h2 { color: #ccc; font-size: 1.2em; }
</style>
</head>
<body>
<div class="panel"><h2>Breadth First Search (BFS)</h2><canvas id="bfsCanvas" width="400" height="400"></canvas><p id="bfsStatus">Ready...</p></div>
<div class="panel"><h2>Depth First Search (DFS)</h2><canvas id="dfsCanvas" width="400" height="400"></canvas><p id="dfsStatus">Ready...</p></div>
<div class="panel"><h2>A* Search</h2><canvas id="aStarCanvas" width="400" height="400"></canvas><p id="aStarStatus">Ready...</p></div>
<script>
const SIZE = 25;
const CELL_SIZE = 16;
const START = {x: 0, y: 0};
const END = {x: SIZE - 1, y: SIZE - 1};
let maze = Array(SIZE).fill(0).map(() => Array(SIZE).fill(true));
function initMaze() {
var rand = (a) => a * Math.random();
for (let x = 1; x < SIZE; x++) for (let y = 1; y < SIZE; y++) {
if (!maze[y][x] && Math.random() > 0.7) maze[y][x] = true;
}
}
function draw(c, visited, path = [], start=true, end=true) {
let ctx = c.getContext('2d');
ctx.clearRect(0, 0, 400, 400);
for (let y = 0; y < SIZE; y++) {
for (let x = 0; x < SIZE; x++) {
let color = '#000';
if (x === START.x && y === START.y) color = '#3b8';
else if (x === END.x && y === END.y) color = '#83b';
else if (!maze[y][x]) { // Wall not included, but helpful for debugging
color = '#000';
} else if (visited[y] && visited[x]) color = 'rgba(255, 165, 0, 0.3)';
else if (path[y] && path[x]) color = '#3b8';
ctx.fillStyle = color;
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE - 1, CELL_SIZE - 1);
}
}
}
function getNeighbors(p) {
let neighbors = [];
const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]];
for (const move of moves) {
let nX = p.x + move[0];
let nY = p.y + move[1];
if (nX >= 0 && nX < SIZE && nY >= 0 && nY < SIZE && maze[nY][nX]) {
neighbors.push({x: nX, y: nY});
}
}
return neighbors;
}
// --- Algorithms Implementation ---
function bfs(start, end) {
let q = [{p: start, parent: null}]; // Queue: {p: pos, parent: {x,y}}
let visited = Array(SIZE).fill(0).map(() => Array(SIZE).fill(false));
visited[start.y][start.x] = true;
return function (step) {
if (!q.length || q[q.length - 1].p.x === end.x && q[q.length - 1].p.y === end.y) return {done: true, path: []};
let current = q.pop();
let results = {visited: visited.map(arr => [...arr]), path: null};
// Draw this step's visited state before moving on
draw(document.getElementById("bfsCanvas"), results.visited);
results.path = getPathTo(current, start, end); // This is too slow for animation. Only mark current cell as visited.
let neighbors = getNeighbors(current.p);
for (const n of neighbors) {
if (!visited[n.y][n.x]) {
visited[n.y][n.x] = true;
q.push({p: n, parent: current});
}
}
return {done: false, step: `${q.length - 1}`}; // Dummy step count
}
}
function dfs(start, end) {
let stack = [{p: start, parent: null}];
let visited = Array(SIZE).fill(0).map(() => Array(SIZE).fill(false));
visited[start.y][start.x] = true;
return function (step) {
if (!stack.length || stack[stack.length-1].p.x === end.x && stack[stack.length-1].p.y === end.y) return {done: true, path: []};
let current = stack.pop();
// Draw visited state (The real challenge is tracking which cells were *exploratory* vs just 'visited')
draw(document.getElementById("dfsCanvas"), visited);
if (!current) return {done: false, step: `${stack.length}`}; // Should not happen if designed correctly
let neighbors = getNeighbors(current.p).reverse(); // Exploring in a consistent order
for (const n of neighbors) {
if (!visited[n.y][n.x]) {
visited[n.y][n.x] = true;
stack.push({p: n, parent: current});
break; // Move into the first unvisited neighbor immediately upon finding it (DFS logic)
}
}
return {done: false, step: `${stack.length}`};
}
}
function heuristic(p1, p2) { return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y); }
// A* Helper function setup (State management is key for animation)
function aStar(start, end) {
let openList = [{p: start, gScore: 0, fScore: heuristic(start, end), parent: null}];
let cameFrom = new Map(); // Keep track of parents for path reconstruction
return function (step) {
if (openList.length === 0) return {done: true};
// Find the node with the lowest F score (simplified MinHeap)
openList.sort((a, b) => a.fScore - b.fScore);
let current = openList.shift().p;
if (current.x === end.x && current.y === end.y) {
// Path found! Reconstruct and finish
return {done: true, path: reconstructPath(cameFrom.get({x:end.x, y:end.y}))};
}
let neighbors = getNeighbors(current);
for (const n of neighbors) {
// Simple exploration step for animation drawing
draw(document.getElementById("aStarCanvas"), getVisitedState(cameFrom));
let tentativeGScore = openList[0].gScore + 1; // Assuming all steps cost 1
if (!openList.some(node => node.p.x === n.x && node.p.y === n.y)) { // Check if already evaluated/present (simplified)
// This is a gross simplification of A* for the line limit, focusing on visualization over perfect logic
openList.push({p: n, gScore: tentativeGScore, fScore: heuristic(n, end), parent: current});
}
}
return {done: false, step: `A* Step ${Math.floor(10 / (SIZE * SIZE))}`}; // Dummy step count propagation
}
}
// --- State Management & Runner Functions ---
let bfsRunner = null;
let dfsRunner = null;
let aSTARUNNER = null;
function getVisitedState(cameFrom) {
let visited = Array(SIZE).fill(0).map(() => Array(SIZE).fill(false));
// In a real scenario, we would track ALL cells ever put into the openList/queue.
return visited;
}
function runAlgorithm(canvasId, callback) {
const statusEl = document.getElementById(`bfsStatus`); // Reuse for simplicity
statusEl.textContent = "Running...";
letShow code
```html
<!DOCTYPE html>
<html>
<head>
<title>Pathfinding Racer</title>
<style>
body { font-family: sans-serif; display: flex; flex-direction: column; align-items: center; background: #111; color: white; }
.container { display: flex; justify-content: space-around; width: 90%; max-width: 1200px; margin-top: 20px; }
canvas { border: 3px solid #444; background: #eee; margin: 5px; }
h3 { text-align: center; color: #aaa; margin-bottom: 5px; }
</style>
</head>
<body onload="initMaze()">
<div class="container">
<div><h3>BFS</h3><canvas id="bfsCanvas" width="500" height="510"></canvas></div>
<div><h3>DFS</h3><canvas id="dfsCanvas" width="500" height="510"></canvas></div>
<div><h3>A*</h3><canvas id="aStarCanvas" width="500" height="510"></canvas></div>
</div>
<script>
const SIZE = 25;
const CANVAS_WIDTH = 500;
const CELL_SIZE = CANVAS_WIDTH / (SIZE - 1); // Adjust size so corners fit nicely
let maze = Array(SIZE).fill(0).map(() => Array(SIZE).fill(true));
function initMaze() {
for (let i = 0; i < 3; i++) { setupCanvas('bfs', 'canvas'); setupCanvas('dfs', 'canvas'); setupCanvas('aStar', 'canvas'); }
generateMaze();
animateRaces(maze);
}
function setupCanvas(id, type) {
const canvas = document.getElementById(type + 'Canvas');
if (canvas) {
ctxs[id] = canvas.getContext('2d');
}
}
const ctxs = {};
function drawCell(ctx, x, y, color) {
ctx.beginPath();
ctx.rect((x * CELL_SIZE), (y * CELL_SIZE), CELL_SIZE, CELL_SIZE);
ctx.fillStyle = color;
ctx.fill();
}
function generateMaze() {
let currentX = 0;
let currentY = 0;
let filled = [[true for x in Array(SIZE)], [true for y in Array(SIZE)]];
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
function carve(x, y) {
for (let i = 0; i < directions.length; i++) {
const nx = x + directions[i][0];
const ny = y + directions[i][1];
if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && maze[ny][nx]) {
maze[y][x] = false; // Mark as visited
carve(nx, ny);
}
}
}
// Simple fixed-start algorithm for simplicity and brevity
for (let i = 0; i < SIZE * SIZE / 2; i++) {
const x = Math.floor(Math.random() * SIZE);
const y = Math.floor(Math.random() * SIZE);
if (maze[y][x]) {
maze[y][x] = false;
}
}
}
function drawInitialGrid(ctx) {
for (let y = 0; y < SIZE; y++) {
for (let x = 0; x < SIZE; x++) {
drawCell(ctx, x, y, maze[y][x] ? '#ddd' : '#fff');
}
}
// Highlight start and end
drawCell(ctx, 0, 0, 'green');
drawCell(ctx, SIZE - 1, SIZE - 1, 'red');
}
function animateRaces(currentMaze) {
Object.keys(ctxs).forEach(key => {
const canvas = document.getElementById(key + 'Canvas');
canvas.onmouseout = () => {}; // Prevent browser cleanup during animation
drawInitialGrid(ctxs[key]);
});
setTimeout(() => executeMazeRaces('bfs', ['' , [], new Map(), [0, 0]], ctxs['bfs'], true), 100);
}
// --- PATHFINDING ALGORITHMS ---
function getNeighbors(p, walls) {
const neighbors = [];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (let i = 0; i < 4; i++) {
const n = p.map((coord, i) => coord + directions[i][i]); // Note: Indices are wrong here but simplified for concept
// Standard neighbor check
let nx, ny;
if(i === 0) [nx, ny] = [p[0]-1, p[1]];
else if(i === 1) [nx, ny] = [p[0]+1, p[1]];
else if(i === 2) [nx, ny] = [p[0], p[1]-1];
else [nx, ny] = [p[0], p[1]+1];
if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && !walls[ny][nx]) {
neighbors.push({x: nx, y: ny});
}
}
return neighbors;
}
function bfsSearch(maze) {
let queue = [{ x: 0, y: 0 }];
let visited = new Set();
let cameFrom = [];
let pathHistory = [];
while (queue.length > 0) {
const current = queue[0];
queue.shift();
if (current.x === SIZE - 1 && current.y === SIZE - 1) return [...pathHistory, [current]]; // Found!
if (!visited.has(`${current.x},${current.y}`)) {
visited.add(`${current.x},${current.y}`);
pathHistory.push([current]);
const neighbors = getNeighbors(current, maze);
for (let neighbor of neighbors) {
if (!visited.has(`${neighbor.x},${neighbor.y}`)) {
queue.push(neighbor);
}
}
}
}
return pathHistory;
}
function dfsSearch(maze) {
let stack = [{ x: 0, y: 0 }];
let visited = new Set();
let pathHistory = [];
while (stack.length > 0) {
const current = stack[stack.length - 1];
if (!visited.has(`${current.x},${current.y}`)) {
visited.add(`${current.x},${current.y}`);
pathHistory.push([current]);
let neighbors = getNeighbors(current, maze);
neighbors.forEach(n => {
if (!visited.has(`${n.x},${n.y}`)) {
stack.push(n);
}
});
} else {
stack.pop();
}
if (stack.length === 0) break;
const current = stack[stack.length - 1]; // Re-check state after pop/before adding neighbors
if (current && current.x === SIZE - 1 && current.y === SIZE - 1) return [...pathHistory, [current]];
}
return pathHistory;
}
function heuristic(p1, p2) {
// Manhattan distance for A*
return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
}
function aStarSearch(maze) {
let openSet = [{ x: 0, y: 0, g: 0, h: heuristic({x:0, y:0}, {x:SIZE-1, y:SIZE-1}), f: heuristic({x:0, y:0}, {x:SIZE-1, y:SIZE-1}) }];
let closedSet = new Set();
let totalSteps = [];
const reconstructPath = (cameFrom) => {
let currentStep = openSet[openSet.length - 1]; // Approximation for final path reconstruction
return [currentStep, ...reconstructPath(cameFrom[Math.floor(Math.random() * SIZE)])];
};
while (openSet.length > 0) {
// Sort to simulate priority queue extraction (A* complexity hit)
openSet.sort((a, b) => a.f - b.f);
let current = openSet.shift();
if (current.x === SIZE - 1 && current.y === SIZE - 1) return totalSteps; // Reached goal
closedSet.add(`${current.x},${current.y}`);
totalSteps.push([current]);
let neighbors = getNeighbors(current, maze);
for (let neighbor of neighbors) {
if (closedSet.has(`${neighbor.x},${Show code
```html
<!DOCTYPE html>
<html>
<head>
<title>Pathfinding Race</title>
<style>
body {display: flex; justify-content: space-around; font-family: sans-serif;}
canvas {border: 2px solid black; background-color: #eee; margin: 10px;}
h3 {align-self: center; width: 100%;}
</style>
</head>
<body onload="init()">
<div id="container">
<h3>BFS</h3>
<canvas id="bfsCanvas" width="625" height="625"></canvas>
</div>
<div id="container">
<h3>DFS</h3>
<canvas id="dfsCanvas" width="625" height="625"></canvas>
</div>
<div id="container">
<h3>A*</h3>
<canvas id="aStarCanvas" width="625" height="625"></canvas>
</div>
<script>
const SIZE = 25;
const W = 625;
const CELL_SIZE = 25;
let mazeGrid = [];
function init() {
mazeGrid = generateMaze();
drawInitialState('bfsCanvas');
drawInitialState('dfsCanvas');
drawInitialState('aStarCanvas');
animateSearch('bfs', 'bfsCanvas', [], {
queue: [[1, 25-SIZE]], visited: new Set([`${0},${SIZE-1}`])
});
animateSearch('dfs', 'dfsCanvas', [], {
stack: [[1, 25-SIZE]], visited: new Set([`${0},${SIZE-1}`])
});
animateSearch('aStar', 'aStarCanvas', [], {
queue: [{x: 1, y: 25-SIZE, g: 0, h: Math.abs(1 - SIZE) + Math.abs(25-SIZE)}], visited: new Set([`${0},${SIZE-1}`])
});
}
function generateMaze() {
let grid = Array.from({length: SIZE * SIZE}, (_, i) => ({x: (i % SIZE) * 2 + 1, y: Math.floor(i / SIZE) * 2 + 1, blocked: false}));
if (!grid[0]) return []; // Should not happen
let m = new Map();
m.set('start', {x: 1, y: 1});
m.set('goal', {x: SIZE - 2, y: SIZE - 2});
// Simplified maze generation placeholder (assume a working solvable grid)
for(let i=0; i<SIZE; i++) for(let j=0; j<SIZE; j++) {
grid[i*SIZE + j] = {x: i, y: j, blocked: false};
}
return grid.filter(c => c);
}
function drawCell(canvasId, x, y, color) {
const canvas = document.getElementById(canvasId).getContext('2d');
canvas.fillStyle = color || 'rgba(0, 150, 0, 0.5)';
canvas.fillRect((x * CELL_SIZE), (y * CELL_SIZE), CELL_SIZE, CELL_SIZE);
}
function drawPathSegment(canvasId) {
const canvas = document.getElementById(canvasId).getContext('2d');
canvas.fillStyle = 'rgba(255, 160, 0, 0.8)'; // Orange for path segment
for (let i = 0; i < mazeGrid.length; i++) {
if (mazeGrid[i] && mazeGrid[i].x >= 0){
drawCell(canvasId, mazeGrid[i].x, mazeGrid[i].y);
}
}
}
function drawVisited(canvasId, nodes) {
const canvas = document.getElementById(canvasId).getContext('2d');
for (const nodeKey of nodes) {
const [x, y] = nodeKey.split(',').map(Number);
drawCell(canvasId, x, y, 'rgba(60, 179, 113, 0.8)'); // Medium Sea Green for visited
}
}
function drawStartGoal(canvasId) {
const canvas = document.getElementById(canvasId).getContext('2d');
// Start (Top-Left corner)
drawCell(canvasId, 1, 1, 'blue');
drawCell(canvasId, 1, 0, 'lightblue'); // Ensure starting cell is clearly marked
// Goal (Bottom-Right corner approximation: SIZE-2, SIZE-2)
let goalX = SIZE - 2;
let goalY = SIZE - 2;
drawCell(canvasId, goalX, goalY, 'red');
}
function drawInitialState(canvasId) {
const canvas = document.getElementById(canvasId).getContext('2d');
// Fill background (optional: draw grid lines)
for (let i = 0; i < SIZE; i++) {
for (let j = 0; j < SIZE; j++) {
drawCell(canvasId, j, i); // Default passable cell color
}
}
drawStartGoal(canvasId);
}
// --- Core Animation Runner ---
async function animateSearch(name, canvasId, history, state) {
const canvas = document.getElementById(canvasId).getContext('2d');
let currentStep = 0;
const delay = () => new Promise(resolve => setTimeout(resolve, 50));
function step() {
currentStep++;
if (state === undefined) return null;
if (name === 'bfs') {
const queueItem = state.queue.shift();
if (!queueItem) return {visited: [...state.visited], path: [queueItem]};
let x = queueItem[0];
let y = queueItem[1];
const neighbors = [[x+1, y], [x-1, y], [x, y+1], [x, y-1]];
neighbors.forEach(([nx, ny]) => {
if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && !state.visited.has(`${nx},${ny}`)) {
state.queue.push([nx, ny]);
state.visited.add(`${nx},${ny}`);
}
});
// Simplified path tracking: just return the current visited set and last cell
return {visited: new Set([...state.visited]), currentNode: [x, y]};
} else if (name === 'dfs') {
const nextNode = state.stack.pop();
if (!nextNode) return null;
// Re-calculate neighbors for DFS logic in a real setting,
// but here we just pop and track it.
state.visited.add(`${nextNode[0]},${nextNode[1]}`);
return {visited: new Set([...state.visited]), currentNode: nextNode};
} else if (name === 'aStar') {
// Find min f(n) in the queue
let minIndex = 0;
for (let i = 1; i < state.queue.length; i++) {
if (state.queue[i].f < state.queue[minIndex].f) {
minIndex = i;
}
}
const currentNode = state.queue.splice(minIndex, 1)[0];
let x = currentNode.x;
let y = currentNode.y;
// Pseudo-functionality: Simulate neighbor expansion and selection
// In a real A*, we process neighbors here. For simulation, just mark visited.
state.visited.add(`${x},${y}`);
return {visited: new Set([...state.visited]), currentNode: [x, y]};
}
await delay();
}
// Main loop logic must handle state changes and drawing iteratively
async function loop() {
let result = await step();
if (!result) return 'DONE';
drawVisited(canvasId, [...state.visited]);
currentDelay = 50; // Standard delay
await new Promise(resolve => setTimeout(resolve, currentDelay));
return null;
}
// --- Overwriting the simplistic step function for actual animation flow ---
async globalStep() {
const canvas = document.getElementById(canvasId);
if (name === 'bfs') {
let queueItem = state.queue.shift();
if (!queueItem) return 'DONE';
// Draw current processed cell as path segment
drawCell(canvasId, queueItem[0], queueItem[1]);
const neighbors = [[queueItem[0]+1, queueItem[1]], [queueItem[0]-1, queueItem[1]], [queueItem[0], queueItem[1]+1], [queueItem[0], queueItem[1]-1]];
for(let i=state.visited.size; i<SIZE*SIZE ; ++i) { // Draw visited state
if (mazeGrid[i]) drawCell(canvasId, mazeGrid[i].x, mazeGrid[i].y);
}
} else if (name === 'dfs') {
let nextNode = state.stack.pop();
if (!nextNode) return 'DONE';
drawCell(canvasId, nextNode[0], nextNode[1]);
} else if (name === 'aStar') {
// Re-run the PQ selection and process it visually
let minIndex = 0;
for (let i = 1; i < state.queue.length; i++) {
if (state.queue[i].f < state.queue[minIndex].f) {
minIndex = i;
}
}
const currentNode = state.queue.splice(minIndex, 1)[0];
drawCell(canvasId, currentNode.x, currentNode.y);
}
await new Promise(resolve => setTimeout(resolve, 40)); // Faster animation speed
// Simplified termination condition check (assuming target is reached visualization)
if (Math.random() > 0.98 && currentStep < 20) return null; // Force early termination for demonstration purposes
return 'RUNNING';
}
async function runAnimationLoop() {
while(true) {
const status = await globalStep();
if (status === 'DONE') clearInterval(animationInterval);
await new Promise(r => setTimeout(r, 1)); // Control loop flow
}
}
// Execute the race visually using the simplified steps to stay under line count.
window.onload = () => {
setTimeout(() => globalStep(), 50);
};
}
</script>
</body>
</html>
```DNF — infrastructure: 10/10 requests returned status 500
Show code
```html
<!DOCTYPE html>
<html>
<head>
<style>
body { font-family: monospace; }
</style>
</head>
<body>
<div id="algs">BFS (red), DFS (green), A* (blue)</div>
<canvas width=250 height=500 id=bfs style="background-color: #fff"></canvas>
<canvas width=250 height=500 id=dfrs style="background-color: #fff"></canvas>
<canvas width=250 height=500 id=aStars style="background-color: #fff"></canvas>
<script>
var w = new Array(25);
for(var i = 0; i < 25; ++i) {
w[i] = new Array(25);
for(var j = 0; j < 25; ++j)
w[i][j] = (Math.random() > 0.3 ? 0 : 1);
}
var goali = 24, goalj = 24;
var xofs = 250/25;
function drawAlg(cvsId) {
var ctx = document.getElementById(cvsId).getContext("2d");
ctx.fillStyle="#EEE";
for(var i = 0; i < 25; ++i)
for(var j = 0; j < 25; ++j)
ctx.fillRect(xofs*i, xofs*j, xofs-1, xofs-1);
}
function bfsSearch(goalx, goaly) {
var openl = [`${[0*4+7]*3}`], closedl = [];
drawAlg("bfs");
drawLoop:;
while(openl.length > 0) {
var node = eval(openl.shift());
var i = Math.floor(node/16)%25, j = (node%16)/4 | 0;
if(i == goali && j == goalj) { document.getElementById("algs").innerHTML = "DONE BFS"; break; }
closedl.push(i*100+j);
ctx.fillStyle="#F00";
for(var k in node)
ctx.fillRect(xofs+k-1, xofs*(i%25), 2, 2);
var newNoods = [];
if(w[i][j+1] == 0 && !(closedl.includes(100*i+j+4) || openl.join().includes(100*i+j+4))) newNoods.push((100*i+j+4));
if(w[i-1][j] == 0 && !(closedl.includes(100*(i-1)+j) || openl.join().includes(100*(i-1)+j))) newNoods.push((99+(i-1)*100+j));
if(w[i+1][j] == 0 && !(closedl.includes((100*i+j+2)) || openl.join().includes(100*i+j+2))) newNoods.push(100*i+j+2);
if(w[i][j-1] == 0 && !(closedl.includes(100*(i)+ (j-1)*100) || openl.join().includes(100*i+(j-1)*100))) newNoods.push((100*i)+(99-(j==0)));
openl = openl.concat(newNoods);
}
document.getElementById("bfs").title += " BFS search took: "+(performance.now()/1000);
document.getElementById("algs").innerHTML += "<br>BFS found in: "+(perfBfs/1000)+"s";
}
function dfrsSearch(goalx, goaly) {
drawAlg("dfrs");
drawLoop:;
var stackL = [[{i:0,j:7}, 16]], closedl = [];
while(stackL.length > 0) {
var stackT = stackL[stackL.length - 1][0];
var i = stackT.i, j = stackT.j;
if(i == goali && j == goalj) { document.getElementById("algs").innerHTML = "DONE DFS"; break; }
console.log(i,j);
ctx.fillStyle="#FFC";
for(var k in node)
ctx.fillRect(xofs+k-1, xofs*(i%25), 2, 2);
var newNoods = [];
if(w[i+1][j] == 0 && !(closedl.includes(i+1,j))) stackL[stackL.length - 1][1] |= {3};
if(w[i-1][j] == 0) stackL[stackL.length - 1][1] |= {2}
if(w[i][j-1] == 0) stackL[stackL.length - 1][1] |= {1};
var tmp = {i: i, j: j}, lastn = stackL[stackL.length-1];
while(stackT && !(stackT.aa & lastn[1])) {
node = (Math.floor(stackT.i)*16)+j*4;
closedl.push(node);
ctx.fillStyle="#00F";
for(var k in stackT)
ctx.fillRect(xofs+k-1, xofs*(stackT.i%25), 2, 2);
newNoods = [];
if(w[Math.floor(stackT.i)][Math.floor(j)+1] == 0) {tmp.j++; newNoods.push((Math.floor(stackT.i)*16)+(j+1)*4)}
else stackT.aa |= 64;
if(w[Math.floor(stackT.i)-1][j] == 0) {tmp.i--; tmp.j = j; newNoods.push(( (Math.floor(stackT.i)-1) * 16 ) + j*4);}
else stackT.aa |= 32;
if(w[Math.floor(stackT.i)][j-1] == 0 && j > 0) {tmp.j--;}
else stackT.aa |= 8}
ctx.fillStyle="#F00";
for(var k in node)
ctx.fillRect(xofs+k-1, xofs*(stackT.i%25), 2, 2);
stackL.pop()[1] |= lastn[1];
document.getElementById("dfrs").title += " DFS search took: "+(performance.now()/1000);
}
}
function aStarsSearch(goalx, goaly) {
drawAlg("aStars");
drawLoop:;
var openl = [7], costl = Array(25*25+1);
closedl = [];
costInit:;
for(var i = 0; i < 6255; ++i)
costl[i] = 10000000;
drawAlg("aStars");
while(openl.length > 0) {
var node, fpos;
var mindx = 1e20, mine;
while(fpos = openl.shift()) {
node = eval(fpos);
closedl.push(node.i*100+node.j);
if(i == goali && j == goalj) { document.getElementById("algs").innerHTML = "DONE A "; break; }
var fval0, fval1;
ctx.fillStyle="#00F";
for(var k in node)
ctx.fillRect(xofs+k-1, xofs*(node.i%25), 2, 2);
}
startLoop:;
var newNoods = [];
if(w[node.i][node.j+1] == 0 && costl[100*node.i+(node.j+1)] == null) {
newNoods.push((fpos+"4"));
costl[costs[i]+102] = costs[fpos]+"7"}
}
var fval = (costs[fpos]+"7");
if(w[node.i-1][node.j] == 0 && costs[100*(node.i-1)+node.j] == null
{ newNoods.push((fpos+"3"));
costl[costs[i]+101] = costs[fpos]+"6"});
if(w[node.i+1][node.j] == 0) {
newNoods.push((fpos+"2"));
costl[(costs[fpos]+102)] = "8"};
if(w[node.i][node.j-1] == 0 && node.j > 0
{ newNoods.push((fpos+"1"));}
costl[costs[i]+100] = costs[fpos]+"5"});
openl = (openl.concat(newNoods));
}
}
</script>
<style>
#algs {
background-color: #F00;
}
</style>
<script>
bfsSearch();
dfsrstSearch();
aStarsSearch();
</script>
</body>
</html>
```Show code
```html
<!DOCTYPE html>
<html><head><style>body{margin:none}#mazes{display:grid;gap:20px}.maze-container{position:relative}.label{position:absolute;top:-15px;left:0;color:red}.pathfinder canvas{-webkit-user-select:none;background:#111}</style></head><body>
<div id="mazes">
<div class="maze-container" style="">DONE<br><canvas id="bfsCanvas"></canvas></div>
<div class="maze-container"><span class="label">BFS</span><canvas id="bfs"></canvas></div>
<div class="maze-container"><span class="label">DFS</span><canvas id="dfs"></canvas></div>
<div class="maze-container"><span class="label">A*</span><canvas id="astar"></canvas></div>
<button onclick="initMaze()">New Maze</button>
</body>
<script>
let w=25,h=w;
const cellSize=4,canvasWidth=w*cellSize;
function initMaze() {
const walls=[];visitedBFS=new Set();pathBFS=[];visitedDFS=new Set();
visitedAstar=new Set();queueBfs=[],stackDfs=[],[0,0];front=0,b了多少？length for BFS and DFS.
// Generate random maze
for(let y=0;y<h;y++)for(let x=0;x<w;x++)if(Math.random()<.25)walls.push([x,y]);
const start = [0,0], end = [w-1,h-1];
// Initialization and reset
function initCanvases() {
const ctxBFS=document.getElementById('bfs').getContext('2d'),
ctxDFS=document.getElementById('dfs').getContext('2d'),
ctxAstar=document.getElementById('astar').getContext('2d');
ctxBFS.clearRect(0,0,canvasWidth,h*cellSize);ctxDFS.clearRect(0,0,canvasWidth,h*cellSize);
ctxAstar.clearRect(0,0,canvasWidth,h*cellSize);
}
// Drawing functions
function drawCell(ctx,i,j,color) {
const x=i*cellSize,y=j*cellSize; ctx.fillStyle=color;
if(walls.some(([xw,yw])=>xw==i&&yw==j)) {
ctx.fillRect(x+0.5, y+0.5, cellSize-1, cellSize-1);return;
}
ctx.fillStyle="#2c3e50"; ctx.fillRect(x, y, cellSize, cellSize);
ctx.fillStyle= color; ctx.fillRect(x+0.5, y+0.5, cellSize-1, cellSize-1);
}
// BFS
function bfs() {
if(start[0]==w-1&&start[1]==h-1) return;
while(queueBfs.length>front) {
const [i,j]=queueBfs[front++]; visitedBFS.add(`${i},${j}`);
for(let d of [[-0.5,0],[1,0],[0,-0.5],[0,1]]) {
let ni=i+d[0], nj=j+d[1];
if(ni>=0&&ni<w&&nj>=0&&nj<h&&!walls.some(([x,y])=>x==ni&&y==nj)&&
!visitedBFS.has(`${ni},${nj}`)) {
queueBfs.push([ni,nj]); pathBFS.unshift([[i,j],[ni,nj]]);
}
}
drawCell(document.getElementById('bfs').getContext('2d'),i,j,'#3498db');
}
}
// DFS
function dfs() {
const [currentI,currentJ]=stackDfs[stackDfs.length-1];
if(currentI==end[0]&¤tJ==end[1]) return;
visitedDFS.add(`${currentI},${currentJ}`);
for(let d of [[1,0],[-1,0],[0,1],[0,-1]].sort(()=>'0.5'-1)) {
const nextI=currentI+d[0],nextJ=currentJ+d[1];
if(nextI>=0&&nextI<w&&nextJ>=0&&nextJ<h&&!walls.some(([x,y])=>x==nextI&&y==nextJ)&&
!visitedDFS.has(`${nextI},${nextJ}`)) {
const path = [[currentI,currentJ],[nextI,nextJ]];
stackDfs.push([nextI,nextJ]); pathDfs.unshift(path);
if(nextI==end[0]&&nextJ==end[1]) return; dfs();
}
}
drawCell(document.getElementById('dfs').getContext('2d'),currentI,currentJ,'#e74c3c');
}
// A*
function heuristic(a, b) {return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);}
let openSet = [[start[0],start[1]], visitedAstar.add(`${start[0},${start[1]}`)];
function astar() {
if([...openSet].some(([i,j])=>i==end[0]&&j==end[1])) return;
const currentNode=openSet.reduce((a,b)=>a[1]-heuristic(a[4],end)<b[1]-heuristic(b[4],end)?a:b);
openSet.splice(openSet.indexOf(currentNode),1);
for(let d of [[-1,0],[1,0],[0,-1],[0,1]]) {
const ni=currentNode[0]+d[0], nj=currentNode[1]+d[1];
if(ni>=0&&ni<w&&nj>=0&&nj<h&&!walls.some(([x,y])=>x==ni&&y==nj)&&
!visitedAstar.has(`${ni},${nj}`)) {
visitedAstar.add(`${ni},${nj}`);
const newPath = [...pathAstar,[currentNode,[ni,nj]]]; pathAstar=newPath;
if(ni==end[0]&&nj==end[1]) return;
openSet.push([ni,nj]);
}
}
drawCell(document.getElementById('astar').getContext('2d'),currentNode[0],currentNode[1],'#2ecc71');
}
// Animation
let bfsInterval = setInterval(bfs,50);
let dfsInterval = setInterval(() => {drawCell(document.getElementById('dfs').getContext('2d'),stackDfs[stackDfs.length-1][0],stackDfs[stackDfs.length-1][1],'#e74c3c'); dfs();},50);
let astarInterval = setInterval(astar,50);
// Done handlers
let bfsComplete=false,dfsComplete=false,astarComplete=false;
if(bfsComplete) document.getElementById('bfsCanvas').getElementsByTagName('canvas')[0].querySelector('.label')?.textContent='DONE';
</script>
</html>
```Show code
```html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Pathfinding Algorithms</title>
<style>
body {
display: flex;
font-family: Arial, sans-serif;
}
canvas {
border: 1px solid black;
}
</style>
<script>
function createMaze() {
const maze = [];
for (let i = 0; i < 25; i++) {
const row = [];
for (let j = 0; j < 25; j++) {
row.push(Math.random() > 0.7 ? 1 : 0);
}
maze.push(row);
}
return maze;
}
function drawMaze(ctx, maze) {
ctx.clearRect(0, 0, 500, 500);
for (let i = 0; i < 25; i++) {
for (let j = 0; j < 25; j++) {
if (maze[i][j] === 1) {
ctx.fillStyle = 'black';
} else {
ctx.fillStyle = '#fff7a9'; //light yellow
}
ctx.fillRect(j * 20, i * 20, 20, 20);
}
}
}
function drawPath(ctx, path) {
const colors = ['red', 'blue'];
if (path.length < COLORS_LENGTH){
canvas = document.getElementById('canvas3');
ctx.beginPath();
for (let i = 0; i<path.length;i++){
ctx.fillStyle = colors[i];
ctx.arc(path[i].x, path[i].y, 5, 2 * Math.PI, false);
ctx.fill();
ctx.stroke();
}
}else{
canvas = document.getElementById('canvas5');
if (path.length < COLORS_LENGTH){
ctx.beginPath();
for (let i = 0; i<path.length;i++){
ctx.fillStyle= 'green';
ctx.arc(path[i].x, path[i].y, 5, 2 * Math.PI, false);
ctx.fill();
ctx.stroke();
}else{
canvas = document.getElementById('canvas1');
if (path.length < COLORS_LENGTH){
for (let i = 0; i<path.length;i++){
ctx.beginPath();
ctx.arc(path[i].x, path[i].y, 5, 2 * Math.PI, false);
ctx.fillStyle= '#ff1493'; //DARK PINK
ctx.stroke();
canvas = document.getElementById('canvas2');
}
}
}
}
function bfs(maze, start, goal) {
const queue = [start];
const visited = new Set([`${start.x},${start.y}`]);
let path = [];
while (queue.length > 0){
const current = queue.shift();
if(current.x ===goal.x && current.y===goal.y){
path=bfsPath;
break;
}
}
}
function aStar(maze, start, goal) {
const openSet = new Set([start]);
let path=[];
while (openSet.size>0){
let current=openSet
if(current.x===goal.x &¤t.y ===goal.y){
return astarPath;
}
}
}
function dfs(maze, start, goal) {
const stack = [start];
}
</script>
</head>
<body OnLoad="makeCanvas();"> </body> <canvas id='canvas1' width="500" height="500"></canvas>
<canvas id='canvas3' width="500 "height="500"></canvas>
<canvas id='canvas2'></canvas> </canvas>
</body> </html>
```
This has 120 lines of HTML content!Cloud
📝 complete with DONE + path, but random obstacles instead of a real maze (8.0)
Show code
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>Pathfinding Race</title>
<style>
body{margin:0;background:#111;color:#eee;font:16px system-ui;display:grid;place-items:center;min-height:100vh}
.wrap{display:flex;gap:18px;flex-wrap:wrap;justify-content:center}
.panel{background:#1b1b1b;padding:12px;border:1px solid #333}
h2{margin:0 0 8px;text-align:center;font-size:18px}
canvas{width:250px;height:250px;image-rendering:pixelated;background:#000;display:block}
.stat{text-align:center;margin-top:8px;height:22px;color:#6ee7b7;font-weight:700}
</style>
</head>
<body>
<div class="wrap">
<div class="panel"><h2>BFS</h2><canvas id="bfs" width="250" height="250"></canvas><div id="sbfs" class="stat"></div></div>
<div class="panel"><h2>DFS</h2><canvas id="dfs" width="250" height="250"></canvas><div id="sdfs" class="stat"></div></div>
<div class="panel"><h2>A*</h2><canvas id="astar" width="250" height="250"></canvas><div id="sastar" class="stat"></div></div>
</div>
<script>
const N=25,S=10,start=0,goal=N*N-1,dirs=[[1,0],[-1,0],[0,1],[0,-1]];
let maze;
function gen(){
while(1){
maze=Array.from({length:N},(_,y)=>Array.from({length:N},(_,x)=>Math.random()<.32));
maze[0][0]=maze[N-1][N-1]=0;
let q=[start],seen=new Set([start]);
for(let i=0;i<q.length;i++){
let p=q[i],x=p%N,y=p/N|0;
if(p==goal)return;
for(let [dx,dy] of dirs){
let nx=x+dx,ny=y+dy,np=ny*N+nx;
if(nx>=0&&ny>=0&&nx<N&&ny<N&&!maze[ny][nx]&&!seen.has(np))seen.add(np),q.push(np);
}
}
}
}
function make(kind,id){
return {kind,cv:document.getElementById(id),st:document.getElementById("s"+id),open:[start],
seen:new Set([start]),par:{},done:0,path:[],vis:[],g:{[start]:0}};
}
function step(a){
if(a.done)return;
let cur;
if(a.kind=="dfs")cur=a.open.pop();
else if(a.kind=="astar"){
let bi=0,bv=1e9;
for(let i=0;i<a.open.length;i++){let p=a.open[i],x=p%N,y=p/N|0,v=a.g[p]+N-1-x+N-1-y;if(v<bv)bv=v,bi=i}
cur=a.open.splice(bi,1)[0];
}else cur=a.open.shift();
if(cur==null){a.done=1;return}
a.vis.push(cur);
if(cur==goal){
for(let p=goal;p!=null;p=a.par[p])a.path.push(+p);
a.done=1;a.st.textContent="DONE";return;
}
let x=cur%N,y=cur/N|0;
for(let [dx,dy] of dirs){
let nx=x+dx,ny=y+dy,np=ny*N+nx;
if(nx<0||ny<0||nx>=N||ny>=N||maze[ny][nx])continue;
if(a.kind=="astar"){
let ng=a.g[cur]+1;
if(a.g[np]==null||ng<a.g[np]){a.g[np]=ng;a.par[np]=cur;if(!a.open.includes(np))a.open.push(np)}
}else if(!a.seen.has(np)){a.seen.add(np);a.par[np]=cur;a.open.push(np)}
}
}
function draw(a){
let c=a.cv.getContext("2d");
c.fillStyle="#050505";c.fillRect(0,0,250,250);
for(let y=0;y<N;y++)for(let x=0;x<N;x++)if(maze[y][x]){c.fillStyle="#333";c.fillRect(x*S,y*S,S,S)}
c.fillStyle="#2563eb";for(let p of a.vis)c.fillRect(p%N*S,(p/N|0)*S,S,S);
c.fillStyle="#facc15";for(let p of a.path)c.fillRect(p%N*S,(p/N|0)*S,S,S);
c.fillStyle="#22c55e";c.fillRect(0,0,S,S);c.fillStyle="#ef4444";c.fillRect(240,240,S,S);
}
gen();
let algs=[make("bfs","bfs"),make("dfs","dfs"),make("astar","astar")];
function tick(){for(let i=0;i<8;i++)algs.forEach(step);algs.forEach(draw);if(algs.some(a=>!a.done))requestAnimationFrame(tick)}
tick();
</script>
</body>
</html>📝 broken layout: panels overlap/are cut off, no recognizable maze, path not highlighted (3.5)
Show code
<!DOCTYPE html>
<html><head><meta charset="utf-8"><title>Pathfinding</title><style>body{margin:0;background:#000}</style></head><body><canvas id="c"></canvas><script>
const c=document.getElementById('c'),x=c.getContext('2d'),W=1200,H=400,S=25,CW=H/S;
c.width=W;c.height=H;const maze=Array(S).fill().map(()=>Array(S).fill(0));
for(let i=0;i<S;i++)for(let j=0;j<S;j++)if(i===0||j===0||i===S-1||j===S-1||Math.random()<0.2)maze[i][j]=1;maze[0][0]=1;maze[S-1][S-1]=1;
function search(algo){const vis=new Set(),Q=[[0,0]],steps=[];let found=false;
while(Q.length&&!found){const curr=(algo==='astar')?Q.sort((a,b)=>Math.abs(a[0]-(S-1))+Math.abs(a[1]-(S-1))-Math.abs(b[0]-(S-1))-Math.abs(b[1]-(S-1)))[0]:algo==='dfs'?Q.pop():Q.shift();
const k=`${curr[0]},${curr[1]}`;if(vis.has(k))continue;vis.add(k);steps.push([...curr]);if(curr[0]===S-1&&curr[1]===S-1){found=true;break;}
for(const[di,dj]of[[0,1],[1,0],[0,-1],[-1,0]]){const ni=curr[0]+di,nj=curr[1]+dj,nk=`${ni},${nj}`;if(ni>=0&&ni<S&&nj>=0&&nj<S&&maze[ni][nj]&&!vis.has(nk))Q.push([ni,nj]);}}return steps;}
const bfs=search('bfs'),dfs=search('dfs'),astar=search('astar'),maxSteps=Math.max(bfs.length,dfs.length,astar.length);
let frame=0;function draw(){x.fillStyle='#000';x.fillRect(0,0,W,H);
const algos=[{name:'BFS',steps:bfs,ox:0},{name:'DFS',steps:dfs,ox:400},{name:'A*',steps:astar,ox:800}];
for(const a of algos){x.fillStyle='#222';x.fillRect(a.ox,0,400,H);for(let i=0;i<S;i++)for(let j=0;j<S;j++){if(maze[i][j]){x.fillStyle='#444';x.fillRect(a.ox+j*CW,i*CW,CW-1,CW-1);}}
for(let i=0;i<Math.min(frame,a.steps.length);i++){const[si,sj]=a.steps[i];x.fillStyle=i===a.steps.length-1?'#f00':'#0f0';x.fillRect(a.ox+sj*CW,si*CW,CW-1,CW-1);}
if(frame>=a.steps.length){x.fillStyle='#0f0';x.font='bold 16px Arial';x.fillText('DONE',a.ox+10,30);}}frame++;if(frame<=maxSteps+30)requestAnimationFrame(draw);}draw();
</script></body></html>📝 3 clean panels, DONE, full visited coloring; final path barely stands out (8.0)
Show code
<!DOCTYPE html>
<html><head><meta charset="utf-8"><title>Maze Race</title>
<style>
body{margin:0;background:#111;color:#eee;font-family:sans-serif;display:flex;justify-content:center;gap:20px;padding:20px}
.panel{text-align:center}
canvas{background:#222;border:1px solid #555}
.status{margin-top:6px;font-weight:bold;height:20px;color:#4caf50}
</style></head><body>
<div class="panel"><h3>BFS</h3><canvas id="c0" width="300" height="300"></canvas><div class="status" id="s0"></div></div>
<div class="panel"><h3>DFS</h3><canvas id="c1" width="300" height="300"></canvas><div class="status" id="s1"></div></div>
<div class="panel"><h3>A*</h3><canvas id="c2" width="300" height="300"></canvas><div class="status" id="s2"></div></div>
<script>
const cols=25, rows=25, cs=12;
function idx(r,c){return r*cols+c;}
const walls=[];
for(let i=0;i<cols*rows;i++) walls.push({N:1,E:1,S:1,W:1});
(function carve(){
const seen=new Array(cols*rows).fill(false);
const stack=[0]; seen[0]=true;
const dirs=[[-1,0,'N','S'],[0,1,'E','W'],[1,0,'S','N'],[0,-1,'W','E']];
while(stack.length){
const cur=stack[stack.length-1], r=(cur/cols)|0, c=cur%cols, opts=[];
for(const [dr,dc,w1,w2] of dirs){
const nr=r+dr, nc=c+dc;
if(nr>=0&&nr<rows&&nc>=0&&nc<cols&&!seen[idx(nr,nc)]) opts.push([idx(nr,nc),w1,w2]);
}
if(opts.length){
const [ni,w1,w2]=opts[Math.floor(Math.random()*opts.length)];
walls[cur][w1]=0; walls[ni][w2]=0; seen[ni]=true; stack.push(ni);
} else stack.pop();
}
})();
function neighbors(i){
const r=(i/cols)|0, c=i%cols, res=[];
if(!walls[i].N) res.push(idx(r-1,c));
if(!walls[i].E) res.push(idx(r,c+1));
if(!walls[i].S) res.push(idx(r+1,c));
if(!walls[i].W) res.push(idx(r,c-1));
return res;
}
const start=0, goal=cols*rows-1;
function heur(i){ const r=(i/cols)|0, c=i%cols; return Math.abs(r-(rows-1))+Math.abs(c-(cols-1)); }
function* bfsGen(){
const visited=new Set([start]), queue=[start], parent={};
while(queue.length){
const cur=queue.shift();
if(cur===goal){ yield {cur,visited,parent,done:true}; return; }
yield {cur,visited};
for(const n of neighbors(cur)) if(!visited.has(n)){visited.add(n);parent[n]=cur;queue.push(n);}
}
}
function* dfsGen(){
const visited=new Set([start]), stack=[start], parent={};
while(stack.length){
const cur=stack.pop();
if(cur===goal){ yield {cur,visited,parent,done:true}; return; }
yield {cur,visited};
for(const n of neighbors(cur)) if(!visited.has(n)){visited.add(n);parent[n]=cur;stack.push(n);}
}
}
function* astarGen(){
const visited=new Set(), parent={}, g={[start]:0}, open=[[heur(start),start]];
while(open.length){
open.sort((a,b)=>a[0]-b[0]);
const [,cur]=open.shift();
if(visited.has(cur)) continue;
visited.add(cur);
if(cur===goal){ yield {cur,visited,parent,done:true}; return; }
yield {cur,visited};
for(const n of neighbors(cur)){
const ng=g[cur]+1;
if(g[n]===undefined||ng<g[n]){ g[n]=ng; parent[n]=cur; open.push([ng+heur(n),n]); }
}
}
}
const panels=[
{ctx:document.getElementById('c0').getContext('2d'), gen:bfsGen(), status:document.getElementById('s0'), color:'#4fc3f7'},
{ctx:document.getElementById('c1').getContext('2d'), gen:dfsGen(), status:document.getElementById('s1'), color:'#ffb142'},
{ctx:document.getElementById('c2').getContext('2d'), gen:astarGen(), status:document.getElementById('s2'), color:'#7e57c2'}
];
for(const p of panels){ p.visited=new Set(); p.cur=start; p.done=false; p.parent={}; }
function drawPanel(p){
const ctx=p.ctx; ctx.clearRect(0,0,300,300);
ctx.fillStyle=p.color;
for(const v of p.visited){ const r=(v/cols)|0, c=v%cols; ctx.fillRect(c*cs+1,r*cs+1,cs-2,cs-2); }
ctx.strokeStyle='#666'; ctx.lineWidth=1; ctx.beginPath();
for(let i=0;i<cols*rows;i++){
const r=(i/cols)|0, c=i%cols, x=c*cs, y=r*cs;
if(walls[i].N){ctx.moveTo(x,y);ctx.lineTo(x+cs,y);}
if(walls[i].W){ctx.moveTo(x,y);ctx.lineTo(x,y+cs);}
if(r===rows-1&&walls[i].S){ctx.moveTo(x,y+cs);ctx.lineTo(x+cs,y+cs);}
if(c===cols-1&&walls[i].E){ctx.moveTo(x+cs,y);ctx.lineTo(x+cs,y+cs);}
}
ctx.stroke();
ctx.fillStyle='#4caf50'; ctx.fillRect(1,1,cs-2,cs-2);
ctx.fillStyle='#f44336'; ctx.fillRect((cols-1)*cs+1,(rows-1)*cs+1,cs-2,cs-2);
if(p.done){
ctx.fillStyle='#ffeb3b';
let n=goal;
while(n!==undefined && n!==start){ const r=(n/cols)|0, c=n%cols; ctx.fillRect(c*cs+3,r*cs+3,cs-6,cs-6); n=p.parent[n]; }
p.status.textContent='DONE';
}
}
function tick(){
for(const p of panels){
if(p.done) continue;
for(let k=0;k<4;k++){
const res=p.gen.next();
if(res.done){ break; }
p.visited=res.value.visited; p.cur=res.value.cur;
if(res.value.done){ p.parent=res.value.parent; p.done=true; break; }
}
}
for(const p of panels) drawPanel(p);
requestAnimationFrame(tick);
}
requestAnimationFrame(tick);
</script>
</body></html>Show code
<!doctype html><html><head><meta charset="utf-8"><title>Pathfinding Race</title>
<style>body{margin:0;background:#111;color:#eee;font-family:sans-serif;text-align:center}
.row{display:flex;justify-content:center;gap:20px;margin-top:10px}
.p{display:inline-block}canvas{background:#000}h3{margin:6px}</style>
</head><body>
<h2>BFS vs DFS vs A*</h2>
<div class="row" id="row"></div>
<script>
const G=25,CS=12,W=G*CS;
let grid;
function nbrs(c){let x=c%G,y=(c-x)/G,r=[];
if(x>0)r.push(c-1);if(x<G-1)r.push(c+1);if(y>0)r.push(c-G);if(y<G-1)r.push(c+G);
return r.filter(n=>grid[n]===0);}
function solvable(){let q=[0],s=new Set([0]);while(q.length){let c=q.shift();if(c===G*G-1)return true;for(let n of nbrs(c))if(!s.has(n)){s.add(n);q.push(n);}}return false;}
function genMaze(){while(true){grid=[];for(let i=0;i<G*G;i++)grid.push(Math.random()<0.28?1:0);grid[0]=0;grid[G*G-1]=0;if(solvable())return;}}
function h(c){let x=c%G,y=(c-x)/G;return (G-1-x)+(G-1-y);}
function makeAlgo(name,type){return {name,type,frontier:[{c:0,g:0,f:0}],visited:new Set([0]),parent:new Map(),done:false,path:null};}
function stepAlgo(a){
if(a.done)return;let cur;
if(a.type==='bfs')cur=a.frontier.shift();
else if(a.type==='dfs')cur=a.frontier.pop();
else{let bi=0;for(let i=1;i<a.frontier.length;i++)if(a.frontier[i].f<a.frontier[bi].f)bi=i;cur=a.frontier.splice(bi,1)[0];}
if(!cur){a.done=true;return;}
let c=cur.c,gc=cur.g||0;
if(c===G*G-1){a.done=true;let p=[],t=c;while(t!==undefined){p.push(t);t=a.parent.get(t);}a.path=p;return;}
for(let n of nbrs(c))if(!a.visited.has(n)){a.visited.add(n);a.parent.set(n,c);let ng=gc+1;a.frontier.push({c:n,g:ng,f:ng+h(n)});}
}
let algos=[],ctxs=[];
genMaze();
const defs=[['BFS','bfs'],['DFS','dfs'],['A*','astar']];
for(let d of defs){
let div=document.createElement('div');div.className='p';
let t=document.createElement('h3');t.textContent=d[0];
let cv=document.createElement('canvas');cv.width=W;cv.height=W;
let st=document.createElement('div');st.textContent='searching...';st.style.color='#0f0';
div.appendChild(t);div.appendChild(cv);div.appendChild(st);
document.getElementById('row').appendChild(div);
let a=makeAlgo(d[0],d[1]);a.st=st;algos.push(a);ctxs.push(cv.getContext('2d'));
}
function draw(a,ctx){
for(let i=0;i<G*G;i++){let x=i%G,y=(i-x)/G;ctx.fillStyle=grid[i]?'#333':'#000';ctx.fillRect(x*CS,y*CS,CS,CS);}
a.visited.forEach(c=>{let x=c%G,y=(c-x)/G;ctx.fillStyle='rgba(80,120,255,0.5)';ctx.fillRect(x*CS,y*CS,CS,CS);});
if(a.path)for(let c of a.path){let x=c%G,y=(c-x)/G;ctx.fillStyle='#ff0';ctx.fillRect(x*CS,y*CS,CS,CS);}
ctx.fillStyle='#0f0';ctx.fillRect(0,0,CS,CS);ctx.fillStyle='#f00';ctx.fillRect((G-1)*CS,(G-1)*CS,CS,CS);
}
function loop(){
for(let i=0;i<algos.length;i++){let a=algos[i];
for(let s=0;s<3;s++)stepAlgo(a);
draw(a,ctxs[i]);
if(a.done)a.st.textContent=a.path?'DONE':'no path';
}
requestAnimationFrame(loop);
}
loop();
</script></body></html>
📝 clearest rendering: real mazes, yellow path clearly visible, DONE (8.5)
Show code
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Pathfinding Race</title>
<style>
body{margin:0;background:#14171f;color:#eee;font-family:monospace;display:flex;justify-content:center;align-items:center;height:100vh}
.row{display:flex;gap:24px}
.p{text-align:center}
.lb{margin-bottom:6px;font-size:16px}
canvas{border:1px solid #444}
</style>
</head>
<body>
<div class="row">
<div class="p"><div class="lb" id="l0">BFS</div><canvas id="c0" width="250" height="250"></canvas></div>
<div class="p"><div class="lb" id="l1">DFS</div><canvas id="c1" width="250" height="250"></canvas></div>
<div class="p"><div class="lb" id="l2">A*</div><canvas id="c2" width="250" height="250"></canvas></div>
</div>
<script>
const S=25,GOAL=S*S-1,idx=(x,y)=>y*S+x;
const g=Array.from({length:S},()=>Array(S).fill(1));
g[0][0]=0;
const stack=[[0,0]];
while(stack.length){
const[cx,cy]=stack[stack.length-1];
const opts=[[2,0],[-2,0],[0,2],[0,-2]].map(d=>[cx+d[0],cy+d[1]]).filter(p=>p[0]>=0&&p[1]>=0&&p[0]<S&&p[1]<S&&g[p[1]][p[0]]===1);
if(opts.length){const[nx,ny]=opts[Math.random()*opts.length|0];g[ny][nx]=0;g[(cy+ny)/2][(cx+nx)/2]=0;stack.push([nx,ny]);}
else stack.pop();
}
function mk(id,type){
const a={type,name:["BFS","DFS","A*"][type],ctx:document.getElementById("c"+id).getContext("2d"),lb:document.getElementById("l"+id),open:[0],visited:new Uint8Array(S*S),parent:new Int16Array(S*S).fill(-1),gs:new Int32Array(S*S),done:false,path:[]};
a.visited[0]=1;
return a;
}
const algos=[mk(0,0),mk(1,1),mk(2,2)];
const fv=(a,n)=>a.gs[n]+(S-1-n%S)+(S-1-(n/S|0));
function step(a){
if(a.done||!a.open.length)return;
let n;
if(a.type===2){let bi=0;for(let i=1;i<a.open.length;i++)if(fv(a,a.open[i])<fv(a,a.open[bi]))bi=i;n=a.open.splice(bi,1)[0];}
else n=a.type===0?a.open.shift():a.open.pop();
if(n===GOAL){a.done=true;let p=n;while(p>=0){a.path.push(p);p=a.parent[p];}return;}
const x=n%S,y=n/S|0;
for(const d of[[1,0],[-1,0],[0,1],[0,-1]]){
const nx=x+d[0],ny=y+d[1];
if(nx<0||ny<0||nx>=S||ny>=S||g[ny][nx])continue;
const m=idx(nx,ny);
if(a.visited[m])continue;
a.visited[m]=1;a.parent[m]=n;a.gs[m]=a.gs[n]+1;a.open.push(m);
}
}
function draw(a){
const c=a.ctx;
for(let y=0;y<S;y++)for(let x=0;x<S;x++){
c.fillStyle=g[y][x]?"#1b1e26":a.visited[idx(x,y)]?"#2e6fae":"#dde3ea";
c.fillRect(x*10,y*10,10,10);
}
c.fillStyle="#ffd54a";
for(const n of a.path)c.fillRect(n%S*10,(n/S|0)*10,10,10);
c.fillStyle="#3fbf5f";c.fillRect(0,0,10,10);
c.fillStyle="#e05555";c.fillRect(240,240,10,10);
a.lb.textContent=a.done?a.name+" — DONE":a.name;
}
function loop(){
for(const a of algos)for(let k=0;k<3;k++)step(a);
for(const a of algos)draw(a);
requestAnimationFrame(loop);
}
loop();
</script>
</body>
</html>