A* (star) pathfinding...

RifleFire

Member
Are there any good, well commented, A* type path finding completed GML based solutions that work in GM:S yet? We were hoping to find one with movement penalties (harder to walk thru forest than grassy plains,etc) too.
We had an old a* solution from the old forums but something in the newer versions of GM:S broke it and we cannot figure out what code is broken ( i am pretty new to GML coding. ).
If you have any knowledge of a working a* solution, we are in desperate need of one.
Thanks for any help you can give...
RF
 
Z

zircher

Guest
If nothing turns up, as a plan B would you mind posting the broken solution? Perhaps we can find out what is not working in that code.
 

FrostyCat

Redemption Seeker
Are you absolutely sure it's something intrinsic to GMS, or did your project gave it input in the wrong format? Maybe that script expected a grid but you gave it an array instead. Maybe that script used sleep() to automatically move stuff while it should have returned a path or list of square to go through.

Also, why are you resistant to doing it yourself? If you don't already have the entire field's costs in grid or 2D array form, a double-for loop would give you that. Once that is done, you can implement A* from the raw algorithm yourself. A priority queue plus a couple of 2D arrays would do, not that hard.

Trust me, when I got an assignment for A* pathfinding in university, I bashed my head on the keyboard after I was done --- not because it was difficult (it really wasn't), but because I remembered chickening out of it 6 years earlier on.
 
P

ph101

Guest
Are there any good, well commented, A* type path finding completed GML based solutions that work in GM:S yet?
Yet? GM:S includes A* path finding out of the box in the function: mp_grid_path(id, path, xstart, ystart, xgoal, ygoal, allowdiag);
Manual explains well enough how to use it, there are also several vids on youtube which might help. You may need full version GM:S, in the old days it wasn't in the free version as I recall.
 

FrostyCat

Redemption Seeker
Yet? GM:S includes A* path finding out of the box in the function: mp_grid_path(id, path, xstart, ystart, xgoal, ygoal, allowdiag);
Manual explains well enough how to use it, there are also several vids on youtube which might help. You may need full version GM:S, in the old days it wasn't in the free version as I recall.
Reminder:
  • mp_*() functions assume uniform costs across nodes.
  • mp_*() functions assume a square grid.
  • mp_*() functions have been available in the free version of GMS for some time now.
 

RifleFire

Member
The old A* solution that the gmc thread author had going was good but it didn't movement weight as far as i knew. The link to the old GMC version was on the http://gmc.yoyogames.com/index.php?showtopic=580116&hl= thread. I hope i have linked to it correctly. It came in from GM81 just fine at first for me but then later, something in GM:S changed and it no longer worked. (eg: the ball doesn't move nor draw pathfinding in room 2 anymore in the basic old a* solution). I would love to get that old solution fixed and get it going again in a new project. I am very new to GML so please be patient with me and thanks for any help you all can give.
RF
 
Last edited:

FrostyCat

Redemption Seeker
After about half an hour of debugging, I finally got it.

I'll give you a patched version of getShortestPath that will get it back up and running again.
Code:
/*
getShortestPath(SourceNode, TargetNode): ds_list
Computes the shortest path between the two nodes. 
Returns a ds_list containing all the nodes in the path (first and last are included)
If a path could not be found, noone is returned
*/

var Source, Target, OpenedList, ClosedList, PreviousNodes, TentativeDistances, CurrentNode, End, Connections;
var tentativeDistance, Score, heuristicValue, lastConnection, currentScore;

Source = argument[0];
Target = argument[1];

OpenedList = ds_priority_create(); //{Value: Node, Priority: Score}
ClosedList = ds_list_create();
PreviousNodes = ds_map_create();//{Key: Node, Value: PreviousNode}
TentativeDistances = ds_map_create(); //{Key: Node, Value: Distance}

CurrentNode = noone;
ds_priority_add(OpenedList, Source, 1);
ds_map_add(TentativeDistances, Source, 0);

while (ds_priority_size(OpenedList) > 0) {
    CurrentNode = ds_priority_find_min(OpenedList);

    if (CurrentNode == Target) {
        break;
    }

    ds_priority_delete_min(OpenedList); //Remove current node
    ds_list_add(ClosedList, CurrentNode);
   
    Connections = __Nodes[CurrentNode, 1];
    End = false;
    lastConnection = ds_map_find_last(Connections);
    for (var Neighbour = ds_map_find_first(Connections); End == false; 
        Neighbour = ds_map_find_next(Connections, Neighbour)) {
        if (Neighbour == lastConnection) {
            End = true;
        }
       
        if (ds_list_find_index(ClosedList, Neighbour) != -1) {
            continue;
        }
       
        if (!filterPath(id, Neighbour)) {
            continue;
        }
       
        tentativeDistance = ds_map_find_value(Connections, Neighbour) + ds_map_find_value(TentativeDistances, CurrentNode);
        heuristicValue = getHeuristic(Neighbour, Target);
       
        if (!ds_map_exists(TentativeDistances, Neighbour)) {
            ds_map_add(TentativeDistances, Neighbour, tentativeDistance);
        } else if (tentativeDistance < ds_map_find_value(TentativeDistances, Neighbour)) {
            ds_map_replace(TentativeDistances, Neighbour, tentativeDistance);
        }
       
        currentScore = ds_priority_find_priority(OpenedList, Neighbour);
        Score = ds_map_find_value(TentativeDistances, Neighbour) + heuristicValue + 1;

        if (Score < currentScore || currentScore == 0 || is_undefined(currentScore)) {
            if (currentScore == 0 || is_undefined(currentScore)) {
                ds_priority_add(OpenedList, Neighbour, Score);
            } else {
                ds_priority_change_priority(OpenedList, Neighbour, Score);
            }
           
            if (!ds_map_exists(PreviousNodes, Neighbour)) {
                ds_map_add(PreviousNodes, Neighbour, CurrentNode);
            } else {
                ds_map_replace(PreviousNodes, Neighbour, CurrentNode);
            }
        }
    }
}

ds_priority_destroy(OpenedList);
ds_list_destroy(ClosedList);
ds_map_destroy(TentativeDistances);
   
if (CurrentNode != Target) {
    ds_map_destroy(PreviousNodes);
    return(noone);
}


