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.
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.
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);
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: