// Cloned by Tony Forde on 3 Nov 2021 from World "A star (clone by Tony Forde) (clone by Tony Forde)" by Tony Forde
// Please leave this clone trail here.
// Cloned by Tony Forde on 3 Nov 2021 from World "A star (clone by Tony Forde)" by Tony Forde
// Please leave this clone trail here.
const cols = 4;
const rows = 4;
const diagonal = false;
const speed = 10;
const percentageWalls = 0.2;
var grid = new Array(cols);
var openSet = []; // Unvisited nodes
var closedSet = []; // Visited nodes
var start; // Start
var end; // End
var path = []; // Path to goal
var currentSquare = 1;
var w; // Width
var h; // Height
var nextMovej;
var nextMovei;
function Spot(i, j) {
this.i = i;
this.j = j;
this.f = 0;
this.g = 0;
this.h = 0;
this.neighbors = []; // An array to store all neighbors of Spot
this.previous = undefined;
this.wall = false; // Add an obstacle. By default, every sppt added is NOT a wall.
// Set % number of wall spots and randomise
if (random(1) < percentageWalls) this.wall = true;
this.show = function (col) {
fill(col);
if (this.wall) fill(0); // Walls are black
noStroke();
//ellipse(this.i * w + w / 2, this.j * h + h / 2, w / 2, h / 2);
rect(this.i * w, this.j * h, w - 1, h - 1);
};
this.addNeighbors = function (grid) {
var i = this.i;
var j = this.j;
// Neighbors' comparative grid positions depend on where current node
// is on the grid, e.g. corner, edge, middle, etc... different options.
// Below allows for non-diagonal travel, i.e. it only caters for:
// 1. UP 2. DOWN 3. LEFT 4. RIGHT
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]);
// Below allows for non-diagonal travel, i.e. it also caters for:
// 5. TOP LEFT 6. TOP RIGHT 7. BOTTOM LEFT 8. BOTTOM RIGHT
if (diagonal) {
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() {
createCanvas(400, 400);
console.log("A*");
console.log("starting at square 1 and moving to...");
w = width / cols;
h = width / rows;
frameRate(speed);
// Making a 2D array
for (var i = 0; i < cols; i++) grid[i] = new Array(rows);
// Create a new object for each spot in the grid
// so we can assign some values to, i.e. f, g and h values for starters
for (var i = 0; i < cols; i++)
for (var j = 0; j < rows; j++) grid[i][j] = new Spot(i, j);
// Add the neighbors of the spot
for (var i = 0; i < cols; i++)
for (var j = 0; j < rows; j++) grid[i][j].addNeighbors(grid);
start = grid[2][3];
end = grid[1][1];
// start = grid[0][0];
// end = grid[cols - 1][rows - 1];
// Make sure start and end spots are never a wall
start.wall = false;
end.wall = false;
openSet.push(start);
console.log(grid);
}
function draw() {
if (openSet.length > 0) {
// While Open Set is not empty, keep going...
// console.log('Open set length = ' + openSet.length);
var winner = 0; // Set the lowest, i.e. WINNING, index
// Check which one is the lowest, i.e. current WINNER
for (var i = 0; i < openSet.length; i++)
if (openSet[i].f < openSet[winner].f) {
winner = i;
}
var current = openSet[winner];
// If current node equals END node, then we are done!
if (current === end) {
noLoop();
console.log("DONE!");
// console.log('Next Move - row / col: ' + nextMovej + ' ,' + nextMovei);
}
// Else continue below...
// Remove current node from Open Set
removeFromArray(openSet, current);
// And push current to Closed Set
closedSet.push(current);
// Evaluate all neighbors before pushing them to Open Set
var neighbors = current.neighbors;
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
// var newPath = false; // Default // TFXXXXXXXXXXXXX
// If Closed Set does NOT include the neighbor
// AND it is NOT a wall
if (!closedSet.includes(neighbor) && !neighbor.wall) {
// var tempG = current.g + 1; // TFXXXXXXXXXXXXX
var tempG = current.g + heuristic(neighbor, current); // TFXXXXXXXXXXXXX
var newPath = false; // Default // TFXXXXXXXXXXXXX
// Check if Open Set includes neighbor
if (openSet.includes(neighbor)) {
if (tempG < neighbor.g) {
neighbor.g = tempG;
newPath = true;
}
} else {
neighbor.g = tempG;
newPath = true;
openSet.push(neighbor);
}
if (newPath) {
// Only need to calulate heuristic if we've found a new path
// Now assign a heuristic value to the neighbor, i.e. distance to end goal:
neighbor.h = heuristic(neighbor, end);
// Now calculate f(n) = g(n) + h(n):
neighbor.f = neighbor.g + neighbor.h;
currentSquare++;
console.log("current winner is square " + winner + 1);
console.log("current winner has f(n) = " + openSet[winner].f);
console.log("now check square " + currentSquare + " where...");
console.log("g(" + currentSquare + ") = " + neighbor.g);
console.log("h(" + currentSquare + ") = " + neighbor.h);
console.log("f(" + currentSquare + ") = " + neighbor.f);
// Set current spot to be parent of the next one (in next for loop interation)
neighbor.previous = current;
}
}
}
// increase the g, i.e. distance from the start, for each additional neighbor
// Now add all neighbors of current ONLY IF they have not been visted before.
} else {
console.log("No solution.");
noLoop();
return;
// No solution
}
background(255);
for (var i = 0; i < cols; i++)
for (var j = 0; j < rows; j++) grid[i][j].show(color(255));
for (var i = 0; i < closedSet.length; i++)
closedSet[i].show(color(255, 0, 0));
for (var i = 0; i < openSet.length; i++) openSet[i].show(color(0, 255, 0));
path = [];
var temp = current;
path.push(temp);
while (temp.previous) {
// While there is a path history, i.e. previous node
path.push(temp.previous);
temp = temp.previous;
}
//for (var i = 0; i < path.length; i++) path[i].show(color(0, 0, 255));
// Draw path line
noFill();
stroke(255, 0, 200);
strokeWeight(w / 4);
beginShape();
for (var i = 0; i < path.length; i++) {
vertex(path[i].i * w + w / 2, path[i].j * h + h / 2);
}
for (var i = path.length-1; i >= 0; i--) {
console.log('Path - row, col: ' + path[i].j + ', ' + path[i].i);
var firstIndex = path.length - 1;
var nextMoveIndex;
//console.log('firstIndex: ' + firstIndex);
//console.log('Start - row / col: ' + path[firstIndex].j + ' ,' + path[firstIndex].i);
if (firstIndex > 0) {
nextMoveIndex = path.length - 2;
//console.log('nextMoveIndex: ' + nextMoveIndex);
nextMovej = path[nextMoveIndex].j;
nextMovei = path[nextMoveIndex].i;
//console.log('Next Move - row / col: ' + nextMovej + ' ,' + nextMovei);
}
console.log('*** Next Move - row / col: ' + nextMovej + ' ,' + nextMovei);
}
endShape();
}
function removeFromArray(arr, elt) {
// Custom function to remove an object from an array.
// Loop backwards through array.
// Only reason for going backwards is if we delete something it shortens the array length.
// So we could skip an element in the loop.
for (var i = arr.length - 1; i >= 0; i--) if (arr[i] == elt) arr.splice(i, 1); // Splice deletes a particular element in an array at an index
}
function heuristic(a, b) {
// Custom function to estimate distance from points a to b.
var d;
if (diagonal) {
// Calculate the Euclidean or 2D distance for diagonal search
d = dist(a.i, a.j, b.i, b.j);
} else {
// Calculate the "Manhattan" or "Taxi Cab" distance for non-diagonal search
d = abs(a.i - b.i) + abs(a.j - b.j);
}
return d;
}