pathfinding/EdgeTrace.js

import AStar from "./AStar.js";

const ERROR_PADDING = 0.001;

/**
 * pathfinder using the edges of rectangles as nodes
 */
class EdgeTrace {
    /**
     * @param {number} width The maximum width of your entity, used as padding around obstacles
     * @param {Rectangle} bounds optional outer bounds, this is useful if rectangles touch a wall
     */
    constructor(width, bounds = null) {
        this.nodes = [];
        this.width = width * 0.5;
        this.bounds = bounds;
    }

    /**
     * save the rectangle corners as nodes
     * @param {Rectangle[]} rects 
     */
    updateNodes(rects) {
        this.nodes = [];

        rects.forEach(r => {
            this.nodes.push({
                x: r.x1 - this.width,
                y: r.y1 - this.width
            });
            this.nodes.push({
                x: r.x2 + this.width,
                y: r.y1 - this.width
            });
            this.nodes.push({
                x: r.x2 + this.width,
                y: r.y2 + this.width
            });
            this.nodes.push({
                x: r.x1 - this.width,
                y: r.y2 + this.width
            });
        });

        this.rects = rects;
    }

    /**
     * calculate a path
     * @param {{x: Number, y:Number}} start 
     * @param {{x: Number, y:Number}} end 
     * @return {Array.<{x: Number, y:Number}>} 
     */
    calc(start, end) {
        let nodes = this.nodes.concat([start, end]);

        let astar = new AStar((node) => {
            let ret = [];

            nodes.forEach(n => {
                if (node.x == n.x && node.y == n.y) return;

                if (this.bounds !== null && !this.bounds.contains(n.x, n.y)) return;

                for (let r = 0; r < this.rects.length; r++) {
                    if (this.rects[r].intersectsLine(node.x, node.y, n.x, n.y, this.width - ERROR_PADDING)) return;
                }

                ret.push({ x: n.x, y: n.y });
            });

            return ret;
        });

        return astar.calc(start, end);
    }
}

export default EdgeTrace;