math/BSP.js

import Rectangle from "./Rectangle.js";
import SeededRandom from "./SeededRandom.js";
import MST from "./MST.js";

class Leaf extends Rectangle {
    constructor(x, y, w, h, bsp) {
        super(x, y, w, h);

        this.bsp = bsp;
        this.rand = bsp.rand;

        this.padding = this.bsp.options.padding;
        this.min = this.bsp.options.roomMinSize + this.bsp.options.padding * 2;
    }

    /**
     * returns true if this leaf has no children, aka if we are on the lowest level
     * @returns {boolean}
     */
    isLeaf() {
        return !this.left_child && !this.right_child;
    }

    split() {
        if (!this.isLeaf()) return false;

        let splitH = this.rand.bool();
        if (this.w / this.h >= 1.25) {
            splitH = false;
        } else if (this.h / this.w >= 1.25) {
            splitH = true;
        }

        let max = (splitH ? this.h : this.w) - this.min;
        if (max < this.min) return false;

        let split = this.rand.int(this.min, max);
        this.splitH = splitH;

        if (splitH) {
            this.left_child = new Leaf(this.x, this.y, this.w, split, this.bsp);
            this.right_child = new Leaf(this.x, this.y + split, this.w, this.h - split + 1, this.bsp);
        } else {
            this.left_child = new Leaf(this.x, this.y, split, this.h, this.bsp);
            this.right_child = new Leaf(this.x + split, this.y, this.w - split + 1, this.h, this.bsp);
        }
        return true;
    }

    createRooms() {
        if (this.isLeaf()) {
            let min = this.bsp.options.roomMinSize;
            let w = this.rand.int(min, Math.max(min, this.w - this.padding * 2));
            let h = this.rand.int(min, Math.max(min, this.h - this.padding * 2));
            let x = this.x + this.padding + this.rand.int(0, this.w - this.padding * 2 - w);
            let y = this.y + this.padding + this.rand.int(0, this.h - this.padding * 2 - h);

            this.room = new Rectangle(x, y, w, h);
            this.room.leaf = this;
            this.bsp.rooms.push(this.room);
        } else {
            this.left_child.createRooms();
            this.right_child.createRooms();
        }
    }

    getRectangles() {
        if (this.isLeaf()) {
            return [this.room.clone()];
        } else {
            let rects = [];
            rects = rects.concat(this.left_child.getRectangles());
            rects = rects.concat(this.right_child.getRectangles());
            return rects;
        }
    }

    expandX() {
        if (!this.room) return;
        if (this.room.x > this.x + this.padding) this.room.x--;
        if (this.room.w < this.w - this.padding) this.room.w++;
    }

    expandY() {
        if (!this.room) return;
        if (this.room.y > this.y + this.padding) this.room.y--;
        if (this.room.h < this.h - this.padding) this.room.h++;
    }

    /**
     * Connect the rooms recursively using the original binary tree structure
     * @param {number} expand 
     */
    connectBSP(expand = 3) {
        if (this.isLeaf()) return;

        this.left_child.connect();
        this.right_child.connect();

        let a = this.left_child.getRectangles();
        let b = this.right_child.getRectangles();

        if (this.left_child.x < this.right_child.x) {
            let aright = [];

            a.forEach(r => {
                if (r.h < 3) return;
                for (let y = r.y + 1; y < r.y2 - 1; y++) {
                    if (!aright[y] || aright[y] < r.x + r.w) {
                        aright[y] = r.x + r.w;
                    }
                }
            });

            let bleft = [];
            b.forEach(r => {
                if (r.h < 3) return;
                for (let y = r.y + 1; y < r.y2 - 1; y++) {
                    if (!bleft[y] || bleft[y] > r.x) {
                        bleft[y] = r.x;
                    }
                }
            });

            let possible = [];
            let shortest = [];

            for (let y = this.y; y < this.y2; y++) {
                if (aright[y] && bleft[y]) possible.push([y, aright[y], bleft[y]]);
            }

            possible.sort((a, b) => (a[2] - a[1]) - (b[2] - b[1]));

            possible.forEach(p => {
                if (!shortest.length || p[2] - p[1] == shortest[0][2] - shortest[0][1]) {
                    shortest.push(p);
                }
            });

            let conn = this.rand.entry(shortest);

            if (!conn) {
                if (expand > 0) {
                    this.left_child.expandY();
                    this.right_child.expandY();
                    this.connect(expand - 1);
                }
                return;
            }

            this.corridor = new Rectangle(conn[1], conn[0], conn[2] - conn[1], 1);
            this.bsp.corridors.push(this.corridor);
        } else {
            let abottom = [];
            a.forEach(r => {
                if (r.w < 3) return;
                for (let x = r.x + 1; x < r.x2 - 1; x++) {
                    if (!abottom[x] || abottom[x] < r.y + r.h) {
                        abottom[x] = r.y + r.h;
                    }
                }
            });

            let btop = [];
            b.forEach(r => {
                if (r.w < 3) return;
                for (let x = r.x + 1; x < r.x2 - 1; x++) {
                    if (!btop[x] || btop[x] > r.y) {
                        btop[x] = r.y;
                    }
                }
            });

            let possible = [];
            let shortest = [];

            for (let x = this.x; x < this.x + this.w; x++) {
                if (abottom[x] && btop[x]) possible.push([x, abottom[x], btop[x]]);
            }

            possible.sort((a, b) => (a[2] - a[1]) - (b[2] - b[1]));

            possible.forEach(p => {
                if (!shortest.length || p[2] - p[1] == shortest[0][2] - shortest[0][1]) {
                    shortest.push(p);
                }
            });

            let conn = this.rand.entry(shortest);

            if (!conn) {
                if (expand > 0) {
                    this.left_child.expandX();
                    this.right_child.expandX();
                    this.connect(expand - 1);
                }
                return;
            }

            this.corridor = new Rectangle(conn[0], conn[1], 1, conn[2] - conn[1]);
            this.bsp.corridors.push(this.corridor);
        }
    }

    calculateFrontiers() {
        if (this.isLeaf()) {
            this.frontier = {
                n: [this.room],
                w: [this.room],
                s: [this.room],
                e: [this.room]
            };
        } else {
            this.left_child.calculateFrontiers();
            this.right_child.calculateFrontiers();

            if (this.splitH) {
                this.frontier = {
                    n: this.left_child.frontier.n,
                    s: this.right_child.frontier.s,
                    w: [...this.left_child.frontier.w, ...this.right_child.frontier.w],
                    e: [...this.left_child.frontier.e, ...this.right_child.frontier.e]
                };
            } else {
                this.frontier = {
                    w: this.left_child.frontier.w,
                    e: this.right_child.frontier.e,
                    n: [...this.left_child.frontier.n, ...this.right_child.frontier.n],
                    s: [...this.left_child.frontier.s, ...this.right_child.frontier.s]
                };
            }
        }
    }

    getPossibleConnections() {
        if (this.isLeaf()) return [];

        let ret = [];

        if (this.splitH) {
            let as = this.right_child.frontier.n;
            let bs = this.left_child.frontier.s;

            as.forEach(a => {
                bs.forEach(b => {
                    let conn = this.checkConnY(a, b);
                    if (conn) {
                        ret.push([a, b, conn, this.splitH]);
                    }
                });
            });
        } else {
            let as = this.right_child.frontier.w;
            let bs = this.left_child.frontier.e;

            as.forEach(a => {
                bs.forEach(b => {
                    let conn = this.checkConnX(a, b);
                    if (conn) {
                        ret.push([a, b, conn, this.splitH]);
                    }
                });
            });
        }

        return [...ret, ...this.left_child.getPossibleConnections(), ...this.right_child.getPossibleConnections()];
    }

