// Cloned by Tristan Everitt on 18 Oct 2022 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
const useHeuristic = true; // false: h(n) = 0
const bestFirst = true; // true: f(n) = h(n); false: f(n) = g(n) + h(n)
// is diagonal move allowed
const diagonal = true;
const useWalls = true;
const white = false;
const rand = true;
const randomLowerBound = 1;
const randomUpperBound = 20;
const fixedRando = 50;
const wallAmountLower = 0;
const wallAmountUpper = 0.6;
const frameRateValue = 0; // 0 = Use defaults; 1= very slow
// canvas size
const cw = 900;
const ch = 600;
// How many columns and rows
// different each time
let rando = rand ? AB.randomIntAtoB(randomLowerBound, randomUpperBound) : fixedRando;
let cols = 9 * rando;
let rows = 6 * rando;
// how many walls to make, from 0 to 1
// different each time
const wallAmount = useWalls ? AB.randomFloatAtoB(wallAmountLower, wallAmountUpper) : 0;
const backcolor = 'white';
const wallcolor = 'black';
const pathcolor = 'darkred';
const opencolor = white ? 'white' : 'lightgreen';
const closedcolor = white ? 'white' : 'lightpink';
// 2D array
let grid = new Array(cols);
// Open and closed set
let openSet = [];
let closedSet = [];
// Start and end
let start;
let end;
// Width and height of each cell of grid
let w, h;
// The road taken
let path = [];
//=== heuristic ===========================
// this must be always optimistic - real time will be this or longer
function heuristic(a, b) {
if (useHeuristic) {
return diagonal ? dist(a.i, a.j, b.i, b.j) : abs(a.i - b.i) + abs(a.j - b.j);
} else {
return 0;
}
// 2D distance
// dist is a P5 function
// else not diagonal, can only go across and down
// so this is optimistic
// note this is not optimistic if we can do diagonal move
}
// 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);
// }
//}
arr.splice(arr.indexOf(elt), 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 = undefined;
// Am I an wall?
this.wall = random(1) < wallAmount;
// Display me
this.show = function (col) {
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) {
fill(col);
rect(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
if (frameRateValue) {
frameRate(frameRateValue);
}
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);
}
}
// Start and end
start = grid[0][0];
end = grid[cols - 1][rows - 1];
start.wall = false;
end.wall = false;
// openSet starts with beginning only
openSet.push(start);
console.log('start search');
}
function draw()
// the search goes on over many timesteps
// each timestep, check one more square and draw current partial solution
{
let current;
// --- begin still searching -----------------------------
if (openSet.length > 0) {
// Best next option
let winner = 0;
for (let i = 0; i < openSet.length; i++) {
winner = openSet[i].f < openSet[winner].f ? i : winner;
}
current = openSet[winner];
// Did I finish?
if (current === end) {
noLoop();
console.log("success - found path");
}
// 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 -----------
neighbors.forEach(neighbor => {
// Valid next spot?
if (!closedSet.includes(neighbor) && !neighbor.wall) {
const tempG = (bestFirst ? 0 : current.g) + heuristic(neighbor, current);
// Is this a better path than before?
let newPath = false;
if (openSet.includes(neighbor)) {
if (tempG < neighbor.g) {
neighbor.g = tempG;
newPath = true;
}
} else {
neighbor.g = tempG;
newPath = true;
openSet.push(neighbor);
}
// Yes, it's a better path
if (newPath) {
neighbor.h = heuristic(neighbor, end);
neighbor.f = (bestFirst ? 0 : neighbor.g) + neighbor.h;
neighbor.previous = current;
}
}
});
//--- end of for loop -----------
}
// --- end still searching -----------------------------
else {
console.log('fail - no path exists');
noLoop();
return;
}
// 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();
}
}
closedSet.forEach(item => {
item.show(closedcolor);
});
openSet.forEach(item => {
item.show(opencolor);
});
// Find the path by working backwards
path = [];
let temp = current;
path.push(temp);
while (temp.previous) {
path.push(temp.previous);
temp = temp.previous;
}
if (diagonal) {
// path as continuous line
noFill();
stroke(pathcolor);
strokeWeight(w / 8);
beginShape();
path.forEach(item => {
vertex((item.i * w) + w / 2, (item.j * h) + h / 2);
});
endShape();
} else {
// path as solid blocks
path.forEach(item => {
item.show(pathcolor);
});
}
}