// Cloned by Isuru on 2 Nov 2024 from World "A star" by "Coding Train" project
// Please leave this clone trail here.
/**** A00014865 - Customized code ****/
// I have enclosed my customizations in this format.
// Name: T Mudiyanselage Isuru Chandana Bandara Tennakoon
// Student No: A00014865
/****************************/
// A00014865 - Also denoted some customizations in this format
// 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
// is diagonal move allowed
const diagonal = false; // A00014865 - Cars can't pass through walls
// canvas size
const cw = 900;
const ch = 600;
// How many columns and rows
// different each time
// MH edit
let rando = AB.randomIntAtoB(3, 5); // A00014865 - Make the grid not too small
// rando = 2;
let cols = 9 * rando;
let rows = 6 * rando;
/**** A00014865 - Minimum frequency of streets **/
const minHorizontalStreetAmount = 0.9;
const minVerticalStreetAmount = 0.95;
/****************************/
const backcolor = "white";
const wallcolor = "black";
const pathcolor = "darkred";
/**** A00014865 - Define different colors for destination of each car ****/
const endColor1 = "red";
const endColor2 = "purple";
const endColor3 = "orange";
const endColor4 = "green";
/****************************/
const opencolor = "lightgreen";
const closedcolor = "lightpink";
// 2D array
let grid = new Array(cols);
// Open and closed set
/**** A00014865 - Define open and closed sets for each car ****/
let openSet1 = [];
let closedSet1 = [];
let openSet2 = [];
let closedSet2 = [];
let openSet3 = [];
let closedSet3 = [];
let openSet4 = [];
let closedSet4 = [];
/*********** */
// Start and end
/**** A00014865 - Define start and end for each car ****/
let startCar1;
let endCar1;
let startCar2;
let endCar2;
let startCar3;
let endCar3;
let startCar4;
let endCar4;
/*********** */
// Width and height of each cell of grid
let w, h;
// The road taken
/**** A00014865 - Define path and completion status for each car ****/
let path1 = [];
let path2 = [];
let path3 = [];
let path4 = [];
let path1Complete = false;
let path2Complete = false;
let path3Complete = false;
let path4Complete = false;
/*********** */
let imgCar1;
let imgCar2;
let imgCar3;
let imgCar4;
let imgStreet;
let imgWall;
// A00014865 - Load the images.
function preload() {
imgCar1 = loadImage("/uploads/isuru/car_1.png");
imgCar2 = loadImage("/uploads/isuru/car_2.png");
imgCar3 = loadImage("/uploads/isuru/car_3.png");
imgCar4 = loadImage("/uploads/isuru/car_4.png");
imgStreet = loadImage("/uploads/isuru/street.png");
imgWall = loadImage("/uploads/isuru/wall.jpg");
}
//=== 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 (let 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?
// A00014865 - Allow 4 cars to claim a spot in their path
this.previous = [undefined, undefined, undefined, undefined];
// A00014865 - Is this spot a car?
this.isCar = undefined;
// A00014865 - Start with all walls
this.wall = true;
// Display me
this.show = function (col) {
if (this.wall) {
image(imgWall, this.i * w, this.j * h, w, h); // A00014865 - Draw wall image
} else if (!this.isCar && !this.wall) {
image(imgStreet, this.i * w, this.j * h, w, h); // A00014865 - Draw street image
}
if (col) {
fill(col);
rect(this.i * w, this.j * h, w, h);
}
};
/**** A00014865 - Draw car image ****/
this.showCar = function (img) {
image(img, this.i * w, this.j * h, w, h);
};
/*********** */
// Figure out who my neighbors are
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) {
// diagonals are also neighbours:
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() {
// slower frame rate to see how it is working
frameRate(5);
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);
/**** A00014865 - This portion was developed with the help of Perplexity AI ****/
// https://www.perplexity.ai/search/there-is-a-2d-js-array-contain-NjPdMbOqQ7W2jzvCk0_TEw.
// A00014865 - Create horizontal streets
for (let i = 0; i < cols; i += 3) {
for (let j = 0; j < rows; j++) {
if (AB.randomFloatAtoB(0, 1) < minHorizontalStreetAmount)
grid[i][j].wall = false; // Place streets
}
}
// A00014865 - Create vertical streets
for (let j = 0; j < rows; j += 6) {
for (let i = 0; i < cols; i++) {
if (AB.randomFloatAtoB(0, 1) < minVerticalStreetAmount)
grid[i][j].wall = false; // Place streets
}
}
/*********** */
// Start and end
/**** A00014865 - place start and end at random locations ****/
startCar1 =
grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
endCar1 = grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
startCar2 =
grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
endCar2 = grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
startCar3 =
grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
endCar3 = grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
startCar4 =
grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
endCar4 = grid[AB.randomIntAtoB(0, cols - 1)][AB.randomIntAtoB(0, rows - 1)];
/****************************/
/**** A00014865 - Make the start position a car. Make start and end part of streets ****/
startCar1.isCar = true;
startCar1.wall = false;
endCar1.wall = false;
startCar2.isCar = true;
startCar2.wall = false;
endCar2.wall = false;
startCar3.isCar = true;
startCar3.wall = false;
endCar3.wall = false;
startCar4.isCar = true;
startCar4.wall = false;
endCar4.wall = false;
/****************************/
// openSet starts with beginning only
/**** A00014865 - Push start position to openSet of each car ****/
openSet1.push(startCar1);
openSet2.push(startCar2);
openSet3.push(startCar3);
openSet4.push(startCar4);
/****************************/
console.log("start search");
}
function draw() {
/**** A00014865 - Move drawing background up so that it doesn't overwrite next car's path ****/
// Draw current state of everything
background(backcolor);
for (let i = 0; i < cols; i++)
for (let j = 0; j < rows; j++) grid[i][j].show();
/****************************/
/**** A00014865 - Update path completion status for each path ****/
while (!path1Complete || !path2Complete || !path3Complete || !path4Complete) {
if (!path1Complete) {
path1Complete = findPath(
openSet1,
closedSet1,
startCar1,
endCar1,
imgCar1,
endColor1,
path1,
0
);
}
if (!path2Complete) {
path2Complete = findPath(
openSet2,
closedSet2,
startCar2,
endCar2,
imgCar2,
endColor2,
path2,
1
);
}
if (!path3Complete) {
path3Complete = findPath(
openSet3,
closedSet3,
startCar3,
endCar3,
imgCar3,
endColor3,
path3,
2
);
}
if (!path4Complete) {
path4Complete = findPath(
openSet4,
closedSet4,
startCar4,
endCar4,
imgCar4,
endColor4,
path4,
3
);
}
}
/****************************/
/**** A00014865 - Move cars one step when all paths are complete ****/
if (path1Complete && path2Complete && path3Complete && path4Complete) {
console.log("All paths complete!");
// A00014865 - Reset f,g,h, and previous values for next path finding iteration
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
grid[i][j].f = 0;
grid[i][j].g = 0;
grid[i][j].h = 0;
grid[i][j].previous = [undefined, undefined, undefined, undefined];
}
}
// A00014865 - Make the previous spot not a car
startCar1.isCar = false;
startCar2.isCar = false;
startCar3.isCar = false;
startCar4.isCar = false;
// A00014865 - Move the start position to the next spot of the path
if (path1.length > 1) startCar1 = path1[path1.length - 2];
if (path2.length > 1) startCar2 = path2[path2.length - 2];
if (path3.length > 1) startCar3 = path3[path3.length - 2];
if (path4.length > 1) startCar4 = path4[path4.length - 2];
startCar1.isCar = true;
startCar2.isCar = true;
startCar3.isCar = true;
startCar4.isCar = true;
openSet1 = [startCar1];
closedSet1 = [];
openSet2 = [startCar2];
closedSet2 = [];
openSet3 = [startCar3];
closedSet3 = [];
openSet4 = [startCar4];
closedSet4 = [];
path1Complete = false;
path2Complete = false;
path3Complete = false;
path4Complete = false;
}
/****************************/
}
/**** A00014865 - Extracted path finding logic for reuse ****/
function findPath(
openSet,
closedSet,
start,
end,
carImg,
endColor,
path,
carId
) {
/**** A00014865 - Color end in different color ****/
end.show(endColor);
start.showCar(carImg);
/****************************/
let current;
// the search goes on over many timesteps
// each timestep, check one more square and draw current partial solution
// --- begin still searching -----------------------------
if (openSet.length > 0) {
// Best next option
let winner = 0;
for (let i = 0; i < openSet.length; i++)
if (openSet[i].f < openSet[winner].f) winner = i;
current = openSet[winner];
// Did I finish?
if (current === end) {
/**** A00014865 - Search complete. Path found. Draw the path ****/
// Find the path by working backwards
path.length = 0;
let temp = current;
while (temp) {
path.push(temp);
temp = temp.previous[carId];
}
for (let i = 0; i < path.length - 1; i++) path[i].show(endColor);
console.log("success - found path");
return true; // A00014865 - Search complete. Path found.
/****************************/
}
// Best option moves from openSet to closedSet
removeFromArray(openSet, current);
closedSet.push(current);
// Check all the neighbors
let neighbors = current.neighbors;
//--- start of for loop -----------
for (let i = 0; i < neighbors.length; i++) {
let neighbor = neighbors[i];
// Valid next spot?
// A00014865 - Added isCar check
if (!closedSet.includes(neighbor) && !neighbor.wall && !neighbor.isCar) {
let g = current.g + gfn(neighbor, current); // add up g values in cumulative way
// Is this a better path than before?
let 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[carId] = current; // A00014865 - Update the designated spot in the previous array
}
}
}
//--- end of for loop -----------
}
// --- end still searching -----------------------------
else {
console.log("fail - no path exists");
return true; // A00014865 - Search complete. Path not found
}
return false; // A00014865 - Search not complete yet
}
/****************************/