Labyrinth Proc Gen in GML

/*
Firstly, there needs to be 3 objects:

labyrinth_generation (the name doesn't matter for this one)
obj_room (this name DOES matter)
obj_corridor (so does this one!)

obj_room and obj_corridor should both have the same sprite; a filled in square that is the same
size as your WALL_SIZE macro (check below). So for mine, the sprite is a 64x64 white square, if
you use 32x32 as a grid size, you should make it a 32x32 white square. labyrinth_generation doesn't
need a sprite. You can set these objects to invisible if you are simply using the grid for your
labyrinth. No code is necessary in obj_room or obj_corridor.

You also have to set 3 (three) macros:

WALL_SIZE
FLOOR
WALL

Set WALL_SIZE equal to whatever you want your grid size to be (mine is 64x64), FLOOR equal
to whatever value you want the grid to use as a floor and WALL equal to whatever value you
want your grid to use as a wall.

Finally, you will need 3 (three) scripts:

generate_rooms()
generate_corridor()
rectangle_intersect()

Those names matter so keep them, unless you edit the code. Paste the first section of code below into
the Create Event of your generation object (labyrinth_generation in this example). Below that are the
scripts for generate_rooms(), generate_corridor() and rectangle_intersect(). This work is licensed under
a Creative Commons Attribution 3.0 Australia License (https://creativecommons.org/licenses/by/3.0/au/). =D

-RefresherTowel
*/


/*************************************************/
/***** GENERATION OBJECT CREATION CODE START *****/
/*************************************************/

randomize();

//Set the width and height of the room
room_width = WALL_SIZE*150;
room_height = WALL_SIZE*150;

//Set the width and height of the grid
grid_width = room_width/WALL_SIZE;
grid_height = room_height/WALL_SIZE;

arena = ds_grid_create(grid_width,grid_height);
ds_grid_clear(arena,WALL);

//Start room position variation
var start_random = 10;
//X and y of the first room coordinates
start[0] = round(grid_width/2)-irandom(start_random/2)+irandom(start_random);
start[1] = round(grid_height/2)-irandom(start_random/2)+irandom(start_random);

//Corridor min and max length & width
corridor_length[0] = 5;
corridor_length[1] = 15;
corridor_width[0] = 2;
corridor_width[1] = 6;

//Room min and max size
rm_size[0] = 10;
rm_size[1] = 45;

//Min and max number of rooms
rm_max_no[0] = 3;
rm_max_no[1] = 10;

//Make sure at least 1 room is generated
if (rm_max_no[0] < 1) {
    rm_max_no[0] = 1;
}
if (rm_max_no[1] < 1) {
    rm_max_no[1] = 1;
}

//Actual number of rooms and corridors
rm_no = irandom_range(rm_max_no[0],rm_max_no[1]);
corridor_no = rm_no-1;

//Allow rooms to overlap?
overlap = false;

generate_rooms();

/*************************************************/
/****** GENERATION OBJECT CREATION CODE END ******/
/*************************************************/




/*************************************************/
/****** generate_rooms() SCRIPT CODE START *******/
/*************************************************/

///generate_rooms();

//Make sure the arrays don't hold data
rm = noone;
corridor = noone;
pos = noone;
room_array = noone;

//Initialise the counter (to break the for if it can't generate a room)
var c = 0;

