// Clone by Akshat Sen of:
// "4-Agent A Star" by Aaqid Masoodi
// https://ancientbrain.com/world.php?world=5488323698
// Please leave this clone trail here.
// This work builds on top MY original draft in python Pygame/OpenGL project
// You can view that project from the link below...
// https://github.com/aaqidmasoodi/A-Star-Python
// SUGGESTION
// The world generation is entirely randomized, so I recommend reloading the world a few times
// until you find a scenario with many intersecting paths.
// This way, you'll observe a lot of rerouting in action.
// Also, set the frame rate (FRAMES_PER_SECOND) really low (like 3 or 6) for better visibility!
let grid;
let turn = 1;
//====== T BOX =========
// MH edit
let FRAMES_PER_SECOND = 10; // 6
let rows = 25;
let cols = 25;
let windowSize = 800;
let cellSize = windowSize / Math.max(rows, cols);
let debug = false;
// ======= END T BOX ============
let agents = [];
let destinations = [];
let AB_MESSAGE_BOX = [];
let images = {};
// i am using this variable to choose path color.. don't touch this one...
let path = [];
let path_color = null;
// Load different images for each agent and with each goal
// "Red(1)", "Purple(2)", "Yellow(3)", "Green(4)"
function preload() {
// images.agent = loadImage('/uploads/infinitebutdiscrete/ufored.png');
images.agent_red = loadImage('/uploads/infinitebutdiscrete/AgentRed.png');
images.agent_purple = loadImage('/uploads/infinitebutdiscrete/AgentPurple.png');
images.agent_yellow = loadImage('/uploads/infinitebutdiscrete/AgentYellow.png')
images.agent_green = loadImage('/uploads/infinitebutdiscrete/AgentGreen.png');
// images.goal = loadImage('/uploads/infinitebutdiscrete/goal_flag.png');
images.goa_red = loadImage('/uploads/infinitebutdiscrete/GoalFlagRed.png');
images.goa_purple = loadImage('/uploads/infinitebutdiscrete/GoalFlagPurple.png');
images.goa_yellow = loadImage('/uploads/infinitebutdiscrete/GoalFlagYellow.png');
images.goa_green = loadImage('/uploads/infinitebutdiscrete/GoalFlagGreen.png');
// House Type 1 with different Rotations
images.obstacle_House1N = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType1N.png');
images.obstacle_House1R90 = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType1R90.png');
images.obstacle_House1L90 = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType1L90.png');
images.obstacle_House1180 = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType1180.png');
// House Type 2
images.obstacle_House2N = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType2N.png');
images.obstacle_House2R90 = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType2R90.png');
images.obstacle_House2L90 = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType2L90.png');
images.obstacle_House2180 = loadImage('/uploads/infinitebutdiscrete/ObstacleHouseType2180.png');
// ------------
images.obstacle_tree = loadImage('/uploads/infinitebutdiscrete/ObstacleTree.png');
images.street = loadImage('/uploads/infinitebutdiscrete/sandStreet.png');
}
function setup() {
createCanvas(windowSize, windowSize);
frameRate(FRAMES_PER_SECOND);
// Create Grid
grid = new Grid(rows, cols);
// Populate the Grid with Walls and Bushes
grid.populate();
// I pre-compute the neighbours so that i do not have to do it on the fly... makes the whole thing faster
// [Idea Credit: The Coding Train]
grid.computeAndAddSpotNeighbours();
// Initialize agents with random positions and goals
// DO NOT CHANGE AGENT NUMBER
for (let i = 0; i < 4; i++) {
let agent = new Agent(grid);
if (debug) console.log(`Agent create with i = ${agent.i} and j = ${agent.j}`)
agents.push(agent);
agent.startSpot.wall = false;
agent.startSpot.agent = agent;
agent.endSpot.wall = false;
destinations.push(agent.endSpot);
}
}
// p5.js draw loop
// Main loop
function draw() {
// I've created a message box array to which i am pushing messages that might be useful.
// Have to do it this way due to how the AB messaging system works (clearing previous context after each message)
AB.msg(AB_MESSAGE_BOX);
// Each agent takes turns moving
// If you put it one after the other.. without them taking turns
// everything break... you'd assume that each function runs consecutively and it shouldn't cause any problems.. but..
// i don't know why it doesnt..
switch (turn % 4) {
case 1:
moveAgent(agents[0], agents[0].startSpot, agents[0].endSpot);
break;
case 2:
moveAgent(agents[1], agents[1].startSpot, agents[1].endSpot);
break;
case 3:
moveAgent(agents[2], agents[2].startSpot, agents[2].endSpot);
break;
case 0:
moveAgent(agents[3], agents[3].startSpot, agents[3].endSpot);
break;
}
grid.show();
turn++;
}
// Function to move each agent towards its goal
/* The sole purpose of this function is to compute the path for
a particular agent and make the agent move one step. Once the agent computes the path,
the Spots in the grid will chagne f, g, and h values and there i also call grid.clear() after getting the path
with clears the entire grid back to all 0s.
*/
function moveAgent(agent, start, end) {
if (agent.i !== end.i || agent.j !== end.j) {
path = agent.getPath(start, end);
path_color = agent.color; // setting path color so that i can have different path colors.. again.. better not touch this one.
grid.clear();
if (path.length > 1) {
// first shift will get rid of the spot where the agent is right now..
start = path.shift();
// this is the spot we need .. the next spot..
start = path.shift();
agent.moveOneStep(start);
}
} else {
// ${agent.color == "Yellow" ? "Orange" : agent.color}
// Yellow looks almost invisible on white background...
// that's why i have to set it to orange
let log_message_destination = `Agent <b style="color: ${agent.color == "Yellow" ? "Orange" : agent.color};">${agent.color}</b> reached Destination.<br>`;
if (!AB_MESSAGE_BOX.includes(log_message_destination))
AB_MESSAGE_BOX.push(log_message_destination);
}
}
const wallImageTypes = [
"H1N", "H1R90", "H1L90", "H1180",
"H2N", "H2R90", "H2L90", "H2180"
]
// Spot class
class Spot {
constructor(i, j) {
this.i = i;
this.j = j;
this.f = 0;
this.g = 0;
this.h = 0;
this.destination_color = null;
this.neighbours = [];
this.previous = null;
// this.wall = random() < 0.25;
this.wall = false;
this.wallImage = wallImageTypes[Math.floor(Math.random() * wallImageTypes.length)]
// console.log(this.wallImage)
this.bush = false;
this.agent = false;
}
draw() {
let x = this.i * cellSize;
let y = this.j * cellSize;
noStroke();
if (path.includes(this)) {
if (path_color == "Red") {
fill(255, 127, 127);
} else if (path_color == "Purple") {
// 177, g: 156, b: 217
fill(177, 156, 217);
} else if (path_color == "Yellow") {
// r: 255, g: 255, b: 237
fill(255, 255, 160);
} else if (path_color == "Green") {
// r: 144, g: 238, b: 144
fill(144, 238, 144);
}
rect(x, y, cellSize, cellSize);
} else if (this.agent) {
// console.log(this.agent.color);
switch (this.agent.color) {
case "Red":
image(images.agent_red, this.agent.i * cellSize, this.agent.j * cellSize, cellSize, cellSize);
break;
case "Purple":
image(images.agent_purple, this.agent.i * cellSize, this.agent.j * cellSize, cellSize, cellSize);
break;
case "Yellow":
image(images.agent_yellow, this.agent.i * cellSize, this.agent.j * cellSize, cellSize, cellSize);
break;
case "Green":
image(images.agent_green, this.agent.i * cellSize, this.agent.j * cellSize, cellSize, cellSize);
break;
}
}
else if (destinations.includes(this)) {
switch(this.destination_color) {
case "Red":
image(images.goa_red, x, y, cellSize, cellSize);
break;
case "Purple":
image(images.goa_purple, x, y, cellSize, cellSize);
break;
case "Yellow":
image(images.goa_yellow, x, y, cellSize, cellSize);
break;
case "Green":
image(images.goa_green, x, y, cellSize, cellSize);
break;
}
} else if (this.bush) {
image(images.obstacle_tree, x, y, cellSize, cellSize);
}
else if (this.wall) {
switch (this.wallImage) {
case "H1N":
image(images.obstacle_House1N, x, y, cellSize, cellSize);
break;
case "H1R90":
image(images.obstacle_House1R90, x, y, cellSize, cellSize);
break;
case "H1L90":
image(images.obstacle_House1L90, x, y, cellSize, cellSize);
break;
case "H1180":
image(images.obstacle_House1180, x, y, cellSize, cellSize);
break;
case "H2N":
image(images.obstacle_House2N, x, y, cellSize, cellSize);
break;
case "H2R90":
image(images.obstacle_House2R90, x, y, cellSize, cellSize);
break;
case "H2L90":
image(images.obstacle_House2L90, x, y, cellSize, cellSize);
break;
case "H2180":
image(images.obstacle_House2180, x, y, cellSize, cellSize);
break;
// default:
// image(images.obstacle_House1180, x, y, cellSize, cellSize);
// break;
}
} else if (this.bush) {
image(images.obstacle_tree, x, y, cellSize, cellSize);
} else {
image(images.street, x, y, cellSize, cellSize);
}
}
}
// Grid class
class Grid {
constructor(rows, cols) {
this.rows = rows;
this.cols = cols;
this.spots = new Array(rows).fill().map(() => new Array(cols));
}
// Populate the grid with walls and streets.
populate() {
let blockSize = 3; // Size of each building block
let streetWidth = 1; // Width of the streets
for (let i = 0; i < this.rows; i++) {
for (let j = 0; j < this.cols; j++) {
let spot = new Spot(i, j);
// Create wider streets and thicker building blocks
if ((i % blockSize < streetWidth) || (j % blockSize < streetWidth)) {
spot.wall = random() > 0.9; // Streets
} else {
if (random() > 0.4) {
spot.wall = true; // Building walls
} else {
spot.bush = true; // this is to replace the image of the wall to a bush
spot.wall = true; // wall must also be true
}
}
// add spot to the grid
this.spots[i][j] = spot;
}
}
}
// will add neighbours of each Spot.
computeAndAddSpotNeighbours() {
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
let spot = this.spots[i][j];
if (i > 0) spot.neighbours.push(this.spots[i - 1][j]);
if (i < cols - 1) spot.neighbours.push(this.spots[i + 1][j]);
if (j > 0) spot.neighbours.push(this.spots[i][j - 1]);
if (j < rows - 1) spot.neighbours.push(this.spots[i][j + 1]);
// console.log(i)
}
}
}
show() {
for (let i = 0; i < this.rows; i++) {
for (let j = 0; j < this.cols; j++) {
this.spots[i][j].draw();
}
}
}
clear() {
for (let row of this.spots) {
for (let spot of row) {
spot.f = spot.g = spot.h = 0;
spot.previous = null;
}
}
}
static heuristic(spot1, spot2) {
return abs(spot1.i - spot2.i) + abs(spot1.j - spot2.j);
}
}
colors = ["Red", "Purple", "Yellow", "Green"]
let i = 0
// Agent class
class Agent {
constructor(grid) {
this.grid = grid;
this.i = floor(random(rows));
this.j = floor(random(cols));
this.startSpot = grid.spots[this.i][this.j];
this.endSpot = grid.spots[floor(random(rows))][floor(random(cols))];
this.openSet = [];
this.closedSet = [];
this.color = colors[i];
this.endSpot.destination_color = this.color;
// console.log(`Destination color for agent ${this.color} is ${this.endSpot.destination_color}`)
i++;
}
getPath(start, destination) {
if (debug) console.log("Get path was called..");
this.path = [];
this.openSet = [start];
this.closedSet = [];
start.g = 0;
start.h = Grid.heuristic(start, destination);
start.f = start.g + start.h;
while (this.openSet.length > 0) {
// Finds the node in openSet with the lowest f-score (estimated total cost)
let current = this.openSet[0]; // Assume the first element has the lowest f-score
for (let node of this.openSet) {
if (node.f < current.f) {
current = node; // Update current if a node with a lower f-score is found
}
}
if (current === destination) {
this.path = [];
while (current) {
this.path.push(current);
current = current.previous;
}
this.path.reverse();
return this.path;
}
this.openSet = this.openSet.filter(s => s !== current);
this.closedSet.push(current);
for (let neighbor of current.neighbours) {
if (!this.closedSet.includes(neighbor) && !neighbor.wall && !neighbor.agent) {
let tempG = current.g + 1;
if (!this.openSet.includes(neighbor) || tempG < neighbor.g) {
neighbor.previous = current;
neighbor.g = tempG;
neighbor.h = Grid.heuristic(neighbor, destination);
neighbor.f = neighbor.g + neighbor.h;
if (!this.openSet.includes(neighbor)) {
this.openSet.push(neighbor);
}
}
}
}
}
if (debug) console.log("No Path was found...");
return [];
}
moveOneStep(step) {
let { i, j } = step;
// console.log(step);
this.grid.spots[this.i][this.j].agent = null;
this.i = i;
this.j = j;
this.startSpot = grid.spots[this.i][this.j]
this.grid.spots[i][j].agent = this;
}
}