Trying to generate phrase inside grid at random

I'm new to game dev and it's my first time posting in this forum. I'm halfway through the trial period and about 40 hours deep into tutorials, free and purchased, and some playing around. Granted, this is a very short time. I'm just trying to figure out what GMS is capable of. I have a series of tasks I'm trying to create.

Currently, I want a phrase, any phrase, like "to be or not to be," to populate inside a grid in a specific way. The first letter of the phrase could appear anywhere inside the grid, say a 16x20 grid of 32-pixel squares. Then, each additional letter would appear next to the previous in any direction other than the one occupied by the previous. The entire phrase would spell out this way, ignoring spaces between words. Once the phrase is complete, all remaining blank squares would fill with random letters, essentially hiding the phrase. There are some additional functions and checks I'd like to run but that's essentially it for now.

Can GMS2 do this? I can generate the grid and fill it with random letters. I've tried storing the phrase in a 2d array letter by letter and using for loops to generate it but the code to place the next letter in a random direction escapes me. I've tried storing the code in an array to move each letter differently but haven't gotten that to work, either. Ideally, too, the phrase wouldn't be drawn but would be comprised of sprites.

Any guidance would be appreciated. Sorry for the wide gaps in my knowledge. If you can recommend any tutorials you think could get me close, I'll take those, too.
 

Nidoking

