<!DOCTYPE html>
<html>
<head>
<title>Autonomous Cars A* Pathfinding</title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.9.0/p5.js"></script>
<style>
body { display: flex; flex-direction: column; align-items: center; }
canvas { border: 2px solid black; }
</style>
</head>
<body>
<h2>Autonomous Cars A* Pathfinding Simulation</h2>
<script>
class AStarPathfinder {
static findPath(grid, start, goal, occupiedCells) {
const openSet = [];
const closedSet = new Set();
const cameFrom = new Map();
const gScore = new Map();
const fScore = new Map();
openSet.push(start);
gScore.set(start.toString(), 0);
fScore.set(start.toString(), this.heuristic(start, goal));
while (openSet.length > 0) {
// Get node with lowest f-score
const current = openSet.reduce((lowest, node) =>
(fScore.get(node.toString()) || Infinity) <
(fScore.get(lowest.toString()) || Infinity) ? node : lowest
);
// Check if goal reached
if (current.x === goal.x && current.y === goal.y) {
const path = [current];
let curr = current;
while (cameFrom.has(curr.toString())) {
curr = cameFrom.get(curr.toString());
path.unshift(curr);
}
return path;
}
// Remove current from open set and add to closed set
openSet.splice(openSet.indexOf(current), 1);
closedSet.add(current.toString());
// Check neighbors (4-directional movement)
const neighbors = [
createVector(current.x + 1, current.y),
createVector(current.x - 1, current.y),
createVector(current.x, current.y + 1),
createVector(current.x, current.y - 1)
];
for (let neighbor of neighbors) {
// Skip if neighbor is in closed set or is an obstacle
if (closedSet.has(neighbor.toString()) ||
neighbor.x < 0 || neighbor.x >= grid[0].length ||
neighbor.y < 0 || neighbor.y >= grid.length ||
grid[neighbor.y][neighbor.x] === 1 ||
occupiedCells.some(cell =>
cell.x === neighbor.x && cell.y === neighbor.y)
) continue;
const tentativeGScore =
(gScore.get(current.toString()) || 0) + 1;
// If neighbor not in open set, add it
if (!openSet.some(n => n.x === neighbor.x && n.y === neighbor.y)) {
openSet.push(neighbor);
}
// If this path is not better, skip
else if (tentativeGScore >= (gScore.get(neighbor.toString()) || Infinity)) {
continue;
}
// This path is the best until now. Record it!
cameFrom.set(neighbor.toString(), current);
gScore.set(neighbor.toString(), tentativeGScore);
fScore.set(
neighbor.toString(),
tentativeGScore + this.heuristic(neighbor, goal)
);
}
}
return []; // No path found
}
// Manhattan distance heuristic
static heuristic(a, b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
}
class Car {
constructor(start, goal, color) {
this.position = start;
this.goal = goal;
this.path = [];
this.color = color;
this.arrived = false;
}
draw() {
fill(this.color);
rect(
this.position.x * GRID_SIZE,
this.position.y * GRID_SIZE,
GRID_SIZE,
GRID_SIZE
);
// Draw goal marker
noFill();
stroke(this.color);
strokeWeight(2);
rect(
this.goal.x * GRID_SIZE,
this.goal.y * GRID_SIZE,
GRID_SIZE,
GRID_SIZE
);
}
}
class TrafficSimulation {
constructor(cols, rows) {
this.cols = cols;
this.rows = rows;
// Create grid with street-like pattern
this.grid = Array(rows).fill().map(() => Array(cols).fill(0));
this.createStreetGrid();
// Create cars
this.cars = this.createCars();
}
createStreetGrid() {
for (let y = 0; y < this.rows; y++) {
for (let x = 0; x < this.cols; x++) {
// Create street-like pattern with some randomness
if (x % 4 === 0 || y % 4 === 0) {
this.grid[y][x] = 0; // street
} else {
// Randomly add some building blocks
this.grid[y][x] = random() < 0.2 ? 1 : 0;
}
}
}
}
createCars() {
const carColors = [
color(255, 0, 0), // Red
color(0, 255, 0), // Green
color(0, 0, 255), // Blue
color(255, 165, 0) // Orange
];
const cars = [];
for (let carColor of carColors) {
let start, goal;
do {
start = createVector(
floor(random(this.cols)),
floor(random(this.rows))
);
goal = createVector(
floor(random(this.cols)),
floor(random(this.rows))
);
} while (
this.grid[start.y][start.x] === 1 ||
this.grid[goal.y][goal.x] === 1 ||
(start.x === goal.x && start.y === goal.y)
);
cars.push(new Car(start, goal, carColor));
}
return cars;
}
getOccupiedCells(excludeCar) {
return this.cars
.filter(car => car !== excludeCar && !car.arrived)
.map(car => car.position);
}
moveStep() {
for (let car of this.cars) {
// Skip if car has arrived
if (car.arrived) continue;
// Check if car has reached its goal
if (car.position.x === car.goal.x && car.position.y === car.goal.y) {
car.arrived = true;
continue;
}
// Recalculate path if no path exists
if (car.path.length <= 1) {
const occupiedCells = this.getOccupiedCells(car);
car.path = AStarPathfinder.findPath(
this.grid,
car.position,
car.goal,
occupiedCells
);
}
// Move to next position if path exists
if (car.path.length > 1) {
car.position = car.path[1];
car.path.shift();
}
}
}
draw() {
// Draw grid
for (let y = 0; y < this.rows; y++) {
for (let x = 0; x < this.cols; x++) {
// Draw building blocks
if (this.grid[y][x] === 1) {
fill(200);
rect(x * GRID_SIZE, y * GRID_SIZE, GRID_SIZE, GRID_SIZE);
}
// Grid lines
stroke(230);
noFill();
rect(x * GRID_SIZE, y * GRID_SIZE, GRID_SIZE, GRID_SIZE);
}
}
// Draw cars
this.cars.forEach(car => car.draw());
}
}
// Simulation parameters
const GRID_SIZE = 40;
const COLS = 20;
const ROWS = 15;
let simulation;
function setup() {
createCanvas(COLS * GRID_SIZE, ROWS * GRID_SIZE);
simulation = new TrafficSimulation(COLS, ROWS);
frameRate(2); // Slow down to see path changes
}
function draw() {
background(255);
// Move cars
simulation.moveStep();
// Draw everything
simulation.draw();
}
</script>
</body>
</html>