p5.js pathfinder

pathfinder.js

/* Pathfinding Visualizer using P5.js*/

const grid = [];
const cols = 50;
const rows = 35;
// cell size should be calculated based on number of rows and cols
const cellSize = 10;
let start;
let end;
let path = [];

class Cell {
    constructor(x, y) {
        this.x = x;
        this.y = y;
        this.f = 0;
        this.g = 0;
        this.h = 0;
        this.previous = undefined;
        this.neighbors = [];
        this.wall = false;
    }

    show(col) {
        fill(col);
        if (this.wall) {
            fill(0);
        }
        stroke(0);
        rect(this.x * cellSize, this.y * cellSize, cellSize, cellSize);
    }

    addNeighbors(grid) {
        const x = this.x;
        const y = this.y;
        // Combine the following four if statements into one using logical OR (||) operator
        if (x < cols - 1 || x > 0 || y < rows - 1 || y > 0) {
            if (x < cols - 1) {
                this.neighbors.push(grid[x + 1][y]);
            }
            if (x > 0) {
                this.neighbors.push(grid[x - 1][y]);
            }
            if (y < rows - 1) {
                this.neighbors.push(grid[x][y + 1]);
            }
            if (y > 0) {
                this.neighbors.push(grid[x][y - 1]);
            }
        }
    }
}

function setup() {
    createCanvas(cols * 11, rows * 11);
    for (let i = 0; i < cols; i++) {
        grid[i] = [];
        for (let j = 0; j < rows; j++) {
            grid[i][j] = new Cell(i, j);
        }
    }
    for (let i = 0; i < cols; i++) {
        for (let j = 0; j < rows; j++) {
            if (random(1) < 0.27) {
                grid[i][j].wall = true;
            }
        }
    }
    start = grid[floor(random(cols))][floor(random(rows))];
    end = grid[floor(random(cols))][floor(random(rows))];
    start.wall = false;
    end.wall = false;
    path = aStar(grid, start, end);
    stop();
}

function stop() {
    noLoop();
}

function heuristic(a, b) {
    const d = dist(a.x, a.y, b.x, b.y);
    return d;
}

function draw() {
    for (let i = 0; i < cols; i++) {
        for (let j = 0; j < rows; j++) {
            grid[i][j].show(color(255));
        }
    }
    for (let i = 0; i < cols; i++) {
        for (let j = 0; j < rows; j++) {
            grid[i][j].addNeighbors(grid);
        }
    }
    path = aStar(grid, start, end); // update path
    if (path) {
        // check if path exists
        for (let i = 0; i < path.length; i++) {
            path[i].show(color(240, 210, 0));
        }
    }
    // start green, end red
    start.show(color(0, 255, 0));
    end.show(color(255, 0, 0));
}

// A* algorithm
function aStar(_grid, start, end) {
    const openSet = new PriorityQueue();
    const closedSet = new Set();
    start.costFromStart = 0;
    start.estimatedCostToGoal = heuristic(start, end);
    start.totalCost = start.costFromStart + start.estimatedCostToGoal;
    openSet.enqueue(start, start.totalCost);

    let pathFound = false;

    while (!openSet.isEmpty() && !pathFound) {
        const current = openSet.dequeue().element;

        if (current === end) {
            const path = [];
            let temp = current;
            path.push(temp);
            while (temp.previous) {
                path.push(temp.previous);
                temp = temp.previous;
            }
            console.log(`Shortest path length: ${path.length}`);
            pathFound = true;
            return path.reverse();
        }

        closedSet.add(current);

        for (let i = 0; i < current.neighbors.length; i++) {
            const neighbor = current.neighbors[i];
            if (!closedSet.has(neighbor) && !neighbor.wall) {
                const tempCostFromStart = current.costFromStart + heuristic(neighbor, current);
                let newPath = false;
                if (openSet.contains(neighbor)) {
                    if (tempCostFromStart < neighbor.costFromStart) {
                        neighbor.costFromStart = tempCostFromStart;
                        newPath = true;
                    }
                } else {
                    neighbor.costFromStart = tempCostFromStart;
                    newPath = true;
                    neighbor.estimatedCostToGoal = heuristic(neighbor, end);
                    neighbor.totalCost = neighbor.costFromStart + neighbor.estimatedCostToGoal;
                    neighbor.previous = current;
                    openSet.enqueue(neighbor, neighbor.totalCost);
                }
                if (newPath) {
                    neighbor.estimatedCostToGoal = heuristic(neighbor, end);
                    neighbor.totalCost = neighbor.costFromStart + neighbor.estimatedCostToGoal;
                    neighbor.previous = current;
                }
                if (!openSet.contains(neighbor)) {
                    openSet.enqueue(neighbor, neighbor.totalCost);
                }
            }
        }
    }
}

class PriorityQueue {
    constructor() {
        this.items = [];
    }

    enqueue(element, priority) {
        const queueElement = { element, priority };
        let added = false;
        for (let i = 0; i < this.items.length; i++) {
            if (queueElement.priority < this.items[i].priority) {
                this.items.splice(i, 0, queueElement);
                added = true;
                break;
            }
        }
        if (!added) {
            this.items.push(queueElement);
        }
    }

    dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items.shift();
    }

    isEmpty() {
        return this.items.length === 0;
    }

    contains(element) {
        for (let i = 0; i < this.items.length; i++) {
            if (this.items[i].element === element) {
                return true;
            }
        }
        return false;
    }
}