我正在尝试创建一个很酷的小视觉效果,展示 Dijkstra 算法如何在网格上工作。用户应该单击两个图块,然后它应该显示所有已搜索到的图块。此时,我已经能够成功绘制搜索到的所有图块,但我现在想将其转换为动画,而不是程序最后一次绘制所有图块。问题是,当我使用 setTimout 方法时,无论两点之间的距离如何,它似乎只绘制 4 个图块,并且它完全忽略了大多数其他 setTimout 调用。这是网格的图像。
这是我的大部分代码,不包括一些辅助函数和创建网格并包含对handleClick函数的调用的drawgrid函数。
向 Dijkstra 函数提供起始和结束坐标
function handleClick(event) {
let xPos = event.offsetX;
let yPos = event.offsetY;
let col = Math.floor(xPos / colWidth);
let row = Math.floor(yPos / colWidth);
if (selectingStart) {
context.fillStyle = "rgb(0, 255, 0)";
context.fillRect(col * colWidth, row * colWidth, 49.5, 49.5);
startNode = createCoordinate(col, row);
selectingStart = false;
} else if (selectingEnd) {
context.fillStyle = "rgb(255, 0, 0)";
context.fillRect(col * colWidth, row * colWidth, 49.5, 49.5);
endNode = createCoordinate(col, row);
selectingEnd = false;
dijkstra(startNode, endNode);
canvas.removeEventListener("click", handleClick);
}
}
创建左、右、上、下图块并检查它们是否是结束坐标。检查完瓷砖后,它将被漆成蓝色。
目前,我正在围绕图块绘制逻辑设置超时方法。我也尝试将它包裹在 if 语句中,但随后我会收到一条错误消息,指出坐标[0] 未定义。
function dijkstra(startCoordinate, endCoordinate) {
let pathFound = false;
let coordinates = [];
coordinates.push(startCoordinate);
let timer = 0;
while (coordinates.length > 0) {
if (coordinates[0] === endCoordinate) {
console.log("ENOUGH")
return true;
}
let leftTile = createCoordinate(coordinates[0].xPos - 1, coordinates[0].yPos);
let rightTile = createCoordinate(coordinates[0].xPos + 1, coordinates[0].yPos);
let bottomTile = createCoordinate(coordinates[0].xPos, coordinates[0].yPos - 1);
let topTile = createCoordinate(coordinates[0].xPos, coordinates[0].yPos + 1);
if (coordinates[0].xPos > 0 && !visitedNodes.has(stringifyCoordinate(leftTile))) {
if (compareCoordinates(leftTile, endCoordinate)) {
console.log("ENOUGH")
return true;
}
coordinates.push(leftTile);
timer++;
setTimeout(function () {
context.fillStyle = "rgb(0, 0, 255)";
context.fillRect((coordinates[0].xPos - 1) * colWidth, coordinates[0].yPos * colWidth, 49.5, 49.5);
}, 0 + timer * 0)
}
if (coordinates[0].xPos < (canvasWidth / colWidth) && !visitedNodes.has(stringifyCoordinate(rightTile))) {
if (compareCoordinates(rightTile, endCoordinate)) {
console.log("ENOUGH")
return true;
}
coordinates.push(rightTile);
timer++;
setTimeout(function () {
context.fillStyle = "rgb(0, 0, 255)";
context.fillRect((coordinates[0].xPos + 1) * colWidth, coordinates[0].yPos * colWidth, 49.5, 49.5);
}, 0 + timer * 0)
// alert("FILL");
}
if (coordinates[0].yPos > 0 && !visitedNodes.has(stringifyCoordinate(bottomTile))) {
if (compareCoordinates(bottomTile, endCoordinate)) {
console.log("ENOUGH")
return true;
}
coordinates.push(bottomTile);
timer++;
setTimeout(function () {
context.fillStyle = "rgb(0, 0, 255)";
context.fillRect(coordinates[0].xPos * colWidth, (coordinates[0].yPos - 1) * colWidth, 49.5, 49.5);
}, 0 + timer * 0)
}
if (coordinates[0].yPos < (canvasWidth / colWidth) && !visitedNodes.has(stringifyCoordinate(topTile))) {
if (compareCoordinates(topTile, endCoordinate)) {
console.log("ENOUGH")
return true;
}
coordinates.push(topTile);
timer++;
setTimeout(function () {
context.fillStyle = "rgb(0, 0, 255)";
context.fillRect(coordinates[0].xPos * colWidth, (coordinates[0].yPos + 1) * colWidth, 49.5, 49.5);
}, 0 + timer * 0)
}
visitedNodes.add(stringifyCoordinate(coordinates[0]));
coordinates.shift();
}
}
drawGrid()
我很感谢您的帮助。
主要问题是,当
setTimeout
回调执行时,整个Dijkstra算法已经完成,并且coordinates
已经发生了变异。发生这种情况是因为 dijkstra
正在同步运行,而异步任务只能在 JavaScript 的调用堆栈为空时执行,即在 dijkstra
返回之后。那时coordinates[0]
不再是你所期望的点,而是最终找到目标并且dijkstra
可以返回的入口。
如果您想像这样使用
setTimeout
,则必须确保回调访问为此目的而保留的变量,以便它们在回调执行之前不会被更改。您可以使用本地(块范围)变量来做到这一点——而不是在整个算法中不断变化的coordinates
。
我还建议避免重复代码。左、上、右、下的情况几乎相同,因此可以更好地在单个代码块和这四个方向上的循环中完成。
显然您应该使用更重要的超时值(而不是 0),例如每个刻度 100 毫秒。
这是对
dijkstra
函数的修改,可以做到这一点:
function dijkstra(startCoordinate, endCoordinate) {
if (compareCoordinates(startCoordinate, endCoordinate)) { // Trivial case
fillTile(endCoordinate, "rgb(255, 255, 0)")
return true;
}
const coordinates = [];
coordinates.push(startCoordinate);
visitedNodes.add(stringifyCoordinate(startCoordinate));
let timer = 0;
while (coordinates.length > 0) {
const tile = coordinates.shift();
// Avoid code repetition: use loop for the four directions
for (const [dx, dy] of [[-1, 0], [0, -1], [1, 0], [0, 1]]) {
const neighbor = createCoordinate(tile.xPos + dx, tile.yPos + dy);
if (!validCoordinate(neighbor) || visitedNodes.has(stringifyCoordinate(neighbor))) continue;
visitedNodes.add(stringifyCoordinate(neighbor));
coordinates.push(neighbor);
timer++;
const found = compareCoordinates(neighbor, endCoordinate);
setTimeout(function () {
// neighbor is a variable that will not have been mutated.
// Maybe use a different color when the target is reached:
const color = found ? "rgb(255, 255, 0)" : "rgb(0, 0, 255)";
fillTile(neighbor, color); // Avoid code repetition: use reusable function
}, 0 + timer * 100); // Use a timeout that is relevant for the user experience
if (found) return true;
}
}
}
// Utility function to verify whether coordinates are valid
const validCoordinate = ({xPos, yPos}) =>
xPos >= 0 && xPos * colWidth < canvasWidth && yPos >= 0 && yPos * colWidth < canvasWidth;
// Function to fill a tile, so to avoid code repetition
function fillTile(tile, color) {
context.fillStyle = color;
context.fillRect(tile.xPos * colWidth, tile.yPos * colWidth, colWidth, colWidth);
}
function handleClick(event) {
let xPos = event.offsetX;
let yPos = event.offsetY;
let col = Math.floor(xPos / colWidth);
let row = Math.floor(yPos / colWidth);
if (selectingStart) {
startNode = createCoordinate(col, row);
fillTile(startNode, "rgb(0, 255, 0)"); // Avoid code repetition: use reusable function
selectingStart = false;
} else if (selectingEnd) {
endNode = createCoordinate(col, row);
fillTile(endNode, "rgb(255, 0, 0)"); // Avoid code repetition: use reusable function
selectingEnd = false;
dijkstra(startNode, endNode);
canvas.removeEventListener("click", handleClick);
}
}
// Rest of the code to make the snippet runnable
const canvas = document.querySelector("canvas");
const context = canvas.getContext("2d");
const canvasWidth = canvas.width;
canvas.addEventListener("click", handleClick);
const colWidth = 50;
let selectingStart = true;
let selectingEnd = true;
let startNode, endNode;
const visitedNodes = new Set;
function drawGrid() {
for (let i = 0; i < canvasWidth; i += colWidth) {
context.moveTo(0, i);
context.lineTo(canvasWidth, i);
context.moveTo(i, 0);
context.lineTo(i, canvasWidth);
}
context.stroke();
}
const createCoordinate = (xPos, yPos) => ({xPos, yPos});
const stringifyCoordinate = ({xPos, yPos}) => JSON.stringify([xPos, yPos]);
const compareCoordinates = (a, b) => stringifyCoordinate(a) === stringifyCoordinate(b);
drawGrid();
<canvas width="800" height="600"></canvas>
最后,你可以看看promisifying
setTimeout
,这样你就可以受益于async
和await
。这样你就可以让 dijkstra
返回一个在动画完成时解析的承诺。