前言
在路径规划与图论问题中，广度优先搜索（BFS）是解决无权图最短路径问题的经典算法。相比 A*等启发式搜索，BFS 逻辑简单且能保证找到步数最少的路径，非常适合用于网格地图寻路或状态空间搜索。
本章我们将通过 JavaScript 完整实现 BFS 算法，并利用 Canvas 绘制交互网格，动态展示搜索过程。这种可视化方式能直观地帮助理解队列扩展、节点访问标记以及路径回溯的核心机制。
BFS 核心逻辑
BFS 的核心在于'层层推进'。我们使用一个队列来存储待访问的节点，每次从队头取出一个节点，检查其上下左右四个邻居。如果邻居未被访问且不是障碍物，则将其加入队列并记录路径信息。为了确保能找到最短路径，我们需要维护一个已访问集合（Set），避免重复处理同一个节点。
为了实现动画效果，我们在遍历过程中加入了异步等待，让浏览器有机会渲染每一帧的状态变化，从而形成流畅的视觉反馈。
代码实现
下面是一个完整的 HTML + JavaScript 示例。你可以直接保存为 .html 文件在浏览器中运行。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>BFS Algorithm Visualization</title>
<style>
body {
font-family: Arial, sans-serif;
text-align: center;
margin: 20px;
}
canvas {
border: 1px solid #000;
margin: 10px auto;
display: block;
}
button {
padding: 10px 20px;
margin: 5px;
cursor: pointer;
}
.controls {
margin: 20px;
}
</style>
</head>
<body>
<h1>Breadth-First Search (BFS) Visualization</h1>
<div class="controls">
<button id="start-btn">Set Start</button>
<button id="end-btn">Set End</button>
<button id="wall-btn">Toggle Walls</button>
<button id="clear-btn">Clear Grid</button>
<button id="run-btn">Run BFS</button>
</div>
<canvas id="grid" width="500" height="500"></canvas>
<script>
// Canvas and grid setup
const canvas = document.getElementById('grid');
const ctx = canvas.getContext('2d');
const gridSize = 20; // 20x20 grid
const cellSize = canvas.width / gridSize;
// Grid state
let grid = Array(gridSize).fill().map(() => Array(gridSize).fill(0));
let start = { x: 5, y: 5 };
let end = { x: 15, y: 15 };
let isSettingStart = false;
let isSettingEnd = false;
let isSettingWalls = false;
// Colors
const colors = {
empty: '#fff',
wall: '#000',
start: '#00f',
end: '#f00',
visited: '#0ff',
path: '#ff0',
};
// Initialize grid
function initGrid() {
grid = Array(gridSize).fill().map(() => Array(gridSize).fill(0));
start = { x: 5, y: 5 };
end = { x: 15, y: 15 };
drawGrid();
}
// Draw the grid
function drawGrid() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let y = 0; y < gridSize; y++) {
for (let x = 0; x < gridSize; x++) {
ctx.strokeStyle = '#ddd';
ctx.strokeRect(x * cellSize, y * cellSize, cellSize, cellSize);
if (grid[y][x] === 1) { // Wall
ctx.fillStyle = colors.wall;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (x === start.x && y === start.y) { // Start
ctx.fillStyle = colors.start;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (x === end.x && y === end.y) { // End
ctx.fillStyle = colors.end;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (grid[y][x] === 2) { // Visited
ctx.fillStyle = colors.visited;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
} else if (grid[y][x] === 3) { // Path
ctx.fillStyle = colors.path;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
}
}
}
// BFS Algorithm
async function bfs() {
const queue = [{ x: start.x, y: start.y, path: [] }];
const visited = new Set();
visited.add(`${start.x},${start.y}`);
const directions = [
{ dx: 1, dy: 0 }, // Right
{ dx: -1, dy: 0 }, // Left
{ dx: 0, dy: 1 }, // Down
{ dx: 0, dy: -1 } // Up
];
while (queue.length > 0) {
const current = queue.shift();
const { x, y, path } = current;
// Mark as visited (except start/end)
if (!(x === start.x && y === start.y) && !(x === end.x && y === end.y)) {
grid[y][x] = 2; // Visited
drawGrid();
await new Promise(resolve => setTimeout(resolve, 50)); // Delay for visualization
}
// Check if reached
if (x === end.x && y === end.y) {
// Highlight path
for (const { x, y } of path) {
grid[y][x] = 3; // Path
drawGrid();
await new Promise(resolve => setTimeout(resolve, 100));
}
return;
}
// Explore neighbors
for (const dir of directions) {
const nx = x + dir.dx;
const ny = y + dir.dy;
if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize &&
grid[ny][nx] !== 1 && !visited.has(`${nx},${ny}`)) {
visited.add(`${nx},${ny}`);
queue.push({ x: nx, y: ny, path: [...path, { x, y }] });
}
}
}
alert("No path found!");
}
// Event Listeners
canvas.addEventListener('click', (e) => {
const x = Math.floor(e.offsetX / cellSize);
const y = Math.floor(e.offsetY / cellSize);
if (isSettingStart) {
start = { x, y };
} else if (isSettingEnd) {
end = { x, y };
} else if (isSettingWalls) {
grid[y][x] = grid[y][x] === 1 ? 0 : 1; // Toggle wall
}
drawGrid();
});
document.getElementById('start-btn').addEventListener('click', () => {
isSettingStart = true;
isSettingEnd = false;
isSettingWalls = false;
});
document.getElementById('end-btn').addEventListener('click', () => {
isSettingStart = false;
isSettingEnd = true;
isSettingWalls = false;
});
document.getElementById('wall-btn').addEventListener('click', () => {
isSettingStart = false;
isSettingEnd = false;
isSettingWalls = true;
});
document.getElementById('clear-btn').addEventListener('click', initGrid);
document.getElementById('run-btn').addEventListener('click', bfs);
// Initialize
initGrid();
</script>
</body>
</html>
关键点解析
- 异步控制：
bfs函数使用了async/await配合setTimeout和Promise。这是为了让浏览器在执行耗时循环时能够刷新 UI，否则整个搜索会瞬间完成，无法看到动画效果。 - 状态管理：
grid数组不仅存储障碍物信息（1），还用来临时标记已访问节点（2）和最终路径（3）。每次状态变更都调用drawGrid重绘。 - 交互设计：通过点击按钮切换模式（设置起点、终点、墙壁），最后点击 Run 触发搜索。这种设计降低了测试门槛，方便快速验证不同场景。
实际开发中，如果遇到更复杂的地图或性能要求，可以将网格逻辑封装成类，或者使用 Web Worker 处理计算以避免阻塞主线程。但对于学习算法原理，这个 Demo 已经足够清晰了。