//This is a car that can achieve "self-driving" and can avoid other cars on the road!
/*Comment*/
/*I didn't do it based on Astar because I wanted to make a new map,
and my mission has four targets, which might require modifying a lot of code,
so I thought it would be better to make a new one.*/
/*Reference*/
//About map
//https://www.youtube.com/watch?app=desktop&v=sN7JotC3vdM
//About path dynamic programming and heuristic functions
/*I followed the same logic but redesigned the function so it can be run using p5.js*/
//https://github.com/bgrins/javascript-astar/blob/master/astar.js
//About A* algorithm
//https://github.com/CodingTrain/website-archive/blob/main/CodingChallenges/CC_051_astar/P5/sketch.js
//https://briangrinstead.com/blog/astar-search-algorithm-in-javascript/
//p5.js command reference
//https://p5js.org/libraries/
/* Define some variables and initialize them */
// Canvas and grid size
var cols = 20;
var rows = 20;
var cw = 600;
var ch = 600;
var grid = new Array(cols);
var openSet = [];
var closedSet = [];
var start, end;
var w, h;
var path = [];
var cars = [];
var carCount = 4;
var frameCounter = 0; // Frame counter
// MH edit
var moveInterval = 30; // Number of frames between car movements
// Define an array of colors, each color is in RGB format
var carColors = [
[255, 0, 0], // Red
[0, 255, 0], // Green
[0, 0, 255], // Blue
[255, 165, 0], // Orange
[128, 0, 128], // Purple
[255, 192, 203] // Pink
];
function setup() {
createCanvas(cw, ch);
w = width / cols;
h = height / rows;
/*Setup function,Initializes the canvas,grid and cars*/
// Initialize the grid
for (var i = 0; i < cols; i++) {
grid[i] = new Array(rows);
for (var j = 0; j < rows; j++) {
grid[i][j] = new Spot(i, j);
}
}
// Add neighbors to each spot
for (var d = 0; d < cols; d++) {
for (var e = 0; e < rows; e++) {
grid[d][e].addNeighbors(grid);
}
}
// Initialize cars
initCars();
}
/* Draw function,grid and car */
function draw() {
background(220);
// Draw the grid
drawGrid();
// Update frame counter
frameCounter++;
// Control car movement frequency
if (frameCounter % moveInterval === 0) {
for (var i = 0; i < cars.length; i++) {
cars[i].move();
}
}
// MH edit
// frameRate(60);
// Draw destinations
for (var a = 0; a < cars.length; a++) {
drawDestination(cars[a]);
}
// Draw cars and their paths
for (var b = 0; b < cars.length; b++) {
drawCar(cars[b]);
}
}
/* Car constructor function*/
function Car(id, position, destination) {
this.id = id;
this.position = position;
this.destination = destination;
this.path = [];
this.previous = null;
this.color = carColors[id % carColors.length]; // Assign color
this.updatePath();
}
Car.prototype.updatePath = function() {
var obstacles = [];
for (var i = 0; i < cars.length; i++) {
if (cars[i].id !== this.id) {
obstacles.push(cars[i].position);
}
}
this.path = astar(this.position, this.destination, obstacles);
};
//Updated method appears in the submitted document
Car.prototype.move = function() {
if (this.path.length > 0) {
var nextStep = this.path[0];
if (!isOccupied(nextStep, this.id)) {
this.position = nextStep;
this.path.shift();
if (this.position.i === this.destination.i && this.position.j === this.destination.j) {
this.path = [];
}
} else {
// Path is blocked, replan the path
this.updatePath();
}
} else {
// No path, try to replan
this.updatePath();
}
};
//Handle the situation where the path is blocked and decide whether to call Updated
/*Initialize cars*/
function initCars() {
for (var i = 0; i < carCount; i++) {
var start, end;
do {
start = grid[Math.floor(Math.random() * cols)][Math.floor(Math.random() * rows)];
} while (start.wall);
var attempts = 0;
do {
end = grid[Math.floor(Math.random() * cols)][Math.floor(Math.random() * rows)];
attempts++;
if (attempts > 1000) {
// If too many attempts, reselect the starting point
start = grid[Math.floor(Math.random() * cols)][Math.floor(Math.random() * rows)];
attempts = 0;
}
} while (end.wall || (end === start) || !pathExists(start, end));
cars.push(new Car(i, start, end));
}
}
// Check if a path exists between start and end
function pathExists(start, end) {
var obstacles = []; // No other cars at initialization
var tempPath = astar(start, end, obstacles);
return tempPath.length > 0;
}
/* A* algorithm */
function astar(start, end, obstacles) {
var openSet = [];
var closedSet = [];
openSet.push(start);
// Reset node information
for (var i = 0; i < cols; i++) {
for (var 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;
}
}
while (openSet.length > 0) {
var winner = 0;
for (var c = 0; c < openSet.length; c++) {
if (openSet[c].f < openSet[winner].f) {
winner = c;
}
}
var current = openSet[winner];
if (current === end) {
var path = [];
var temp = current;
while (temp.previous) {
path.push(temp);
temp = temp.previous;
}
path.reverse();
return path;
}
openSet.splice(winner, 1);
closedSet.push(current);
var neighbors = current.neighbors;
for (var d = 0; d < neighbors.length; d++) {
var neighbor = neighbors[d];
if (!closedSet.includes(neighbor) && !neighbor.wall && !isObstacle(neighbor, obstacles)) {
var tempG = current.g + 1;
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, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
}
}
return [];
}
/* Help functions:Check for obstacles and calculate heuristic value */
function heuristic(a, b) {
return Math.abs(a.i - b.i) + Math.abs(a.j - b.j); // Manhattan distance
}
function isObstacle(node, obstacles) {
for (var i = 0; i < obstacles.length; i++) {
var obs = obstacles[i];
if (node.i === obs.i && node.j === obs.j) {
return true;
}
}
return false;
}
function isOccupied(position, carId) {
for (var i = 0; i < cars.length; i++) {
var car = cars[i];
if (car.id !== carId && car.position.i === position.i && car.position.j === position.j) {
return true;
}
}
return false;
}
/* Color design and road generation module for four cars */
function Spot(i, j) {
this.i = i;
this.j = j;
this.f = 0;
this.g = 0;
this.h = 0;
this.neighbors = [];
this.previous = undefined;
// Generate roads and buildings
if (i % 3 === 0 || j % 3 === 0) {
this.wall = false; // Road
} else {
this.wall = true; // Building
}
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]);
};
this.show = function() {
if (this.wall) {
fill(50); // Building color
noStroke();
rect(this.i * w, this.j * h, w, h);
} else {
fill(200); // Road color
noStroke();
rect(this.i * w, this.j * h, w, h);
}
};
}
// Draw the grid
function drawGrid() {
for (var i = 0; i < cols; i++) {
for (var j = 0; j < rows; j++) {
grid[i][j].show();
}
}
}
// Draw the car and its path
function drawCar(car) {
// Draw the path
noFill();
stroke(car.color[0], car.color[1], car.color[2]);
beginShape();
vertex(car.position.i * w + w / 2, car.position.j * h + h / 2);
for (var i = 0; i < car.path.length; i++) {
var spot = car.path[i];
vertex(spot.i * w + w / 2, spot.j * h + h / 2);
}
endShape();
// Draw the car
fill(car.color[0], car.color[1], car.color[2]);
noStroke();
ellipse(
car.position.i * w + w / 2,
car.position.j * h + h / 2,
w / 2,
h / 2
);
}
// Draw the destination
function drawDestination(car) {
fill(car.color[0], car.color[1], car.color[2]);
noStroke();
rect(
car.destination.i * w + w / 4,
car.destination.j * h + h / 4,
w / 2,
h / 2
);
}