[SOLVED] Kruskal's Maze Generation, Joining Sets

[Bentley]

I was reading about Kruskal's maze algorithm (http://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm), and after many mistakes, I understand how it works, but I don't know a good way to merge sets. The author of that link uses a tree data structure. So he can merge entire sets by just "adding one tree as a subtree of another". I don't know how to do that in GML, so I was thinking of work-arounds. Does anyone have any ideas for merging sets?

Thanks for reading.

 

[NightFrost]

You've already marked this as solved, but... Any reason why you want to use Kruskal's in particular? I haven't tried implementing that but I have done recursive backtracker and growing tree, and both can be ran while-ing away across a single array without needing to glue data structures together.

 

[GrizzliusMaximus]

You can possibly use gms 2.3's constructors to make a node which contains a list of other nodes and those other nodes will have a list of other nodes and it goes on and on. That's the basics of a tree data structure.

 

[Bentley]

You've already marked this as solved, but... Any reason why you want to use Kruskal's in particular? I haven't tried implementing that but I have done recursive backtracker and growing tree, and both can be ran while-ing away across a single array without needing to glue data structures together.

Thanks for the reply. I'm doing this maze just for fun/learning. I thought with the new GML changes I might be able to do it. I ended up with something like this (it's ugly but w/e):
o_control [Create]

for (var j = 0; j < ROWS; j++)
for (var i = 0; i < COLS; i++)
{
    with (instance_create_layer(i * CELL_SIZE, j * CELL_SIZE, layer, o_cell))
    {
        // Give each cell a unique set
        set = instance_number(object_index);
    }
}

(Edited a bit ) And one go of the algorithm would be something like this (using instances to make it easier atm)

    if (ds_list_size(edges) <= 1)
    {
        show_message("maze done");
        exit;
    }

    ds_list_shuffle(edges);

    // Get the edge's x, y, and direction
    var _cx  = edges[| 0][X];
    var _cy  = edges[| 0][Y];
    var _dir = edges[| 0][DIR];

    // Get the room coordinates for the two cells the edge connects
    var _x1 = _cx * CELL_SIZE + CELL_SIZE / 2;
    var _y1 = _cy * CELL_SIZE + CELL_SIZE / 2;
    var _x2 = (_cx + lengthdir_x(1, _dir)) * CELL_SIZE + CELL_SIZE / 2;
    var _y2 = (_cy + lengthdir_y(1, _dir)) * CELL_SIZE + CELL_SIZE / 2;

    var _cell_A = instance_position(_x1, _y1, o_cell);
    var _cell_B = instance_position(_x2, _y2, o_cell);
    var _set_into = _cell_A.set;
    var _set_from = _cell_B.set;

    // They must be from diff sets
    if (_set_into != _set_from)
    {
        // Break walls between the two cells
        _cell_A.walls[_dir div 90] = false;
        _cell_B.walls[ (_dir == NORTH ? SOUTH : EAST) div 90 ] = false;
   
        // Merge all cells with B's set to A's set
        with (o_cell)
        {
            if (set == _set_from)
            {
                set = _set_into;
            }
        }
    }

    ds_list_delete(edges, 0);

 

[Bentley]

@GrizzliusMaximus thx for the reply and I will check it out (got to go atm, but I will def. look into it when I'm back).