/// @description buildDungeon(height,width,minwidth,minheight)
/// @param height
/// @param width
/// @param minwidth
/// @param minheight
/*
We start with a rectangular dungeon filled with wall cells. We are going to split this dungeon recursively until each sub-dungeon has approximately the size of a room.
The dungeon splitting uses this operation :

1.choose a random direction : horizontal or vertical splitting
2.choose a random position (x for vertical, y for horizontal)
3.split the dungeon into two sub-dungeons
4. Repeat until the lowest sub-dungeons have approximately the size of the rooms we want to generate.

Connecting the BSP
To build corridors, we loop through all the leafs of the tree, connecting each leaf to its sister. If the two rooms have face-to-face walls, we can use a straight corridor. Else we have to use a Z shaped corridor.
Repeat for all levels
 */

//script arguments
//randomize();
//random_set_seed(3); //3-4 produces a wrong link.
var height    = argument0;
var width     = argument1;
var minwidth  = argument2;
var minheight = argument3;

var spawnPlaced = false;
//setup for bsp records to be stored in an array
enum bsp{
Final,
Parent,
Generation,
Xleft,
Xright,
Ytop,
Ybot,
Joined,
Child1,
Child2,
Sibling
};

var bspList = 0; //room records
var bspcount = 0;//current room

//initial dungeon size, before subdivisions
bspList[0,bsp.Final]      = false;
bspList[0,bsp.Parent]     = "farts";
bspList[0,bsp.Generation] = 0;
bspList[0,bsp.Xleft]      = 0;
bspList[0,bsp.Xright]     = width;
bspList[0,bsp.Ytop]       = 0;
bspList[0,bsp.Ybot]       = height;
bspList[0,bsp.Joined]     = true;
bspList[0,bsp.Child1]     = 1;
bspList[0,bsp.Child2]     = 2;
bspList[0,bsp.Sibling]    = "farts";

//loop through each entry in the bspList until we run out of entries that can be divided along either axis
while(true)
{
    //this is our constantly updated terminate condition
    var entries = array_height_2d(bspList);
    if (bspcount == entries)
    {
        break;
    }

    //consider the current dungeon, divide it if it is not finalized
    if (bspList[bspcount,bsp.Final] == false)
    {
        //1.choose a random direction : 0 horizontal or 1 vertical splitting
        if (abs(bspList[bspcount,bsp.Xleft] - bspList[bspcount,bsp.Xright]) < 2*minwidth)
        {
            var dirbranch = 1;
        }
        else if (abs(bspList[bspcount,bsp.Ybot] - bspList[bspcount,bsp.Ytop]) < 2*minheight)
        {
            var dirbranch = 0;
        }
        else
        {
            var dirbranch = irandom(1);
        }
        //2.choose a random position (x for vertical, y for horizontal)
        if (dirbranch == 0) //horizontal
        {
            var leftbound = bspList[bspcount,bsp.Xleft] + minwidth;
            var rightbound = bspList[bspcount,bsp.Xright] - minwidth;
            var splitpos = irandom_range(leftbound,rightbound) ;
        }
        else if (dirbranch == 1) //vertical
        {
            var splitpos = irandom_range(bspList[bspcount,bsp.Ytop] + minheight ,  bspList[bspcount,bsp.Ybot] - minheight);
        }
        //3.split the dungeon into two sub-dungeons/leaves
        //1st leaf
        var leafid = entries;
        bspList[leafid,bsp.Parent]     = bspcount;
        bspList[leafid,bsp.Generation] = bspList[bspcount,bsp.Generation] + 1;
        bspList[bspcount,bsp.Child1]   = leafid; //add children to parent
        bspList[leafid,bsp.Sibling]    = leafid + 1; //add sibling for lookup
        //this part depends on how the split happened.
        //as a rule, leaf one is top/left and two is bot/right. Just because.
        if (dirbranch == 0) //horizontal
        {
            bspList[leafid,bsp.Xleft]  = bspList[bspcount,bsp.Xleft] ;
            bspList[leafid,bsp.Xright] = splitpos;
            bspList[leafid,bsp.Ytop]   = bspList[bspcount,bsp.Ytop];
            bspList[leafid,bsp.Ybot]   = bspList[bspcount,bsp.Ybot];
        }
        else if (dirbranch == 1) //vertical
        {
            bspList[leafid,bsp.Xleft]  = bspList[bspcount,bsp.Xleft] ;
            bspList[leafid,bsp.Xright] = bspList[bspcount,bsp.Xright];
            bspList[leafid,bsp.Ytop]   = bspList[bspcount,bsp.Ytop] ;
            bspList[leafid,bsp.Ybot]   = splitpos;
        }
        //mark as unjoined
        bspList[leafid,bsp.Joined] = false;

        //2nd leaf
        leafid = bspList[leafid,bsp.Sibling];
        bspList[leafid,bsp.Parent]     = bspcount;
        bspList[leafid,bsp.Generation] = bspList[bspcount,bsp.Generation] + 1;
        bspList[bspcount,bsp.Child2]   = leafid; //add children to parent
        bspList[leafid,bsp.Sibling]    = leafid - 1; //add sibling for lookup
        //this part depends on how the split happened.
        //as a rule, leaf one is top/left and two is bot/right. Just because.
        if (dirbranch == 0) //horizontal
        {
            bspList[leafid,bsp.Xleft]  = splitpos ;
            bspList[leafid,bsp.Xright] = bspList[bspcount,bsp.Xright];
            bspList[leafid,bsp.Ytop]   = bspList[bspcount,bsp.Ytop];
            bspList[leafid,bsp.Ybot]   = bspList[bspcount,bsp.Ybot];
        }
        else if (dirbranch == 1) //vertical
        {
            bspList[leafid,bsp.Xleft]  = bspList[bspcount,bsp.Xleft] ;
            bspList[leafid,bsp.Xright] = bspList[bspcount,bsp.Xright];
            bspList[leafid,bsp.Ytop]   = splitpos ;
            bspList[leafid,bsp.Ybot]   = bspList[bspcount,bsp.Ybot];
        }
        //not joined yet
        bspList[leafid,bsp.Joined] = false;
        //mark as final/not final
        if (abs(bspList[leafid,bsp.Xleft] - bspList[leafid,bsp.Xright]) <= (2*minwidth) &&
            abs(bspList[leafid,bsp.Ytop] - bspList[leafid,bsp.Ybot]) <= (2*minheight)   ||
           (abs(bspList[leafid-1,bsp.Xleft] - bspList[leafid-1,bsp.Xright]) <= (2*minwidth ) &&
            abs(bspList[leafid-1,bsp.Ytop] - bspList[leafid-1,bsp.Ybot]) <= (2*minheight ))
        )
        {
            bspList[leafid,bsp.Final] = true;
            bspList[leafid-1,bsp.Final] = true;
        }
        else
        {
            bspList[leafid,bsp.Final] = false;
            bspList[leafid-1,bsp.Final] = false;
        }
      }
//move on to next leaf
bspcount ++;
}