    /**
     * calculate edges using mst
     */
    getEdges() {
        let vertices = [];

        this.bsp.rooms.forEach((r, i) => {
            vertices.push(i);
        });

        this.calculateFrontiers();
        let connections = this.getPossibleConnections();

        let edges = connections.map(c => {
            return [this.bsp.rooms.indexOf(c[0]), this.bsp.rooms.indexOf(c[1])];
        });

        let mst = new MST(vertices);
        mst.edges = edges;
        mst.calculate();

        mst.tree.forEach(edge => {
            let a = this.bsp.rooms[edge[0]];
            let b = this.bsp.rooms[edge[1]];

            let conn = connections.find(c => {
                return (c[0] === a && c[1] === b) || (c[0] === b && c[1] === a);
            });

            if (conn) {
                let horizontal = conn[3];
                let d = conn[2];

                let corridor = horizontal ? new Rectangle(d.x, d.y1, 1, d.y2 - d.y1) : new Rectangle(d.x1, d.y, d.x2 - d.x1, 1);
                this.bsp.corridors.push(corridor);
            }
        });
    }

    checkConnX(a, b) {
        let aright = {};
        let bleft = {};

        for (let y = a.y; y < a.y2; y++) {
            if (!aright[y] || aright[y] < a.x + a.w) {
                aright[y] = a.x + a.w;
            }
        }

        for (let y = b.y; y < b.y2; y++) {
            if (!bleft[y] || bleft[y] > b.x) {
                bleft[y] = b.x;
            }
        }

        let possible = [];
        let minY = Math.min(a.y, b.y);
        let maxY = Math.max(a.y2, b.y2);

        for (let y = minY; y < maxY; y++) {
            if (aright[y] && bleft[y]) possible.push({
                y: y,
                x1: Math.min(aright[y], bleft[y]),
                x2: Math.max(aright[y], bleft[y])
            });
        }

        return this.rand.entry(possible);
    }

    checkConnY(a, b) {
        let abottom = {};
        let btop = {};

        for (let x = a.x; x < a.x2; x++) {
            if (!abottom[x] || abottom[x] < a.y2) {
                abottom[x] = a.y2;
            }
        }

        for (let x = b.x; x < b.x2; x++) {
            if (!btop[x] || btop[x] > b.y) {
                btop[x] = b.y;
            }
        }

        let possible = [];
        let minX = Math.min(a.x, b.x);
        let maxX = Math.max(a.x2, b.x2);

        for (let x = minX; x < maxX; x++) {
            if (abottom[x] && btop[x]) possible.push({
                x: x,
                y1: Math.min(abottom[x], btop[x]),
                y2: Math.max(abottom[x], btop[x])
            });
        }

        return this.rand.entry(possible);
    }
}

/**
 * Binary Space Partitioning
 * 
 * @example
 * let bsp = new Bsp(30, 20);
 * bsp.calculate();
 * 
 * for (const r of bsp.rooms) {...}
 * for (const r of bsp.corridors) {...}
 */
class BSP {
    /**
     * @param {Number} width width of the base rectangle
     * @param {Number} height height of the base rectangle
     * @param {Object} options
     * @param {Number} options.padding space between the rooms
     * @param {Number} options.roomMinSize minimum room size
     * @param {Number} options.roomMaxSize maximum room size
     * @param {SeededRandom} options.rand random instance
     */
    constructor(width, height, options = {}) {
        this.width = width;
        this.height = height;

        this.options = Object.assign({
            padding: 1,
            roomMinSize: 4,
            roomMaxSize: 6
        }, options);

        this.rand = this.options.rand ? this.options.rand : new SeededRandom();

        this.corridors = [];
        this.rooms = [];
    }

    /**
     * Calculate it
     */
    calculate() {
        let root = new Leaf(0, 0, this.width - 1, this.height - 1, this);
        this.createBsp(root);
        root.createRooms();
        root.getEdges();
    }

    createBsp(l) {
        if (l.isLeaf()) {
            if (l.w > this.options.roomMaxSize || l.h > this.options.roomMaxSize) {
                if (l.split()) {
                    this.createBsp(l.left_child);
                    this.createBsp(l.right_child);
                }
            }
        }
    }
}

export default BSP