Legacy GM Reducing lag in my tile-based path finding code?

MeBoingus

Member
Hi all,

I'm working on a game that features potentially thousands of different tiles (placable by the player) and I'm currently stuck in a bit of a rut. In essence, I'm trying to set up creatures that can path find via an MP grid.

The system I'm working with at the moment does the following:

Checks all tiles in a specified radius around the creature.
Checks if those tiles are the 'walkable' type.
If they are, their tile ID is added to a DS list.
We then shuffle the DS list and loop through each tile, checking to see if we can path find to it.
If we can, we break the loop and output a message (this is just for testing purposes, in future, they'll switch states and start the new path).
If we get through the loop and there's no path found, we simply show a different message.


Although this system does work, it is (of course) not very scalable. When there are a few of these 'creatures' in the room, there's often a 1-2 second delay. I've narrowed the bottleneck down to the loop in finding the nearby tiles (a 5x5 radius [5 tiles in all directions] is 100 iterations, for example).

Is there anything I could do to improve this code?

See below:

GML:
var gridX, gridY, radius, tileStack;

gridX = coord_to_grid(x); // Simply round(x / gridSize) * gridSize to find the exact x position of the 'tile' we're in.
gridY = coord_to_grid(y);
radius = 5;

tileStack = ds_list_create();

mp_grid_destroy(myMP);
myMP = mp_grid_create(gridX - (gridSize * radius), gridY - (gridSize * radius), radius * 2, radius * 2, gridSize, gridSize);
mp_grid_add_rectangle(myMP, gridX - (gridSize * radius), gridY - (gridSize * radius), gridX + (gridSize * radius), gridY + (gridSize * radius));
// Clear, create and fill in the MP grid.

for (var iY = -radius; iY < radius; iY ++)
{
    for (var iX = -radius; iX < radius; iX ++)
    {
        var tID = tile_layer_find(10, gridX + (gridSize * iX), gridY + (gridSize * iY));
        
        // Loop through the radius around the instance and find each tile ID in the X * X area.
                
        if (tile_get_left(tID) == 0 && tile_get_top(tID) == 0) // If this tile is the one we're after
        {
            var tX, tY;
            
            tX = tile_get_x(tID);
            tY = tile_get_y(tID);
            
            mp_grid_clear_cell(myMP, (tX / gridSize) - (gridX / gridSize) + radius, (tY / gridSize) - (gridY / gridSize) + radius); // Clear the tile's location from the MP grid.
            
            ds_list_add(tileStack, tID); // Add the tile to the DS list of "walkable" tiles.
        }
    }
}


var queueItem, pathPossible;
ds_list_shuffle(tileStack); // Shuffle the DS list so that we look at the tiles in a random order.
pathPossible = false;

for (var i = 0; i < ds_list_size(tileStack); i ++)
{
    queueItem = tileStack[| 0];
    ds_list_delete(tileStack, 0);
    
    if (mp_grid_path(myMP, myPath, x, y, tile_get_x(queueItem) + irandom(gridSize), tile_get_y(queueItem) + irandom(gridSize), 1)) // If we can path find to the specified 'random' tile:
    {
        pathPossible = true;
        break;
    }
}

if (pathPossible)
{
    show_debug_message("Path found!");
}
else
{
    show_debug_message("NO path found!");
}
 

Simon Gust

Member
If I'm understanding right, you're searching for places for your creatures to walk to in a rectangular area.
Then, you collect all possible spots that aren't blocked and are walkable and such.
Then you select one of those spots to move to.

Maybe, it would be better if you did the process in reverse.
create a list of like 10 positions at random, this will be your "try" list.
Then loop through these positions and check if the tile corresponds and is walkable and if you can mp_grid_path(blablabla).
The first one to succeed will be the destination.

If none is found, then there is always a next time (next frame).
Just an idea.
 

devKathy

Member
Agreed. There's not really a way to avoid multiple lengthy computations, if we have to attempt to find paths to all free tiles.
 

MeBoingus

Member
If I'm understanding right, you're searching for places for your creatures to walk to in a rectangular area.
Then, you collect all possible spots that aren't blocked and are walkable and such.
Then you select one of those spots to move to.

Maybe, it would be better if you did the process in reverse.
create a list of like 10 positions at random, this will be your "try" list.
Then loop through these positions and check if the tile corresponds and is walkable and if you can mp_grid_path(blablabla).
The first one to succeed will be the destination.

If none is found, then there is always a next time (next frame).
Just an idea.

The main issue is that due to the nature of MP grids, I still need to loop through the tiles in order to add their locations to the grid.
One possible fix for this would be to spawn an object in the location of each 'walkable' tile, but this would completely negate the purpose of using tiles in the first place (I.E. Not having thousands of instances spawned in).

Basically, I need to find a faster way to get all of the tiles within a given rectangle. I'll dig a little bit and report back if I find anything of note.
 

devKathy

Member
You could potentially just loop through once to create this ds_list of walkable tiles, then do partial updates as the game state changes.

Kinda like how video compression works.
 

MeBoingus

Member
Well, I figured out a really great solution.

I implemented a 'queue' system. Wherein all of the animals can decide that they want to move, and they will be added and have their paths calculated in groups of 5. Once added to the group, they simply sit around and wait until they're called upon by a 'master' object that handles the DS list containing the 'queue.'
 

TheouAegis

Member
You're using Studio 1. Tiles are horrible in Studio 1, just as they are in GM8. You shouldn't be doing tile collisions in Studio 1 at all, you should be generating an array (or buffer if memory use is a concern for some reason) and fill it with mask values for each tile in the room, since Studio 1 doesn't have tile masks like Studio 2. This could just be the tile's "index" (tile_get_left(tID) div tile_width + tile_get_height(tID) div tile_height * background_get_width(bg) div tile_width) or arbitrary values you decide (e.g., 0 for empty, 1 for solid, 2 for quicksand, 3 for ice). Then use that array/buffer to look up tile attributes instead of the tiles themselves.
 

MeBoingus

Member
You're using Studio 1. Tiles are horrible in Studio 1, just as they are in GM8. You shouldn't be doing tile collisions in Studio 1 at all, you should be generating an array (or buffer if memory use is a concern for some reason) and fill it with mask values for each tile in the room, since Studio 1 doesn't have tile masks like Studio 2. This could just be the tile's "index" (tile_get_left(tID) div tile_width + tile_get_height(tID) div tile_height * background_get_width(bg) div tile_width) or arbitrary values you decide (e.g., 0 for empty, 1 for solid, 2 for quicksand, 3 for ice). Then use that array/buffer to look up tile attributes instead of the tiles themselves.
I actually started out with this method originally, and I may look back into it now. Apparently I turned into Mr. Hyde when using a DS Grid to handle "tiles", and decided to draw all of them onto the screen at all times, instead of the ones that were visible in the view (with a buffer around the sides).

With that being said, my current method is pushing around 1100 FPS on my coal-powered PC. So unless I run into some huge issue later on, I may stick with this.


I'm actually not working on a game, I'm just trying to learn and come up with an efficient method to power the idea I've had for @matharoo's Crafting-related GameJam.
 
Top