GameMaker Possible help getting my head around implementing a variable Mondrian/Mosaic style sprite slicing routine?

[Japster]

Hi guys - working on a quick puzzle game as a free Xmas game, and it relies upon having an image cut up into random(ish) rectangles, Mondrian style... (completely real-time randomized, as opposed to a few different layouts, hence my problem!)

I'm using a recursive split method, and the first cut works fine, but I'm struggling to get my head around how to work the logic to work properly iteratively. I always seem to have a meltdown trying to implement recursive logic...

So, if I run it once, passing in the original source sprite, I get 2 smaller partial sprites as expected, either split horizontally or vertically, using this coordinate logic - this sets the coordinates correctly, from what I can tell... ie.:-



ie. I get a random horizontal/vertical split, 2 sprites:-





But if I call it again, twice, from itself, trying to pass in the 2 newly-created cut out sprites, to further split them (if they're large enough, given a minimum pixel size, otherwise I keep which half/halves I have, and exit to end that branch), I just get (e.g.) this?:-



Ideally, I've LOVE to be able to cut an image up like, eg. these examples below (albeit down to smaller pieces), but I can't seem to figure out a routine for that, hence trying the recursive binary split method...



Now I know that my code for this is horrendous, but here's the 'split' function in it's entirety - I set up some global variables in the game, and all the game code itself does is pretty much call the initial instance of this sprite-slicing routine, to fill a global ds_grid with sprite piece ID's and their correct locations within the main source image:-

Also have the following macro's set up:-

#macro Spr_ID 0
#macro x_Pos 1
#macro y_Pos 2
#macro Discard_Piece 3

#macro random_split 0
#macro hori_split 1
#macro vert_split 2

/// Slice_Sprite (Source_Sprite, This_Sprite_Piece_Index,Offset_X,Offset_Y, Split_Type)
/// @param Source_Sprite
/// @param This_Sprite_Piece_Index
/// @param Offset_X
/// @param Offset_Y
/// @param Split_Type

var source_sprite = argument[0];
var This_Sprite_Piece_Index = argument[1];
var Offset_X = argument[2];
var Offset_Y = argument[3];

var minimum_Split_Size = Smallest_Slice_Size_In_Pixels*2;

//if (argument_count != 5)
//{
//    var split_type = random_split;
//}
//else
//{
    var split_type = argument[4];
   
    if (split_type == random_split)
    {
        split_type = choose(hori_split,vert_split);
    }
//}

var t_height = sprite_get_height(source_sprite);
var t_width = sprite_get_width(source_sprite);

var vertical_split_position = 0;
var horizontal_split_position = 0;

if (split_type = hori_split)
{
    var vertical_split_position =
        (t_height >= (minimum_Split_Size)) *
        irandom_range(Smallest_Slice_Size_In_Pixels+1,t_height-Smallest_Slice_Size_In_Pixels);
}

if (split_type = vert_split)
{
    var horizontal_split_position =
        (t_width >= (minimum_Split_Size)) *
        irandom_range(Smallest_Slice_Size_In_Pixels+1,t_width-Smallest_Slice_Size_In_Pixels);
}

if (!horizontal_split_position && !vertical_split_position)
{
    return false; // Leave alone / end this branch, as we've hit minimum size!
}

// Draw to surface, and cut both parts back out...

var t_Jigsaw = surface_create(t_width*Puzzle_Scale,t_height*Puzzle_Scale);

surface_set_target(t_Jigsaw);
draw_clear_alpha(c_black, 1);
draw_sprite_ext(source_sprite, 0, Offset_X, Offset_Y,Puzzle_Scale,Puzzle_Scale,0,c_white,1);

var t_x1 = Offset_X; // Will always be top-left
var t_y1 = Offset_Y; // Will always be top-left

var t_x4 = Offset_X + t_width*Puzzle_Scale;  // Will always be bottom-right
var t_y4 = Offset_Y + t_height*Puzzle_Scale; // Will always be bottom-right


if (split_type == hori_split) // Going to slice Horizontally!
{
    var t_x2 = t_x4; // Will always be top-left
    var t_y2 = Offset_Y + (vertical_split_position*Puzzle_Scale); // Will always be top-left

    var t_x3 = Offset_X;//horizontal_split_position*Puzzle_Scale; // Will always be bottom-right
    var t_y3 = Offset_Y + (vertical_split_position*Puzzle_Scale+1);   // Will always be bottom-right      
}
else
{      
    var t_x2 = Offset_X + (horizontal_split_position*Puzzle_Scale); // Will always be top-left
    var t_y2 = t_y4; // Will always be top-left

    var t_x3 = Offset_X + (horizontal_split_position*Puzzle_Scale+1); // Will always be bottom-right
    var t_y3 = t_y1; //vertical_split_position*Puzzle_Scale;   // Will always be bottom-right  
}

// discard the passed in 'source' sprite if not initial project sprite
if (This_Sprite_Piece_Index != 0) sprite_delete (source_sprite);

var t_sprite_1 = sprite_create_from_surface(t_Jigsaw, t_x1, t_y1, t_x2-t_x1,t_y2-t_y1, false, false, 0, 0);
Slice_Sprite_ID_List[# This_Sprite_Piece_Index, Spr_ID] = t_sprite_1;
Slice_Sprite_ID_List[# This_Sprite_Piece_Index, x_Pos] = t_x1;
Slice_Sprite_ID_List[# This_Sprite_Piece_Index, y_Pos] = t_y1;
   
var This_Sprite_Piece_Index_2 = Next_Piece_Grid_ID;
Next_Piece_Grid_ID += 1;

show_debug_message(string(Next_Piece_Grid_ID));

var t_sprite_2 = sprite_create_from_surface(t_Jigsaw, t_x3, t_y3, t_x4-t_x3,t_y4-t_y3, false, false, 0, 0);
Slice_Sprite_ID_List[# This_Sprite_Piece_Index_2, Spr_ID] = t_sprite_2;
Slice_Sprite_ID_List[# This_Sprite_Piece_Index_2, x_Pos] = t_x3;
Slice_Sprite_ID_List[# This_Sprite_Piece_Index_2, y_Pos] = t_y3;

surface_reset_target();
surface_free(t_Jigsaw);

//  ^^^   Done this split! -----------------

// Next, we recursively call this routine again for each piece, if either/both are big enough...
// --------------------------------------------
// Split SPRITE 1 if possible

t_height =     sprite_get_height(t_sprite_1);
t_width  =     sprite_get_width(t_sprite_1);
var t_split = -1; // default to no split

if  (t_height >= minimum_Split_Size) && (t_width >= minimum_Split_Size)
{
    t_split = choose(hori_split,vert_split);
}
else
{
    if  (t_height >= minimum_Split_Size)
    {
        t_split = hori_split;      
    }
    else
    {
        if (t_width >= minimum_Split_Size) t_split = vert_split;
    }
}

if (t_split >= 0) var t_result = Slice_Sprite(t_sprite_1,This_Sprite_Piece_Index,t_x1,t_y1,t_split); // We can split again, so recurse.

// --------------------------------------------
// Split SPRITE 2 if possible

t_height =     sprite_get_height(t_sprite_2);
t_width  =     sprite_get_width(t_sprite_2);
var t_split_2 = -1; // default to no split
   
if  (t_height >= minimum_Split_Size) && (t_width >= minimum_Split_Size)
{
    t_split_2 = choose(hori_split,vert_split);
}
else
{
    if  (t_height >= minimum_Split_Size)
    {
        t_split_2 = hori_split;      
    }
    else
    {
        if (t_width >= minimum_Split_Size) t_split_2 = vert_split;
    }
}
   
if (t_split_2 >= 0) var t_result = Slice_Sprite(t_sprite_2,This_Sprite_Piece_Index_2,t_x3,t_y3,t_split_2); // We can split again, so recurse.

return (t_split || t_split_2); // if we split at least 1 of these created 'halves', return true...

Any help pointing me towards my stupid mistake(s) would be greatly appreciated guys!


Cheers!

 

[Nidoking]

I don't understand why you've got extra logic in the function to handle re-splitting the sprites. Surely, you'd call the function, get two new sprites, and then just call the same function on those sprites?

 

[Japster]

I don't understand why you've got extra logic in the function to handle re-splitting the sprites. Surely, you'd call the function, get two new sprites, and then just call the same function on those sprites?

Cheers for the input @Nidoking - it's basically because I'm seeing if either resultant piece is large enough to allow further splitting, once I've split the source sprite in any iteration of the routine - if at least one IS, then that called instance of the routine should call another iteration to do this, and once dealt with for this source piece, just returns. Then each called instance does the same (until they all end naturally, when they can no longer split either of their 'source' pieces further.)

This way, I figured recursively calling the routine *should* split all available created pieces, once all recursions are complete?

It doesn't atm, but only, I think, because I'm obviously doing something daft!

I mean, I could perform the minimum size check in the calling routine, but I want each iteration to only split further if the pieces are bigger than the minimum size allowable, and then only on an axis that fits this criteria - and once I crack this, not even that, as the lowest levels will be randomly split OR just left as-is, to give some random skill 'wiggle'....

Hope that explains my logic / thinking mate!

EDIT:- The reason I don't simply call it again for each piece from the main calling instance, ie. in a loop etc, is because as it splits, it creates double instances each time, which is a nightmare to deal with without using recursion (although I guess I can perhaps initially run the split, save all new pieces back to the grid, re-run using the grid, and stop running once I have NO splits flagged for any given run), but again, struggling to get my head around it, and recursion definitely seems the neatest, most logical (for me) way of solving this particular problem?

 

[Japster]

Project attached - I added some outlines for the pieces, which shows me that my logic is REALLY wrong....



Test Project

 

[Nidoking]

(although I guess I can perhaps initially run the split, save all new pieces back to the grid, re-run using the grid, and stop running once I have NO splits flagged for any given run)

This is what I would recommend. I think recursion is really not your friend here. You can even put the pieces in a separate grid as you determine that they're too small, so that you're only looping over the ones that might still be big enough, although your size checks should be light enough, and the number of pieces small enough, that you wouldn't be saving much time. This also allows you to, say, run the loop only a certain number of times and see the results after each iteration, to help you track where anything might be going wrong in the algorithm. Maybe the first loop works as intended, but something's going wrong with the second loop.

 

[Japster]

Hi @Nidoking! -REALLY appreciate you coming back to me on this mate.... ...and I was so ready to try your kind suggestion, but...

I've fixed a stupid error, and... ...this is now so close, I can almost taste it....

Project link updated... ...PS - If we manage to crack this guys, I'm not precious - anyone can use the routine once it works (hence I didn't mind sharing the project!), I don't care!:-



EDIT:- Figured I'd try and break it... Still marks the exact correct positions every time, just an issue with where I'm dropping the sprite on the surface, and grabbing it from (lots of "data from outside surface" errors)...

 

[Padouk]

I'd still keep the recursion as lean and clean as possible. Do the work only at the leaf of that depth first search algorithm.

puzzle_splice recursivly call itself without doing anything until the puzzle pieces are too small.
They can't be split anymore? They are effective puzzle fragments... that's when you create your instance.

--

Note sure exactly where you are going with this so i'm just throwing version using a stack.
I recursivly break the Pieces in two and when I hit a leaf, I push it on the stack.
Once the recursion bubble up. That stack can be sequencially looked at to do whatever you want.

function puzzle_splice(x,y, width, height, stack) {
   //.. code ommited.. you already know how to split right...


   if can still split in two then {
      //This is your recursive loop
      puzzle_splice(x1, y1, width1, height1, stack);
      puzzle_splice(x2, y2, width2, height2, stack);
   }

   else {
      //We have reached the end... this is a leaf (or a puzzle fragment) let's push it to the stack
      puzzle_push(stack, x, y, width, height);
   }
}

function puzzle_push(stack, x, y, width, height)
{
  //If you prefere array use array...
  //if you prefer to create your layer_instance here. create it here.....
  //I'm using a buffer cause i'm lazy and it self increment the offset and the new items are always "pushed" at the end that's what I want..
  buffer_write(stack, buffer_f32, x);
  buffer_write(stack, buffer_f32, y);
  buffer_write(stack, buffer_f32, width);
  buffer_write(stack, buffer_f32, height);
}

Now it's just a matter of calling that recursion... to fill in that stack

var stack = buffer_create(1024, buffer_fixed, 4);
puzzle_split(0, 0, your_image_width, your_image_height, stack);


//You can now have access to your puzzle in a sequential way.... create your surface and break that surface here.
var stack_size = buffer_tell(stack);
buffer_seek(stack, buffer_seek_start, 0);
for(var i = 0; i < stack_size< i++) {
   var puzzle_x = buffer_read(stack, buffer_f32);
   var puzzle_y = buffer_read(stack, buffer_f32);
   var puzzle_width = buffer_read(stack, buffer_f32);
   var puzzle_height = buffer_read(stack, buffer_f32);

   //You do whatever you like here ...
   draw_sprite_general(sp_sprite, 0, puzzle_x , puzzle_y, puzzle_width , puzzle_height , ....
}

 

[Japster]

Thanks @Padouk @Nidoking !

I must say, that looks a lot neater than what I've done! - I've also figured out I don't need to keep creating surfaces, whoops...

Had a quick play of my routine, using simpler logic to decide whether or not to split again, and so far:-





Still need to re-jig the weighting algorithm, and tbh, I'm definitely leaning towards making it none-recursive - this is not only a headache to implement, but probably to maintain / work on!

 

[Japster]

BTW - I realised I never updated this thread guys, sorry!...

I managed to get this working okay in the end, by using both @Nidoking and @Padouk's advice and logic to tweak my existing routine!

It's now NONE-recursive, and stores temp working slice data as 'areas' in an array, works really well for my current requirements (but see below), and is a darned sight easier to understand / maintain!

Many thanks guys! - Will post the new code up once I can comment it better, and get it to correctly select minumum and maximum lengths - it still seems to struggle with what should be an easy issue! - I'm guessing it's maths-related...

ie. 'too long minimum side length' specification and too many pieces, causes it to hang as it simply cannot make enough pieces (Looking at creating a foolproof algorithm to ensure that this doesn't happen).

Thanks again for the kind help and thoughts, guys!

 

[Liquid]

normally recursive should be easier to programm.
flattening a recursive problem is possable always, but needs to store some extra data of the progress.

i used recursive code once in GM2 and it given me lots and lots of stack overflow errors.
GM2 was (at the time i used recursion) only able to get into recursion depth of 22, after that it thrown an error.
i guess it made a copy of the whole object every time entering a new recursion depth and soon after 22 depth the stack was full.....
(just guessing)
maybe this is fixed now and you can use recursion proberbly now.

ok i guess i am slightly offtopic...sorry