Here is the JS code for the program:
const gridWidth = 10;
const gridHeight = 10;
let grid = [];
let startNode = { x: 0, y: 0 };
let targetNode = { x: 9, y: 9 };
function createGrid() {
const gridElement = document.getElementById('grid');
for (let i = 0; i < gridHeight; i++) {
const row = document.createElement('div');
for (let j = 0; j < gridWidth; j++) {
const node = document.createElement('div');
node.className = 'node';
if (i === startNode.y && j === startNode.x) {
node.className += ' start';
} else if (i === targetNode.y && j === targetNode.x) {
node.className += ' target';
} else if (grid[i][j]) {
node.className += ' obstacle';
}
node.addEventListener('click', () => toggleObstacle(node, j, i));
row.appendChild(node);
}
gridElement.appendChild(row);
}
}
function toggleObstacle(node, x, y) {
if (node.classList.contains('obstacle')) {
node.classList.remove('obstacle');
grid[y][x] = false;
} else {
node.classList.add('obstacle');
grid[y][x] = true;
}
}
function initializeGrid() {
for (let i = 0; i < gridHeight; i++) {
grid[i] = [];
for (let j = 0; j < gridWidth; j++) {
// Randomly assign obstacles
const isObstacle = Math.random() < 0.2; // Adjust the obstacle probability as needed
grid[i][j] = isObstacle;
}
}
}
function runPathfinding() {
const path = findPath(startNode, targetNode);
if (path) {
visualizePath(path);
} else {
alert('No path found!');
}
}
function findPath(start, target) {
const openList = [];
const closedList = [];
const cameFrom = {};
// Initialize the start node
const startNode = {
position: { x: start.x, y: start.y },
gScore: 0,
fScore: heuristic(start, target),
};
openList.push(startNode);
while (openList.length > 0) {
// Find the node with the lowest fScore
let current = openList[0];
let currentIndex = 0;
for (let i = 1; i < openList.length; i++) {
if (openList[i].fScore < current.fScore) {
current = openList[i];
currentIndex = i;
}
}
// Check if the target has been reached
if (current.position.x === target.x && current.position.y === target.y) {
return reconstructPath(cameFrom, current);
}
// Move the current node from open list to closed list
openList.splice(currentIndex, 1);
closedList.push(current);
// Generate neighbor nodes
const neighbors = getNeighbors(current.position);
for (const neighbor of neighbors) {
if (closedList.some((node) => node.position.x === neighbor.x && node.position.y === neighbor.y)) {
continue; // Ignore the neighbor which is already evaluated
}
const gScore = current.gScore + 1;
// Distance between neighbors is always 1 in this grid
const existingNodeIndex = openList.findIndex((node) => node.position.x === neighbor.x && node.position.y === neighbor.y);
if (existingNodeIndex === -1) {
// Discover a new node
const newNode = {
position: { x: neighbor.x, y: neighbor.y },
gScore: gScore,
fScore: gScore + heuristic(neighbor, target),
};
openList.push(newNode);
cameFrom[`${neighbor.x},${neighbor.y}`] = current;
} else {
// Update existing node if new path is better
const existingNode = openList[existingNodeIndex];
if (gScore < existingNode.gScore) {
existingNode.gScore = gScore;
existingNode.fScore = gScore + heuristic(neighbor, target);
cameFrom[`${neighbor.x},${neighbor.y}`] = current;
}
}
}
}
// No path found
return null;
}
function reconstructPath(cameFrom, current) {
const path = [];
while (current) {
path.unshift(current.position);
current = cameFrom[`${current.position.x},${current.position.y}`];
}
return path;
}
function getNeighbors(position) {
const { x, y } = position;
const neighbors = [];
// Add top neighbor
if (y > 0) {
neighbors.push({ x, y: y - 1 });
}
// Add bottom neighbor
if (y < gridHeight - 1) {
neighbors.push({ x, y: y + 1 });
}
// Add left neighbor
if (x > 0) {
neighbors.push({ x: x - 1, y });
}
// Add right neighbor
if (x < gridWidth - 1) {
neighbors.push({ x: x + 1, y });
}
return neighbors;
}
function heuristic(node, target) {
// Simple Manhattan distance heuristic
return Math.abs(node.x - target.x) + Math.abs(node.y - target.y);
}
function visualizePath(path) {
const gridElement = document.getElementById('grid');
const nodes = gridElement.getElementsByClassName('node');
// Reset grid colors
for (const node of nodes) {
node.classList.remove('path');
}
// Highlight path
for (const position of path) {
const nodeIndex = position.y * gridWidth + position.x;
nodes[nodeIndex].classList.add('path');
}
}
initializeGrid();
createGrid();
function getNeighbors(position) {
const { x, y } = position;
const neighbors = [];
// Add top neighbor
if (y > 0 && !grid[y - 1][x]) {
neighbors.push({ x, y: y - 1 });
}
// Add bottom neighbor
if (y < gridHeight - 1 && !grid[y + 1][x]) {
neighbors.push({ x, y: y + 1 });
}
// Add left neighbor
if (x > 0 && !grid[y][x - 1]) {
neighbors.push({ x: x - 1, y });
}
// Add right neighbor
if (x < gridWidth - 1 && !grid[y][x + 1]) {
neighbors.push({ x: x + 1, y });
}
return neighbors;
}
This JavaScript code represents a basic grid-based pathfinding algorithm. Let’s break it down and explain each part:
- The code defines the dimensions of the grid (
gridWidth
and gridHeight
) and initializes the grid array (grid
).
-
startNode
and targetNode
represent the starting and target positions on the grid.
- The
createGrid
function creates the grid on the webpage by dynamically generating HTML elements. It assigns CSS classes to represent different types of nodes (start, target, and obstacles) and attaches click event listeners to toggle obstacles on the grid.
- The
toggleObstacle
function is called when a node is clicked. It toggles the obstacle status of the clicked node and updates the corresponding value in the grid
array.
- The
initializeGrid
function randomly assigns obstacles to the grid based on a specified probability (0.2
in this case). It fills the grid
array accordingly.
- The
runPathfinding
function is called when the pathfinding algorithm needs to be executed. It calls the findPath
function to retrieve the path between the start and target nodes. If a path is found, it calls the visualizePath
function to highlight the path on the grid. Otherwise, it displays an alert indicating that no path was found.
- The
findPath
function implements the A* pathfinding algorithm. It maintains an open list of nodes to be evaluated, a closed list of evaluated nodes, and a cameFrom
object to track the optimal path. It iterates until the open list is empty or the target node is reached. It calculates the gScore and fScore for each neighbor and updates the open list accordingly. If a path is found, it calls the reconstructPath
function to retrieve the optimal path.
- The
reconstructPath
function reconstructs the path from the cameFrom
object by tracing back from the target node to the start node.
- The
getNeighbors
function returns the neighboring positions of a given position on the grid. It considers the top, bottom, left, and right neighbors and checks for out-of-bounds positions and obstacles in the grid
array.
- The
heuristic
function calculates the Manhattan distance heuristic between two nodes. It is used to estimate the distance between a node and the target node.
- The
visualizePath
function highlights the nodes in the calculated path by adding a CSS class to the corresponding HTML elements.
To add Field of View (FOV) to this code, you would need to define how the FOV works and modify the getNeighbors
function accordingly. FOV determines which nodes are visible or accessible from a given node based on a certain range or vision cone. You would need to specify the FOV rules and update the getNeighbors
function to consider the FOV restrictions when generating the neighboring positions.