Member
You could do something like add a random -1, 0, or 1 to each index and repeat until you find an empty cell in that direction (naturally, checking that you don't go outside the grid), or if you can't find an empty cell, back up and try again from the previous letter. You could also choose a random direction - 0 = up, 1 = up-right, etc.
 
You could do something like add a random -1, 0, or 1 to each index and repeat until you find an empty cell in that direction (naturally, checking that you don't go outside the grid), or if you can't find an empty cell, back up and try again from the previous letter. You could also choose a random direction - 0 = up, 1 = up-right, etc.
Is what you suggest automated, or possible to automate in the create event? When a player enters the room, I want the grid to populate immediately. And if the room is entered again, the phrase would be in a totally different random order.
 

Nidoking

Member
If you can find a way to do what I suggested in a way that is not automated in the Create event, I would love to hear about it.
 

Roleybob

Member
Ok, figured I'd give this a go.

Note:
  1. I'm just trying to give an idea of how you might do it so hopefully you understand the logic, therefore I haven't tested for bugs, so...
  2. Hope that someone with more experience can check and streamline this, or maybe give you a much easier way to do it
  3. This is going to be slow - the longer the phrase is (and the smaller the dimensions of the array), the more attempts the code will likely have to make to try to populate the array
  4. Remember to randomise();

GML:
var array_phrase_size;
array_phrase_size = 12;        //set to the highest value array cell in array_phrase[xx]//
    
array_phrase[12] = "t";        //set the phrase that we want to populate the final array with//
array_phrase[11] = "o";        //this is done manually here but a script could be written to automate,//
array_phrase[10] = "b";        //including setting the array_phrase_size variable to the correct value//
array_phrase[9] = "e";
array_phrase[8] = "o";
array_phrase[7] = "r";
array_phrase[6] = "n";
array_phrase[5] = "o";
array_phrase[4] = "t";
array_phrase[3] = "t";
array_phrase[2] = "o";
array_phrase[1] = "b";
array_phrase[0] = "e";

var array_width;         //how many columns we want in the array (will be 1 higher than the value given)//
var array_height;        //how many rows we want in the array (will be 1 higher than the value given)//
var cell_x;   
var cell_y;              //the x and y positions of cell in the array that we want to add the next letter to//
var iii;
var jjj;                 //iii and jjj used as counters for the for loops//
var success;             //whether we have succesfully stored the entire phrase in the array//
var letter_position;     //which letter of the phrase we are currently trying to add//
var cell_direction;      //which cell we are checking for availability to store the next letter in//
var list;                //use this to create a ds_list to determine which cell we are going to put the next letter in//

array_width = 16;   
array_height = 20;       //the number of rows and columns we want in the array//
success = false;         //whether we have succeded in storing the entire phrase into the array//

while !(success)
{

    for (iii = array_width; iii >= 0; iii  -= 1)        //create (or reset) the array with value 0 in each cell//
    {
        for (jjj = array_height; jjj >= 0; jjj  -= 1)
        {
            array[iii, jjj] = 0;
        }
    }

    cell_x = irandom(array_width);
    cell_y = irandom(array_height);              //start in a random cell of the array//
    letter_position = array_phrase_size;         //start with the first letter of the phrase to be added to the array//
    cell_direction = 0;                          //which direction in the array grid we are going to place the next letter//

    array[cell_x, cell_y] = array_phrase[letter_position];    //put the first letter of the phrase into the first chosen cell of the array//

    //for each letter in the phrase, find which neighbouring cells in the array are available and put them into a list//
    for (iii = array_phrase_size - 1; iii >= 0; iii -= 1)   
    {
        list = ds_list_create();

        if (cell_x < array_width)
        {
            if (array[cell_x + 1, cell_y] == 0)
                ds_list_add[list, "r"];
        }
        if (cell_x > 0)
        {
            if (array[cell_x - 1, cell_y] == 0)
                ds_list_add[list, "l"];
        }
        if (cell_y < array_height)
        {
            if (array[cell_x, cell_y + 1] == 0)
                ds_list_add[list, "d"];
        }
        if (cell_y > 0)
        {
            if (array[cell_x, cell_y - 1] == 0)
                ds_list_add[list, "u"];
        }
   
        //if there are no available positions in the array to put the next letter in, set iii to -1 so that we start the while loop again//
        if ds_list_empty(list)
        {
            ds_list_destroy(list);
            iii = -1;   
        }

        //if there is at least 1 available cell for the next letter,//
        //shuffle the list to randomly decide which available cell to put the next letter into//
        else
        {
            ds_list_shuffle(list);
    
            cell_direction = ds_list_find_index(list, 0);

            if (cell_direction == "r")
                cell_x += 1;
            else
            if (cell_direction == "l")
                cell_x -= 1;
            else
            if (cell_direction == "d")
                cell_y += 1;
            else
            if (cell_direction == "u")
                cell_y -= 1;
    
            //put the letter into the chosen cell of the array//
            array[cell_x, cell_y] = array_phrase[letter_position];
            ds_list_destroy(list);
    
            //move on to the next letter in the phrase//
            letter_position -=1;
    
            //if the phrase has been completed, remove the phrase from memory and end the while loop//
            if (letter_position == -1)
            {
                array_phrase = 0;
                success = true;
            }
        }
    }
}

//populate the unused cells of the array with a random letter//
for (iii = array_width; iii >= 0; iii -= 1)
{
    for (jjj = array_height; jjj >= 0; jjj -= 1)
    {
        if (array[iii, jjj] = 0)
            array[iii, jjj] = choose("a", "b", "c", ....... "y", "z");
    }
}
 
Last edited:

Nidoking

Member
That's... a lot to unpack. I believe the OP was asking for a grid, but you used a two-dimensional array. Easy enough to translate, but ds_grid_set_region or ds_grid_clear saves you at least one set of nested for loops. I don't see why you would create an array of letters instead of using a string and string parsing functions. Then the list shuffling seems a bit heavy to be done in a loop like this. It's fine, but I feel like creating and destroying a list that many times in a loop is poor design. I would just populate the list one time, shuffle it for each letter, and step through the list until you find an empty cell or you hit the end of the list and realize that you're surrounded by letters. Restarting the for loop also seems like a big pain to me. I would back up one letter and try again, although that requires more state tracking to reduce the amount of revisiting the same cell over and over. Manipulating the indices of a for loop directly is just asking for trouble - you definitely just want to break and let the while handle restarting the loop if that's the way you want to go. That's what the while is there for.

Finally, and this isn't part of the design but would be a good idea to add, you should probably do something with the random letters generated at the end to make sure you're not creating alternate paths with the same letters as the phrase. Preventing the generator from producing a copy of any letter within two cells of the one you're filling in, or better, any letter of the phrase that's within two cells, might be worth considering.
 

Roleybob

Member
Yes it is. I think it's going to be more difficult to understand the logic if you have to backtrack 5 letters to find another option though.

  • I figured that a 1D array to hold the target phrase would make it easier to understand as it focuses on the logic rather than creating another complication
  • Yes, it is not efficient design but the list is there to determine and randomise what "directions" the next letter can go in, I'm not using the list to hold the letters but rather the directions of the next available cells
  • The iii = -1 was to add a shortcut to restart the while by stopping the for loop from continuing when the code got to a point that it already couldn't get any further but fair play, maybe not a good idea. I got myself in a muddle and couldn't decide whether the while would execute again if I used a break - I didn't have GM open at the time
Thanks for your input though :)
 
Last edited:

TheouAegis

Member
The way I would handle this is to use a recursive-backtracking (or hunt-kill?) algorithm to plot out a random path, keeping track of the length of the path. If the length of the path is shorter than the length of the phrase, scrap it and generate a new path. Once the path is generated, break the algorithm and then populate the grid with random letters in each unfilled cell.
 
Last edited:

Roleybob

Member
Hmm, something very wrong with my code and I want to figure it out but have to go now... Maybe figure it out tomorrow

But OP probably wants to follow the advice of Nidoking or TheouAegis anyway
 

TheouAegis

Member
I think this is what the OP was looking for:
Code:
randomize();
maze_width = 16;
maze_height = 16;
grid = ds_grid_create(maze_width,maze_height);

var list = ds_list_create();
var word = string_replace_all(string_upper("Make America Great Again")," ","");
var length = string_length(word);
var loop = 1;
var i = 0;
var rand, count, next_x, next_y, current_x, current_y;

while loop {
    if i == 0 {
        ds_grid_clear(grid,0);
        current_x = irandom(maze_width - 1);
        current_y = irandom(maze_height - 1);
        next_x = current_x;
        next_y = current_y;
        count = 0;
        ds_list_clear(list);

    }
    rand = irandom(3);
    i = 4;
    while i {
        switch rand
        {
            case 0: if (current_x == 0)  || (ds_list_find_index(list, current_y * maze_width + current_x - 1) | 1)
                    {
                        rand = ++rand & 3;
                        i--;
                    }
                    else
                    {
                        next_x = current_x - 1;
                        i = -1;
                    }
                    break;

            case 1: if (current_x == maze_width - 1) || (ds_list_find_index(list,current_y * maze_width + current_x + 1) | 1)
                    {
                        rand = ++rand & 3;
                        i--;
                    }
                    else
                    {
                        next_x = current_x + 1;
                        i = -1;
                    }
                    break;

            case 2: if (current_y == 0) || (ds_list_find_index(list,(current_y - 1) * maze_width + current_x) | 1)
                    {
                        rand = ++rand & 3;
                        i--;
                    }
                    else    
                    {
                        next_y = current_y - 1;
                        i = -1;
                    }
                    break;

            case 3: if (current_y == maze_height - 1) || (ds_list_find_index(list,(current_y + 1) * maze_width + current_x) | 1)
                    {
                        rand = ++rand & 3;
                        i--;
                    }
                    else
                    {
                        next_y = current_y + 1;
                        i = -1;
                    }
                    break;
        }
    }

    ds_list_add(list,current_y * maze_width + current_x);
    current_x = next_x;
    current_y = next_y;
    if ++count == length
        loop = 0;
}

for(i=0; i<length; i++)
    grid[# list[|i] mod maze_width, list[|i] div maze_width] = string_char_at(word,i+1);

for(next_x = 0; next_x < maze_width; next_x++)
for(next_y = 0; next_y < maze_height; next_y++)
    if grid[#next_x, next_y] == 0
        grid[#next_x, next_y] = chr(irandom_range(ord("A"),ord("Z")));
ds_list_destroy(list);
Code:
var i,j;
for(i=0; i<maze_width; i++)
for(j=0; j<maze_height; j++)
    draw_text(i * 32, j * 32, grid[#i, j]);
 
Last edited:

Roleybob

Member
Looks like this is solved now but this is working for me.

It's still pretty sloppy though

GML:
randomise();

array_width = 20;
array_height = 16;       //the number of rows and columns we want in the array//

var cell_x;
var cell_y;              //the x and y positions of cell in the array that we want to add the next letter to//
var iii;
var jjj;                 //iii and jjj used as counters for the for loops//
var success;             //whether we have succesfully stored the entire phrase in the array//
var letter_position;     //which letter of the phrase we are currently trying to add//
var cell_direction;      //which cell we are checking for availability to store the next letter in//
var list;                //use this to create a ds_list to determine which cell we are going to put the next letter in//
var array_phrase_size;     //how long the target phrase is (will be 1 digit longer)//

success = false;         //whether we have succeded in storing the entire phrase into the array//
array_phrase_size = 12;        //set to the highest value array cell in array_phrase[xx]//

array_phrase[12] = "T";        //set the phrase that we want to populate the final array with//
array_phrase[11] = "O";        //this is done manually here but a script could be written to automate,//
array_phrase[10] = "B";        //including setting the array_phrase_size variable to the correct value//
array_phrase[9] = "E";
array_phrase[8] = "O";
array_phrase[7] = "R";
array_phrase[6] = "N";
array_phrase[5] = "O";
array_phrase[4] = "T";
array_phrase[3] = "T";
array_phrase[2] = "O";
array_phrase[1] = "B";
array_phrase[0] = "E";

while !(success)
{
    //create (or reset) the array with value 0 in each cell//
    for (iii = array_width; iii >= 0; iii --)       
    {
        for (jjj = array_height; jjj >= 0; jjj --)
        {
            array[iii, jjj] = 0;
        }
    }
 
    cell_x = irandom(array_width);
    cell_y = irandom(array_height);              //start in a random cell of the array//
    letter_position = array_phrase_size;         //start with the first letter of the phrase to be added to the array//
    cell_direction = 0;                          //which direction in the array grid we are going to place the next letter//

    array[cell_x, cell_y] = array_phrase[letter_position];    //put the first letter of the phrase into the first chosen cell of the array//
    letter_position -= 1;

    //for the current letter, find the available adjacent cells//
    for (iii = letter_position; iii >= 0; iii --)
    {

        list = ds_list_create();
        ds_list_clear(list);
 
        //for each direction from the current cell, check whether the edge of the grid has been reached, or if the cell is already filled//
        if (cell_x < array_width)
            if (array[cell_x + 1, cell_y] == 0)
                ds_list_add(list, 1);
        if (cell_x > 0)
            if (array[cell_x - 1, cell_y] == 0)
                ds_list_add(list, 2);
        if (cell_y < array_height)
            if (array[cell_x, cell_y + 1] == 0)
                ds_list_add(list, 3);
        if (cell_y > 0)
            if (array[cell_x, cell_y - 1] == 0)    
                ds_list_add(list, 4);

        //if there are no availble cells, break the for loop to restart the while//
        if (ds_list_empty(list))
            break;
         
        //if there is at least one availble cell, randomly determine which cell to put the next letter in//
        else
        {              
            ds_list_shuffle(list);

            cell_direction = ds_list_find_value(list, 0);

            if (cell_direction == 1)
                cell_x += 1;
            else
            if (cell_direction == 2)
                cell_x -= 1;
            else
            if (cell_direction == 3)
                cell_y += 1;
            else
            if (cell_direction == 4)
                cell_y -= 1;
 
            array[cell_x, cell_y] = array_phrase[letter_position];
 
            //move on to the next letter. if the phrase has been completed then break from the while//                 
            letter_position -=1;        
            if (letter_position == -1)
            {
                success = true;
            }            
        }
    }
}
 
ds_list_destroy(list);

//populate the unused cells of the array with a random letter//
for (iii = array_width; iii >= 0; iii --)
{
    for (jjj = array_height; jjj >= 0; jjj --)
    {
        if (array[iii, jjj] == 0)
            array[iii, jjj] = choose("o", "x");
    }
}
Oh, and I assumed that you didn't need to be told this but to draw the grid:

draw event
GML:
var iii;
var jjj;

for (iii = array_width; iii >= 0; iii -= 1)
{
    for (jjj = array_height; jjj >= 0; jjj -= 1)
    {
        if (array[iii, jjj] != 0)
            draw_text(x + (iii * 32), y + (jjj * 32), array[iii, jjj]);       
    }
}
 
Last edited:
Top