Question - Code Recursion

Discussion in 'GameMaker Studio 2 Community Tech Support' started by Japster, May 11, 2019.

  1. Japster

    Japster Member

    Joined:
    Aug 5, 2017
    Posts:
    51
    Looking at this recursion thread, as I'm having a VERY strange recursion issue.... Our recursive routine always returns a string value, and this works fine in VM, but screws up (even when only running 1 iteration/level of recursion) using YYC. I literally check the values are strings just prior to calling itself, and once called, suddenly the returned value is no longer a string? - If anyone, maybe that genius @YellowAfterlife :) can help out with info or just plain something daft we're doing (we're currently leaning towards it being a YYC compiler or code creation issue, as out of ideas - assigned the value separately, performed the splice function outside of the call, remmed out chunks of code, but all to no avail!

    We've even swapped around IDE versions and runtimes, just in case, but no joy...

    The recursive routine (btw, 'state' is a string, initally passed in via the calling routine as "" / empty) is as follows:-

    Code:
    /// GridSolver_SolveRecursive (solver,playableCoordinates,state,playablePieces,recDepth)
    /// @param solver
    /// @param playableCoordinates
    /// @param state
    /// @param playablePieces
    /// @param recDepth
    var solver = argument[0];
    var playableCoordinates = argument[1];
    var state = argument[2];
    var playablePieces = argument[3];
    var recDepth = argument[4];
    //show_debug_message("state : "+state+".");
    //show_debug_message("String Length : "+string(string_length(state))); 
     
    var randomPieces = Array_Shuffle(playablePieces);
    if (string_length(state) >= (min(5,floor(Total_Tiles/4))))
        return state;
    //if (string_length(state) > floor(CurrentPlayableTileCount/4)){
    //    return state;
    //}
    var bestSolution = state;
    var subSolution = "";
    for (var shapeIndex = 0; shapeIndex < array_length_1d(randomPieces); shapeIndex++)
    {
        var shapeNumber = randomPieces[shapeIndex]; 
        for (var coordinateIndex = 0; coordinateIndex < array_length_1d(playableCoordinates); coordinateIndex++)
        {
            var coordData = playableCoordinates[coordinateIndex];
            var xx = coordData[Coordinate_PROPS_X];
            var yy = coordData[Coordinate_PROPS_Y];
     
            for (var rotation = 0; rotation < UniqueRotations[shapeNumber]; rotation++)
            {
                var shapeData = ShapeData_Create(shapeNumber,rotation);
            
                var offsetPieceCoordinates = ShapeData_GetOffsetCoordinates(shapeData,xx,yy);
                
                if GridSolver_CellsAreAvailable(solver,offsetPieceCoordinates)
                {             
                    GridSolver_SetCellsAvailability(solver,offsetPieceCoordinates,false);
                
                    var t_state = state + string(shapeNumber);
                    show_debug_message("1 state is string : "+string(is_string(state)));
                    show_debug_message("1 argument is string : "+string(is_string(state+string(shapeNumber))));
                    show_debug_message("1 subSolution is string : "+string(is_string(subSolution)));
                    show_debug_message("1 bestSolution is string : "+string(is_string(bestSolution)));
                    var t_result = GridSolver_SolveRecursive(
                        solver,
                        Array_Splice(playableCoordinates,coordinateIndex,1),
                        state + string(shapeNumber),
                        playablePieces,
                        recDepth+1);
                    
                    var subSolution = t_result;
                    show_debug_message("2 state is string : "+string(is_string(state)));
                    show_debug_message("2 argument is string : "+string(is_string(state+string(shapeNumber))));
                    show_debug_message("2 subSolution is string : "+string(is_string(subSolution)));
                    show_debug_message("2 bestSolution is string : "+string(is_string(bestSolution)));
                    GridSolver_SetCellsAvailability(solver,offsetPieceCoordinates,true);
                    show_debug_message("3 state is string : "+string(is_string(state)));
                    show_debug_message("3 argument is string : "+string(is_string(state+string(shapeNumber))));
                    show_debug_message("3 subSolution is string : "+string(is_string(subSolution)));
                    show_debug_message("3 bestSolution is string : "+string(is_string(bestSolution)));
                    if (string_length(subSolution) > string_length(bestSolution))
                    {
                        bestSolution = subSolution;
                        if (string_length(bestSolution) >= (min(5,floor(Total_Tiles/4))))
                        {
                            return bestSolution;
                        }
                    }
                }
            }
        }
    }
    return bestSolution;
    ...and the debug output is:-

    Code:
    Total memory used = 34236847(0x020a69af) bytes
    **********************************.
    Entering main loop.
    **********************************.
    Received stats and achievements from Steam
    Resizing swap chain...Resizing window...
    state : .
    String Length : 0
    1 state is string : 1
    1 argument is string : 1
    1 subSolution is string : 1
    1 bestSolution is string : 1
    state : 3.
    String Length : 1
    1 state is string : 1
    1 argument is string : 1
    1 subSolution is string : 1
    1 bestSolution is string : 1
    state : 32.
    String Length : 2
    2 state is string : 1
    2 argument is string : 1
    2 subSolution is string : 0
    2 bestSolution is string : 1
    3 state is string : 1
    3 argument is string : 1
    3 subSolution is string : 0
    3 bestSolution is string : 1
    ERROR!!! :: ############################################################################################
    FATAL ERROR in
    action number 1
    of Mouse Event for Left Pressed
    for object Steam_Set:
    string_length argument 1 incorrect type (undefined) expecting a String (YYGS)
    ############################################################################################
    --------------------------------------------------------------------------------------------
    called from - gml_Script_GridSolver_SolveRecursive (line 75)
    called from - gml_Script_GridSolver_SolveRecursive (line 55)
    called from - gml_Script_GridSolver_Solve (line 12)
    called from - gml_Object_Steam_Set_Mouse_4 (line 27)

    Again, any light shed on this with a view to resolving it would be most appreciated!

    Thanks all!


    Den / Japster
     
    Last edited: May 11, 2019
  2. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    936
    The code on it's own is too involved for me to know what is really happening, like the other scripts called I don't know what happens in those,
    but I wanna know which script is the recursive one?
    Looking through the script, if this is the main script, it's not technically recursive
     
    Last edited: May 11, 2019
    Japster likes this.
  3. FrostyCat

    FrostyCat Member

    Joined:
    Jun 26, 2016
    Posts:
    4,547
    I can't really see what could have gone wrong either. Two things you might want to try:
    • Using the argumentn form instead of argument[n]
    • Cutting out t_state and t_result entirely
    As an additional diagnostic measure, you should use string() to print out the intermediate values as well, not just the result of is_string(). Normally this isn't necessary, but with a potential engine-level type bug involved there really is no other choice.
     
    Japster and Joe Ellis like this.
  4. Joe Ellis

    Joe Ellis Member

    Joined:
    Aug 30, 2016
    Posts:
    936
    I doubt it is an engine level bug, I'm suspecting that its a simple coding error (I've had at least 200 of those, sometimes the most ridiculous thing), but I spose we need to see what @Japster has to say first
     
    Japster likes this.
  5. Japster

    Japster Member

    Joined:
    Aug 5, 2017
    Posts:
    51
    Hi @Joe Ellis !

    The actual script IS recursive mate - there's a calling routine that sets it up, then calls the routine pasted:-

    GridSolver_SolveRecursive (solver,playableCoordinates,state,playablePieces,recDepth)

    ...It then repeatedly calls itself:-

    ie.

    var t_result = GridSolver_SolveRecursive(
    solver,
    Array_Splice(playableCoordinates,coordinateIndex,1),
    state + string(shapeNumber),
    playablePieces,
    recDepth+1);

    ....once it has processed the current board location.

    It was a tricky one to get working recursively, but in VM it works perfectly... :(

    PS - recDepth is just for debugging purposes...


    @FrostyCat - thanks for the input too mate...

    The t_State was actually added as a debug test, to 'get at' the value before the recursive call returned a corrupted variable (it even comes back as <undefined>, and the routine CANNOT normally exit/return at ANY POINT without passing what was given in (so possible corruption upon entry OR corruption on exit)), I should have been a bit clearer, but I was dog-tired... :)

    ps - yep, good suggestion - we initially printed out the string - it's fine for a couple of recursions, then doesn't print anything when this happens - it's what threw us initially, and only after investigating did we realise it was no longer defined on the back of the last recursive call! - hence the 'Is_String' debug... Before that, it was simply which shapes it's managed to fit into the board at the current point/path to a full solution - ie "1" or "135" / "332", then it suddenly becomes 'undefined'....

    The argumentn form sounds like a thing to try, cheers - I'd been using that one exclusively since starting with GMS2, but recently started using the bracketed variant...

    We've racked our brains (I've got a good friend involved (and in fact he worked out this whole solution to my original problem for me), and neither of us can see anything wrong with that code) and WERE thinking it MUST be a code error, but mountains of debug code, alternative coding and consistently incorrect debug results are really making us now think it's a YYC issue - I've logged an official support request last night, so here's hoping, but yeah, given I need to work on releasing a BIG update, so a workaround is probably preferable at this point, for speed purposes, while a potential fix is worked on IF it's an engine / compiler issue....

    Argh!

    EDIT:- No joy mate... change to argumentn format, same result.....

    Log Output:-

    Code:
    ___________________________________________
    ############################################################################################
    FATAL ERROR in
    action number 1
    of Mouse Event for Left Pressed
    for object Steam_Set:
    
    string_length argument 1 incorrect type (undefined) expecting a String (YYGS)
    ############################################################################################
    --------------------------------------------------------------------------------------------
    called from - gml_Script_GridSolver_SolveRecursive (line 77)
    called from - gml_Script_GridSolver_SolveRecursive (line 55)
    called from - gml_Script_GridSolver_SolveRecursive (line 55)
    called from - gml_Script_GridSolver_Solve (line 12)
    called from - gml_Object_Steam_Set_Mouse_4 (line 27)
    Debug code:-

    Code:
    1 state is string : 1
    1 argument is string : 1
    1 subSolution is string : 1
    1 bestSolution is string : 1
    1 state is string : 1
    1 argument is string : 1
    1 subSolution is string : 1
    1 bestSolution is string : 1
    1 state is string : 1
    1 argument is string : 1
    1 subSolution is string : 1
    1 bestSolution is string : 1
    2 state is string : 1
    2 argument is string : 1
    2 subSolution is string : 0
    2 bestSolution is string : 1
    3 state is string : 1
    3 argument is string : 1
    3 subSolution is string : 0
    3 bestSolution is string : 1
    So, it (GridSolver_SolveRecursive) gets called from the calling routine (GridSolve_Solve) fine, calls itself once fine at line 55, then calls itself from inside THAT instance, and the 3rd level instance fails when trying to access that string variable, at line 77.

    @Nocturne any possible ideas please fella? - Sorry to keep tagging you, but I do always appreciate the fact that you try to help too.... :)
     
    Last edited: May 11, 2019
  6. YellowAfterlife

    YellowAfterlife ᴏɴʟɪɴᴇ ᴍᴜʟᴛɪᴘʟᴀʏᴇʀ Forum Staff Moderator

    Joined:
    Apr 21, 2016
    Posts:
    2,404
    Micah_DS and Japster like this.
  7. Japster

    Japster Member

    Joined:
    Aug 5, 2017
    Posts:
    51
    @YellowAfterlife THANK YOU mate! - I'm currently using version 2.2.2.413 of the IDE, and runtime 2.2.1.287 (I did use the latest of both to test, but as they've not helped, and as you mention, some VERY weird 'alarm' type (not firing, etc) bugs cropped up when using the later runtime, I reverted back to these)...

    I've checked your links and that is EXACTLY what we're experiencing.... What I'm a bit put out by is that despite giving example code in both of your cases, YoYo have just closed those with an 'unable to reproduce' status?!

    I grabbed 2.2.0.x of the runtime and guess what? - you're right - Recursion works PERFECTLY, and ALWAYS, even over 50+ runs and 1,000's of iterations, gives the expected returned result (TRUE for is_string, and the correct string returned), although as it's a much older runtime, it gives me graphical depth and other issues on the game now, so can't really use it as a workaround. So YoYo really need to fix this ASAP, it seems.... (The only solution to this problem IS using recursion, and it should just work, as has been proven)...

    @Nocturne could we please get YellowAfterLife's bug reports re-opened? - I could supply my project too, but YAL's code is simple and VERY easy to reproduce the bug with - I've tried it too....
     
    Last edited: May 11, 2019
    Micah_DS likes this.
  8. Nocturne

    Nocturne Friendly Tyrant Forum Staff Admin

    Joined:
    Apr 13, 2016
    Posts:
    6,894
    One of the bugs was closed as unable to reproduce, while the other was closed as fixed (although your issue would suggest it's not... :( ) I would ask that you file a new bug report yourself, and include a simple project link as well as a link to this topic and the other bug reports. The other bug reports probably won't be re-opened, but a new bug will be created and assigned from your sample project. Oh, and I don't mind being tagged at all, but I would request you don't tag any of the other YYG staff, thanks!
     
    Japster likes this.
  9. Japster

    Japster Member

    Joined:
    Aug 5, 2017
    Posts:
    51
    Thanks as always @Nocturne , and apologies, I'll untag Dan, whoops... :)
     
    Nocturne likes this.
  10. Japster

    Japster Member

    Joined:
    Aug 5, 2017
    Posts:
    51
    Ps - We *may* be able to get this working by using a global, as it's not a multiple threads at once recursion method, so hoping this will give us a workaround (although ideally we ultimately need it to work the way it does, so we can optimise it as a 'multiple simultaneous threads from main' type solution - I'll also log my own bug report - My project is around 80MB at present, so I might strip out the music files to reduce the size, unless it's not an issue...

    Cheers!
     
  11. Japster

    Japster Member

    Joined:
    Aug 5, 2017
    Posts:
    51
    Well, at least the 'global' results hack/workaround is working for us now... Slightly off-topic @Nocturne , but the optimisations are in, and I have to say, when it works as expected, GMS2 and in particular YYC is bloody impressive...

    ...working out the best placements for 3 moves ahead across a board, with a choice of 7 different shapes for each move, and 4 orientations each time, marking a temp grid and recursing / backtracking as it goes, takes just 19-20ms to return a 'best play' solution, on my admittedly quick system, but still, WOW!

    Working out to a depth of even 5 moves, across random shapes, placement, and orientations to get the best allocation of shapes, just takes 500-600ms, which given we're now talking 100's of 1,000's (and in some cases, millions) of combinations, is pretty amazing!

    Yeah, the code's impressive (although the REALLY clever bits/scripts aren't mine!), but I honestly thought GMS2 would struggle with this re. speed, given the magnitude of the calculations / task....

    Colour me impressed, guys! :D

    (just out of interest, with 5 moves ahead, and no short-circuiting optimisations, we worked out there would have been potentially over 2,000,000,000,000 possible move combinations to check for, on a 20 tile remaining layout.....).
     
    Last edited: May 11, 2019

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