var Path;
Path = ds_list_create();
while (true) {
    ds_list_add(Path, CurrentNode);

    if (CurrentNode == Source) {
        reversedPath = ds_list_create();
        for (i = ds_list_size(Path) - 1; i >=0; i-=1) {
            ds_list_add(reversedPath, ds_list_find_value(Path, i));
        }
       
        ds_list_destroy(Path);
        ds_map_destroy(PreviousNodes);
        return(reversedPath);
    }

    CurrentNode = ds_map_find_value(PreviousNodes, CurrentNode);
}

For anyone who is interested in learning how to use the debugger, I think this is an excellent case study involving both comments and local watch values. The problem is in getShortestPath. Once you think you have a good idea where the problem is, open the spoiler for the answer:
ds_priority_find_priority() returns undefined in GMS, but 0 in 8.1 and below. The original author's assumption of the legacy behaviour has been broken. This shuts down line 64 permanently and prevents the open list from expanding.
 

RifleFire

Member
My thanks FrostyCat! Your solution worked perfectly. You know, i dimly thought it might have to do with keywords changing values as GM:S evolved but I never suspected that GM:S made such a change in the legacy way of doing things. To me, this A* solution by the original author was a very complex code solution. You must be a pro at GML coding! That was so fast. NICE WORK! Thank you again.
RF
P.s. How hard would it be to put in weighted movement on the original authors solution? Got any hints or would you be feeling adventuresome and want to try adding it? Heh. I know its beyond me right this moment in my learning.
 
Last edited:
L

L0v3

Guest
I have this insanely long script I made to learn the algorithm myself, might give you some insight on how it looks in GML. You could somewhat easily customize it to use a grid with cost values for the tiles, such as forest, road, etc, instead of the random cost values given to it. Here it is:

Code:
///mp_grid_astar(grid, path, x_start, y_start, x_goal, y_goal, xstart, ystart, hcells, vcells, cellwidth, cellheight);

// Finds and creates the shortes path from the start position to the goal position.
// The path is created using the given mp_grid and is stored to the given path index.
// Note: This overwrites any existing path stored in the index.

// grid             = Index of the mp_grid that is to be used.
// path             = Index of the path that path is to be stored to.
// x_start          = Starting x-coordinate to go from.
// y_start          = Starting y-coordinate to go from.
// x_goal           = Destination x-coordinate to go to.
// y_goal           = Destination y-coordinate to go to.

// The following arguments should match the same as those used to create the original grid.
// I know... Blame yoyo, no get methods for mp_grid to acquire these.

//  xstart        = Starting x coordinate of the mp_grid in the room.
//  ystart        = Starting y coordinate of the mp_grid in the room.
//  hcells        = Number of horizontal cells that the mp_grid will contain.
//  vcells        = Number of vertical cells that the mp_grid will contain.
//  cellwidth     = The width (in pixels) of each individual cell of the mp_grid.
//  cellheight    = The height (in pixels) of each individual cell of the mp_grid.

//@Return: Boolean if path was successfully created.

//Converts arguments to locals.
var grid = argument0;
var path = argument1;
var x1 = argument2;
var y1 = argument3;
var x2 = argument4;
var y2 = argument5;
var grid_x = argument6;
var grid_y = argument7;
var hcells = argument8;
var vcells = argument9;
var cellwidth = argument10;
var cellheight = argument11;

//Converts x/y coordinates to grid indexes.
var x1 = floor((x1 / cellwidth));
var y1 = floor((y1 / cellheight));
var x2 = floor((x2 / cellwidth));
var y2 = floor((y2 / cellheight));

//Clears path of existing points.
path_clear_points(path);
path_set_closed(path, false);

//Initialize ds_grid from mp_grid.
var ds_grid = ds_grid_create(hcells, vcells);
ds_grid = mp_grid_to_ds_grid(grid, ds_grid);

//Check if target is within grid.
if (x1 > hcells or x1 < 0) or (y1 > vcells or y1 < 0)
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);
 
    //Return False
    return false;
}

//Check if target is same as start.
if x1 = x2 and y1 = y2
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);
 
    //Return False
    return false;
}

//Check if target is in a closed cell.
if ds_grid_get(ds_grid, x2, y2) = -1
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);
 
    //Return False
    return false;
}

//Initialize Node Containers.
var list_closed = ds_list_create();
var list_open = ds_priority_create();

//Creates initial node.
var node_start = ds_list_create();
var parent = noone;
var cost = 0;
var distance = floor((point_distance(x1, y1, x2, y2)) + 0.5);
var value = cost + distance;
ds_list_add(node_start, x1, y1, parent, cost, distance, value);

//Adds initial node to open list.
ds_priority_add(list_open, node_start, value);

//Loops until open list is empty.
while !ds_priority_empty(list_open)
{
    //Finds lowest cost open node.
    var node = ds_priority_delete_min(list_open);
 
    //Setup local variables used in loop.
    var xx, yy, i, i2;
    var angle = 0;
 
    //Enters loop to create 8 succesors.
    for (i = 0; i < 8; i++)
    {
        //Gets variables from node.
        var nx = ds_list_find_value(node, 0);
        var ny = ds_list_find_value(node, 1);
     
        //Calculates Coordinates.
        xx = floor((nx + lengthdir_x(1, angle)) + 0.5);
        yy = floor((ny + lengthdir_y(1, angle)) + 0.5);
        angle += 45;    
     
        //Validates coordinates are within grid bounds.
        if (xx > hcells or xx < 0) or (yy > vcells or yy < 0)
        {
            //Enters next loop.
            continue;
        }
     
        //Creates succesor.
        var succesor = ds_list_create();
        parent = node;
        if i & 1 //Checks if odd.
        {
            //Angled cost.
            cost = 14; //sqrt(2);
        }
        else
        {
            //Linear cost.
            cost = 10;
        }
        distance = floor(point_distance(xx, yy, x2, y2) + 0.5);
        value = cost + distance;
        ds_list_add(succesor, xx, yy, parent, cost, distance, value);
     
        //Check if succesor is in a closed cell.
        if ds_grid_get(ds_grid, xx, yy) = -1
        {
            //Destroy the succesor.
            ds_list_destroy(succesor);
         
            //Enters next loop.
            continue;
        }    
     
        //Check if node is the goal.
        if xx = x2 and yy = y2
        {          
            //Creates path list.
            var list_path = ds_list_create();
            var node_path = succesor;
            var parent = ds_list_find_value(node_path, 2);
            ds_list_add(list_path, node_path);
         
            //Traces parents back to initial node.
            while node_path != node_start
            {
                parent = ds_list_find_value(node_path, 2);
                ds_list_add(list_path, parent);
                node_path = parent;
            }
         
            //Creates the path from the path list.
            for (i2 = ds_list_size(list_path) - 1; i2 >= 0; i2--)
            {
                var node_point = ds_list_find_value(list_path, i2);
                var xx = (grid_x + (ds_list_find_value(node_point, 0) * cellwidth)) + cellwidth / 2;
                var yy = (grid_y + (ds_list_find_value(node_point, 1) * cellheight)) + cellheight / 2;
                path_add_point(path, xx, yy, 100);
            }
         
            //Clean-Up Leaks
            ds_grid_destroy(ds_grid);
            ds_list_destroy(list_path);
            ds_list_destroy(node);
            ds_list_destroy(succesor);
         
            //Loops through closed list.
            for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
            {
                //Cleans up leaks.
                var obj = ds_list_find_value(list_closed, i2);
                ds_list_destroy(obj);
            }
         
            //Loops through open list.
            var size = ds_priority_size(list_open);
            for (i2 = 0; i2 < size; i2++)
            {
                //Cleans up leaks.
                var obj = ds_priority_delete_min(list_open);
                ds_list_destroy(obj);
            }
         
            //Destroys lists.
            ds_list_destroy(list_closed);
            ds_priority_destroy(list_open);
         
            //Return True
            return true;
        }
     
        //Creates a copy of open list to sweep through.
        var list_open_copy = ds_priority_create();
        ds_priority_copy(list_open_copy, list_open);
        var size = ds_priority_size(list_open_copy);
     
        //Creates a continue check boolean, for nested loops.
        var continue_check = false;
     
        //Check if node with same position is in the open list.
        for (i2 = 0; i2 < size; i2++)
        {
            //Gets values from current index.
            var obj = ds_priority_delete_min(list_open_copy);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
            var obj_value = ds_list_find_value(obj, 5)
         
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Check if value of obj is lower then succesor.
                if obj_value < value
                {
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
                 
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
                else
                {
                    //Update object with succesor values.
                    ds_list_replace(succesor, 2, ds_list_find_value(obj, 2));
                    ds_list_replace(succesor, 3, ds_list_find_value(obj, 3));
                    ds_list_replace(succesor, 4, ds_list_find_value(obj, 4));
                    ds_list_replace(succesor, 5, ds_list_find_value(obj, 5));
                 
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
                 
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
            }
        }
     
        //Deletes copy of open list.
        ds_priority_destroy(list_open_copy);
     
        //Check if should continue.
        if continue_check
        {
            continue;
        }
     
        //Check if node with same position is in the closed list.
        for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
        {
            //Gets values from current index.
            var obj = ds_list_find_value(list_closed, i2);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
         
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Destroy the succesor.
                ds_list_destroy(succesor);
             
                //Updates continue check to skip loop.
                continue_check = true;
                break;
            }
        }
     
        //Check if should continue.
        if continue_check
        {
            continue;
        }

        //Add succesor to open list.
        ds_priority_add(list_open, succesor, value);
    }
 
    //Adds node to closed list.
    ds_list_add(list_closed, node);
}

//Exhausted all nodes.

//Clean-Up Leaks
ds_grid_destroy(ds_grid);

//Loops through closed list.
for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
{
    var obj = ds_list_find_value(list_closed, i2);
    ds_list_destroy(obj);
}

//Destroys lists.
ds_list_destroy(list_closed);
ds_priority_destroy(list_open);

//Return True
return false;

If you wish, I could tweak it and implement another version that takes a ds_grid with custom values for tile cost and use those instead of the fixed cost. You would however need to setup the grid yourself, since I dunno your game.
 

RifleFire

Member
Hey L0v3,
Thanks for sharing the script. it looks great. Yes, if you could, Please do a tweaked new version with customized values for tile cost instead of the fixed cost. Also if possible, please give further explanation of "set up the grid". Just a small example would help greatly. I am still learning GML and this is all almost over my head. It sure helps to have multiple sources to look at. Your script and also the gmc author solution are great to look at and learn from. Many thanks for sharing your script and i would love to see the tweaked version script and if possible, an small solution using it if you have the time for it. That script looked like a lot of work.
Thank you so much for your help,
RF
 
L

L0v3

Guest
Here's an updated version that takes a ds_grid for custom cost values which is added to the normal linear/angled values. Havn't tested it, but if you have a setup grid should work.

Code:
///mp_grid_astar(grid, cost, path, x_start, y_start, x_goal, y_goal, xstart, ystart, hcells, vcells, cellwidth, cellheight);

// Finds and creates the shortes path from the start position to the goal position.
// The path is created using the given mp_grid and is stored to the given path index.
// Note: This overwrites any existing path stored in the index.

// grid             = Index of the mp_grid that is to be used.
// cost             = Index of the ds_grid that is to be used get costs of tiles.
// path             = Index of the path that path is to be stored to.
// x_start          = Starting x-coordinate to go from.
// y_start          = Starting y-coordinate to go from.
// x_goal           = Destination x-coordinate to go to.
// y_goal           = Destination y-coordinate to go to.

// The following arguments should match the same as those used to create the original grid.
// I know... Blame yoyo, no get methods for mp_grid to acquire these.

//  xstart        = Starting x coordinate of the mp_grid in the room.
//  ystart        = Starting y coordinate of the mp_grid in the room.
//  hcells        = Number of horizontal cells that the mp_grid will contain.
//  vcells        = Number of vertical cells that the mp_grid will contain.
//  cellwidth     = The width (in pixels) of each individual cell of the mp_grid.
//  cellheight    = The height (in pixels) of each individual cell of the mp_grid.

//@Return: Boolean if path was successfully created.

//Converts arguments to locals.
var grid = argument0;
var cost_grid = argument1;
var path = argument2;
var x1 = argument3;
var y1 = argument4;
var x2 = argument5;
var y2 = argument6;
var grid_x = argument7;
var grid_y = argument8;
var hcells = argument9;
var vcells = argument10;
var cellwidth = argument11;
var cellheight = argument12;

//Converts x/y coordinates to grid indexes.
var x1 = floor((x1 / cellwidth));
var y1 = floor((y1 / cellheight));
var x2 = floor((x2 / cellwidth));
var y2 = floor((y2 / cellheight));

//Clears path of existing points.
path_clear_points(path);
path_set_closed(path, false);

//Initialize ds_grid from mp_grid.
var ds_grid = ds_grid_create(hcells, vcells);
ds_grid = mp_grid_to_ds_grid(grid, ds_grid);

//Check if target is within grid.
if (x1 > hcells or x1 < 0) or (y1 > vcells or y1 < 0)
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Check if target is same as start.
if x1 = x2 and y1 = y2
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Check if target is in a closed cell.
if ds_grid_get(ds_grid, x2, y2) = -1
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Initialize Node Containers.
var list_closed = ds_list_create();
var list_open = ds_priority_create();

//Creates initial node.
var node_start = ds_list_create();
var parent = noone;
var cost = 0;
var distance = floor((point_distance(x1, y1, x2, y2)) + 0.5);
var value = cost + distance;
ds_list_add(node_start, x1, y1, parent, cost, distance, value);

//Adds initial node to open list.
ds_priority_add(list_open, node_start, value);

//Loops until open list is empty.
while !ds_priority_empty(list_open)
{
    //Finds lowest cost open node.
    var node = ds_priority_delete_min(list_open);

    //Setup local variables used in loop.
    var xx, yy, i, i2;
    var angle = 0;

    //Enters loop to create 8 succesors.
    for (i = 0; i < 8; i++)
    {
        //Gets variables from node.
        var nx = ds_list_find_value(node, 0);
        var ny = ds_list_find_value(node, 1);
     
        //Calculates Coordinates.
        xx = floor((nx + lengthdir_x(1, angle)) + 0.5);
        yy = floor((ny + lengthdir_y(1, angle)) + 0.5);
        angle += 45;    
     
        //Validates coordinates are within grid bounds.
        if (xx > hcells or xx < 0) or (yy > vcells or yy < 0)
        {
            //Enters next loop.
            continue;
        }
     
        //Creates succesor.
        var succesor = ds_list_create();
        parent = node;
        cost = ds_grid_get(cost_grid, xx, yy);
        if i & 1 //Checks if odd.
        {
            //Angled cost.
            cost += 14; //sqrt(2);
        }
        else
        {
            //Linear cost.
            cost += 10;
        }
        distance = floor(point_distance(xx, yy, x2, y2) + 0.5);
        value = cost + distance;
        ds_list_add(succesor, xx, yy, parent, cost, distance, value);
     
        //Check if succesor is in a closed cell.
        if ds_grid_get(ds_grid, xx, yy) = -1
        {
            //Destroy the succesor.
            ds_list_destroy(succesor);
         
            //Enters next loop.
            continue;
        }    
     
        //Check if node is the goal.
        if xx = x2 and yy = y2
        {          
            //Creates path list.
            var list_path = ds_list_create();
            var node_path = succesor;
            var parent = ds_list_find_value(node_path, 2);
            ds_list_add(list_path, node_path);
         
            //Traces parents back to initial node.
            while node_path != node_start
            {
                parent = ds_list_find_value(node_path, 2);
                ds_list_add(list_path, parent);
                node_path = parent;
            }
         
            //Creates the path from the path list.
            for (i2 = ds_list_size(list_path) - 1; i2 >= 0; i2--)
            {
                var node_point = ds_list_find_value(list_path, i2);
                var xx = (grid_x + (ds_list_find_value(node_point, 0) * cellwidth)) + cellwidth / 2;
                var yy = (grid_y + (ds_list_find_value(node_point, 1) * cellheight)) + cellheight / 2;
                path_add_point(path, xx, yy, 100);
            }
         
            //Clean-Up Leaks
            ds_grid_destroy(ds_grid);
            ds_list_destroy(list_path);
            ds_list_destroy(node);
            ds_list_destroy(succesor);
         
            //Loops through closed list.
            for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
            {
                //Cleans up leaks.
                var obj = ds_list_find_value(list_closed, i2);
                ds_list_destroy(obj);
            }
         
            //Loops through open list.
            var size = ds_priority_size(list_open);
            for (i2 = 0; i2 < size; i2++)
            {
                //Cleans up leaks.
                var obj = ds_priority_delete_min(list_open);
                ds_list_destroy(obj);
            }
         
            //Destroys lists.
            ds_list_destroy(list_closed);
            ds_priority_destroy(list_open);
         
            //Return True
            return true;
        }
     
        //Creates a copy of open list to sweep through.
        var list_open_copy = ds_priority_create();
        ds_priority_copy(list_open_copy, list_open);
        var size = ds_priority_size(list_open_copy);
     
        //Creates a continue check boolean, for nested loops.
        var continue_check = false;
     
        //Check if node with same position is in the open list.
        for (i2 = 0; i2 < size; i2++)
        {
            //Gets values from current index.
            var obj = ds_priority_delete_min(list_open_copy);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
            var obj_value = ds_list_find_value(obj, 5)
         
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Check if value of obj is lower then succesor.
                if obj_value < value
                {
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
                 
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
                else
                {
                    //Update object with succesor values.
                    ds_list_replace(succesor, 2, ds_list_find_value(obj, 2));
                    ds_list_replace(succesor, 3, ds_list_find_value(obj, 3));
                    ds_list_replace(succesor, 4, ds_list_find_value(obj, 4));
                    ds_list_replace(succesor, 5, ds_list_find_value(obj, 5));
                 
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
                 
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
            }
        }
     
        //Deletes copy of open list.
        ds_priority_destroy(list_open_copy);
     
        //Check if should continue.
        if continue_check
        {
            continue;
        }
     
        //Check if node with same position is in the closed list.
        for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
        {
            //Gets values from current index.
            var obj = ds_list_find_value(list_closed, i2);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
         
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Destroy the succesor.
                ds_list_destroy(succesor);
             
                //Updates continue check to skip loop.
                continue_check = true;
                break;
            }
        }
     
        //Check if should continue.
        if continue_check
        {
            continue;
        }

        //Add succesor to open list.
        ds_priority_add(list_open, succesor, value);
    }

    //Adds node to closed list.
    ds_list_add(list_closed, node);
}

//Exhausted all nodes.

//Clean-Up Leaks
ds_grid_destroy(ds_grid);

