setTimout 方法不起作用，未执行应有的次数

Question

我正在尝试创建一个很酷的小视觉效果，展示 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()

我很感谢您的帮助。

Answer 1

主要问题是，当

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

返回一个在动画完成时解析的承诺。