//Loop through the target number of rooms to create them
for(var i=0;i<rm_no;i++) {
    //Starting room
    if (i == 0) {
        //Create the room and store it in the rm array
        rm[i] = instance_create(start[0]*WALL_SIZE,start[1]*WALL_SIZE,obj_room);

        //Choose the width and height
        var width = irandom_range(rm_size[0],rm_size[1]);
        var height = irandom_range(rm_size[0],rm_size[1]);

        //Store the room properties in an array to be checked against if overlapping is set to false
        room_array[i,0] = start[0];
        room_array[i,1] = start[1];
        room_array[i,2] = width;
        room_array[i,3] = height;

        //Set the room to the correct width and height
        rm[i].width = width;
        rm[i].height = height;
        rm[i].image_xscale = width;
        rm[i].image_yscale = height;

        //Generate the corridor for the room
        pos = generate_corridor(i,start,width,height,-1); //-1 for the first room direction

        /*
        The pos variable is now an array containing 5 elements: the grid x and grid y coordinates of the next room,
        the direction from the next room to the corridor that leads into it and the width and height of the next room
        (pos[0],pos[1],pos[2],pos[3],pos[4]). We will use this to create the new room in the next loop.
        */

        //Give the room a number; not used in this generation script but might be useful for something else
        rm[i].no = i;

        //Set the arena grid inside the room to FLOOR
        for (var xx=start[0];xx<start[0]+width;xx++) {
            for (var yy=start[1];yy<start[1]+height;yy++) {
                arena[# xx,yy] = FLOOR;
            }
        }
    }
    //Other rooms
    else if (i < rm_no-1) {
        rm[i] = instance_create(pos[0]*WALL_SIZE,pos[1]*WALL_SIZE,obj_room);
        //Get the width and height for the room, which was generated in the previous corridor
        var width = pos[3];
        var height = pos[4];
        //Store room properties for overlapping check
        room_array[i,0] = pos[0];
        room_array[i,1] = pos[1];
        room_array[i,2] = width;
        room_array[i,3] = height;
        //Set the width and height
        rm[i].width = width;
        rm[i].height = height;
        rm[i].image_xscale = width;
        rm[i].image_yscale = height;

        /*
        If the room is outside the grid bounds (this should never happen!)
        the gen will restart
        */
        if (pos[0] < 1 || pos[0]+width > grid_width-1 || pos[1] < 1 || pos[1]+height > grid_height-1 || place_meeting(x,y,obj_room)) {
            show_debug_message("Room outside bounds, restarting!");
            room_restart();
            break;
        }
        else {
            //Give the room a number and generate its corridor
            rm[i].no = i;
            //Set the arena grid inside the room to FLOOR
            for (var xx=pos[0];xx<pos[0]+width;xx++) {
                for (var yy=pos[1];yy<pos[1]+height;yy++) {
                    arena[# xx,yy] = FLOOR;
                }
            }
            //Generate the new corridor
            pos = generate_corridor(i,pos,width,height,pos[2]);
            //If a new corridor can't be generated then stop
            if (pos == 0) {
                show_debug_message("Too many rooms, stopping generation");
                break;
            }
        }
    }
    //Generate the last room
    else {
        rm[i] = instance_create(pos[0]*WALL_SIZE,pos[1]*WALL_SIZE,obj_room);
        //Width and height from corridor
        var width = pos[3];
        var height = pos[4];
        //Store room properties for overlapping check
        room_array[i,0] = pos[0];
        room_array[i,1] = pos[1];
        room_array[i,2] = width;
        room_array[i,3] = height;
        //Set the width and height
        rm[i].width = width;
        rm[i].height = height;
        rm[i].image_xscale = width;
        rm[i].image_yscale = height;
        //Restart if outside bounds (should never happen!)
        if (pos[0] < 1 || pos[0]+width > grid_width-1 || pos[1] < 1 || pos[1]+height > grid_height-1 || place_meeting(x,y,obj_room)) {
            show_debug_message("Room outside bounds, restarting!");
            room_restart();
            break;
        }
        else {
            rm[i].no = i;
            //Set the arena grid inside the room to FLOOR
            for (var xx=pos[0];xx<pos[0]+width;xx++) {
                for (var yy=pos[1];yy<pos[1]+height;yy++) {
                    arena[# xx,yy] = FLOOR;
                }
            }
        }
    }
    //If too many iterations have happened without being able to generate a room break the loop
    if (c < 1000) {
        c++;
    }
    else {
        show_debug_message("Cant generate a room, stopping!");
        break;
    }
}

/*************************************************/
/******* generate_rooms() SCRIPT CODE END ********/
/*************************************************/




/*************************************************/
/***** generate_corridor() SCRIPT CODE START *****/
/*************************************************/

///generate_corridor(corridor_no,pos,room_width,room_height,old_corridor_dir);
var c_no = argument0;
var r_pos = argument1;
var r_width = argument2;
var r_height = argument3;
var p_dir = argument4;

//Generate a new corridor if the corridor limit hasn't been reached
if (c_no < corridor_no) {

    //Set a random direction
    dir = irandom(3);

    //If the random direction goes back along the previous generated corridor, pick a new direction
    if (dir == p_dir) {
        dir = (dir+1) mod 4;
    }

    //Check to see if the corridor + new room will fit
    var fits = false;
    var attempts = 0;
    while (fits == false) {
        //Pick a length for the corridor
        var length = irandom_range(corridor_length[0],corridor_length[1]);
        var c_width = irandom_range(corridor_width[0],corridor_width[1]);
        //Pick a width and height for the room at the end of the new corridor
        var new_width = irandom_range(rm_size[0],rm_size[1]);
        var new_height = irandom_range(rm_size[0],rm_size[1]);
        //Cycle through the potential directions, finding the coordinates for the new room
        switch (dir) {
            case 0:
                new_x = r_pos[0]+r_width;
                new_y = r_pos[1]+irandom(r_height-1);

                //Make the corridor move to try to fit the width without spilling over the side
                while (new_y+c_width > r_pos[1]+r_height-1) {
                    new_y--;
                    if (new_y <= r_pos[1]) {
                        new_y = r_pos[1];
                        break;
                    }
                }

                //If overlapping is allowed
                if (overlap) {
                    //If the corridor or new room goes outside the grid boundary, pick a new direction to branch into
                    if (new_x+length+new_width > grid_width-1 || new_y < 1 || new_y+new_height > grid_height-1) {
                        dir = (dir+1) mod 4;
                    }
                    //Otherwise it fits
                    else {
                        fits = true;
                    }
                }

                //If overlapping isn't allowed
                else {
                    //Check against the boundaries
                    if (new_x+length+new_width > grid_width-1 || new_y < 1 || new_y+new_height > grid_height-1) {
                        dir = (dir+1) mod 4;
                    }

                    //Otherwise check against overlap
                    else {
                        var rooms_cleared = 0;
                        for (var k=0;k<instance_number(obj_room);k++) {
                            if (rectangle_intersect(new_x+length,room_array[k,0],new_y,room_array[k,1],new_width,room_array[k,2],new_height,room_array[k,3])) {
                                //Try a new direction if current direction leads to an overlap
                                dir = (dir+1) mod 4;
                                fits = false;
                                break;
                            }
                            else {
                                //Add to the rooms cleared variable for every room that is checked and doesn't overlap
                                rooms_cleared++;
                            }
                        }

                        //If all the rooms are clear, then the new room will fit, otherwise it won't
                        if (rooms_cleared == instance_number(obj_room)) {
                            fits = true;
                        }
                        else {
                            fits = false;
                        }
                    }
                }
            break;

            //As above but for a new direction
            case 1:
                new_x = r_pos[0]+irandom(r_width-1);
                new_y = r_pos[1];
                while (new_x+c_width > r_pos[0]+r_width-1) {
                    new_x--;
                    if (new_x <= r_pos[0]) {
                        new_x = r_pos[0];
                        break;
                    }
                }
                if (overlap) {
                    if (new_y-length-new_height < 1 || new_x < 1 || new_x+new_width > grid_width-1) {
                        dir = (dir+1) mod 4;
                    }
                    else {
                        fits = true;
                    }
                }
                else {
                    if (new_y-length-new_height < 1 || new_x < 1 || new_x+new_width > grid_width-1) {
                        dir = (dir+1) mod 4;
                    }
                    else {
                        var rooms_cleared = 0;
                        for (var k=0;k<instance_number(obj_room);k++) {
                            if (rectangle_intersect(new_x,room_array[k,0],new_y-length-new_height,room_array[k,1],new_width,room_array[k,2],new_height,room_array[k,3])) {
                                dir = (dir+1) mod 4;
                                fits = false;
                                break;
                            }
                            else {
                                rooms_cleared++;
                            }
                        }
                        if (rooms_cleared == instance_number(obj_room)) {
                            fits = true;
                        }
                        else {
                            fits = false;
                        }
                    }
                }
            break;

            //As above but for a new direction
            case 2:
                var new_x = r_pos[0];
                var new_y = r_pos[1]+irandom(r_height-1);
                while (new_y+c_width > r_pos[1]+r_height-1) {
                    new_y--;
                    if (new_y <= r_pos[1]) {
                        new_y = r_pos[1];
                        break;
                    }
                }
                if (overlap) {
                    if (new_x-length-new_width < 1 || new_y < 1 || new_y+new_height > grid_height-1) {
                        dir = (dir+1) mod 4;
                    }
                    else {
                        fits = true;
                    }
                }
                else {
                    if (new_x-length-new_width < 1 || new_y < 1 || new_y+new_height > grid_height-1) {
                        dir = (dir+1) mod 4;
                    }
                    else {
                        var rooms_cleared = 0;
                        for (var k=0;k<instance_number(obj_room);k++) {
                            if (rectangle_intersect(new_x-length-new_width,room_array[k,0],new_y,room_array[k,1],new_width,room_array[k,2],new_height,room_array[k,3])) {
                                dir = (dir+1) mod 4;
                                fits = false;
                                break;
                            }
                            else {
                                rooms_cleared++;
                            }
                        }
                        if (rooms_cleared == instance_number(obj_room)) {
                            fits = true;
                        }
                        else {
                            fits = false;
                        }
                    }
                }
            break;

            //As above but for a new direction
            case 3:
                new_x = r_pos[0]+irandom(r_width-1);
                new_y = r_pos[1]+r_height;
                while (new_x+c_width > r_pos[0]+r_width-1) {
                    new_x--;
                    if (new_x <= r_pos[0]) {
                        new_x = r_pos[0];
                        break;
                    }
                }
                if (overlap) {
                    if (new_y+length+new_height > grid_height-1 || new_x < 1 || new_x+new_width > grid_width-1) {
                        dir = (dir+1) mod 4;
                    }
                    else {
                        fits = true;
                    }
                }
                else {
                    if (new_y+length+new_height > grid_height-1 || new_x < 1 || new_x+new_width > grid_width-1) {
                        dir = (dir+1) mod 4;
                    }
                    else {
                        var rooms_cleared = 0;
                        for (var k=0;k<instance_number(obj_room);k++) {
                            if (rectangle_intersect(new_x,room_array[k,0],new_y+length,room_array[k,1],new_width,room_array[k,2],new_height,room_array[k,3])) {
                                dir = (dir+1) mod 4;
                                fits = false;
                                break;
                            }
                            else {
                                rooms_cleared++;
                            }
                        }
                        if (rooms_cleared == instance_number(obj_room)) {
                            fits = true;
                        }
                        else {
                            fits = false;
                        }
                    }
                }
            break;
        }

        //If too many attempts have been made to place a room, then it is impossible, so end the loop
        if (attempts < 1000) {
            attempts++;
        }
        else {
            break;
        }
    }
    //If the new corridor and room fit inside the grid
    if (fits) {
        //Generate the corridor and give it a number; the number isn't used in the script but it might be useful for something else
        corridor[c_no] = instance_create(new_x*WALL_SIZE,new_y*WALL_SIZE,obj_corridor);
        corridor[c_no].no = c_no;
        //Scale the corridor according to the direction it is branching in
        switch (dir) {
            case 0:
                corridor[c_no].image_xscale = length;
                corridor[c_no].image_yscale = c_width;
                //Set the new rooms starting coordinates
                c_pos[0] = new_x+length;
                c_pos[1] = new_y;
                /*
                Set the arena grid inside the corridor to FLOOR (you could create a new macro
                and set this to something else if you wanted to have the rooms and corridors
                be distinct
                */
                for (var xx=new_x;xx<new_x+length+1;xx++) {
                    for (var yy=new_y;yy<new_y+c_width;yy++) {
                        arena[# xx,yy] = FLOOR;
                    }
                }
            break;

            //As above for a different direction
            case 1:
                corridor[c_no].image_yscale = -length;
                corridor[c_no].image_xscale = c_width;
                c_pos[0] = new_x;
                c_pos[1] = new_y-length-new_height;
                for (var yy=new_y;yy>new_y-length-1;yy--) {
                    for (var xx=new_x;xx<new_x+c_width;xx++) {
                        arena[# xx,yy] = FLOOR;
                    }
                }
            break;

            //As above for a different direction
            case 2:
                corridor[c_no].image_xscale = -length;
                corridor[c_no].image_yscale = c_width;
                c_pos[0] = new_x-length-new_width;
                c_pos[1] = new_y;
                for (var xx=new_x;xx>new_x-length-1;xx--) {
                    for (var yy=new_y;yy<new_y+c_width;yy++) {
                        arena[# xx,yy] = FLOOR;
                    }
                }
            break;

            //As above for a different direction
            case 3:
                corridor[c_no].image_yscale = length;
                corridor[c_no].image_xscale = c_width;
                c_pos[0] = new_x;
                c_pos[1] = new_y+length;
                for (var yy=new_y;yy<new_y+length+1;yy++) {
                    for (var xx=new_x;xx<new_x+c_width;xx++) {
                        arena[# new_x,yy] = FLOOR;
                    }
                }
            break;
        }

        /*
        Let the new room know which direction corridor that creates it is so we
        can make sure the next corridor doesn't go back in the same direction
        */
        c_pos[2] = (dir+2) mod 4;

        //Pass through the width and height of the next room
        c_pos[3] = new_width;
        c_pos[4] = new_height;

        /*
        Return an array containing the grid x and y coordinates c_pos[0] & c_pos[1] for the next room,
        the direction of the old corridor c_pos[2] and the width and height c_pos[3] & c_pos[4] for the
        next room, so we can use them to generate it
        */
        return c_pos;
    }
}

/*************************************************/
/****** generate_corridor() SCRIPT CODE END ******/
/*************************************************/




/*************************************************/
/**** rectangle_intersect() SCRIPT CODE START ****/
/*************************************************/

///rectangle_intersect(rect1_x,rect2_x,rect1_y,rect2_y,rect1_width,rect2_width,rect1_height,rect2_height);
//Adapted from a mozilla code fragment with the help of Sidorakh
var rect1_x,rect2_x,rect1_y,rect2_y,rect1_width,rect2_width,rect1_height,rect2_height;
rect1_x = argument0-1;
rect2_x = argument1-1;
rect1_y = argument2-1;
rect2_y = argument3-1;
rect1_width = argument4+1;
rect2_width = argument5+1;
rect1_height = argument6+1;
rect2_height = argument7+1;

if (rect1_x < rect2_x + rect2_width &&
   rect1_x + rect1_width > rect2_x &&
   rect1_y < rect2_y + rect2_height &&
   rect1_height + rect1_y > rect2_y) {
    return true;
}
else {
    return false;
}

/*************************************************/
/***** rectangle_intersect() SCRIPT CODE END *****/
/*************************************************/

//And you're done!