// Configuration parameters
const diagonal = false;
const cw = 900;
const ch = 600;
const cols = 19;
const rows = 16;
const wallAmount = 0.3;
const backcolor = 'lightgreen';
const wallcolor = 'grey';
const pointColor = 'red';
const additionalPointColors = ['blue', 'purple', 'orange']; // Colors for additional points
let grid = new Array(cols);
let w, h;
let paths = [];
let currentSteps = [0, 0, 0, 0]; // Step counters for each point
const frameDelay = 10;
let frameCounters = [0, 0, 0, 0]; // Frame delay counters for each point
let startPoints = [];
let end;
let finishOrder = []; // Track colors in finish order
let finishedPoints = [false, false, false, false]; // Flags for each point's finished status
// Heuristic function for A*
function heuristic(a, b) {
return diagonal ? dist(a.i, a.j, b.i, b.j) : abs(a.i - b.i) + abs(a.j - b.j);
}
// g function for A*
function gfn(a, b) {
return diagonal ? dist(a.i, a.j, b.i, b.j) : abs(a.i - b.i) + abs(a.j - b.j);
}
// Utility to remove an element from an array
function removeFromArray(arr, elt) {
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] == elt) {
arr.splice(i, 1);
}
}
}
// Spot class represents each cell on the grid
function Spot(i, j) {
this.i = i;
this.j = j;
this.f = 0;
this.g = 0;
this.h = 0;
this.neighbors = [];
this.previous = undefined;
this.wall = random(1) < wallAmount;
this.show = function (col) {
fill(this.wall ? wallcolor : col || backcolor);
noStroke();
rect(this.i * w, this.j * h, w, h);
};
this.addNeighbors = function (grid) {
let i = this.i;
let j = this.j;
if (i < cols - 1) this.neighbors.push(grid[i + 1][j]);
if (i > 0) this.neighbors.push(grid[i - 1][j]);
if (j < rows - 1) this.neighbors.push(grid[i][j + 1]);
if (j > 0) this.neighbors.push(grid[i][j - 1]);
if (diagonal) {
if (i > 0 && j > 0) this.neighbors.push(grid[i - 1][j - 1]);
if (i < cols - 1 && j > 0) this.neighbors.push(grid[i + 1][j - 1]);
if (i > 0 && j < rows - 1) this.neighbors.push(grid[i - 1][j + 1]);
if (i < cols - 1 && j < rows - 1) this.neighbors.push(grid[i + 1][j + 1]);
}
};
}
function setup() {
createCanvas(cw, ch);
w = width / cols;
h = height / rows;
// Create grid
for (let i = 0; i < cols; i++) grid[i] = new Array(rows);
for (let i = 0; i < cols; i++) for (let j = 0; j < rows; j++) grid[i][j] = new Spot(i, j);
// Set up neighbors
for (let i = 0; i < cols; i++) for (let j = 0; j < rows; j++) grid[i][j].addNeighbors(grid);
// Define multiple start points
startPoints = [grid[0][0], grid[0][rows - 1], grid[cols - 1][0], grid[cols - 1][rows - 1]];
// Set random end point that is not one of the start points
let randomEnd;
do {
let randomX = Math.floor(random(cols));
let randomY = Math.floor(random(rows));
randomEnd = grid[randomX][randomY];
} while (startPoints.includes(randomEnd)); // Ensure end is not a start point
end = randomEnd;
end.wall = false;
// Calculate initial paths for each point
for (let i = 0; i < startPoints.length; i++) {
startPoints[i].wall = false;
paths.push(findPath(startPoints[i], end));
}
}
// A* function to find a path while avoiding other points
function findPath(start, end) {
let openSet = [start];
let closedSet = [];
let path = [];
// Reset all spots' parameters
for (let col of grid) {
for (let spot of col) {
spot.f = spot.g = spot.h = 0;
spot.previous = undefined;
}
}
while (openSet.length > 0) {
let winner = 0;
for (let i = 0; i < openSet.length; i++) {
if (openSet[i].f < openSet[winner].f) winner = i;
}
let current = openSet[winner];
if (current === end) break;
removeFromArray(openSet, current);
closedSet.push(current);
for (let neighbor of current.neighbors) {
if (!closedSet.includes(neighbor) && !neighbor.wall) {
let tempG = current.g + gfn(neighbor, current);
let newPath = false;
if (openSet.includes(neighbor)) {
if (tempG < neighbor.g) {
neighbor.g = tempG;
newPath = true;
}
} else {
neighbor.g = tempG;
newPath = true;
openSet.push(neighbor);
}
if (newPath) {
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
}
}
// Retrace path
let temp = end;
path.push(temp);
while (temp.previous) {
path.push(temp.previous);
temp = temp.previous;
}
return path.reverse();
}
function draw() {
background(backcolor);
// Draw grid
for (let i = 0; i < cols; i++) for (let j = 0; j < rows; j++) grid[i][j].show();
// Draw paths with alternating large squares
for (let i = 0; i < paths.length; i++) {
let path = paths[i];
for (let j = 0; j < path.length; j++) {
let spot = path[j];
// Draw a large white square with thick black borders
fill('white');
stroke('black');
strokeWeight(13);
rect(spot.i * w + w * 0.13 , spot.j * h + h *0.12 , w * 0.75, h * 0.70);
}
}
// Move each point along its path
for (let i = 0; i < paths.length; i++) {
if (finishedPoints[i]) continue; // Skip finished points
let currentPos = paths[i][currentSteps[i]];
if (frameCounters[i] >= frameDelay) {
// Update the current step if there are more steps in the path
if (currentSteps[i] < paths[i].length - 1) {
currentSteps[i]++;
}
frameCounters[i] = 0;
} else {
frameCounters[i]++;
}
// Draw the point only if it has not finished
if (currentPos !== end) {
fill(i === 0 ? pointColor : additionalPointColors[i - 1]);
noStroke();
ellipse(currentPos.i * w + w / 2, currentPos.j * h + h / 2, w * 0.6, h * 0.6);
}
// If the point reaches the endpoint, mark it as finished
if (currentPos === end && !finishedPoints[i]) {
finishedPoints[i] = true;
finishOrder.push(i === 0 ? pointColor : additionalPointColors[i - 1]);
}
}
// Draw the finish point with a 'Finish' label
fill('yellow');
noStroke();
ellipse(end.i * w + w / 2, end.j * h + h / 2, w * 0.8, h * 0.8);
fill('red');
textSize(24);
textAlign(CENTER, CENTER);
text('Finish', end.i * w + w / 2, end.j * h + h / 2);
// Display the finish order
textSize(18);
textAlign(LEFT, TOP);
let yOffset = 10;
for (let i = 0; i < finishOrder.length; i++) {
fill(finishOrder[i]);
text(`${finishOrder[i]} finished`, 10, yOffset);
yOffset += 30;
}
}