I am trying to create a cool little visual of how Dijkstra's algorithm works on a grid. The user is supposed to click on two tiles and then it should show you all the tiles that have been searched. At this point, I have been able to successfully paint all the tiles that are searched but I now want to turn it into an animation rather than the program painting all the tiles at once at the end. The issue is when I use the setTimout method it only seems to paint 4 tiles regardless of the distance between the two points and it completely ignores most of the other setTimout calls. Here is the image of the grid.
Image before setTimeouts are added Image after setTimeouts are added
Here is the majority of my code excluding some helper functions and the drawgrid function that creates the grid and includes the call to handleClick function.
Feeds the Dijkstra function with starting and end coordinates
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);
}
}
Creates left, right, top, and bottom tiles and checks to see if they are the end coordinate. After the tile is checked it will be painted blue.
Currently, I am setting the timeout methods around the tile painting logic. I tried also wrapping it around the if statements but then I would get an error saying that coordinate[0] was undefined.
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()
I appreciate the help.
The main problem is that by the time the setTimeout callback executes, the whole Dijkstra algorithm has already finished, and coordinates has mutated. This happens because dijkstra is running synchronously, and asynchronous tasks can only execute when JavaScript's call stack is empty, so after dijkstra has returned. At that time coordinates[0] is no longer the point you expected, but is the entry from which the target was eventually found and dijkstra could return.
If you want to use setTimeout like that, you must make sure the callback accesses variables that are reserved for that purpose so that they will not be altered before the callback gets to execute. You can do that with a local (block scoped) variable -- instead of coordinates which keeps on mutating throughout the algorithm.
I would also suggest to avoid that code repetition you have. The cases for left, top, right, bottom are almost the same, so this can better be done in a single code block and a loop over these four directions.
And obviously you should use a timeout value that is more significant (not 0), like 100 milliseconds per tick.
Here is a modification of your dijkstra function that will do it:
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>Finally, you could have a look at promisifying setTimeout so that you can have the benefit of async and await. This way you can make dijkstra return a promise that resolves when the animation has been completed.