//Loops through closed list.
for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
{
    var obj = ds_list_find_value(list_closed, i2);
    ds_list_destroy(obj);
}

//Destroys lists.
ds_list_destroy(list_closed);
ds_priority_destroy(list_open);

//Return True
return false;

You need to setup some sort of ds_grid for your terrain, with diffrent values for your tiles. The higher the cost value the more expensive that tile is to go through. You would need to convert your map somehow to a grid, with keeping track of your diffrent tile types such as forest, road, etc.
 

RifleFire

Member
Thank you for the updated version of your script L0v3! I will try to see if i can figure out the setup. Its so great that there are examples to work from now. Many Thanks to you and everyone for their help!
RF
 
H

Haydads

Guest
Here's an updated version that takes a ds_grid for custom cost values which is added to the normal linear/angled values. Havn't tested it, but if you have a setup grid should work.

Code:
///mp_grid_astar(grid, cost, path, x_start, y_start, x_goal, y_goal, xstart, ystart, hcells, vcells, cellwidth, cellheight);

// Finds and creates the shortes path from the start position to the goal position.
// The path is created using the given mp_grid and is stored to the given path index.
// Note: This overwrites any existing path stored in the index.

// grid             = Index of the mp_grid that is to be used.
// cost             = Index of the ds_grid that is to be used get costs of tiles.
// path             = Index of the path that path is to be stored to.
// x_start          = Starting x-coordinate to go from.
// y_start          = Starting y-coordinate to go from.
// x_goal           = Destination x-coordinate to go to.
// y_goal           = Destination y-coordinate to go to.

// The following arguments should match the same as those used to create the original grid.
// I know... Blame yoyo, no get methods for mp_grid to acquire these.

//  xstart        = Starting x coordinate of the mp_grid in the room.
//  ystart        = Starting y coordinate of the mp_grid in the room.
//  hcells        = Number of horizontal cells that the mp_grid will contain.
//  vcells        = Number of vertical cells that the mp_grid will contain.
//  cellwidth     = The width (in pixels) of each individual cell of the mp_grid.
//  cellheight    = The height (in pixels) of each individual cell of the mp_grid.

//@Return: Boolean if path was successfully created.

//Converts arguments to locals.
var grid = argument0;
var cost_grid = argument1;
var path = argument2;
var x1 = argument3;
var y1 = argument4;
var x2 = argument5;
var y2 = argument6;
var grid_x = argument7;
var grid_y = argument8;
var hcells = argument9;
var vcells = argument10;
var cellwidth = argument11;
var cellheight = argument12;

//Converts x/y coordinates to grid indexes.
var x1 = floor((x1 / cellwidth));
var y1 = floor((y1 / cellheight));
var x2 = floor((x2 / cellwidth));
var y2 = floor((y2 / cellheight));

//Clears path of existing points.
path_clear_points(path);
path_set_closed(path, false);

//Initialize ds_grid from mp_grid.
var ds_grid = ds_grid_create(hcells, vcells);
ds_grid = mp_grid_to_ds_grid(grid, ds_grid);

//Check if target is within grid.
if (x1 > hcells or x1 < 0) or (y1 > vcells or y1 < 0)
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Check if target is same as start.
if x1 = x2 and y1 = y2
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Check if target is in a closed cell.
if ds_grid_get(ds_grid, x2, y2) = -1
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Initialize Node Containers.
var list_closed = ds_list_create();
var list_open = ds_priority_create();

//Creates initial node.
var node_start = ds_list_create();
var parent = noone;
var cost = 0;
var distance = floor((point_distance(x1, y1, x2, y2)) + 0.5);
var value = cost + distance;
ds_list_add(node_start, x1, y1, parent, cost, distance, value);

//Adds initial node to open list.
ds_priority_add(list_open, node_start, value);

//Loops until open list is empty.
while !ds_priority_empty(list_open)
{
    //Finds lowest cost open node.
    var node = ds_priority_delete_min(list_open);

    //Setup local variables used in loop.
    var xx, yy, i, i2;
    var angle = 0;

    //Enters loop to create 8 succesors.
    for (i = 0; i < 8; i++)
    {
        //Gets variables from node.
        var nx = ds_list_find_value(node, 0);
        var ny = ds_list_find_value(node, 1);
   
        //Calculates Coordinates.
        xx = floor((nx + lengthdir_x(1, angle)) + 0.5);
        yy = floor((ny + lengthdir_y(1, angle)) + 0.5);
        angle += 45;  
   
        //Validates coordinates are within grid bounds.
        if (xx > hcells or xx < 0) or (yy > vcells or yy < 0)
        {
            //Enters next loop.
            continue;
        }
   
        //Creates succesor.
        var succesor = ds_list_create();
        parent = node;
        cost = ds_grid_get(cost_grid, xx, yy);
        if i & 1 //Checks if odd.
        {
            //Angled cost.
            cost += 14; //sqrt(2);
        }
        else
        {
            //Linear cost.
            cost += 10;
        }
        distance = floor(point_distance(xx, yy, x2, y2) + 0.5);
        value = cost + distance;
        ds_list_add(succesor, xx, yy, parent, cost, distance, value);
   
        //Check if succesor is in a closed cell.
        if ds_grid_get(ds_grid, xx, yy) = -1
        {
            //Destroy the succesor.
            ds_list_destroy(succesor);
       
            //Enters next loop.
            continue;
        }  
   
        //Check if node is the goal.
        if xx = x2 and yy = y2
        {        
            //Creates path list.
            var list_path = ds_list_create();
            var node_path = succesor;
            var parent = ds_list_find_value(node_path, 2);
            ds_list_add(list_path, node_path);
       
            //Traces parents back to initial node.
            while node_path != node_start
            {
                parent = ds_list_find_value(node_path, 2);
                ds_list_add(list_path, parent);
                node_path = parent;
            }
       
            //Creates the path from the path list.
            for (i2 = ds_list_size(list_path) - 1; i2 >= 0; i2--)
            {
                var node_point = ds_list_find_value(list_path, i2);
                var xx = (grid_x + (ds_list_find_value(node_point, 0) * cellwidth)) + cellwidth / 2;
                var yy = (grid_y + (ds_list_find_value(node_point, 1) * cellheight)) + cellheight / 2;
                path_add_point(path, xx, yy, 100);
            }
       
            //Clean-Up Leaks
            ds_grid_destroy(ds_grid);
            ds_list_destroy(list_path);
            ds_list_destroy(node);
            ds_list_destroy(succesor);
       
            //Loops through closed list.
            for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
            {
                //Cleans up leaks.
                var obj = ds_list_find_value(list_closed, i2);
                ds_list_destroy(obj);
            }
       
            //Loops through open list.
            var size = ds_priority_size(list_open);
            for (i2 = 0; i2 < size; i2++)
            {
                //Cleans up leaks.
                var obj = ds_priority_delete_min(list_open);
                ds_list_destroy(obj);
            }
       
            //Destroys lists.
            ds_list_destroy(list_closed);
            ds_priority_destroy(list_open);
       
            //Return True
            return true;
        }
   
        //Creates a copy of open list to sweep through.
        var list_open_copy = ds_priority_create();
        ds_priority_copy(list_open_copy, list_open);
        var size = ds_priority_size(list_open_copy);
   
        //Creates a continue check boolean, for nested loops.
        var continue_check = false;
   
        //Check if node with same position is in the open list.
        for (i2 = 0; i2 < size; i2++)
        {
            //Gets values from current index.
            var obj = ds_priority_delete_min(list_open_copy);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
            var obj_value = ds_list_find_value(obj, 5)
       
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Check if value of obj is lower then succesor.
                if obj_value < value
                {
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
               
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
                else
                {
                    //Update object with succesor values.
                    ds_list_replace(succesor, 2, ds_list_find_value(obj, 2));
                    ds_list_replace(succesor, 3, ds_list_find_value(obj, 3));
                    ds_list_replace(succesor, 4, ds_list_find_value(obj, 4));
                    ds_list_replace(succesor, 5, ds_list_find_value(obj, 5));
               
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
               
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
            }
        }
   
        //Deletes copy of open list.
        ds_priority_destroy(list_open_copy);
   
        //Check if should continue.
        if continue_check
        {
            continue;
        }
   
        //Check if node with same position is in the closed list.
        for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
        {
            //Gets values from current index.
            var obj = ds_list_find_value(list_closed, i2);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
       
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Destroy the succesor.
                ds_list_destroy(succesor);
           
                //Updates continue check to skip loop.
                continue_check = true;
                break;
            }
        }
   
        //Check if should continue.
        if continue_check
        {
            continue;
        }

        //Add succesor to open list.
        ds_priority_add(list_open, succesor, value);
    }

    //Adds node to closed list.
    ds_list_add(list_closed, node);
}

//Exhausted all nodes.

//Clean-Up Leaks
ds_grid_destroy(ds_grid);

//Loops through closed list.
for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
{
    var obj = ds_list_find_value(list_closed, i2);
    ds_list_destroy(obj);
}

//Destroys lists.
ds_list_destroy(list_closed);
ds_priority_destroy(list_open);

//Return True
return false;

You need to setup some sort of ds_grid for your terrain, with diffrent values for your tiles. The higher the cost value the more expensive that tile is to go through. You would need to convert your map somehow to a grid, with keeping track of your diffrent tile types such as forest, road, etc.
Hey,
I know this thread is fairly old, but could you explain the cost grid.
What sort of values are we expecting to see here?
In the script above it mentions 10 cost for linear and 14 for diagonal, does this assume that to travel a cell edge to edge has a default cost of 10?
I understand that that 14 is the cost from corner to corner, but why are 10 and 14 used? Why not 1 and 1.4 for example?
Sorry for digging up old threads, just trying to get my head around this.
 

NightFrost

Member
Likely a choice to make all distances integer. But you'd be substituting your own terrain movement costs anyway. Otherwise the costs would be uniform across the graph, and then you just as well might use mp_grid commands instead because that's the type of graph it traverses on. Two biggest reasons to writing your own A* instead of using builtin commands would be 1) custom travel costs between each node and 2) a graph that is not shaped like a grid. I gave the script you quoted just a cursory glance but it seems to be doing a lot of work compared to some I've seen. It is likely to be on the slower end as A* scripts go (then again the author admits learning A* while writing it).
 
Yeah, I figured the same as well, my custom A* implementation is, at the very least, way less complicated. I also feel like it's a bit easier to just create your own grid, rather than using the mp_grid, considering you're already doing the heavy lifting that the mp_grid is intended for, but perhaps that's personal preference, and it assumes you have created a path resource named path, something which isn't actually explained. I prefer to return a list of points or -1 if no solution is found.
 
Here's an updated version that takes a ds_grid for custom cost values which is added to the normal linear/angled values. Havn't tested it, but if you have a setup grid should work.

Code:
///mp_grid_astar(grid, cost, path, x_start, y_start, x_goal, y_goal, xstart, ystart, hcells, vcells, cellwidth, cellheight);

// Finds and creates the shortes path from the start position to the goal position.
// The path is created using the given mp_grid and is stored to the given path index.
// Note: This overwrites any existing path stored in the index.

// grid             = Index of the mp_grid that is to be used.
// cost             = Index of the ds_grid that is to be used get costs of tiles.
// path             = Index of the path that path is to be stored to.
// x_start          = Starting x-coordinate to go from.
// y_start          = Starting y-coordinate to go from.
// x_goal           = Destination x-coordinate to go to.
// y_goal           = Destination y-coordinate to go to.

// The following arguments should match the same as those used to create the original grid.
// I know... Blame yoyo, no get methods for mp_grid to acquire these.

//  xstart        = Starting x coordinate of the mp_grid in the room.
//  ystart        = Starting y coordinate of the mp_grid in the room.
//  hcells        = Number of horizontal cells that the mp_grid will contain.
//  vcells        = Number of vertical cells that the mp_grid will contain.
//  cellwidth     = The width (in pixels) of each individual cell of the mp_grid.
//  cellheight    = The height (in pixels) of each individual cell of the mp_grid.

//@Return: Boolean if path was successfully created.

//Converts arguments to locals.
var grid = argument0;
var cost_grid = argument1;
var path = argument2;
var x1 = argument3;
var y1 = argument4;
var x2 = argument5;
var y2 = argument6;
var grid_x = argument7;
var grid_y = argument8;
var hcells = argument9;
var vcells = argument10;
var cellwidth = argument11;
var cellheight = argument12;

