// Cloned by Mervin Shibu George on 5 Nov 2024 from World "A star" by "Coding Train" project
// Please leave this clone trail here.
// flag for diagonal paths
const diagonal = true;
// canvas size
const cw = 600;
const ch = 600;
const GRIDSIZE = 16; // square grid of 16x16, can be reduced to something like 10x10 to see how cars react to other cars
var cols = GRIDSIZE;
var rows = GRIDSIZE;
const wallAmount = 0.8; // 80% of cells in a BLOCK of Street are wall
const backcolor = '#1C1C1C'; // color of the road
const wallcolor = '#A52A2A'; // color of buildings/walls
const CARCOUNT = 4; // number of cars, don't change it to more than 4 without adding more colors in carColors
// The road taken
var path = new Array(CARCOUNT); // array of paths to store path taken by each car
var traversedPath = new Array(CARCOUNT); // array of paths to keep a track of traversed path (for displaying the graphics)
// 2D array
var grid = new Array(cols);
// Start and end
var start = new Array(CARCOUNT); // array to store start points of each car
var end = new Array(CARCOUNT); // array to store destination points of each car
var carColors = ["blue", "red", "green", "purple"]; // color of cars based on index
// Width and height of each cell of grid
var w, h;
var calculateCount = 0; // just a variable to check how many times path was calculated in total for all cars
//=== heuristic ===========================
// this must be always optimistic - real time will be this or longer
function heuristic(a, b) {
if (diagonal) return (dist(a.i, a.j, b.i, b.j));
// 2D distance
// dist is a P5 function
else return (abs(a.i - b.i) + abs(a.j - b.j));
// else not diagonal, can only go across and down
// so this is optimistic
// note this is not optimistic if we can do diagonal move
}
//=== g function =======================================
// g function is known distance from start along a known path
// we work this out by adding up adjacent squares in a cumulative fashion
// note g definition should be separate from h definition (in earlier version they were confused)
function gfn(a, b) {
if (diagonal) return (dist(a.i, a.j, b.i, b.j)); // 2D distance
else return (abs(a.i - b.i) + abs(a.j - b.j)); // else go across and down
}
// Function to delete element from the array
function removeFromArray(arr, elt) {
// Could use indexOf here instead to be more efficient
for (var i = arr.length - 1; i >= 0; i--)
if (arr[i] == elt)
arr.splice(i, 1);
}
// 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
// An object to describe a spot in the grid
function Spot(i, j) {
// Location
this.i = i;
this.j = j;
// f, g, and h values for A*
this.f = 0;
this.g = 0;
this.h = 0;
// Neighbors
this.neighbors = [];
// Where did I come from?
this.previous = new Array(CARCOUNT); // since there are 4 cars, this array will have 4 elements, one for each car
// Deciding if node is a wall
// to make blocks in street, every 4th and 5th coordinate (horizontal or vertical) will always be road
// rest of the coordinates form the blocks. 80% of cells in a BLOCK of Street are wall by default (decided by wallAmount)
if (i % 5 == 3 || i % 5 == 4 || j % 5 == 3 || j % 5 == 4) {
this.wall = false
} else if (random(1) < wallAmount) {
this.wall = true;
} else {
this.wall = false;
}
// Display me
this.show = function (col, shape) {
if (this.wall) {
fill(wallcolor);
noStroke();
// wall fills square
rect(this.i * w, this.j * h, w, h);
// wall only partially fills square
// ellipse ( this.i * w + w / 2, this.j * h + h / 2, w * 0.7, h * 0.7 );
}
else if (col) {
strokeWeight(0);
fill(this.specialColor ?? col); // specialColor is only set for start and end points
if (shape == "ellipse") {
stroke("white");
strokeWeight(this.specialColor ? 2 : 0); // highlighting car with a stroke if it's inside a start or end point
ellipse(this.i * w + w / 2, this.j * h + h / 2, w * 0.7, h * 0.7);
} else {
rect(this.i * w, this.j * h, w, h);
}
}
};
// Figure out who my neighbors are
this.addNeighbors = function (grid) {
var i = this.i;
var 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]);
// diagonals are also neighbours:
// Added extra condition to make sure the car doesn't travel through 0 width corners, i.e., in between 2 walls that are connected by a corner
if (diagonal)
{
if (i > 0 && j > 0 && !(grid[i][j - 1].wall || grid[i - 1][j].wall)) this.neighbors.push(grid[i - 1][j - 1]);
if (i < cols - 1 && j > 0 && !(grid[i][j - 1].wall || grid[i + 1][j].wall)) this.neighbors.push(grid[i + 1][j - 1]);
if (i > 0 && j < rows - 1 && !(grid[i][j + 1].wall || grid[i - 1][j].wall)) this.neighbors.push(grid[i - 1][j + 1]);
if (i < cols - 1 && j < rows - 1 && !(grid[i][j + 1].wall || grid[i + 1][j].wall)) this.neighbors.push(grid[i + 1][j + 1]);
}
}
}
// Setting up the grid and precalculating the path of each car with A*
// All the path calculation along with resolving conflicts between car is done by the setup function
// draw function is only used to display the grid frame by frame
function setup() {
// MH edit
// slower frame rate to see how it is working
frameRate(3);
createCanvas(cw, ch);
// Grid cell size
w = width / cols;
h = height / rows;
// Making a 2D array
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);
// All the neighbors
for (let i = 0; i < cols; i++)
for (let j = 0; j < rows; j++)
grid[i][j].addNeighbors(grid);
let occupied = new Set(); // a container to keep track of all start and end points to avoid duplicates
for (let i = 0; i < CARCOUNT; i++) {
//generating 4 random start and end points for each car without duplicates
do {
start[i] = grid[AB.randomIntAtoB(0, GRIDSIZE - 1)][AB.randomIntAtoB(0, GRIDSIZE - 1)];
} while (occupied.has(start[i]));
occupied.add(start[i]);
do {
end[i] = grid[AB.randomIntAtoB(0, GRIDSIZE - 1)][AB.randomIntAtoB(0, GRIDSIZE - 1)];
} while (occupied.has(end[i]));
occupied.add(end[i]);
//setting start and end points as non-walls, in case the randomly generated start and end points are on a wall
start[i].wall = false;
end[i].wall = false;
//setting the specialColor attribute to the start and end points
start[i].specialColor = carColors[i];
end[i].specialColor = carColors[i];
//generating path for ith car, ith car only treats cars 0 to i-1 as obstacles
path[i] = getPathWrapper(start[i], end[i], i, [], 0);
// initializing ith traversedPath to empty array to be used in the draw function
traversedPath[i] = [];
}
console.log("times calculated = ", calculateCount);
}
// This is the wrapper of getPath() function. This function recursively calculates new paths until there is no conflict
function getPathWrapper(start, end, index, holder, maxLength = 0) {
if (maxLength == 100) { // preventing infinite loop, if the car is stuck and has never reached the destination
return [];
}
let currentPath = getPath(start, end, index);
let hasConflict = false;
// checking conflicts with previous cars' paths
// this is kinda like a priority path finding, the 0th index car has highest priority
// hence it doesn't reroute its path to accomodate for other cars
for (let i = 0; i < index; i++) {
if (getConflict(currentPath, path[i])) {
hasConflict = true;
break;
}
}
if (!hasConflict) {
return holder.concat(currentPath);
}
// setting the nodes where the cars are going to be in the next 2 frames as walls
let currentFrame = holder.length + 1;
for (let i = 0; i < index; i++) {
try {
path[i][Math.min(currentFrame, path[i].length - 1)].wall = true;
path[i][Math.min(currentFrame + 1, path[i].length - 1)].wall = true;
} catch (error) {
console.info(`Couldn't setting 'wall' property at i = ${i}, currentFrame = ${currentFrame}`);
console.info("Previous path empty, path[i] = ", path[i]);
}
}
currentPath = getPath(start, end, index); // calculating new path based on the newly set walls
// resetting the nodes where the cars are going to be in the next 2 frames as not walls
for (let i = 0; i < index; i++) {
try {
path[i][Math.min(currentFrame, path[i].length - 1)].wall = false;
path[i][Math.min(currentFrame + 1, path[i].length - 1)].wall = false;
} catch (error) {
console.info(`Couldn't setting 'wall' property at i = ${i}, currentFrame = ${currentFrame}`);
console.info("Previous path empty, path[i] = ", path[i]);
}
}
if (currentPath.length == 0 || currentPath.length == 1) {
return getPathWrapper(start, end, index, holder.concat(start), maxLength + 1);
}
if (currentPath[1] == end) {
return holder.concat([start, currentPath[1]]);
} else {
return getPathWrapper(currentPath[1], end, index, holder.concat(start), maxLength + 1);
}
}
// A* algorithm to find path. Function returns the path of indexth car from start to end
function getPath(start, end, index) {
calculateCount += 1;
let openSet = [start], closedSet = [], path = [];
while (openSet.length > 0) {
// Best next option
var winner = 0;
for (var i = 0; i < openSet.length; i++)
if (openSet[i].f < openSet[winner].f)
winner = i;
var current = openSet[winner]; // openset[winner] will have lowest f in all nodes of openset
// Did I finish?
if (current === end) {
break;
}
// Best option moves from openSet to closedSet
removeFromArray(openSet, current);
closedSet.push(current);
// Check all the neighbors
var neighbors = current.neighbors;
//--- start of for loop -----------
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
// Valid next spot?
if (!closedSet.includes(neighbor) && !neighbor.wall) {
var g = current.g + gfn(neighbor, current); // add up g values in cumulative way
// Is this a better path than before?
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);
}
// Yes, it's a better path
if (newPath) {
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous[index] = current;
}
}
}
//--- end of for loop -----------
}
// Find the path by working backwards
let currentPath = [];
if (current != end) {
return [];
}
var temp = current;
currentPath.push(temp);
while (temp.previous[index]) {
currentPath.push(temp.previous[index]);
temp = temp.previous[index];
}
currentPath.reverse(); // reversed to get the path in correct order (starting node is first in array and ending node is last in array)
for (let i = 0; i < grid.length; i++) {
// resetting the previous array so the current path calculation doesn't mess with
// any future path calculations with different obstacles (moving cars)
for (let j = 0; j < grid[i].length; j++) {
grid[i][j].previous[index] = undefined;
}
}
return currentPath;
}
//returns true if there is car on path p1 conflicts with car on path p2
function getConflict(p1, p2) { // p1 and p2 are 2 path arrays
for (let i = 0; i < p1.length; i++) {
for (let j = 0; j < p2.length; j++) {
if (p1[i] == p2[j])
return true;
//if p1 passed through p2 and p2 passed through p1
if (p1[i + 1] == p2[j] && p2[j + 1] == p1[i])
return true;
}
}
return false;
}
function draw()
{
// Draw current state of everything
background(backcolor);
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
if (start.includes(grid[i][j])) { // displaying start node with appropriate color
grid[i][j].show(carColors[start.indexOf(grid[i][j])]);
} else if (end.includes(grid[i][j])) { // displaying end node with appropriate color
grid[i][j].show(carColors[end.indexOf(grid[i][j])]);
} else {
grid[i][j].show();
}
for (let p = 0; p < path.length; p++) { // displaying cars as circle (ellipse) with appropriate color
if (traversedPath[p].length < path[p].length && path[p][traversedPath[p].length] == grid[i][j]) {
grid[i][j].show(carColors[p], "ellipse");
} else if (traversedPath[p].length >= path[p].length && path[p][path[p].length - 1] == grid[i][j]) {
grid[i][j].show(carColors[p], "ellipse");
}
}
}
}
// pushing the current state each car path to traversedPath
for (let p = 0; p < path.length; p++) {
if (traversedPath[p].length < path[p].length)
traversedPath[p].push(path[p][traversedPath[p].length]);
}
// displaying the traversed paths of every car
for (let p = 0; p < traversedPath.length; p++) {
noFill();
stroke(carColors[p]);
strokeWeight(w / 6);
beginShape();
for (let i = 0; i < traversedPath[p].length; i++)
vertex((traversedPath[p][i].i * w) + w / 2, (traversedPath[p][i].j * h) + h / 2);
endShape();
}
}