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:
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!");
}