Binary Space Partitioning in GML

#macro CELLSIZE 16
#macro MIN_LEAF_SIZE CELLSIZE*15
#macro MAX_LEAF_SIZE CELLSIZE*45

///@func    BSP(function)
///@param   {function}  _func
///@desc    Runs the binary space partition formula, creating leaves until the created leaves
///         are below a specific size. If you want to run a function on the "smallest" leaves
///         (which are basically the rooms, if using for dungeon generation), supply that function
///         as the function argument in BSP
function BSP(_func) {
    leafs = [];

    array_push(leafs,new Leaf(0,0,width,height));

    var _split = true;
    while (_split) {
        _split = false;
        var _leaf_len = array_length(leafs);
        for (var i=0;i<_leaf_len;i++) {
            var _leaf = leafs[i];
            if (_leaf.child[0] == undefined && _leaf.child[1] == undefined) {
                if (_leaf.width > MAX_LEAF_SIZE || _leaf.height > MAX_LEAF_SIZE) {
                    if (_leaf.Split()) {
                        array_push(leafs,_leaf.child[0]);
                        array_push(leafs,_leaf.child[1]);
                        _split = true;
                    }
                }
            }
        }
    }

    var _leaf_len = array_length(leafs);
    for (var i=0;i<_leaf_len;i++) {
        var _leaf = leafs[i];
        with (_leaf) {
            if (child[0] == undefined && child[1] == undefined) {
                _func();
            }
        }
    }
}

///@func    Leaf(x, y, width, height, parent)
///@param   {real}      _x
///@param   {real}      _y
///@param   {real}      _width
///@param   {real}      _height
///@param   {struct}    _parent
function Leaf(_x,_y,_width,_height,_parent = undefined) constructor {
    x = _x;
    y = _y;
    width = _width;
    height = _height;
    child[0] = undefined;
    child[1] = undefined;
    connected = undefined;
    parent = _parent;
    rm = undefined;

    Split = function() {
        if (child[0] != undefined || child[1] != undefined) {
            return false;
        }
        var _splith = irandom(1);
        if (width > height && width / height >= 1.5) {
            _splith = false;
        }
        else if (height > width && height / width >= 1.5) {
            _splith = true;
        }
        var _max = (_splith ? height : width) - MIN_LEAF_SIZE;
        if (_max <= MIN_LEAF_SIZE) {
            return false;
        }
        var _split = irandom_range(MIN_LEAF_SIZE,_max);
        if (_splith) {
            child[0] = new Leaf(x,y,width,_split,self);
            child[1] = new Leaf(x,y+_split,width,height-_split,self);
        }
        else {
            child[0] = new Leaf(x,y,_split,height,self);
            child[1] = new Leaf(x+_split,y,width-_split,height,self);
        }
        return true;
    }

    GetRoom = function() {
        if (rm != undefined) {
            return rm;
        }
        else {
            var lrm = undefined;
            var rrm = undefined;
            if (child[0] != undefined) {
                lrm = child[0].GetRoom();
            }
            if (child[1] != undefined) {
                rrm = child[1].GetRoom();
            }
            if (lrm == undefined && rrm == undefined) {
                return undefined;
            }
            else if (rrm == undefined) {
                return lrm;
            }
            else if (lrm == undefined) {
                return rrm;
            }
            else if (random(1) <= 0.5) {
                return lrm;
            }
            else {
                return rrm;
            }
        }
    }

    CreateRooms = function() {
        if (child[0] != undefined || child[1] != undefined) {
            if (child[0] != undefined) {
                child[0].CreateRooms();
            }
            if (child[1] != undefined) {
                child[1].CreateRooms();
            }
            if (child[0] != undefined && child[1] != undefined) {
                var _rm1 = child[0].GetRoom();
                var _rm2 = child[1].GetRoom();
            }
        }
        else {
            // Add the code to "create" a room here, maybe you want to create an instance, or drill out
            // an area of a grid or whatever. You can just run CreateRooms() from the scope of the topmost leaf and it will
            // filter down through the leaves and run on all the leaves without children (which would be the "rooms" in your
            // dungeon, if you are using it for dungeon generation).
        }
    }
}