A* implementation in TypeScript

AStar.ts

export interface IHasNeighbours<T> {
    getNeighbours(): Iterable<T>;
}

export class AStar {
    static findPath<T extends IHasNeighbours<T>>(start: T, end: T, distanceFunc: (a: T, b: T) => number, estimateFunc?: (a: T) => number): Array<T> {
        estimateFunc ??= (a: T) => distanceFunc(a, end);
        const closed = new Set<T>();
        const queue = new PriorityQueue<NodeWithNumber<Path<T>>>(NodeWithNumber.comparator);
        queue.push(new NodeWithNumber(new Path<T>(start, undefined, 0), 0));
        while (!queue.isEmpty()) {
            const path = queue.pop()!;
            if (closed.has(path.item.lastStep))
                continue;

            if (path.item.lastStep === end)
                return path.item.build();

            closed.add(path.item.lastStep);
            for (const n of path.item.lastStep.getNeighbours()) {
                const d = distanceFunc(path.item.lastStep, n);
                const newPath = path.item.addStep(n, d);
                queue.push(new NodeWithNumber(newPath, newPath.totalCost + estimateFunc(n)));
            }
        }
        return new Array<T>();
    }
}

class Path<T extends IHasNeighbours<T>>{
    constructor(public lastStep: T, public previousSteps: Path<T> | undefined, public totalCost: number) { }

    addStep = (step: T, cost: number) => new Path<T>(step, this, this.totalCost + cost);
    build(): Array<T> {
        let p: Path<T> | undefined = this;
        const array = new Array<T>
        do {
            if (!p)
                return array;

            array.unshift(p.lastStep);
            p = p.previousSteps;
        }
        while (true);
    }
}

class NodeWithNumber<T>{
    constructor(public item: T, public value: number) { }

    static comparator<T>(a: NodeWithNumber<T>, b: NodeWithNumber<T>) {
        return a.value < b.value;
    }
}

class PriorityQueue<T> {
    private readonly items: T[];
    private readonly comparator: (a: T, b: T) => boolean;
    private size: number;

    constructor(comparator?: (a: T, b: T) => boolean) {
        this.items = [];
        this.size = 0;
        this.comparator = comparator || PriorityQueue.defaultComparator;
    }

    static defaultComparator = <T>(a: T, b: T) => a < b;

    isEmpty = () => this.size === 0;
    push(item: T) {
        let size = this.size;
        this.items[this.size] = item;
        this.size += 1;
        while (size > 0) {
            const p = (size - 1) >> 1;
            const ap = this.items[p];
            if (!this.comparator(item, ap))
                break;

            this.items[size] = ap;
            size = p;
        }
        this.items[size] = item;
    };

    pop(): T | undefined {
        if (this.size === 0)
            return undefined;

        const item = this.items[0];
        if (this.size > 1) {
            this.items[0] = this.items[--this.size];
            this.popDown(0);
        } else {
            this.size -= 1;
        }
        return item;
    };

    private popDown(index: number) {
        const size = this.size;
        const halfSize = this.size >>> 1;
        const item = this.items[index];
        while (index < halfSize) {
            let left = (index << 1) + 1;
            let best = this.items[left];
            const right = left + 1;
            if (right < size) {
                if (this.comparator(this.items[right], best)) {
                    left = right;
                    best = this.items[right];
                }
            }

            if (!this.comparator(best, item))
                break;

            this.items[index] = best;
            index = left;
        }
        this.items[index] = item;
    };
}