# 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: