Z
ZombieTom
Guest
Hi guys and girls,
So I'm making a 2D tile-based isometric game in gamemaker studio 2. I'm having a problem with the A* pathfinding algorithm I wrote. It appears to work most of the time but for certain tiles, there is a issue. It's quite in-depth unfortunately, but I'll try to explain.
So, basically, when a unit is selected, all the tiles within its movement range are highlighted. A unit has 16 Action Points maximum and moving a tile in any direction, including diagonals, takes 2 AP. A unit cannot move through wall tiles. I've put a screenshot below of the normal behaviour - I've simplified it to only show part of the movement range for now.
My problem is shown in the screenshot below.
The tile I've outlined with the blue selection box should be highlighted as a tile that can be moved to - there is a path to that tile using 12 AP. However, the path to this tile is not being found. Having worked through it offline using a print out, it can be seen that the reason this path is not found is because the algorithm calculates the path in the direction shown below, leading to a path length of 14 AP (7 tiles) which is rejected as it is too long.
What the program should be doing is calculating the path using the initial steps shown below as this is shorter.
That is the problem - I suspect it is because multiple tiles have the same F score and, once one is chosen, it never goes to check the alternative route. Any help in solving this would be greatly appricated.
The path finding algorithm:
So I'm making a 2D tile-based isometric game in gamemaker studio 2. I'm having a problem with the A* pathfinding algorithm I wrote. It appears to work most of the time but for certain tiles, there is a issue. It's quite in-depth unfortunately, but I'll try to explain.
So, basically, when a unit is selected, all the tiles within its movement range are highlighted. A unit has 16 Action Points maximum and moving a tile in any direction, including diagonals, takes 2 AP. A unit cannot move through wall tiles. I've put a screenshot below of the normal behaviour - I've simplified it to only show part of the movement range for now.
My problem is shown in the screenshot below.
The tile I've outlined with the blue selection box should be highlighted as a tile that can be moved to - there is a path to that tile using 12 AP. However, the path to this tile is not being found. Having worked through it offline using a print out, it can be seen that the reason this path is not found is because the algorithm calculates the path in the direction shown below, leading to a path length of 14 AP (7 tiles) which is rejected as it is too long.
What the program should be doing is calculating the path using the initial steps shown below as this is shorter.
That is the problem - I suspect it is because multiple tiles have the same F score and, once one is chosen, it never goes to check the alternative route. Any help in solving this would be greatly appricated.
The path finding algorithm:
Code:
// argument0 = x coordinate of centre of source tile
// argument1 = y coordinate of centre of source tile
// argument2 = x coordinate of centre of destination tile
// argument3 = y coordinate of centre of destination tile
// argument4 = troop's AP (only want to store paths the troop can move)
// It is important to note that this script identifies tiles by their centre point only
// This script is not called individually when a move is to be made
// Instead, it is called automatically for each tile in a troop's MMR whenever it is recalculated
// The script finds a path to that tile and, only if it is under the maximum path length of a troop with a certain AP, is that path added to the
// MMRpaths grid
// Clear the previous path
ds_list_clear(path);
if(DEBUG)
{
onlyDebugOutputForTile_x = 3072;
onlyDebugOutputForTile_y = 416;
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("------------------------");
show_debug_message(" STARTED NEW PATH ");
show_debug_message("------------------------");
}
}
firstPass = argument5; // IGNORE
startDirection = argument6; // IGNORE
maxPathLength = argument4/AP_PER_TILE;
// Openlist: tile_x, tile_y, F, parent_x, parent_y, tile_paired, G, H, detailedH
// Closedlist: tile_x, tile_y, F, parent_x, parent_y, tile_paired, G, H
// Adjacencylist: tile_x, tile_y
// DetailedHScores: tile_paired, detailedH (angle difference), tilesH
openlist = ds_grid_create(9, 200);
closedlist = ds_grid_create(8, 200);
adjacencylist = ds_grid_create(2, 8);
// In case of multiple tiles with the same F;
detailedHscores = ds_grid_create(3, 20); // A list to hold them
tileToUse = -1; // The unique id of the tile in the openlist to use add the current tile
currentTileReset = false; // A flag to indicate that the current tile was reset from the tile at the top of the sorted openlist
openlistRow = -1; // The row of the chosen tile in the openlist (will not always be the top one, even after sorting by F)
closedlistLength = 0; // Current number of tiles in closed list
openlistLength = 0; // Current number of tiles in open list
// Clear all lists in preperation for new path
ds_grid_clear(closedlist,1000000);
ds_grid_clear(openlist,1000000);
ds_grid_clear(adjacencylist,1000000);
ds_grid_clear(detailedHscores,1000000);
// Get the source tile of the move
source_x = argument0;
source_y = argument1;
source_paired = scr_pairing(source_x, source_y);
// Get the destination tile of the move
dest_x = argument2;
dest_y = argument3;
dest_paired = scr_pairing(dest_x, dest_y);
parentTile_x = -1;
parentTile_y = -1;
detailedH = 0;
// Add source tile to the openlist
ds_grid_set(openlist, 0, openlistLength, source_x);
ds_grid_set(openlist, 1, openlistLength, source_y);
ds_grid_set(openlist, 2, openlistLength, 0); // F of source tile is 0
ds_grid_set(openlist, 3, openlistLength, parentTile_x); // The x and y coordinates of the source tile's parent tile (where we moved from)
ds_grid_set(openlist, 4, openlistLength, parentTile_y); // to reach this tile are irrelevant
ds_grid_set(openlist, 5, openlistLength, source_paired);
ds_grid_set(openlist, 6, openlistLength, 0); // G of source tile is 0
openlistLength++;
// Calculate H from source tile to destination tile in tiles and store it
xH = abs(lengthdir_x(point_distance(source_x, source_y, dest_x, dest_y), point_direction(source_x, source_y, dest_x, dest_y)));
yH = abs(lengthdir_y(point_distance(source_x, source_y, dest_x, dest_y), point_direction(source_x, source_y, dest_x, dest_y)));
tilesH = round(xH/global.tileWidth + yH/global.tileHeight);
ds_grid_set(openlist, 7, openlistLength, tilesH);
ds_grid_set(openlist, 8, openlistLength, detailedH);
for(f = 0; f <= 64; f++) // Should really be while(true) but I want to avoid the potential for infinite loops
{
// Get tile with lowest F from openlist and set to current tile
ds_grid_sort(openlist, 2, true);
currentTile_x = ds_grid_get(openlist, 0, 0);
currentTile_y = ds_grid_get(openlist, 1, 0);
currentTile_F = ds_grid_get(openlist, 2, 0);
parentTile_x = ds_grid_get(openlist, 3, 0);
parentTile_y = ds_grid_get(openlist, 4, 0);
currentTile_paired = ds_grid_get(openlist, 5, 0);
currentTile_G = ds_grid_get(openlist, 6, 0);
currentTile_H = ds_grid_get(openlist, 7, 0);
detailedH = ds_grid_get(openlist, 8, 0);
ds_grid_clear(detailedHscores,1000000);
// Incase of more than one tile with the same F, there are two scenarios:
//
// 1) There are multiple optimal tiles on the path to the destination tile
// 2) One of the tiles with the same F as another tile is actually the destination tile (H = 0)
//
// For scenario 1: Pick the tile with the smallest pixel distance between the centre of the current tile and
// the centre of the destination tile.
//
// For scenario 2: Loop through all the tiles with the same F and pick the one where H is 0 tiles (the destination tile)
// If tiles 0 and 1 on openlist have the same F
if(ds_grid_get(openlist, 2, 0) == ds_grid_get(openlist, 2, 1))
{
// Add them to the detailedHscores list
ds_grid_set(detailedHscores, 0, 0, ds_grid_get(openlist, 5, 0));
ds_grid_set(detailedHscores, 1, 0, ds_grid_get(openlist, 8, 0));
ds_grid_set(detailedHscores, 2, 0, ds_grid_get(openlist, 7, 0));
ds_grid_set(detailedHscores, 0, 1, ds_grid_get(openlist, 5, 1));
ds_grid_set(detailedHscores, 1, 1, ds_grid_get(openlist, 8, 1));
ds_grid_set(detailedHscores, 2, 1, ds_grid_get(openlist, 7, 0));
// Check all others to see if they have the same F
for(p = 2; p < openlistLength; p++)
{
// If they do
if(ds_grid_get(openlist, 2, 1) == ds_grid_get(openlist, 2, p))
{
// Add them to the list
ds_grid_set(detailedHscores, 0, p, ds_grid_get(openlist, 5, p));
ds_grid_set(detailedHscores, 1, p, ds_grid_get(openlist, 8, p));
ds_grid_set(detailedHscores, 2, p, ds_grid_get(openlist, 7, p));
}
else
{
// As soon as a tile with a different F is found, exit the loop (the openlist is sorted by F so no more will equal the lowest F)
break;
}
}
for(p = 0; p < ds_grid_height(detailedHscores); p++)
{
if(ds_grid_get(detailedHscores, 0, p) == 1000000)
continue;
if(ds_grid_get(detailedHscores, 2, p) == 0)
{
tileToUse = ds_grid_get(detailedHscores, 0, 0);
break;
}
}
if(tileToUse == -1)
{
// Get the tile with the lowest detailed H score
ds_grid_sort(detailedHscores, 1, true);
tileToUse = ds_grid_get(detailedHscores, 0, 0);
}
// Search for that tile in the openlist
openlistRow = ds_grid_value_y(openlist, 5, 0, 5, openlistLength, tileToUse);
// Reset current tile
currentTile_x = ds_grid_get(openlist, 0, openlistRow);
currentTile_y = ds_grid_get(openlist, 1, openlistRow);
currentTile_F = ds_grid_get(openlist, 2, openlistRow);
parentTile_x = ds_grid_get(openlist, 3, openlistRow);
parentTile_y = ds_grid_get(openlist, 4, openlistRow);
currentTile_paired = ds_grid_get(openlist, 5, openlistRow);
currentTile_G = ds_grid_get(openlist, 6, openlistRow);
currentTile_H = ds_grid_get(openlist, 7, openlistRow);
detailedH = ds_grid_get(openlist, 8, 0);
currentTileReset = true;
}
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message(" ");
show_debug_message("Openlist "+string(f)+"| Length (tiles) "+string(openlistLength));
for(i = 0; i < openlistLength; i++)
{
show_debug_message(string(i)+" = "+string(ds_grid_get(openlist, 0, i))+","+string(ds_grid_get(openlist, 1, i))+" F: "+string(ds_grid_get(openlist, 2, i))
+" G: "+string(ds_grid_get(openlist, 6, i))+" H: "+string(ds_grid_get(openlist, 7, i))+" D_H: "+string(ds_grid_get(openlist, 8, i))+" Par: "+string(ds_grid_get(openlist, 3, i))+","+string(ds_grid_get(openlist, 4, i)));
}
show_debug_message(" ");
show_debug_message("Duplicates list "+string(f)+"|");
for(i = 0; i < ds_grid_height(detailedHscores); i++)
{
if(ds_grid_get(detailedHscores, 0, i) == 1000000)
continue;
show_debug_message("Detailed H: "+string(ds_grid_get(detailedHscores, 1, i))+" TilesH: "+string(ds_grid_get(detailedHscores, 2, i)));
}
}
}
// Add current tile to closedlist
ds_grid_set(closedlist, 0, closedlistLength, currentTile_x);
ds_grid_set(closedlist, 1, closedlistLength, currentTile_y);
ds_grid_set(closedlist, 2, closedlistLength, currentTile_F);
ds_grid_set(closedlist, 3, closedlistLength, parentTile_x);
ds_grid_set(closedlist, 4, closedlistLength, parentTile_y);
ds_grid_set(closedlist, 5, closedlistLength, currentTile_paired);
ds_grid_set(closedlist, 6, closedlistLength, currentTile_G);
ds_grid_set(closedlist, 7, closedlistLength, currentTile_H);
closedlistLength++;
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message(" ");
show_debug_message("Closedlist "+string(f)+"| Length (tiles) "+string(closedlistLength));
for(i = 0; i < closedlistLength; i++)
{
show_debug_message(string(i)+" = "+string(ds_grid_get(closedlist, 0, i))+","+string(ds_grid_get(closedlist, 1, i))+" <- "+string(ds_grid_get(closedlist, 3, i))+","+string(ds_grid_get(closedlist, 4, i)));
}
}
}
// Remove current tile from openlist (set F large enough so it will never be picked again)
// Current tile may not be first tile in openlist if multiple tiles had same F
if(currentTileReset == false)
{
ds_grid_set(openlist, 0, 0, 1000000);
ds_grid_set(openlist, 1, 0, 1000000);
ds_grid_set(openlist, 2, 0, 1000000);
ds_grid_set(openlist, 3, 0, 1000000);
ds_grid_set(openlist, 4, 0, 1000000);
ds_grid_set(openlist, 5, 0, 1000000);
ds_grid_set(openlist, 6, 0, 1000000);
ds_grid_set(openlist, 7, 0, 1000000);
ds_grid_set(openlist, 8, 0, 1000000);
}
else
{
ds_grid_set(openlist, 0, openlistRow, 1000000);
ds_grid_set(openlist, 1, openlistRow, 1000000);
ds_grid_set(openlist, 2, openlistRow, 1000000);
ds_grid_set(openlist, 3, openlistRow, 1000000);
ds_grid_set(openlist, 4, openlistRow, 1000000);
ds_grid_set(openlist, 5, openlistRow, 1000000);
ds_grid_set(openlist, 6, openlistRow, 1000000);
ds_grid_set(openlist, 7, openlistRow, 1000000);
ds_grid_set(openlist, 8, openlistRow, 1000000);
currentTileReset = false;
openlistRow = -1;
tileToUse = -1;
}
aObstacle = false;
// If last tile added to closedlist is the destination tile, the path has been found
if(ds_grid_get(closedlist, 5, closedlistLength-1) == dest_paired)
{
// Path found
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("Reached end after "+string(f)+" loops");
}
}
break; // Exit the loop (the full path is in the closedlist)
}
// Get all tiles adjacent to current tile
// Individual tiles are identified by the coordinates of their centre point
// Adjacency order
//
// ------------
// / 8 / 1 / 5 /
// ------------
// / 4 / / 2 /
// ------------
// / 7 / 3 / 6 /
// ------------
adj1[0] = currentTile_x+global.halfTileWidth;
adj1[1] = currentTile_y-global.halfTileHeight;
adj2[0] = currentTile_x+global.halfTileWidth;
adj2[1] = currentTile_y+global.halfTileHeight;
adj3[0] = currentTile_x-global.halfTileWidth;
adj3[1] = currentTile_y+global.halfTileHeight;
adj4[0] = currentTile_x-global.halfTileWidth;
adj4[1] = currentTile_y-global.halfTileHeight;
adj5[0] = currentTile_x+global.tileWidth;
adj5[1] = currentTile_y;
adj6[0] = currentTile_x;
adj6[1] = currentTile_y+global.tileHeight;
adj7[0] = currentTile_x-global.tileWidth;
adj7[1] = currentTile_y;
adj8[0] = currentTile_x;
adj8[1] = currentTile_y-global.tileHeight;
ds_grid_clear(adjacencylist,1000000);
ds_grid_set(adjacencylist, 0, 0, adj1[0]);
ds_grid_set(adjacencylist, 1, 0, adj1[1]);
ds_grid_set(adjacencylist, 0, 1, adj2[0]);
ds_grid_set(adjacencylist, 1, 1, adj2[1]);
ds_grid_set(adjacencylist, 0, 2, adj3[0]);
ds_grid_set(adjacencylist, 1, 2, adj3[1]);
ds_grid_set(adjacencylist, 0, 3, adj4[0]);
ds_grid_set(adjacencylist, 1, 3, adj4[1]);
ds_grid_set(adjacencylist, 0, 4, adj5[0]);
ds_grid_set(adjacencylist, 1, 4, adj5[1]);
ds_grid_set(adjacencylist, 0, 5, adj6[0]);
ds_grid_set(adjacencylist, 1, 5, adj6[1]);
ds_grid_set(adjacencylist, 0, 6, adj7[0]);
ds_grid_set(adjacencylist, 1, 6, adj7[1]);
ds_grid_set(adjacencylist, 0, 7, adj8[0]);
ds_grid_set(adjacencylist, 1, 7, adj8[1]);
// For each adjacent tile
for(o = 0; o < ds_grid_height(adjacencylist); o++)
{
adjTile_x = ds_grid_get(adjacencylist, 0, o);
adjTile_y = ds_grid_get(adjacencylist, 1, o);
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message(" ");
show_debug_message("Looking at adjTile "+string(o+1)+" | "+string(adjTile_x)+","+string(adjTile_y));
}
}
// Check if the tile is outside the playable area of the room
if(scr_outsideMap(adjTile_x, adjTile_y) == true)
{
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("\tOutside map - not added to openlist");
}
}
continue; // If it's outside the playable map, forget about it
}
// Check the content of that tile to find if it can be moved to
// Must check for regular obstacle tiles (walls, etc.) and also for units in the tile (troops, civvies and Zombies)
if(scr_returnTileContent(adjTile_x-64, adjTile_y-32, -1, true) >= 1000 || scr_returnTileContent(adjTile_x-64, adjTile_y-32, -1, false) >= 1000)
{
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("\tObstacle or Unit - not added to openlist");
}
}
aObstacle = true;
continue; // If it's a obstacle, forget about it
}
adjTile_paired = scr_pairing(adjTile_x, adjTile_y);
// Check if the tile is in the closedlist
if(ds_grid_value_exists(closedlist, 5, 0, 5, closedlistLength, adjTile_paired) == true)
{
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("\tIn closedlist - not added to openlist");
}
}
continue; // If it's already on the closedlist, forget about it
}
// Check if the tile is in the openlist
// If it's not in the openlist, add it to the openlist
if(ds_grid_value_exists(openlist, 5, 0, 5, openlistLength, adjTile_paired) == false)
{
// Get G, H and F (all in tiles)
G = 1 + currentTile_G; // G is the current tile distance travelled plus 1 (the tile travel distance to this tile from the current tile)
xH = abs(lengthdir_x(point_distance(adjTile_x, adjTile_y, dest_x, dest_y), point_direction(adjTile_x, adjTile_y, dest_x, dest_y)));
yH = abs(lengthdir_y(point_distance(adjTile_x, adjTile_y, dest_x, dest_y), point_direction(adjTile_x, adjTile_y, dest_x, dest_y)));
tilesH = round(xH/global.tileWidth + yH/global.tileHeight);
adjDirection = point_direction(currentTile_x, currentTile_y, adjTile_x, adjTile_y);
// Set a modifier for the distance travelled based on the direction to the adjacent tile
switch (floor(adjDirection))
{
case ADJ_TILE_UP:
Gmod = 0;
break;
case ADJ_TILE_UP_RIGHT:
Gmod = 0.2;
break
case ADJ_TILE_RIGHT:
Gmod = 0;
break;
case ADJ_TILE_DOWN_RIGHT:
Gmod = 0.2;
break;
case ADJ_TILE_DOWN:
Gmod = 0;
break;
case ADJ_TILE_DOWN_LEFT:
Gmod = 0.2;
break;
case ADJ_TILE_LEFT:
Gmod = 0;
break;
case ADJ_TILE_UP_LEFT:
Gmod = 0.2;
break;
}
F = abs(G+Gmod+tilesH);
detailedH = abs(point_distance(adjTile_x, adjTile_y, dest_x, dest_y));
// Add the tile and all information to the openlist
ds_grid_set(openlist, 0, openlistLength, adjTile_x);
ds_grid_set(openlist, 1, openlistLength, adjTile_y);
ds_grid_set(openlist, 2, openlistLength, F);
ds_grid_set(openlist, 3, openlistLength, currentTile_x);
ds_grid_set(openlist, 4, openlistLength, currentTile_y);
ds_grid_set(openlist, 5, openlistLength, adjTile_paired);
ds_grid_set(openlist, 6, openlistLength, G);
ds_grid_set(openlist, 7, openlistLength, tilesH);
ds_grid_set(openlist, 8, openlistLength, detailedH);
openlistLength++;
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("\tAdded to openlist |"+" F: "+string(ds_grid_get(openlist, 2, openlistLength-1))+" G: "+string(ds_grid_get(openlist, 6, openlistLength-1))
+" H: "+string(ds_grid_get(openlist, 7, openlistLength-1))+" P: "+string(ds_grid_get(openlist, 3, openlistLength-1))+","+string(ds_grid_get(openlist, 4, openlistLength-1)));
}
}
}
// If the tile is in the openlist, reset the stored information as neccessary
else
{
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("\tAlready in openlist");
}
}
// Search for the tile in the openlist
openlistRow = ds_grid_value_y(openlist, 5, 0, 5, openlistLength, adjTile_paired);
// Reset the G to the current tile distance travelled plus 1 (the tile travel distance to this tile from the current tile)
oldG = ds_grid_get(openlist, 6, openlistRow);
newG = oldG + 1;
ds_grid_set(openlist, 6, openlistRow, newG);
// The H cannot have changed so simply get it from the openlist
newH = ds_grid_get(openlist, 7, openlistRow);
// Calculate the new F for that tile with the updated G
newF = abs(newG+newH);
// Get the old F from the openlist
oldF = ds_grid_get(openlist, 2, openlistRow);
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("\t\toldF="+string(oldF)+" newF="+string(newF)+" oldG="+string(oldG)+" newG="+string(newG)+" newH="+string(newH));
}
}
// If the new F is less than the old F, the path is shorter going through this tile so update the link to the parent
// ie. the path now goes through the current tile to reach this tile instead of going through the tile this tile was originally
// linked to
if(newF < oldF)
{
ds_grid_set(openlist, 3, openlistRow, currentTile_x);
ds_grid_set(openlist, 4, openlistRow, currentTile_y);
}
// Store the new G and new F information
ds_grid_set(openlist, 2, openlistRow, newF);
ds_grid_set(openlist, 6, openlistRow, newG);
}
}
}
// If main loop exited, the path has been found (or no path was found but this should never happen)
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message(" ");
show_debug_message("Closedlist Final | Length (tiles) "+string(closedlistLength));
for(i = 0; i < closedlistLength; i++)
{
show_debug_message(string(i)+" = "+string(ds_grid_get(closedlist, 0, i))+","+string(ds_grid_get(closedlist, 1, i))+" <- "+string(ds_grid_get(closedlist, 3, i))+","+string(ds_grid_get(closedlist, 4, i))
+" Paired: "+string(ds_grid_get(closedlist, 5, i)));
}
}
}
// If the last tile added to the closedlist was not the destination tile
if(ds_grid_get(closedlist, 5, closedlistLength-1) != dest_paired)
{
// There is no path
//As a troop can only attempt to move to tiles where a path to those tiles exists, something has gone horribly wrong
show_message("Unable to calculate path to all tiles in MMR - exiting game.\n\n"
+"Source tile (not centre coordinates): "+string(source_x-64)+","+string(source_y-32)+"\n"
+"Offending tile (not centre coordinates): "+string(dest_x-64)+","+string(dest_y-32)+"\n\n"
+"Usual solution is to increase number of executions of pathfinder loop.");
// Destroy all temporary data structures
ds_grid_destroy(closedlist);
ds_grid_destroy(openlist);
ds_grid_destroy(adjacencylist);
ds_grid_destroy(detailedHscores);
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("Tile at end of closedlist "+string(nextTile_paired)+" | Dest tile "+string(dest_paired));
}
}
// End the game
game_end();
return false;
}
ds_list_add(path, dest_x, dest_y); // Add the destination tile to the path
nextTileRow = 0;
tileParent_paired = 0;
nextTile_paired = ds_grid_get(closedlist, 5, closedlistLength-1); // Get the tile at the end of the closedlist (the destination tile)
// The closedlist may contain many more tiles than the path
// The path is found by starting at the destination tile and moving backwards along the list of parent tiles until the source tile is reached
// For each tile in the closedlist
for(i = 0; i < closedlistLength; i++)
{
// If that tile is the source tile, the complete path has been built so end the loop
if(nextTile_paired == source_paired)
{
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("Full path found");
}
}
break;
}
else
{
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("Looking for pair "+string(nextTile_paired));
}
}
// Search for the tile in the closedlist
nextTileRow = ds_grid_value_y(closedlist, 5, 0, 5, closedlistLength, nextTile_paired);
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message("Looking at "+string(nextTileRow));
}
}
// Get the x and y coordinates of the tile leading to that tile (it's parent)
tileParent_x = ds_grid_get(closedlist, 3, nextTileRow);
tileParent_y = ds_grid_get(closedlist, 4, nextTileRow);
tileParent_paired = scr_pairing(tileParent_x, tileParent_y);
// Add that tile to the path
ds_list_add(path, tileParent_x, tileParent_y);
// Loop again, checking the next tile
nextTile_paired = tileParent_paired;
}
}
// Full path reconstructed and contained in path list
if(DEBUG)
{
if(argument2 == onlyDebugOutputForTile_x && argument3 == onlyDebugOutputForTile_y)
{
show_debug_message(" ");
show_debug_message("Path | Length (tiles) "+string(ds_list_size(path)/2));
for(i = 0; i < ds_list_size(path); i+=2)
{
if(i = 0)
tileName = " (destination tile)";
if(i = ds_list_size(path) - 2)
tileName = " (source tile)";
show_debug_message(string(i)+" = "+string(ds_list_find_value(path, i))+","+string(ds_list_find_value(path, i+1))+tileName);
tileName = "";
}
}
}
// Destroy all temporary data structures
ds_grid_destroy(closedlist);
ds_grid_destroy(openlist);
ds_grid_destroy(adjacencylist);
ds_grid_destroy(detailedHscores);
pathLength = ds_list_size(path)/2; // Get the path length (in tiles)
// If the path is equal to or below the maximum path length for a troop with full AP
if(pathLength <= maxPathLength+1) // +1 because the source tile is included in the path
{
// Add path and tile identifier to MMRpaths grid
ds_grid_set(global.MMRpaths, 0, global.MMRpaths_count, dest_paired);
ds_list_copy(ds_grid_get(global.MMRpaths, 1, global.MMRpaths_count), path);
global.MMRpaths_count++;
return true; // Return that a path was found and added to MMRpaths grid
}
else
{
return false; // Return that no path was found and has, therefore, not been added to the MMRpaths grid
}
