• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Legacy GM [SOLVED?] Kruskal maze weird bugs

TheouAegis

Member
As part of my further attempts to make my own maze algorithms in GMS1 using buffers (yeah they're slow, but it's more about just toying with memory management attempts), I tried tackling Kruskal's algorithm.

Code:
//Add the cells to the maze separated by 4 walls
buffer_fill(maze,0,1,$F0, maze_size);

//Initialize the sets array and the shuffle "bag" for randomization
var bag = ds_list_create();
for(var i=0; i<maze_size; i++)
{
    sets[i] = i;
    bag[|i] = i;
}

var a,b,c,p,n = 1;
while mapped < maze_size
{
    ds_list_shuffle(bag);

    for(i=0; i<maze_size; i++)
    {
        //Grab a cell pointer out of the bag
        p = bag[|i];

        //Attempt to find a "random" direction to open up
        switch irandom(3)
        {
            case 0:
                //Open to the left
                if p mod maze_width
                {
                    a = buffer_peek(maze,p,1);
                    if a & left
                    {
                        if sets[p] != sets[p-1]
                        {
                            b = buffer_peek(maze,p-1,1);
                            buffer_poke(maze,p,1,a & ~left);
                            buffer_poke(maze,p-1,1,b & ~right);
                            m_kruskal_script(sets,p,p-1);
                            break;
                        }
                    }
                }
            case 1:
                //Open to the right
                if p mod maze_width < maze_width-1
                {
                    a = buffer_peek(maze,p,1);
                    if a & right
                    {
                        if sets[p] != sets[p+1]
                        {
                            b = buffer_peek(maze,p+1,1);
                            buffer_poke(maze,p,1,a & ~right);
                            buffer_poke(maze,p+1,1,b & ~left);
                            m_kruskal_script(sets,p,p+1);
                            break;
                        }
                    }
                }
            case 2:
                //Open to the top
                if p div maze_width
                {
                    a = buffer_peek(maze,p,1);
                    if a & up
                    {
                        if sets[p] != sets[p-maze_width]
                        {
                            b = buffer_peek(maze,p-maze_width,1);
                            buffer_poke(maze,p,1,a & ~up);
                            buffer_poke(maze,p-maze_width,1,b & ~down);
                            m_kruskal_script(sets,p,p-maze_width);
                            break;
                        }
                    }
                }
            case 3:
                //Open to the bottom
                if p div maze_width < maze_height-1
                {
                    a = buffer_peek(maze,p,1);
                    if a & down
                    {
                        if sets[p] != sets[p+maze_width]
                        {
                            b = buffer_peek(maze,p+maze_width,1);
                            buffer_poke(maze,p,1,a & ~down);
                            buffer_poke(maze,p+maze_width,1,b & ~up);
                            m_kruskal_script(sets,p,p+maze_width);
                            break;
                        }
                    }
                }
        }
    }

    //Check if all cells belong to the same set
    for(mapped=0; mapped<maze_size; mapped++)
        if sets[mapped] break;
    show_debug_message(mapped)
}
ds_list_destroy(bag);
The script m_kruskal_script() simply takes the smaller of the two sets specified (vis-a-vis argument0[@argument1] and argument0[@argument2]) and assigns the higher set to the smaller set. The idea is that by the time the maze is done, all entries sets[n] would have a value of 0.

Update: Found one typo in case 2 which was causing the fifth bug.
Update 2: Apparently that one little typo messed everything up. Go fig. I'll still look a bit further into whether the sets were being created properly (e.g., if the set is [0,0,0,4,4] I better see a horizontal path 3 wide every time), but the other bugs are clearly fixed. *sheepish laugh*

HOLY CRAP IS THIS SLOW!!!! Fast enough on a small maze, but 22 seconds just to generate a $60x$60 maze! I think it times out if I go $80x80 because I never even saw it work beyond that.
 
Last edited:
Top