//Copy final room data into into a ds_grid
var dungeon_map = ds_grid_create(width+1,height+1);
ds_grid_set_region(dungeon_map,0,0,width,height,0); //0 is filled, 1 is walkable

var bspcount = 0;
var entries = array_height_2d(bspList);
while (bspcount < entries )
{
    if bspList[bspcount,bsp.Final] == true
    {
        //move the rooms in by one square, prevent them from touching
        var roompad = 1;
        var xleft   = bspList[bspcount,bsp.Xleft] + roompad;
        var xright  = bspList[bspcount,bsp.Xright] - roompad;
        var ytop    = bspList[bspcount,bsp.Ytop] + roompad;
        var ybot    = bspList[bspcount,bsp.Ybot] - roompad;
        var xwig    = abs(xleft-xright);
        var ywig    = abs(ytop-ybot);
        //re-randomize the rooms within their new bounds, keeping in mind the minimum size

        if(xwig >= minwidth)
        {
            xright = irandom_range(xleft+minwidth,xright);
        }
        else
        {
            xright = irandom_range(xleft+minwidth/2,xright);
        }
        if(ywig >= minheight)
        {
            ybot = irandom_range(ytop + minheight,ybot);
        }
        else
        {
            ybot = irandom_range(ytop + minheight/2,ybot);
        }

            bspList[bspcount,bsp.Xleft]  = xleft;
            bspList[bspcount,bsp.Xright] = xright;
            bspList[bspcount,bsp.Ytop]   = ytop;
            bspList[bspcount,bsp.Ybot]   = ybot;
            ds_grid_set_region(dungeon_map,bspList[bspcount,bsp.Xleft],bspList[bspcount,bsp.Ytop],bspList[bspcount,bsp.Xright],bspList[bspcount,bsp.Ybot],irandom_range(2,4));

            //Place the spawn point if we haven't already.
            if (!spawnPlaced)
            {
                ds_grid_set(dungeon_map,(bspList[bspcount,bsp.Xleft] + bspList[bspcount,bsp.Xright])/2,(bspList[bspcount,bsp.Ytop] + bspList[bspcount,bsp.Ybot])/2,"P");
                spawnPlaced = true;
            }

    }
    bspcount++
}
//list to hold rooms to be joined, parents of final rooms will be added as they are joined
var worklist = ds_list_create();

