game_space_path_path_builder.js

import Path from "./path.js";
import Heap from "../../../util/data/heap.js";

/**
 * @module PathBuilder
 * @fileoverview Contains PathBuilder and Point classes.
 */

/**
 * @class
 * A Point used for organizing the Heap for generating paths. Holds values such as the coordinates, the unit at those
 * coordinates, the parent Point, and the appropriate distances used for generating a Path.
 */
class Point {
    constructor(space, pos, parent, g = 0, h = 0, f = 0) {
        this.pos = pos;
        this.unit = space.getUnitAt(pos.x, pos.y);

        this.parent = parent;

        this.g = g;
        this.h = h;
        this.f = f;
    }
}

/**
 * @class
 * Used for generating Paths in a space, from one position to another. The Path will be generated as soon as the
 * PathBuilder is constructed.
 */
class PathBuilder {
    /**
     * Create a new PathBuilder.
     * @param {Space} space Space to generate the Path in
     * @param {Vec2} start Starting position of the Path
     * @param {Vec2} end Ending position of the Path
     * @param {boolean} smooth Whether to smooth/simplify the path by removing unnecessary points. This makes
     * for much more realistic (and efficient to use) paths (Optional)
     * @constructor
     */
    constructor(space, start, end, smooth = true) {
        this.space = space;

        this.start = start;
        this.end = end;

        this.path = null;
        this._generate(smooth);
    }

    /**
     * Get the neighboring Points of a specified Point.
     * @param {Point} point Point to get neighbors off
     * @returns {Point[]} List of neighboring Points
     * @private
     */
    _getNeighbors(point) {
        const s = this.space.unitSize;
        const pos = point.pos.floor(s).addv(s / 2, s / 2);

        const result = [];
        const step = this.space.unitSize;

        for (let x = -1; x <= 1; x++) {
            for (let y = -1; y <= 1; y++) {
                if (x === 0 && y === 0 || (x !== 0 && y !== 0))
                    continue;

                let p = pos.addv(x * step, y * step);
                let n = this.space.getUnitAt(p.x, p.y);
                if (n === null || n.canWalkOn)
                    result.push(new Point(this.space, p, point));
            }
        }

        return result;
    }

    /**
     * Check if an array contains a Point, by checking the positions of the Points.
     * @param {Point[]} array Array to check in
     * @param {Point} point Point to check for
     * @returns {boolean} Whether the array contains the specified Point
     * @private
     */
    _has(array, point) {
        for (const p of array)
            if (p.pos.equals(point.pos))
                return true;

        return false;
    }

    /**
     * Calculate the cost of one Point to another.
     * @param {Point} a Point A
     * @param {Point} b Point B
     * @returns {number} The cost of travelling from one Point to another.
     * @private
     */
    _getCost(a, b) {
        const deltaX = Math.abs(a.pos.x - b.pos.x);
        const deltaY = Math.abs(a.pos.y - b.pos.y);
        return Math.max(deltaX, deltaY) * 10;
    }

    /**
     * Generate the Path using the specified starting and end points.
     * @param {boolean} smooth Whether or not to smooth/simplify the resulting path
     * @private
     */
    _generate(smooth) {
        let count = 0;

        const path = [];

        const startPoint = new Point(this.space, this.start, null);
        const endPoint = new Point(this.space, this.end, null);

        const open = new Heap([], (a, b) => {
            return a.f < b.f;
        });
        const closed = [];

        open.add(startPoint);

        while (open.data.length !== 0) {
            count++;
            if (count > 1E4)
                return;

            //this._sort(open);
            let curr = open.pop();
            closed.push(curr);

            if (curr.pos.dist(this.end) <= this.space.unitSize) {
                path.push(this.end);

                while (curr !== startPoint) {
                    path.push(curr.pos);
                    curr = curr.parent;
                }

                this.path = path.reverse();
                if (smooth)
                    this.path = this._smooth(this.path);

                return;
            }

            const neighbors = this._getNeighbors(curr, this.end);
            if (neighbors.length === 0)
                continue;

            for (const n of neighbors) {
                if (this._has(closed, n))
                    continue;

                const cost = curr.g + this._getCost(curr, n);
                if (cost < n.g || !open.hasCustom((v) => {
                    return v.pos.dist(n.pos) < 1;
                })) {
                    n.g = cost;
                    n.h = this._getCost(n, endPoint);
                    n.f = n.g + n.h;
                    n.parent = curr;

                    if (!open.hasCustom((v) => {
                        return v.pos.dist(n.pos) < 1;
                    }))
                        open.add(n);
                }
            }
        }
    }

    /**
     * Check if the unit at a specified position if filled.
     * @param {Vec2} pos Position to check at
     * @returns {boolean} Whether the unit is filled
     * @private
     */
    _isFilled(pos) {
        const unit = this.space.getUnitAt(pos.x, pos.y);
        if (unit === null)
            return false;

        return !unit.canWalkOn;
    }

    /**
     * Smooth/simplify the path. Removes unnecessary points along the path to make it more efficient.
     * @param {Vec2[]} points Array of points (of the path)
     * @returns {Vec2[]} Smoothed/simplified version of the path
     * @private
     */
    _smooth(points) {
        for (let i = 0; i < points.length; i++) {
            const curr = points[i];

            for (let j = i + 2; j < points.length; j++) {
                const other = points[j];

                let clear = true;
                const length = Math.ceil(curr.dist(other) / this.space.unitSize) * 2;
                for (let k = 0; k < length; k++) {
                    const pos = curr.add(other.sub(curr).norm().mulv(k * this.space.unitSize / 2));
                    if (this._isFilled(pos)) {
                        clear = false;
                        break;
                    }
                }
                if (clear) {
                    points[j - 1] = null;
                    i++;
                } else {
                    break;
                }
            }
        }

        return points.filter((point) => {
            return point !== null;
        });
    }

    /**
     * Get the resulting Path.
     * @returns {Path|null} The resulting path, or null if unsuccessful.
     */
    get() {
        if (this.path === null)
            return null;

        return new Path(this.space, this.path);
    }
}

export default PathBuilder;