// Cloned by Mohamed Afrath Segu Mohamed on 3 Nov 2024 from World "A star" by "Coding Train" project
// Please leave this clone trail here.
// Port of
// https://github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/tree/master/week1-graphs/05_astar
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Part 1: https://youtu.be/aKYlikFAV4k
// Part 2: https://youtu.be/EaZxUCWAjb0
// Part 3: https://youtu.be/jwRT4PCT6RU
//Mohamed Afrath: Movement is restricted to non-diagonal paths
const diagonal = false;
const cw = 900;
const ch = 600;
// MH edit
var rando = 2; // AB.randomIntAtoB(2, 4);
var cols = Math.max(7 * rando, 5);
var rows = Math.max(5 * rando, 5);
// MH edit
// Asmitha Satesh: Randomization of parks, shops, houses with specified probabilities
const shopAmount = AB.randomFloatAtoB(0.05, 0.15);
const houseAmount = AB.randomFloatAtoB(0.05, 0.15);
const parkAmount = AB.randomFloatAtoB(0.05, 0.1);
// Mohamed Afrath: Define unique trail colors to visually distinguish the paths of different cars.
// These colors help in identifying which path belongs to which car during the simulation.
const trailColors = [
'rgba(255, 87, 34, 0.5)', // Bright orange-red
'rgba(0, 123, 255, 0.5)', // Deep blue
'rgba(255, 193, 7, 0.5)', // Golden yellow
'rgba(76, 175, 80, 0.5)', // Fresh green
];
// Asmitha Satesh:
// This block of code sets up visual elements for the simulation.
// It includes defining color constants for various components like streets, parks, houses, and shops,
// and also loads images for these elements to provide a visual representation.
// The `preload()` function ensures that all necessary images are loaded before the simulation starts,
// with logging messages to indicate success or failure for each image load attempt.
// The images include houses, shops, parks, cars, and flags, which will be used during the simulation to create a more realistic visual environment.
const backgroundcolor = '#47484c';
const parkColor = 'green';
const shopColor = 'black';
const housecolor = 'black';
const streetcolor = '#47484c';
const streetLineColor = 'white';
let houseImg, shopImg, parkImg, flagImg, carImgs = [];
// Preload images required for the simulation.
// Loads images of houses, shops, parks, cars, and flags.
function preload() {
houseImg = loadImage('/uploads/afu60/house_min.png', () => console.log('House image loaded'), () => console.error('Failed to load House image'));
shopImg = loadImage('/uploads/afu60/shop-min.png', () => console.log('shop image loaded'), () => console.error('Failed to load shop image'));
parkImg = loadImage('/uploads/afu60/trees.png', () => console.log('Park image loaded'), () => console.error('Failed to load park image'));
carImgs.push(loadImage('/uploads/afu60/car1.png', () => console.log('Car 1 image loaded'), () => console.error('Failed to load car 2 image')));
carImgs.push(loadImage('/uploads/afu60/car2.png', () => console.log('Car 2 image loaded'), () => console.error('Failed to load car 2 image')));
carImgs.push(loadImage('/uploads/afu60/car3.png', () => console.log('Car 3 image loaded'), () => console.error('Failed to load car 3 image')));
carImgs.push(loadImage('/uploads/afu60/car4.png', () => console.log('Car 4 image loaded'), () => console.error('Failed to load car 4 image')));
flagImg = loadImage('/uploads/afu60/greenflag.png', () => console.log('Flag image loaded'), () => console.error('Failed to load flag image'));
}
var grid = [];
var cars = [];
var w, h;
// Mohamed Afrath: Added function to reset node states before finding new paths.
// Reset nodes before recalculating paths for A*.
// Resets f, g, h values and clears the previous reference.
function resetNodes(grid) {
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
grid[i][j].f = 0;
grid[i][j].g = 0;
grid[i][j].h = 0;
grid[i][j].previous = undefined;
}
}
}
function heuristic(a, b) {
if (diagonal) return dist(a.i, a.j, b.i, b.j);
else return abs(a.i - b.i) + abs(a.j - b.j);
}
function gfn(a, b) {
if (diagonal) return dist(a.i, a.j, b.i, b.j);
else return abs(a.i - b.i) + abs(a.j - b.j);
}
function removeFromArray(arr, elt) {
for (var i = arr.length - 1; i >= 0; i--)
if (arr[i] == elt) arr.splice(i, 1);
}
// Represents each spot (cell) in the grid.
// Defines the properties of each spot and assigns a random type (house, shop, park, street).
function Spot(i, j) {
this.i = i;
this.j = j;
this.f = 0;
this.g = 0;
this.h = 0;
this.neighbors = [];
this.previous = undefined;
// Asmitha Satesh: Assigned spot types (park, shop, house, street) based on randomization
const randomType = random();
if (randomType < parkAmount) {
this.type = 'park';
} else if (randomType < parkAmount + shopAmount) {
this.type = 'shop';
} else if (randomType < parkAmount + shopAmount + houseAmount) {
this.type = 'house';
} else {
this.type = 'street';
}
this.show = function(col) {
if (this.type === 'house') {
if (houseImg) {
image(houseImg, this.i * w + w * 0.1, this.j * h + h * 0.1, w * 0.8, h * 0.8); // Adding larger gap around office buildings
} else {
fill(housecolor);
noStroke();
rect(this.i * w, this.j * h, w, h);
}
} else if (this.type === 'park') {
if (parkImg) {
image(parkImg, this.i * w + w * 0.1, this.j * h + h * 0.1, w * 0.8, h * 0.8); // Adding larger gap around parks
} else {
fill(parkColor);
rect(this.i * w + w * 0.1, this.j * h + h * 0.1, w * 0.8, h * 0.8); // Adding larger gap around parks
}
} else if (this.type === 'shop') {
if (shopImg) {
image(shopImg, this.i * w + w * 0.1, this.j * h + h * 0.1, w * 0.8, h * 0.8); // Adding larger gap around parks
} else {
fill(shopColor);
rect(this.i * w + w * 0.1, this.j * h + h * 0.1, w * 0.8, h * 0.8); // Adding larger gap around parks
}
} else if (this.type === 'street') {
fill(streetcolor);
noStroke();
rect(this.i * w, this.j * h, w, h);
stroke(streetLineColor);
strokeWeight(2);
for (let k = 0; k < h; k += 10) {
line(this.i * w + w / 2, this.j * h + k, this.i * w + w / 2, this.j * h + k + 5);
}
} else if (col) {
fill(col);
rect(this.i * w, this.j * h, w, h);
}
//Asmitha Satesh: Draw white lines to differentiate each street
stroke('white');
strokeWeight(1);
line(this.i * w, 0, this.i * w, height);
};
this.addNeighbors = function(grid) {
var i = this.i;
var j = this.j;
// Asmitha Satesh: Modified to only add neighboring spots that are streets to the neighbors list
if (i < cols - 1 && grid[i + 1][j].type === 'street') this.neighbors.push(grid[i + 1][j]);
if (i > 0 && grid[i - 1][j].type === 'street') this.neighbors.push(grid[i - 1][j]);
if (j < rows - 1 && grid[i][j + 1].type === 'street') this.neighbors.push(grid[i][j + 1]);
if (j > 0 && grid[i][j - 1].type === 'street') this.neighbors.push(grid[i][j - 1]);
if (diagonal) {
if (i > 0 && j > 0 && grid[i - 1][j - 1].type === 'street') this.neighbors.push(grid[i - 1][j - 1]);
if (i < cols - 1 && j > 0 && grid[i + 1][j - 1].type === 'street') this.neighbors.push(grid[i + 1][j - 1]);
if (i > 0 && j < rows - 1 && grid[i - 1][j + 1].type === 'street') this.neighbors.push(grid[i - 1][j + 1]);
if (i < cols - 1 && j < rows - 1 && grid[i + 1][j + 1].type === 'street') this.neighbors.push(grid[i + 1][j + 1]);
}
};
}
// Setup function initializes the grid and cars.
// Creates canvas, initializes the grid, sets up cars with start and end points.
function setup() {
frameRate(2);
createCanvas(cw, ch);
w = width / cols;
h = height / rows;
grid = Array.from({
length: cols
}, () => new Array(rows));
for (var i = 0; i < cols; i++)
for (var j = 0; j < rows; j++) grid[i][j] = new Spot(i, j);
for (var i = 0; i < cols; i++)
for (var j = 0; j < rows; j++) grid[i][j].addNeighbors(grid);
let usedStartPoints = new Set(); // Track used start points
let usedEndPoints = new Set(); // Track used end points
// Asmitha Satesh: Initialized cars with unique start and end points, ensuring they are on streets
// Added retry mechanism to find valid start and end points for each car
for (let i = 0; i < 4; i++) {
let start, end;
let attempts = 0;
do {
do {
start = grid[floor(random(cols))][floor(random(rows))];
} while (start.type !== 'street');
do {
end = grid[floor(random(cols))][floor(random(rows))];
} while (end.type !== 'street' || start === end);
let startKey = `${start.i},${start.j}`;
let endKey = `${end.i},${end.j}`;
// Asmitha Satesh: Ensure unique start and end points for each car
if (
!usedStartPoints.has(startKey) &&
!usedEndPoints.has(endKey)
) {
usedStartPoints.add(startKey);
usedEndPoints.add(endKey);
cars.push({
carNumber: i + 1,
start,
end,
carImg: carImgs[i % carImgs.length],
trail: [{
x: start.i * w,
y: start.j * h
}],
waitTimer: 0,
trailColor: trailColors[i % trailColors.length],
currentSpot: start,
reached: false,
path: [],
pathAttempts: 0
});
}
attempts++;
} while ((!start || !end || cars.length <= i) && attempts < 100);
}
if (cars.length < 4) {
console.log('Not all cars could be populated with valid start and end points. Please reload.');
} else {
console.log('start search');
}
}
// Mohamed Afrath: Modified pathfinding to include collision detection and dynamic obstacle handling.
// Find the optimal path from the start to the end using the A* algorithm.
// Includes handling of obstacles and collision detection with other cars.
function findPath(start, end, cars) {
resetNodes(grid); // Reset node states before finding a new path
let openSet = [start];
let closedSet = [];
let path = [];
let maxIterations = 1000000; //Mohamed Afrath: Set a limit to avoid infinite loops
while (openSet.length > 0) {
var winner = 0;
for (var i = 0; i < openSet.length; i++) {
if (openSet[i].f < openSet[winner].f) {
winner = i;
}
}
var current = openSet[winner];
if (current === end) {
let temp = current;
while (temp && maxIterations > 0) {
path.push(temp);
if (!temp.previous) break;
temp = temp.previous;
maxIterations--;
}
if (maxIterations === 0) {
return [];
}
return path.reverse();
}
removeFromArray(openSet, current);
closedSet.push(current);
var neighbors = current.neighbors;
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
//Mohamed Afrath: Check if neighbor is occupied by another car
let occupiedByCar = cars.some((car) => car.currentSpot === neighbor && !car.reached);
if (closedSet.includes(neighbor) || occupiedByCar || neighbor.type !== 'street') {
continue;
}
var g = current.g + gfn(neighbor, current);
var newPath = false;
if (openSet.includes(neighbor)) {
if (g < neighbor.g) {
neighbor.g = g;
newPath = true;
}
} else {
neighbor.g = g;
newPath = true;
openSet.push(neighbor);
}
if (newPath) {
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
//Mohamed Afrath: Set a limit to avoid infinite loops
maxIterations--;
if (maxIterations === 0) {
console.log(`Exceeded maximum iterations while finding path from (${start.i}, ${start.j}) to (${end.i}, ${end.j}). Stopping car.`);
return [];
}
}
return [];
}
// Draw function runs repeatedly to update the simulation.
// Updates car positions, renders the grid, and manages the pathfinding process.
function draw() {
let allCarsReached = true;
background(backgroundcolor);
for (var i = 0; i < cols; i++)
for (var j = 0; j < rows; j++) grid[i][j].show();
// Mohamed Afrath: Rendered start and end points for each car
for (let car of cars) {
fill(car.trailColor); // Set a bold color for the start
noStroke();
rect(car.start.i * w, car.start.j * h, w, h); // Fill the start point square
fill(0);
textSize(20);
textAlign(CENTER, CENTER);
text('S', car.start.i * w + w / 2, car.start.j * h + h / 2); // Label with "S"
// End point with bold background and "D" label
fill(car.trailColor); // Set a bold color for the end
noStroke();
strokeWeight(3);
rect(car.end.i * w, car.end.j * h, w, h);
fill(0);
text('D', car.end.i * w + w / 2, car.end.j * h + h / 2); // Label with "D"
}
// Mohamed Afrath: Updated car paths and positions, including collision detection and rerouting logic
for (let car of cars) {
if (car.end !== car.currentSpot) {
allCarsReached = false;
if (car.waitTimer > 0) {
car.waitTimer--;
continue;
}
if (car.pathAttempts >= 10) {
console.log(`Car ${car.carNumber} path cannot be found after 10 attempts. Stopping car.`);
car.waitTimer = Infinity; // Stop the car permanently
continue;
}
car.path = findPath(car.currentSpot, car.end, cars);
car.pathAttempts++;
if (car.path && car.path.length > 1) {
car.currentSpot = car.path[1]; // Move one step
car.trail.push({
x: car.currentSpot.i * w,
y: car.currentSpot.j * h
});
car.pathAttempts = 0;
} else {
console.warn(`Car ${car.carNumber} cannot find valid path to destination. Waiting!..`)
car.waitTimer = 2; // Wait for 2 frames if no valid path
}
}
}
//Rendered car trails and positions, including images for cars and flags
for (let car of cars) {
//Mohamed Afrath: Draw trail as a thin colored line
stroke(car.trailColor);
strokeWeight(10);
noFill();
beginShape();
for (let t of car.trail) {
vertex(t.x + w / 2, t.y + h / 2);
}
endShape();
// Asmitha Satesh: Draw car at its current position
if (car.end !== car.currentSpot) {
image(car.carImg, car.currentSpot.i * w, car.currentSpot.j * h, w, h);
} else {
if (!car.reached) {
console.log(`Car ${car.carNumber} has reached its destination.`);
car.reached = true;
}
// Asmitha Satesh: Rendered car trails and positions, including images for cars and flags
image(flagImg, car.end.i * w + w * 0.3, car.end.j * h + h * 0.3, w * 0.6, h * 0.7); // Display the flag
}
}
if (allCarsReached) {
noLoop();
console.log('All cars have reached their destinations.');
}
}