//Converts x/y coordinates to grid indexes.
var x1 = floor((x1 / cellwidth));
var y1 = floor((y1 / cellheight));
var x2 = floor((x2 / cellwidth));
var y2 = floor((y2 / cellheight));

//Clears path of existing points.
path_clear_points(path);
path_set_closed(path, false);

//Initialize ds_grid from mp_grid.
var ds_grid = ds_grid_create(hcells, vcells);
ds_grid = mp_grid_to_ds_grid(grid, ds_grid);

//Check if target is within grid.
if (x1 > hcells or x1 < 0) or (y1 > vcells or y1 < 0)
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Check if target is same as start.
if x1 = x2 and y1 = y2
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Check if target is in a closed cell.
if ds_grid_get(ds_grid, x2, y2) = -1
{
    //Clean-Up Leaks
    ds_grid_destroy(ds_grid);

    //Return False
    return false;
}

//Initialize Node Containers.
var list_closed = ds_list_create();
var list_open = ds_priority_create();

//Creates initial node.
var node_start = ds_list_create();
var parent = noone;
var cost = 0;
var distance = floor((point_distance(x1, y1, x2, y2)) + 0.5);
var value = cost + distance;
ds_list_add(node_start, x1, y1, parent, cost, distance, value);

//Adds initial node to open list.
ds_priority_add(list_open, node_start, value);

//Loops until open list is empty.
while !ds_priority_empty(list_open)
{
    //Finds lowest cost open node.
    var node = ds_priority_delete_min(list_open);

    //Setup local variables used in loop.
    var xx, yy, i, i2;
    var angle = 0;

    //Enters loop to create 8 succesors.
    for (i = 0; i < 8; i++)
    {
        //Gets variables from node.
        var nx = ds_list_find_value(node, 0);
        var ny = ds_list_find_value(node, 1);
    
        //Calculates Coordinates.
        xx = floor((nx + lengthdir_x(1, angle)) + 0.5);
        yy = floor((ny + lengthdir_y(1, angle)) + 0.5);
        angle += 45;   
    
        //Validates coordinates are within grid bounds.
        if (xx > hcells or xx < 0) or (yy > vcells or yy < 0)
        {
            //Enters next loop.
            continue;
        }
    
        //Creates succesor.
        var succesor = ds_list_create();
        parent = node;
        cost = ds_grid_get(cost_grid, xx, yy);
        if i & 1 //Checks if odd.
        {
            //Angled cost.
            cost += 14; //sqrt(2);
        }
        else
        {
            //Linear cost.
            cost += 10;
        }
        distance = floor(point_distance(xx, yy, x2, y2) + 0.5);
        value = cost + distance;
        ds_list_add(succesor, xx, yy, parent, cost, distance, value);
    
        //Check if succesor is in a closed cell.
        if ds_grid_get(ds_grid, xx, yy) = -1
        {
            //Destroy the succesor.
            ds_list_destroy(succesor);
        
            //Enters next loop.
            continue;
        }   
    
        //Check if node is the goal.
        if xx = x2 and yy = y2
        {         
            //Creates path list.
            var list_path = ds_list_create();
            var node_path = succesor;
            var parent = ds_list_find_value(node_path, 2);
            ds_list_add(list_path, node_path);
        
            //Traces parents back to initial node.
            while node_path != node_start
            {
                parent = ds_list_find_value(node_path, 2);
                ds_list_add(list_path, parent);
                node_path = parent;
            }
        
            //Creates the path from the path list.
            for (i2 = ds_list_size(list_path) - 1; i2 >= 0; i2--)
            {
                var node_point = ds_list_find_value(list_path, i2);
                var xx = (grid_x + (ds_list_find_value(node_point, 0) * cellwidth)) + cellwidth / 2;
                var yy = (grid_y + (ds_list_find_value(node_point, 1) * cellheight)) + cellheight / 2;
                path_add_point(path, xx, yy, 100);
            }
        
            //Clean-Up Leaks
            ds_grid_destroy(ds_grid);
            ds_list_destroy(list_path);
            ds_list_destroy(node);
            ds_list_destroy(succesor);
        
            //Loops through closed list.
            for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
            {
                //Cleans up leaks.
                var obj = ds_list_find_value(list_closed, i2);
                ds_list_destroy(obj);
            }
        
            //Loops through open list.
            var size = ds_priority_size(list_open);
            for (i2 = 0; i2 < size; i2++)
            {
                //Cleans up leaks.
                var obj = ds_priority_delete_min(list_open);
                ds_list_destroy(obj);
            }
        
            //Destroys lists.
            ds_list_destroy(list_closed);
            ds_priority_destroy(list_open);
        
            //Return True
            return true;
        }
    
        //Creates a copy of open list to sweep through.
        var list_open_copy = ds_priority_create();
        ds_priority_copy(list_open_copy, list_open);
        var size = ds_priority_size(list_open_copy);
    
        //Creates a continue check boolean, for nested loops.
        var continue_check = false;
    
        //Check if node with same position is in the open list.
        for (i2 = 0; i2 < size; i2++)
        {
            //Gets values from current index.
            var obj = ds_priority_delete_min(list_open_copy);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
            var obj_value = ds_list_find_value(obj, 5)
        
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Check if value of obj is lower then succesor.
                if obj_value < value
                {
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
                
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
                else
                {
                    //Update object with succesor values.
                    ds_list_replace(succesor, 2, ds_list_find_value(obj, 2));
                    ds_list_replace(succesor, 3, ds_list_find_value(obj, 3));
                    ds_list_replace(succesor, 4, ds_list_find_value(obj, 4));
                    ds_list_replace(succesor, 5, ds_list_find_value(obj, 5));
                
                    //Destroy the succesor.
                    ds_list_destroy(succesor);
                
                    //Updates continue check to skip loop.
                    continue_check = true;
                    break;
                }
            }
        }
    
        //Deletes copy of open list.
        ds_priority_destroy(list_open_copy);
    
        //Check if should continue.
        if continue_check
        {
            continue;
        }
    
        //Check if node with same position is in the closed list.
        for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
        {
            //Gets values from current index.
            var obj = ds_list_find_value(list_closed, i2);
            var obj_x = ds_list_find_value(obj, 0)
            var obj_y = ds_list_find_value(obj, 1)
        
            //Check if same posotion.
            if obj_x = xx and obj_y = yy
            {
                //Destroy the succesor.
                ds_list_destroy(succesor);
            
                //Updates continue check to skip loop.
                continue_check = true;
                break;
            }
        }
    
        //Check if should continue.
        if continue_check
        {
            continue;
        }

        //Add succesor to open list.
        ds_priority_add(list_open, succesor, value);
    }

    //Adds node to closed list.
    ds_list_add(list_closed, node);
}

