GM:S 1.4 [SOLVED?] Kruskal maze weird bugs

Discussion in 'Advanced Programming Discussion' started by TheouAegis, Nov 20, 2018.

  1. TheouAegis

    TheouAegis Member

    Joined:
    Jul 3, 2016
    Posts:
    6,535
    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: Nov 24, 2018

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice