// Configurations
const diagonal = false; // No diagonal movement for simplicity
const cw = 600; // Canvas width
const ch = 600; // Canvas height
const cols = 20; // Number of columns
const rows = 20; // Number of rows
const wallAmount = 0.2; // Percentage of grid cells that are walls
const numCars = 4; // Number of cars in the simulation
// Colors
const backcolor = 'white';
const wallcolor = 'black';
const pathcolor = 'blue';
const carColors = ['red', 'green', 'orange', 'purple']; // Colors for each car
// Grid and Cars
let grid = [];
let cars = [];
// Cell dimensions
let w, h;
// Spot Class for each cell in 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) {
if (this.wall) {
fill(wallcolor);
rect(this.i * w, this.j * h, w, h);
} else if (col) {
fill(col);
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]);
};
}
// Car Class
function Car(start, end, color) {
this.start = start;
this.end = end;
this.current = start;
this.path = [];
this.color = color;
this.trail = []; // Stores positions visited by the car for drawing trail
this.waitingFrames = 0; // Count frames of waiting
}
// Setup the grid and cars
function setup() {
createCanvas(cw, ch);
w = width / cols;
h = height / rows;
// Slower frame rate for easier tracking
frameRate(5);
// Initialize the grid
for (let i = 0; i < cols; i++) {
grid[i] = new Array(rows);
for (let j = 0; j < rows; j++) {
grid[i][j] = new Spot(i, j);
}
}
// Add neighbors for each cell
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
grid[i][j].addNeighbors(grid);
}
}
// Initialize cars with random start and end positions
for (let i = 0; i < numCars; i++) {
let start = grid[floor(random(cols))][floor(random(rows))];
let end = grid[floor(random(cols))][floor(random(rows))];
while (end.wall || end === start) {
end = grid[floor(random(cols))][floor(random(rows))];
}
start.wall = false;
end.wall = false;
cars.push(new Car(start, end, carColors[i % carColors.length]));
}
}
// Heuristic function (Manhattan distance)
function heuristic(a, b) {
return abs(a.i - b.i) + abs(a.j - b.j);
}
// A* pathfinding function considering other cars as obstacles
function aStar(start, end, carIndex) {
let openSet = [start];
let closedSet = [];
start.g = 0;
start.f = heuristic(start, end);
start.previous = undefined;
// Temporarily mark other cars' positions as obstacles
for (let i = 0; i < cars.length; i++) {
if (i !== carIndex) {
grid[cars[i].current.i][cars[i].current.j].temporaryObstacle = true;
}
}
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) {
let path = [];
let temp = current;
path.push(temp);
while (temp.previous) {
path.push(temp.previous);
temp = temp.previous;
}
clearTemporaryObstacles(); // Clear temporary obstacles once path is found
return path.reverse();
}
openSet.splice(winner, 1);
closedSet.push(current);
let neighbors = current.neighbors;
for (let neighbor of neighbors) {
if (!closedSet.includes(neighbor) && !neighbor.wall && !neighbor.temporaryObstacle) {
let tempG = current.g + 1;
if (!openSet.includes(neighbor)) {
openSet.push(neighbor);
} else if (tempG >= neighbor.g) {
continue;
}
neighbor.g = tempG;
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
}
clearTemporaryObstacles(); // Clear temporary obstacles if no path is found
return [];
}
// Clear temporary obstacles after each path calculation
function clearTemporaryObstacles() {
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
grid[i][j].temporaryObstacle = false;
}
}
}
// Draw function
function draw() {
background(backcolor);
// Draw the grid
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
grid[i][j].show();
}
}
// Draw each car, its path, and trail
for (let i = 0; i < cars.length; i++) {
let car = cars[i];
// Check if car should wait or move
if (isNextPositionOccupied(car, i)) {
car.waitingFrames++;
// Recalculate path if waited enough
if (car.waitingFrames >= 10) { // Recalculate every 10 frames if blocked
car.path = aStar(car.current, car.end, i);
car.waitingFrames = 0; // Reset waiting frames
}
continue; // Skip movement this frame
} else {
car.waitingFrames = 0; // Reset wait if no obstacle
}
// Move the car along its path if not waiting
if (car.path.length > 1) {
car.trail.push({ i: car.current.i, j: car.current.j }); // Add current position to trail
car.current = car.path.shift(); // Move to the next cell in the path
}
// Draw the destination as a circle in the car's color
fill(car.color);
noStroke();
ellipse((car.end.i + 0.5) * w, (car.end.j + 0.5) * h, w / 2, h / 2);
// Draw the trail of the car
for (let pos of car.trail) {
fill(car.color);
noStroke();
ellipse((pos.i + 0.5) * w, (pos.j + 0.5) * h, w / 4, h / 4);
}
// Draw the car
fill(car.color);
rect(car.current.i * w, car.current.j * h, w, h);
}
}
// Check if the next cell in a car's path is occupied by another car
function isNextPositionOccupied(car, carIndex) {
if (car.path.length > 1) {
let nextPos = car.path[1];
for (let i = 0; i < cars.length; i++) {
if (i !== carIndex && cars[i].current.i === nextPos.i && cars[i].current.j === nextPos.j) {
return true;
}
}
}
return false;
}