//Exhausted all nodes.

//Clean-Up Leaks
ds_grid_destroy(ds_grid);

//Loops through closed list.
for (i2 = 0; i2 < ds_list_size(list_closed); i2++)
{
    var obj = ds_list_find_value(list_closed, i2);
    ds_list_destroy(obj);
}

//Destroys lists.
ds_list_destroy(list_closed);
ds_priority_destroy(list_open);

//Return True
return false;

You need to setup some sort of ds_grid for your terrain, with diffrent values for your tiles. The higher the cost value the more expensive that tile is to go through. You would need to convert your map somehow to a grid, with keeping track of your diffrent tile types such as forest, road, etc.
In Line 159 you are checking wether the node is the goal node or not. If it is the goal node then you are creating the path towards this node eventhough it has not checked all nodes yet. This means that this migh not be the fastest path or the past which has the lowest value? Right?
 
After about half an hour of debugging, I finally got it.

I'll give you a patched version of getShortestPath that will get it back up and running again.
Code:
/*
getShortestPath(SourceNode, TargetNode): ds_list
Computes the shortest path between the two nodes.
Returns a ds_list containing all the nodes in the path (first and last are included)
If a path could not be found, noone is returned
*/

var Source, Target, OpenedList, ClosedList, PreviousNodes, TentativeDistances, CurrentNode, End, Connections;
var tentativeDistance, Score, heuristicValue, lastConnection, currentScore;

Source = argument[0];
Target = argument[1];

OpenedList = ds_priority_create(); //{Value: Node, Priority: Score}
ClosedList = ds_list_create();
PreviousNodes = ds_map_create();//{Key: Node, Value: PreviousNode}
TentativeDistances = ds_map_create(); //{Key: Node, Value: Distance}

CurrentNode = noone;
ds_priority_add(OpenedList, Source, 1);
ds_map_add(TentativeDistances, Source, 0);

while (ds_priority_size(OpenedList) > 0) {
    CurrentNode = ds_priority_find_min(OpenedList);

    if (CurrentNode == Target) {
        break;
    }

    ds_priority_delete_min(OpenedList); //Remove current node
    ds_list_add(ClosedList, CurrentNode);
  
    Connections = __Nodes[CurrentNode, 1];
    End = false;
    lastConnection = ds_map_find_last(Connections);
    for (var Neighbour = ds_map_find_first(Connections); End == false;
        Neighbour = ds_map_find_next(Connections, Neighbour)) {
        if (Neighbour == lastConnection) {
            End = true;
        }
      
        if (ds_list_find_index(ClosedList, Neighbour) != -1) {
            continue;
        }
      
        if (!filterPath(id, Neighbour)) {
            continue;
        }
      
        tentativeDistance = ds_map_find_value(Connections, Neighbour) + ds_map_find_value(TentativeDistances, CurrentNode);
        heuristicValue = getHeuristic(Neighbour, Target);
      
        if (!ds_map_exists(TentativeDistances, Neighbour)) {
            ds_map_add(TentativeDistances, Neighbour, tentativeDistance);
        } else if (tentativeDistance < ds_map_find_value(TentativeDistances, Neighbour)) {
            ds_map_replace(TentativeDistances, Neighbour, tentativeDistance);
        }
      
        currentScore = ds_priority_find_priority(OpenedList, Neighbour);
        Score = ds_map_find_value(TentativeDistances, Neighbour) + heuristicValue + 1;

        if (Score < currentScore || currentScore == 0 || is_undefined(currentScore)) {
            if (currentScore == 0 || is_undefined(currentScore)) {
                ds_priority_add(OpenedList, Neighbour, Score);
            } else {
                ds_priority_change_priority(OpenedList, Neighbour, Score);
            }
          
            if (!ds_map_exists(PreviousNodes, Neighbour)) {
                ds_map_add(PreviousNodes, Neighbour, CurrentNode);
            } else {
                ds_map_replace(PreviousNodes, Neighbour, CurrentNode);
            }
        }
    }
}

ds_priority_destroy(OpenedList);
ds_list_destroy(ClosedList);
ds_map_destroy(TentativeDistances);
  
if (CurrentNode != Target) {
    ds_map_destroy(PreviousNodes);
    return(noone);
}


var Path;
Path = ds_list_create();
while (true) {
    ds_list_add(Path, CurrentNode);

    if (CurrentNode == Source) {
        reversedPath = ds_list_create();
        for (i = ds_list_size(Path) - 1; i >=0; i-=1) {
            ds_list_add(reversedPath, ds_list_find_value(Path, i));
        }
      
        ds_list_destroy(Path);
        ds_map_destroy(PreviousNodes);
        return(reversedPath);
    }

    CurrentNode = ds_map_find_value(PreviousNodes, CurrentNode);
}

For anyone who is interested in learning how to use the debugger, I think this is an excellent case study involving both comments and local watch values. The problem is in getShortestPath. Once you think you have a good idea where the problem is, open the spoiler for the answer:
ds_priority_find_priority() returns undefined in GMS, but 0 in 8.1 and below. The original author's assumption of the legacy behaviour has been broken. This shuts down line 64 permanently and prevents the open list from expanding.
So, the first and the second argument are ds_lists which contain two values the current x and y value and the target x and target y value?

When looping through the ds_priority_list "OpenedList" why is the loop broken when the node matches the target node? Shouldnt it loop until there is OpenendList is totally empty?
For example:
I have such a cost grid where the cell with the 0 is my startinge point and the cell with the 8 is my target point. The path with the lowest costs should be from 0 to 1 to to 2 to 3 to 8. This has a total cost sum of 14.
But because the loop breaks when the current node is equal to the target node it could happen that the I get a path from 0 to 7 to 8 which is added together 15 and more than 14. Right?

| 0 | 1 | 6 |
| 7 | 2 | 4 |
| 8 | 3 | 5 |

(I assume that i can move only in 90 degrees)
 
Top