const gridsize = 25;
var cols = gridsize;
var rows = gridsize;
var grid = new Array(cols);
var openSet = [];
var closedSet = [];
var enemy;
var neighbors;
var agent;
var current;
var lowestF;
var w, h;
var k = 0;
var l = 0;
// optimal path
var path = [];
// can find more optimal way of doing this
function removeFromArray(arr, element) {
const index = arr.indexOf(element);
if (index !== -1) {
arr.splice(index, 1);
}
}
function getRandomenemyAndagent(cols, rows, grid) {
let enemy, agent;
do {
enemy = grid[AB.randomIntAtoB(1, cols - 2)][AB.randomIntAtoB(1, rows - 2)];
agent = grid[AB.randomIntAtoB(1, cols - 2)][AB.randomIntAtoB(1, rows - 2)];
} while (enemy.wall || agent.wall || enemy === agent);
enemy.wall = false;
agent.wall = false;
return [enemy, agent];
}
// for project a = enemy, b = agent
function heuristic(a, b){
/*
// Euclidean Distance - better for diagonals
var d = dist(a.i, a.j, b.i, b.j);
return d;
*/
// Manhattan Distance - better for no diagonals
var d = abs(a.i-b.i) + abs(a.j-b.j);
return d;
}
function createGrid(){
for (var i = 0; i < cols; i++){
grid[i] = new Array(rows);
}
}
function createSpots(){
// create Spots -> find where to implement in complex world
for (var i = 0; i < cols; i++){
for (var j = 0; j < rows; j++){
grid[i][j] = new Spot(i, j);
}
}
}
function createNeighbors(){
// create neighbors
for (var i = 0; i < cols; i++){
for (var j = 0; j < rows; j++){
grid[i][j].addNeighbors(grid);
}
}
}
function moveAgent() {
let neighbors = agent.neighbors;
let possibleMoves = neighbors.filter(neighbor => !neighbor.wall);
if (possibleMoves.length > 0) {
// Randomly choose a free neighboring spot
let nextMove = possibleMoves[Math.floor(Math.random() * possibleMoves.length)];
agent = nextMove; // Update the agent's position
}
}
function findLowestFvalue(){
winner = 0;
for (var i = 0; i < openSet.length; i++){
if (openSet[i].f < openSet[winner].f){
winner = i;
}
}
return winner;
}
function findCurrentNeighbors(current, neighbors){
for (var i = 0; i < neighbors.length; i++){
var neighbor = neighbors[i];
// if neighbor not in closed set and not an obstacle, proceed with more checks
if (!closedSet.includes(neighbor) && !neighbor.wall){
var tempG = current.g + 1;
// if neighbor already in open set, check if the new g value is lower than the previous one
var newPath = false;
if (openSet.includes(neighbor)){
// if the new g is lower, change
if (tempG < neighbor.g){
neighbor.g = tempG;
newPath = true;
}
} else{
neighbor.g = tempG;
newPath = true;
openSet.push(neighbor);
}
// does not need to happen again if we did not find a new, better g
if (newPath){
neighbor.h = heuristic(neighbor, agent);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
}
}
function findPath(current) {
path = [];
var temp = current;
while (temp !== enemy) {
path.push(temp);
if (!temp.previous) {
console.error("No previous node found; breaking loop");
break; // Break the loop if previous node is not found
}
temp = temp.previous;
}
path.reverse();
}
function aStarAlgorithm(){
console.log("OpenSet:", openSet);
while (openSet.length > 0) {
// Find the node in openSet with the lowest f value
var winner = findLowestFvalue();
var current = openSet[winner];
console.log("Current: ", current);
// If the current node is the agent, the path has been found
if (current === agent) {
// Construct the path from agent to enemy
findPath(current);
return path; // Path found, exit the function
}
// Move the current node from openSet to closedSet
removeFromArray(openSet, current);
closedSet.push(current);
// Check each neighbor of the current node
var neighbors = current.neighbors;
console.log("Neighbors: ", neighbors);
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
// If neighbor is not in closedSet and not a wall
if (!closedSet.includes(neighbor) && !neighbor.wall) {
var tempG = current.g + heuristic(neighbor, current);
// Check if new path to neighbor is shorter
var newPath = false;
if (openSet.includes(neighbor)) {
if (tempG < neighbor.g) {
neighbor.g = tempG;
newPath = true;
}
} else {
neighbor.g = tempG;
newPath = true;
openSet.push(neighbor);
}
if (newPath) {
neighbor.h = heuristic(neighbor, agent);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
}
}
// No solution
console.log('no solution');
noLoop();
return [];
}
function displayGrid(){
background(0);
// white background
for (var i = 0; i < cols; i++){
for (var j = 0; j < rows; j++){
grid[i][j].show(color(255));
}
}
// display open and closed set
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));
}
// display path
for (var i = 0; i < path.length; i++){
path[i].show(color(0, 0, 255));
}
// display enemy and agent spot
enemy.show(color(255, 77, 255));
agent.show(color(0, 150, 150));
}
function isOccupied(i, j){
if (i === 0 || i === cols - 1 || j === 0 || j === rows - 1){
return true;
}
else{
return random(1) < 0.1;
}
}
function Spot(i, j){
this.i = i;
this.j = j;
this.f = 0;
this.g = 0;
this.h = 0;
this.neighbors = [];
this.previous = undefined;
this.wall = isOccupied(this.i, this.j);
this.show = function(col){
fill(col);
if (this.wall){
fill(0);
}
noStroke();
rect(this.i * w, this.j * h, w - 1, h - 1);
}
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]);
}
/*
// adding diagonals
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 moveAgent() {
let neighbors = agent.neighbors;
let possibleMoves = neighbors.filter(neighbor => !neighbor.wall);
if (possibleMoves.length > 0) {
let nextMove = possibleMoves[Math.floor(Math.random() * possibleMoves.length)];
agent = nextMove; // Update the agent's position
}
}
//---- normal P5 code -------------------------------------------------------
function setup()
{
createCanvas(400, 400);
frameRate(2);
console.log('A*')
w = width / cols;
h = height / rows;
createGrid();
console.log("Grid has been created");
console.log(grid);
createSpots();
console.log("Spots have been created");
console.log(grid);
createNeighbors();
console.log("Neighbors have been created");
console.log(grid);
// initialising enemy point and goal
// Randomly initialize enemy and agent points
[enemy, agent] = getRandomenemyAndagent(cols, rows, grid);
// push enemy node to openset
//openSet.push(enemy);
//console.log(grid);
}
function draw() {
// Always recalculate the path
openSet = [];
closedSet = [];
openSet.push(enemy);
console.log("Enemy: ", enemy);
path = aStarAlgorithm(); // Recalculate the path
// Move enemy if the path is available and has more than one node
if (path && path.length > 1) {
enemy = path[0]; // Move to the next position on the path
}
moveAgent();
// Display all elements of the grid
displayGrid();
}