var bspcount = 0;
var entries = array_height_2d(bspList);
while (bspcount < entries)
{
    if (bspList[bspcount,bsp.Final] == true && bspList[bspcount,bsp.Joined] == false)
    {
        var tleaf1 = bspcount;
        var tleaf2 = bspList[bspcount,bsp.Sibling];
        /*so what we want to do is determine the viable range of path locations.
        there are only 2 possible positions:
        1. Both arrayed Horizontally
        2. Both arrayed vertically
        */
        //step one, determine direction of join

        if  ((bspList[tleaf1,bsp.Xleft] >= bspList[tleaf2,bsp.Xleft] && bspList[tleaf1,bsp.Xleft] <= bspList[tleaf2,bsp.Xright])
            ||
            (bspList[tleaf2,bsp.Xleft] >= bspList[tleaf1,bsp.Xleft] && bspList[tleaf2,bsp.Xleft] <= bspList[tleaf1,bsp.Xright])
            )
        {
            //vertical join
            var xrangel = max(bspList[tleaf1,bsp.Xleft],bspList[tleaf2,bsp.Xleft]);
            var xranger = min(bspList[tleaf1,bsp.Xright],bspList[tleaf2,bsp.Xright]);
            var hallx   = irandom_range(xrangel,xranger)
            var ybot    = min(bspList[tleaf1,bsp.Ybot],bspList[tleaf2,bsp.Ybot]);
            var ytop    = max(bspList[tleaf1,bsp.Ytop],bspList[tleaf2,bsp.Ytop]);
            //create the hall
            ds_grid_set_region(dungeon_map,hallx,ytop,hallx,ybot,1)
        }
        else
        {
            //horizontal join
            var yrangel = max(bspList[tleaf1,bsp.Ytop],bspList[tleaf2,bsp.Ytop]);
            var yranger = min(bspList[tleaf1,bsp.Ybot],bspList[tleaf2,bsp.Ybot]);
            var hally = irandom_range(yrangel,yranger)
            var xleft = min(bspList[tleaf1,bsp.Xright],bspList[tleaf2,bsp.Xright]);
            var xright = max(bspList[tleaf1,bsp.Xleft],bspList[tleaf2,bsp.Xleft]);
            //create the hall
            ds_grid_set_region(dungeon_map,xleft,hally,xright,hally,1)
        }
        //tick em off
        bspList[tleaf1,bsp.Joined] = true;
        bspList[tleaf2,bsp.Joined] = true;
        //add parent to worklist
        ds_list_add(worklist,bspList[tleaf1,bsp.Parent]);


    }
    bspcount++;
}


