// 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;
// A* Algorithm variables
let openSet = [];
let closedSet = [];
// 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.state = 'SEARCHING'; // Initial state
}
// 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
function aStar(start, end) {
openSet = [start];
closedSet = [];
start.g = 0;
start.f = heuristic(start, end);
start.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) {
let path = [];
let temp = current;
path.push(temp);
while (temp.previous) {
path.push(temp.previous);
temp = temp.previous;
}
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) {
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;
}
}
}
return [];
}
// Check if car is in proximity of the destination
function isNearDestination(car) {
const { i, j } = car.current;
const { i: ei, j: ej } = car.end;
return (
(i === ei && abs(j - ej) === 1) || // same column, adjacent row
(j === ej && abs(i - ei) === 1) // same row, adjacent column
);
}
// Draw function
function draw() {
background(backcolor);
// Draw grid border
stroke(0); // Set the border color (black)
strokeWeight(4); // Set the thickness of the border
noFill(); // No fill inside the border
rect(0, 0, cols * w, rows * h); // Draw border around the grid
// 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 [index, car] of cars.entries()) {
// Calculate path if not already done and if the car is searching
if (car.path.length === 0 && car.state === 'SEARCHING') {
car.path = aStar(car.current, car.end);
if (car.path.length > 0) {
console.log(`Car ${index} (${car.color}) - Path found, starting movement.`);
} else {
car.state = 'PATH NOT FOUND';
console.log(`Car ${index} (${car.color}) - No path to destination.`);
}
}
// Check if the car is at or very close to its destination
if (car.current === car.end) {
if (car.state !== 'REACHED') {
car.state = 'REACHED';
console.log(`Car ${index} (${car.color}) - Reached destination at (${car.end.i},${car.end.j}).`);
}
continue; // Skip moving this car if it has reached its destination
} else if (isNearDestination(car)) {
if (car.state !== 'REACHING') {
car.state = 'REACHING';
console.log(`Car ${index} (${car.color}) - Reached destination.`);
}
} else 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
console.log(`Car ${index} (${car.color}) - Moving to (${car.current.i},${car.current.j}).`);
}
// 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); // Destination circle
// 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); // Small dot for trail
}
// Draw the car
fill(car.color);
rect(car.current.i * w, car.current.j * h, w, h);
}
}