//that's all the rooms partnered, now to join the meta-rooms
//final step! go through the worklist ONCE more times, building hallways between segments.
//Each metaroom is added to the worklist only after all its children have been joined
while(ds_list_size(worklist) > 0)
{
    //always pull from bottom of list
    var tleaf1 = worklist[|0];
    var tleaf2 = bspList[tleaf1,bsp.Sibling];

    if (bspList[tleaf1,bsp.Joined] == false)
    {
        if ((bspList[tleaf1,bsp.Xleft] == bspList[tleaf2,bsp.Xleft] && bspList[tleaf1,bsp.Xright] == bspList[tleaf2,bsp.Xright]))
        {
            //Vertical Join
            //First thing: determine which rooms is on top
            if (bspList[tleaf1,bsp.Ytop] < bspList[tleaf2,bsp.Ytop])
            {
                var topleaf = tleaf1;
                var botleaf = tleaf2;
            }
            else if (bspList[tleaf1,bsp.Ytop] > bspList[tleaf2,bsp.Ytop])
            {
                var topleaf = tleaf2;
                var botleaf = tleaf1;
            }
            //we want to join at the closest point, so move up from topleaf[ybot] and down from botleaf[ytop];
            //there are no possible failure states yet, each will always have 1's somewhere
            var offset = 0
            while ((offset < abs(bspList[topleaf,bsp.Ytop] - bspList[topleaf,bsp.Ybot])))
            {
                //test both rows for '1's, end and record if they both have them
                //you idiot, this needs to be two tests
                var toptest = ds_grid_value_exists(dungeon_map, bspList[topleaf,bsp.Xleft], bspList[topleaf,bsp.Ybot] - offset, bspList[topleaf,bsp.Xright], bspList[topleaf,bsp.Ybot] - offset, 1);
                if (toptest == true )
                {
                    var topy = bspList[topleaf,bsp.Ybot] - offset;
                    break;
                }
                offset++
            }
            //now for boty you fucking moron
            var offset = 0
            while( offset < abs(bspList[botleaf,bsp.Ytop] - bspList[botleaf,bsp.Ybot]))
            {
                var bottest = ds_grid_value_exists(dungeon_map, bspList[botleaf,bsp.Xleft], bspList[botleaf,bsp.Ytop] + offset, bspList[botleaf,bsp.Xright], bspList[botleaf,bsp.Ytop] + offset, 1);
                if (bottest == true)
                {
                    var boty = bspList[botleaf,bsp.Ytop] + offset;
                    break;
                }
                offset++;
            }
            //Now, using topy and boty as bounds, we search for columns where both have 1's present
            var offset = 0
            var columns = ds_list_create();
            while (offset <= abs(bspList[topleaf,bsp.Xleft] - bspList[topleaf,bsp.Xright]))
            {
                if(ds_grid_get_sum(dungeon_map, bspList[topleaf,bsp.Xleft] + offset, topy, bspList[topleaf,bsp.Xleft] + offset, boty) >= 2)
                //a leaf will never contribute more than 1, since we stopped at the first occupied cell.
                {
                    if (bspList[topleaf,bsp.Xleft] + offset != 0)
                    {
                        ds_list_add(columns,bspList[topleaf,bsp.Xleft] + offset);
                    }
                }
                offset ++
            }
            if (ds_list_size(columns) > 0)//we found at least one shared columnn. If we didnt, shit be zigzag OR WE BE DUMB!
            {
                //select from the available columns
                var listsize = ds_list_size(columns);
                var listind = irandom_range(0,listsize - 1)
                var hallx  = columns[|listind];
                //create the hall
                ds_grid_set_region(dungeon_map,hallx,topy,hallx,boty,1)
            }
            else
            {
                //also possible we had two ones that both have 1's at the Y offset, but do not have
                //viable columns at the same x-point.
                //in that case we need to move the offset? Or reconsider the whole way this works?
                //currently it doesn't try, so at least its obvious.
                //find some x values
                var offset = 0;
                while (offset <= abs(bspList[topleaf,bsp.Xleft] - bspList[topleaf,bsp.Xright]))
                {
                if(ds_grid_get(dungeon_map, bspList[topleaf,bsp.Xleft] + offset, topy) >= 1)
                {
                    var topx = bspList[topleaf,bsp.Xleft] + offset;
                    break; //right, that's the x value of our top leaf.
                }
                offset ++
                }
                var offset = 0;
                while (offset <= abs(bspList[botleaf,bsp.Xleft] - bspList[botleaf,bsp.Xright]))
                {
                if(ds_grid_get(dungeon_map, bspList[botleaf,bsp.Xleft] + offset, boty) >= 1)
                {
                    var botx = bspList[botleaf,bsp.Xleft] + offset;
                    break; //right, that's the x value of our bottom leaf.
                }
                offset ++
                }
                if (botx < topx)
                {
                    var rx = topx;
                    var lx = botx
                }
                else
                {
                    var lx = topx;
                    var rx = botx
                }
                //draw an L-shape?
                ds_grid_set_region(dungeon_map,rx,topy,rx,boty,1) //3 for debug
                ds_grid_set_region(dungeon_map,lx,boty,rx,boty,1) //3 for debug


            }
            ds_list_destroy(columns);

        }
        else if ((bspList[tleaf1,bsp.Ytop] == bspList[tleaf2,bsp.Ytop] && bspList[tleaf1,bsp.Ybot] == bspList[tleaf2,bsp.Ybot]))//it must be horizontal and we can just do mins/maxs for days
        {

            //HORIZONTAL Join (jesus, a typo in the first line)
            //First thing: determine which room is on the left
            if (bspList[tleaf1,bsp.Xleft] < bspList[tleaf2,bsp.Xleft])
            {
                var lftleaf = tleaf1;
                var rgtleaf = tleaf2;
            }
            else if (bspList[tleaf1,bsp.Xleft] > bspList[tleaf2,bsp.Xleft])
            {
                var lftleaf = tleaf2;
                var rgtleaf = tleaf1;
            }
            //we want to join at the closest point, so move right from lftleaf[xleft] and left from rgtleaf[xright];
            //there are no possible failure states yet, each will always have 1's somewhere
            var offset = 0
            while ((offset < abs(bspList[lftleaf,bsp.Xleft] - bspList[lftleaf,bsp.Xright])))
            {
                //test both rows for '1's, end and record if they both have them
                //you idiot, this needs to be two tests
                var lfttest = ds_grid_value_exists(
                dungeon_map,
                bspList[lftleaf,bsp.Xright] - offset, bspList[lftleaf,bsp.Ytop], bspList[lftleaf,bsp.Xright] - offset, bspList[lftleaf,bsp.Ybot],1);
                if (lfttest == true )
                {
                    var lftx = bspList[lftleaf,bsp.Xright] - offset;
                    break;
                }
                offset++
            }
            //now for rgty you fucking moron
            var offset = 0
            while( offset < abs(bspList[rgtleaf,bsp.Xleft] - bspList[rgtleaf,bsp.Xright]))
            {
                var rgttest = ds_grid_value_exists(dungeon_map, bspList[rgtleaf,bsp.Xleft] + offset,bspList[rgtleaf,bsp.Ytop],bspList[rgtleaf,bsp.Xleft] + offset,  bspList[rgtleaf,bsp.Ybot],  1);
                if (rgttest == true)
                {
                    var rgtx = bspList[rgtleaf,bsp.Xleft] + offset;
                    break;
                }
                offset++;
            }
            //Now, using lftx and rgtx as bounds, we search for rows where both have 1's present
            var offset = 0
            var rows = ds_list_create();
            while (offset <= abs(bspList[lftleaf,bsp.Ytop] - bspList[lftleaf,bsp.Ybot]))
            {
                if(ds_grid_get_sum(dungeon_map, lftx,bspList[lftleaf,bsp.Ytop] + offset,rgtx, bspList[lftleaf,bsp.Ytop] + offset) >= 2) //TODO: reverse the function arguments. Its easy they are named well.
                //a leaf will never contribute more than 1, since we stopped at the first occupied cell.
                {
                    if (bspList[lftleaf,bsp.Ytop] + offset != 0) //probably don't need this. But it's lucky.
                    {
                        ds_list_add(rows,bspList[lftleaf,bsp.Ytop] + offset);
                    }
                }
                offset ++
            }
            if (ds_list_size(rows) > 0)//we found at least one shared columnn. If we didnt, shit be zigzag OR WE BE DUMB!
            {
                //select from the available columns
                var listsize = ds_list_size(rows);
                var listind = irandom_range(0,listsize - 1)
                var hally  = rows[|listind];
                //create the hall
                ds_grid_set_region(dungeon_map,lftx,hally,rgtx,hally,1)
            }
            else
            {
                //zigzag join, brute force that sucker
                //find some y values
                var offset = 0;
                while (offset <= abs(bspList[lftleaf,bsp.Ytop] - bspList[lftleaf,bsp.Ybot]))
                {
                if(ds_grid_get(dungeon_map, lftx,bspList[lftleaf,bsp.Ytop] + offset) >= 1)
                {
                    var lfty = bspList[lftleaf,bsp.Ytop] + offset;
                    break; //right, that's the y value of our left leaf.
                }
                offset ++
                }
                var offset = 0;
                while (offset <= abs(bspList[rgtleaf,bsp.Ytop] - bspList[rgtleaf,bsp.Ybot]))
                {
                if(ds_grid_get(dungeon_map, rgtx, bspList[rgtleaf,bsp.Ytop] + offset) >= 1)
                {
                    var rgty = bspList[rgtleaf,bsp.Ytop] + offset;
                    break; //right, that's the x value of our bottom leaf.
                }
                offset ++
                }
                if (rgty < lfty)
                {
                    var ty = rgty;
                    var by = lfty;
                }
                else
                {
                    var by = rgty;
                    var ty = lfty;
                }
                //draw an L-shape?
                ds_grid_set_region(dungeon_map,rgtx,ty,rgtx,by,1) //3 for debug
                ds_grid_set_region(dungeon_map,lftx,by,rgtx,by,1) //3 for debug

            }
            ds_list_destroy(rows);


        }
        else
        {
            //zigzag join, this will suck. Wrong, this is detected elsewhere.
        }
            //tick em off
            bspList[tleaf1,bsp.Joined] = true;
            bspList[tleaf2,bsp.Joined] = true;
            //add parent to worklist
            ds_list_add(worklist,bspList[tleaf1,bsp.Parent]);
    }
    else
    {
        ds_list_delete(worklist,0);
    }
}
//and spit out the ds_grid for Alex to use. Hi Alex!
return dungeon_map;