Legacy GM [Djikstra's Pathfinding] Did I do it right?

sv3nxd

Member
Hello game-maker-community,

I've been working on a pathfinding-algorithm since yesterday morning. I didn't find any tutorials on how to implement it in GML nor what the most cost-effecient is.
This is really important to me, as pathfinding has been a problem for me for atleast half a year
(If not - then even longer)

I was wondering several things:
  • Should nodes be objects?
  • Can I have several grid's instead of object's?
  • Could 1 grid come with a map,which would store the variables of the nodes instead?
  • ... and several other questions that I couldn't answer.
I think only 2 hours of yesterday were actual programming, the rest of the day I spent just thinking how to implement it - but also how the algorithm actually works in itself.

The algorithm has no problems in a 640x640 room (Nodes being 32px).
But when having a room 1280x960 (Nodes being 32px), then the software freezes for circa 1 second.

The first thing I was working on was: "Were could I store the information for all these nodes?" ... and nothing else made any sense for me but simple objects.
It just seems to be a waste. It just sounds too obvious to be right.

I made a grid and then initialized it with the instance-id of a node, so a grid-field directly correlates to a node.
( I was also wondering if that's the right thing to do here)

There are 3 objects really important to the pathfinding.

  • oNode
  • oDjikstra
  • oColl
oNode - Create Event
Code:
///Set up variables

parent = -1;
cost = -1;
checked = false;
path = false;
oDjikstra - Create Event
Code:
///Setup djikstra-algorithm

//variables for loop
stop = false;
all_cost = 0;

//Grid
SIZE = 32;
grid_w = room_width div SIZE;
grid_h = room_height div SIZE

//Grid erstellen
grid = ds_grid_create(grid_w, grid_h);

//Grid initialiseren - Auf 1'ern werden Nodes gespawnt
ds_grid_set_region(grid,0,0,grid_w - 1,grid_h - 1,-2);
    
//Kollisionen finden
reassemble_nodes();
    
//Craete nodes
for(var row = 0; row < grid_w; row++)
{
    for(var col = 0; col < grid_h; col++)
    {
        if(grid[#row,col] == -2) grid[#row,col] = instance_create(row*SIZE,col*SIZE,oNode);
    }
}

oColl
- Has no events


There are 4 scripts really important to the pathfinding.

  • find_path : End-user-function, that returns a path (or -1) and uses all other functions
  • check_neighbours: Sets neighbours cost and set neighbours as childs
  • set_parent_as_path: (Recursive) Backtracks the path and adds every point to path
  • reassemble_nodes: If enviroment changes, this script is called to delete nodes or create them
find_path();
Code:
///find_path(x1,y1,x2,y2)
//This is the function the user will be using in the end


//Arguments
x1 = argument0;
y1 = argument1;
x2 = argument2;
y2 = argument3;

with(oDjikstra)
{
    //Variables
    stop = false;
    all_cost = 0;
    
  
    //Startcoordinates
    x1 = other.x1;
    y1 = other.y1;
    
    //Goalcoordinates
    x2 = other.x2;
    y2 = other.y2;
    
    //In case a pathsearch has been done before, reset all nodes to create-state
    if(instance_exists(oNode))
    {
        with(oNode)
        {
            cost = -1;
            parent = -1;
            checked = false;
            path = false;
        }
    }
    
    //Initialize variables with instance-ID's for easier use later
    goal = grid[#other.x2 div SIZE, other.y2 div SIZE];
    start = grid[#other.x1 div SIZE,other.y1 div SIZE];
    //Set cost of startnode to 0 so the loop has a startingpoint
    with(start) cost = 0;
    
    while(stop == false)
    {
        //Set variables
        val = 10000;
        all_checked = true; //Check if there are nodes left
        goal_reached = false; //Check if goal-node is reached
        
        //Pathfinding-Loop
        for(var i = 0; i < instance_number(oNode); i++)
        {
            var o = instance_find(oNode,i);
            found = false; //Check for nodes that have not been visited yet
            
            if(o.cost == all_cost) //Check if current node is equal to the current sum of costs of walked nodes
            {   
                with(o)
                {
                    if(!checked)
                    {
                        other.all_checked = false;
                        other.found = true;
                        checked = true; //Mark this note as visited
                        check_neighbours(x div oDjikstra.SIZE,y div oDjikstra.SIZE); //Set neighbours-cost and  set them as childs
                    }
                }   

                if(!found) //If a node has been found, reset 'i' so no node gets skipped
                {
                    all_cost++;
                    i = 0;
                }
            } 
        }
        if(all_checked == true) stop = true; //If no nodes are left, break the loop
    }
        
        
    //Create path
    if(goal_reached)
    {
        djikstras_path = path_add();
                
        with(goal)
        {
            path_add_point(oDjikstra.djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
            set_parent_as_path();
        }
                
        path_reverse(djikstras_path);
        return djikstras_path; //If a goal has been found return path
    }
    return -1; //If no goal has been found return -1
}
check_neighbours();
Code:
///check_neighbours(gridx,gridy)
var gridx = argument0;
var gridy = argument1;

//Stop when no solution or or goal reached
if(oDjikstra.stop) exit;

//Check left neighbour
if(gridx - 1 >= 0)
{
    obj = oDjikstra.grid[#gridx - 1,gridy];
    if(obj.cost == -1)
    {
        with(obj)
        {
            cost = other.cost + 1;
            parent = other;
        }
        //Check if neighbour is goal-node
        if(obj.id == oDjikstra.goal.id)
        {
            oDjikstra.stop = true;
            oDjikstra.goal_reached = true;
            show_debug_message("done");
            exit;
        }
    }
}


//Check right neighbour
if(gridx + 1 < oDjikstra.grid_w)
{
    obj = oDjikstra.grid[#gridx + 1,gridy];
    if(obj.cost == -1)
    {
        with(obj)
        {
            cost = other.cost + 1;
            parent = other;
        }
        //Check if neighbour is goal-node
        if(obj.id == oDjikstra.goal.id)
        {
            oDjikstra.stop = true;
            oDjikstra.goal_reached = true;
            show_debug_message("done");
            exit;
        }
    }
}


//Check top neighbour
if(gridy - 1 >= 0)
{
    obj = oDjikstra.grid[#gridx,gridy - 1];
    if(obj.cost == -1)
    {
        with(obj)
        {
            cost = other.cost + 1;
            parent = other;
        }
        //Check if neighbour is goal-node
        if(obj.id == oDjikstra.goal.id)
        {
            oDjikstra.stop = true;
            oDjikstra.goal_reached = true;
            show_debug_message("done");
            exit;
        } 
    }
}


//Check bottom neighbour
if(gridy + 1 < oDjikstra.grid_h)
{
    obj = oDjikstra.grid[#gridx,gridy + 1];
    if(obj.cost == -1)
    {
        with(obj)
        {
            cost = other.cost + 1;
            parent = other;
        }
        //Check if neighbour is goal-node
        if(obj.id == oDjikstra.goal.id)
        {
            oDjikstra.stop = true;
            oDjikstra.goal_reached = true;
            show_debug_message("done");
            exit;
        }
    }
}
set_parent_as_path();
Code:
//Recursive Function - Execute until there is no parent to be added
//This function backtracks the route and adds it to a predetermined path
if(parent == -1) exit;

with(parent)
{
    path_add_point(oDjikstra.djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
    set_parent_as_path();
}
reassemble_nodes();
Code:
//If a wall gets placed or anything changes (also at startup), this script should be called so no collison-objects gets into the grid
//(Collisionobject should be the size of SIZExSIZ (32 in this case)

for(var i = 0; i < instance_number(oColl); i++)
{
    var o = instance_find(oColl,i);
            
    with(o)
    {
        SIZE = other.SIZE;
        
        //lower left corner
        if(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -2)
            with(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE]) instance_destroy();
        other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] = -1;
        
        //upper left corner
        if(other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -2)
            with(other.grid[#bbox_left div SIZE,bbox_top div SIZE]) instance_destroy();
        other.grid[#bbox_left div SIZE,bbox_top div SIZE] = -1;
        
        //lower right corner
        if(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -2)
            with(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE]) instance_destroy();
        other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] = -1;
        
        //upper right corner
        if(other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -2)
            with(other.grid[#bbox_right div SIZE,bbox_top div SIZE]) instance_destroy();
        other.grid[#bbox_right div SIZE,bbox_top div SIZE] = -1;
    }
}
Thanks for everybody reading this, can't tell you how appreciated it is! :)

As an endnote: Thanks to @MishMash for inspiring me to try this :)

PATHFINDING2.gif
 

jo-thijs

Member
Should nodes be objects?
No, not necessarily.

Can I have several grid's instead of object's?
Sure.

Could 1 grid come with a map,which would store the variables of the nodes instead?
Sure.

The algorithm has no problems in a 640x640 room (Nodes being 32px).
But when having a room 1280x960 (Nodes being 32px), then the software freezes for circa 1 second.
That shouldn't happen for such a small graph yet, so there might indeed be a problem with your implementation.

The first thing I was working on was: "Were could I store the information for all these nodes?" ... and nothing else made any sense for me but simple objects.
It just seems to be a waste. It just sounds too obvious to be right.
That actually does make sense in a lot of situations, to use instances to represent nodes.

The only disadvantage is that instances might waste some resources (memory and performance) when compared to other alternatives.
Often, this will be negligable though.

I made a grid and then initialized it with the instance-id of a node, so a grid-field directly correlates to a node.
( I was also wondering if that's the right thing to do here)
It depends on the topology you're using.
If you always walk in straight lines from one instance to another, then using a grid will introduce tons more nodes than necessary, which will slow down the algorithm.
If, however, you can turn at any intersection of the grid and this might be useful to do to walk around an obstacle to reach a goal, then using a grid will be necessary.

find_path();
Code:
///find_path(x1,y1,x2,y2)
//This is the function the user will be using in the end


//Arguments
x1 = argument0;
y1 = argument1;
x2 = argument2;
y2 = argument3;

with(oDjikstra)
{
//Variables
stop = false;
all_cost = 0;


//Startcoordinates
x1 = other.x1;
y1 = other.y1;

//Goalcoordinates
x2 = other.x2;
y2 = other.y2;

//In case a pathsearch has been done before, reset all nodes to create-state
if(instance_exists(oNode))
{
with(oNode)
{
cost = -1;
parent = -1;
checked = false;
path = false;
}
}

//Initialize variables with instance-ID's for easier use later
goal = grid[#other.x2 div SIZE, other.y2 div SIZE];
start = grid[#other.x1 div SIZE,other.y1 div SIZE];
//Set cost of startnode to 0 so the loop has a startingpoint
with(start) cost = 0;

while(stop == false)
{
//Set variables
val = 10000;
all_checked = true; //Check if there are nodes left
goal_reached = false; //Check if goal-node is reached

//Pathfinding-Loop
for(var i = 0; i < instance_number(oNode); i++)
{
var o = instance_find(oNode,i);
found = false; //Check for nodes that have not been visited yet

if(o.cost == all_cost) //Check if current node is equal to the current sum of costs of walked nodes
{
with(o)
{
if(!checked)
{
other.all_checked = false;
other.found = true;
checked = true; //Mark this note as visited
check_neighbours(x div oDjikstra.SIZE,y div oDjikstra.SIZE); //Set neighbours-cost and set them as childs
}
}

if(!found) //If a node has been found, reset 'i' so no node gets skipped
{
all_cost++;
i = 0;
}
}
}
if(all_checked == true) stop = true; //If no nodes are left, break the loop
}


//Create path
if(goal_reached)
{
djikstras_path = path_add();

with(goal)
{
path_add_point(oDjikstra.djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
set_parent_as_path();
}

path_reverse(djikstras_path);
return djikstras_path; //If a goal has been found return path
}
return -1; //If no goal has been found return -1
}
check_neighbours();
Code:
///check_neighbours(gridx,gridy)
var gridx = argument0;
var gridy = argument1;

//Stop when no solution or or goal reached
if(oDjikstra.stop) exit;

//Check left neighbour
if(gridx - 1 >= 0)
{
obj = oDjikstra.grid[#gridx - 1,gridy];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}


//Check right neighbour
if(gridx + 1 < oDjikstra.grid_w)
{
obj = oDjikstra.grid[#gridx + 1,gridy];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}


//Check top neighbour
if(gridy - 1 >= 0)
{
obj = oDjikstra.grid[#gridx,gridy - 1];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}


//Check bottom neighbour
if(gridy + 1 < oDjikstra.grid_h)
{
obj = oDjikstra.grid[#gridx,gridy + 1];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}
set_parent_as_path();
Code:
//Recursive Function - Execute until there is no parent to be added
//This function backtracks the route and adds it to a predetermined path
if(parent == -1) exit;

with(parent)
{
path_add_point(oDjikstra.djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
set_parent_as_path();
}
reassemble_nodes();
Code:
//If a wall gets placed or anything changes (also at startup), this script should be called so no collison-objects gets into the grid
//(Collisionobject should be the size of SIZExSIZ (32 in this case)

for(var i = 0; i < instance_number(oColl); i++)
{
var o = instance_find(oColl,i);

with(o)
{
SIZE = other.SIZE;

//lower left corner
if(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -2)
with(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE]) instance_destroy();
other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] = -1;

//upper left corner
if(other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -2)
with(other.grid[#bbox_left div SIZE,bbox_top div SIZE]) instance_destroy();
other.grid[#bbox_left div SIZE,bbox_top div SIZE] = -1;

//lower right corner
if(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -2)
with(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE]) instance_destroy();
other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] = -1;

//upper right corner
if(other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -2)
with(other.grid[#bbox_right div SIZE,bbox_top div SIZE]) instance_destroy();
other.grid[#bbox_right div SIZE,bbox_top div SIZE] = -1;
}
}
That doesn't look great to be honest.
Quite a bit of redundancy, some confusing parts and a lot of unnecessary side effects of scripts.

It looks like you're using a while loop to loop over all path lengths.
Inside each iteration, you loop over all nodes, looking for a node that is reached in the amount of steps currently iterated over (the current path length).
If you find one of those, you start iterating over all nodes again, looking for unvisited nodes, visiting the unvisited nodes.
Visiting a node iterates over all neighbors.

In your 1280 x 960 room, you've got a total of 1200 nodes.
You're looping over all of them in each path length iteration.
This means that if the solution path length is 10, then the core part of your program would run 48000 times,
which is starting to get a lot, but should not have caused a 1 second slowdown yet.

The idea of Dijkstra's algorithm is that you only need to iterate over every node once at most, as opposed to iterating over every node for every path length.
If you could achieve this, you'd only need to run the core part of your program 4800 times in the situation described above.

You don't keep track of which nodes should be visited next.
Instead, you make the nodes remember whether they should be visited next and then you go ask every node individually if they should be visited next.

So you need an additional datastructure to keep track of the nodes to visit next.
In your case, you could do with a simple queue or list.
Every time you visit a node, you add its neighbours at the end of the queue/list.
Instead of iterating in a for loop over every find_instance, you'd then just find the next node to visit by popping off / removing the first entry of the queue / list.
This gets rid of the need for the variables: stop, all_cost, val, all_checked and found.
all_checked is in function equivalent to stop, so you didn't need both of them anyway.
stop can be replaced with checking if the queue is empty or the goal has been found.

I'll let you try this idea out on your own first.
If you have any difficulties or remaining questions, feel free to ask for help!

EDIT:
For searching purposes, you might also be interested in knowing that Dijkstra is an example of A*.
 
Last edited:

Simon Gust

Member
There are also some more minor improvements to make that don't have anything to do with your method.
I see, you're accessing a lot of instances using with() loops and dot-operators
Accessing a local variable takes 40% of the time an instance variable does using the dot-operator
Example
Code:
x1 = argument0;
y1 = argument1;
x2 = argument2;
y2 = argument3;

with (oDjikstra)
{
    //Variables
    stop = false;
    all_cost = 0;
     
    //Startcoordinates
    x1 = other.x1;
    y1 = other.y1;
   
    //Goalcoordinates
    x2 = other.x2;
    y2 = other.y2;
   
    ...
You're calling x1, y1, x2, y2 for each instance of oDjikstra.
If you had these 4 variables as local, you would not need the "other"
Code:
var xx1 = argument0;
var yy1 = argument1;
var xx2 = argument2;
var yy2 = argument3;

with (oDjikstra)
{
    //Variables
    stop = false;
    all_cost = 0;
 
    //Startcoordinates
    x1 = xx1;
    y1 = yy1;
   
    //Goalcoordinates
    x2 = xx2;
    y2 = yy2;
   
    ...
local variables are scoped beyond with statements if they're inside the same brackets.

The same goes for variables like your data structures. They can also be shortcut to local variables
The structure will not get copied, just the refrence.
This
Code:
for(var i = 0; i < instance_number(oColl); i++)
{
    var o = instance_find(oColl,i);
   
    with(o)
    {
        SIZE = other.SIZE;
       
        //lower left corner
        if(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -2)
            with(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE]) instance_destroy();
        other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] = -1;
       
        //upper left corner
        if(other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -2)
            with(other.grid[#bbox_left div SIZE,bbox_top div SIZE]) instance_destroy();
        other.grid[#bbox_left div SIZE,bbox_top div SIZE] = -1;
       
        //lower right corner
        if(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -2)
            with(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE]) instance_destroy();
        other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] = -1;
       
        //upper right corner
        if(other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -2)
            with(other.grid[#bbox_right div SIZE,bbox_top div SIZE]) instance_destroy();
        other.grid[#bbox_right div SIZE,bbox_top div SIZE] = -1;
    }
}
to this
Code:
var grid_ = grid;
var SIZE_ = SIZE;
for(var i = 0; i < instance_number(oColl); i++)
{
    var o = instance_id[i];   
    with (o)
    {
        SIZE = SIZE_
       
        //lower left corner
        if(grid_[#bbox_left div SIZE,bbox_bottom div SIZE] != -1 and grid_[#bbox_left div SIZE,bbox_bottom div SIZE] != -2)
            with(grid_[#bbox_left div SIZE,bbox_bottom div SIZE]) instance_destroy();
        grid_[#bbox_left div SIZE,bbox_bottom div SIZE] = -1;
       
        //upper left corner
        if(grid_[#bbox_left div SIZE,bbox_top div SIZE] != -1 and grid_[#bbox_left div SIZE,bbox_top div SIZE] != -2)
            with(grid_[#bbox_left div SIZE,bbox_top div SIZE]) instance_destroy();
        grid_[#bbox_left div SIZE,bbox_top div SIZE] = -1;
       
        //lower right corner
        if(grid_[#bbox_right div SIZE,bbox_bottom div SIZE] != -1 and grid_[#bbox_right div SIZE,bbox_bottom div SIZE] != -2)
            with(grid_[#bbox_right div SIZE,bbox_bottom div SIZE]) instance_destroy();
        grid_[#bbox_right div SIZE,bbox_bottom div SIZE] = -1;
       
        //upper right corner
        if(grid_[#bbox_right div SIZE,bbox_top div SIZE] != -1 and grid_[#bbox_right div SIZE,bbox_top div SIZE] != -2)
            with(grid_[#bbox_right div SIZE,bbox_top div SIZE]) instance_destroy();
        grid_[#bbox_right div SIZE,bbox_top div SIZE] = -1;
    }
}
The next thing I see is the use of instance_find. The function has a quadratic look up rate, so you're better off using
a with loop and rewrite some code or use the built-in instance_id[] array.

Another thing is the use of a instance_exists right before a with() loop. This is not necessary as a with() loop wont loop what it doesn't know.
Code:
if(instance_exists(oNode))
{
    with(oNode)
    {
        cost = -1;
        parent = -1;
        checked = false;
        path = false;
    }
}
to
Code:
with(oNode)
{
    cost = -1;
    parent = -1;
    checked = false;
    path = false;
}
 

sv3nxd

Member
Not an update, but a huge "thank you" to you both. @jo-thijs @Simon Gust

Those tips and improvements are amazing! Sadly I won't pull a late-nighter again - so I'll lay down now.
But I'm SO excited to try everything out tomorrow.

Just by reading both of your comments I learned so much more, the "local variables go into with-statements"-tip is SO helpful.
I always thought the way I do it just doesn't seem right! :D

Have a good night! I really appreciate the help.
 
I've implemented djkstra and a* algorithms in a lot of GMS games and prototypes, and looking over your code this jumps out at me because I used to do something similar:

Code:
//Craete nodes
for(var row = 0; row < grid_w; row++)
{
    for(var col = 0; col < grid_h; col++)
    {
        if(grid[#row,col] == -2) grid[#row,col] = instance_create(row*SIZE,col*SIZE,oNode);
    }
}
There is a fairly large amount of overhead that goes into making and destroying instances that doesn't always rear its head until you start making thousands of them in a single step(or at least, there was through GMS 1.4 - I haven't made an A* type pathfinder from scratch in 2 yet). Try making all your nodes at the start of your room and just leaving them there, using the same nodes each time you run your pathfinding stuff - there shouldn't be a significant performance hit if these nodes don't have any actual events and only hold variables. That also means you can shave off a millisecond or two by establishing their neighbors in advance, rather than finding them in the moment. Alternatively, spread the creation and destruction of the nodes over a couple steps, making or destroying only a few hundred of them each step. I've seen huge gains in speed just from either of those.
 

sv3nxd

Member
I've implemented djkstra and a* algorithms in a lot of GMS games and prototypes, and looking over your code this jumps out at me because I used to do something similar:

Code:
//Craete nodes
for(var row = 0; row < grid_w; row++)
{
    for(var col = 0; col < grid_h; col++)
    {
        if(grid[#row,col] == -2) grid[#row,col] = instance_create(row*SIZE,col*SIZE,oNode);
    }
}
There is a fairly large amount of overhead that goes into making and destroying instances that doesn't always rear its head until you start making thousands of them in a single step(or at least, there was through GMS 1.4 - I haven't made an A* type pathfinder from scratch in 2 yet). Try making all your nodes at the start of your room and just leaving them there, using the same nodes each time you run your pathfinding stuff - there shouldn't be a significant performance hit if these nodes don't have any actual events and only hold variables. That also means you can shave off a millisecond or two by establishing their neighbors in advance, rather than finding them in the moment. Alternatively, spread the creation and destruction of the nodes over a couple steps, making or destroying only a few hundred of them each step. I've seen huge gains in speed just from either of those.
Hello, thanks a lot to the reply!
You are right - that caused an enormous perfomance-issue, which is the reason I completly rewrote the script.
The thing is, the version I posted here in the forums already is the fixed one.

As you see - the creation of oNodes takes place in oDjikstra's Creation Event, which is in the room by startup.
So yes, when the game starts, the nodes get created and are used over and over again - instead of creating new ones every path.
Or did I misinterpret your post?
 
No, that was on me, I didn't realize that oDjikstra was created in the room on startup - I thought it was created when you started your pathfinding.

One other thing to look at, as @jo-thijs brought up, is adding a heuristic to your implementation, as it doesn't look like there is one. A* and Djikstra are largely the same thing, except A* has a heuristic to pre-determine what nodes are the most likely bets to check beforehand, usually something extremely simple like the straight-line distance between nodes. The heuristic makes the algorithm check the most likely nodes first, rather than every possible nodes, and in most cases drastically reduces the number of nodes considered. This makes them optimized for different pathfinding tasks - A* is best at quickly finding the best route between two points (which is what your gif seems to show you want to do), while Djikstra is good at finding a path from one point to every other point, or how to get to a single point from anywhere else on a map. In actual game terms, you would probably use A* in an RTS to find the path for a unit to move to another point(or find a path through a maze), while Djikstra would be used to determine the movement range of a unit in a turn-based strategy game, or to find the path for every enemy unit to get to the player after the player trips an alarm. I use Djikstra more in AI-related tasks than actual pathfinding. If your pathfinding needs are more like "point A to point B" then A* would probably be much faster for you - the tradeoff being that it's not as versatile, and in extreme cases may find a sub-optimal path. That said, given your gif, and the fact that your algorithm comments talk in terms of finding an endpoint, A* might be a much better fit for you.

If you're interested in it, this is a pretty good (and fairly short!) article on A*: http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf
 

sv3nxd

Member
No, that was on me, I didn't realize that oDjikstra was created in the room on startup - I thought it was created when you started your pathfinding.

One other thing to look at, as @jo-thijs brought up, is adding a heuristic to your implementation, as it doesn't look like there is one. A* and Djikstra are largely the same thing, except A* has a heuristic to pre-determine what nodes are the most likely bets to check beforehand, usually something extremely simple like the straight-line distance between nodes. The heuristic makes the algorithm check the most likely nodes first, rather than every possible nodes, and in most cases drastically reduces the number of nodes considered. This makes them optimized for different pathfinding tasks - A* is best at quickly finding the best route between two points (which is what your gif seems to show you want to do), while Djikstra is good at finding a path from one point to every other point, or how to get to a single point from anywhere else on a map. In actual game terms, you would probably use A* in an RTS to find the path for a unit to move to another point(or find a path through a maze), while Djikstra would be used to determine the movement range of a unit in a turn-based strategy game, or to find the path for every enemy unit to get to the player after the player trips an alarm. I use Djikstra more in AI-related tasks than actual pathfinding. If your pathfinding needs are more like "point A to point B" then A* would probably be much faster for you - the tradeoff being that it's not as versatile, and in extreme cases may find a sub-optimal path. That said, given your gif, and the fact that your algorithm comments talk in terms of finding an endpoint, A* might be a much better fit for you.

If you're interested in it, this is a pretty good (and fairly short!) article on A*: http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf
Hello, thank you for your answer!

I'm well-aware on how A* works (Well - more or less), but this was my first pathfinding. So I started with a tip by @MishMash to begin with Djikstras, he even was so kind to explain it to me. He also mentioned the relation from Djiksras to A* - and to understand A* I first should understand Djikstras.

But huge thanks for the link, it's saved and I'm definitley gonna use it.
Have a nice day!
 

sv3nxd

Member
Little Update!

I implemented a prioritylist and it makes it SO much smoother and cleaned the code up a little bit.

In a 1280x960 room I run around 1000-2000 fps. When searching for a way I fall to 400-800 fps. The thing is - It's 20 Instances of the player searching for a way simultaneously! Haha.

A M A Z I N G

Thanks to @jo-thijs and @Simon Gust ! Your tips were amazing.

The next thing is to implement a heuristic.

Here, have a .gif! (Excuse my amazing mapdesign)

 

sv3nxd

Member
YES. And again it's 2 AM ... BUT I cleaned up all the code and put in diagonal movement.


HAVE A .GIF!


Ill try to implement a heuristic tomorrow.
Have a good night.
 

jo-thijs

Member
Little Update!

I implemented a prioritylist and it makes it SO much smoother and cleaned the code up a little bit.

In a 1280x960 room I run around 1000-2000 fps. When searching for a way I fall to 400-800 fps. The thing is - It's 20 Instances of the player searching for a way simultaneously! Haha.

A M A Z I N G

Thanks to @jo-thijs and @Simon Gust ! Your tips were amazing.

The next thing is to implement a heuristic.

Here, have a .gif! (Excuse my amazing mapdesign)

YES. And again it's 2 AM ... BUT I cleaned up all the code and put in diagonal movement.


HAVE A .GIF!


Ill try to implement a heuristic tomorrow.
Have a good night.
Looks nice.

To implementing an A* algorithm, you first have to do the following:
- Have a representation for nodes.
- Have a way to determin starting nodes (with their starting costs) and goal nodes
(there might be multiple, a shooting enemy might be happy already if there's only a fence between them and the player,
whereas a melee enemy might need to get to 1 of the neighbouring squares of the player,
there might also be multiple starting nodes if the player does not get represented as a node and is inbetween multiple nodes, so he can start moving to any of those).
- Have a way to keep track of which nodes have already been visited (in constant time).
- Have a way to keep track of which nodes can be visited next (visitable nodes).
- Have a way to keep track of the cost of the path to reach a visitable node (reaching cost).
Also figure out how you deal with updating this cost if a shorter path is found.
- Have a heuristic that makes a quick estimate on how costly it will be from a given node to reach a goal node with the smallest cost.
This heuristic must be optimistic (never make an estimation that exceeds the actual cost), but also realistic (never a negative cost and as high an estimate as possible through quick calculations).
- Have a way to determin this heuristic value and/or the total cost estimate (the sum of the cost of the path to the node + the heuristic value) for every node
(you could recalculate the heuristic value every time if it is cheap enough calculation wise or you could store the result in a data structure otherwise).
- Have a way to find the visitable node with the smallest total cost estimate in constant time.
- Have a way to find all neighbors of a given node in a linear time with respect to the amount of neighbors.
- Have a way to reconstruct the path taken to reach a given node in the visitable nodes in linear time with respect to the path length.

The algorithm itself then goes as follows:
- Initialize data structures.
- Determin all the starting nodes and add them to the visitable nodes (along with their starting cost and optionally their total cost estimates).
- As long as there are visitable nodes, do the following:
-- Find the visitable node with the smallest total cost estimate.
-- Check if this node is a goal node.
-- If so:
--- Find the path of nodes leading up to this node (including the node itself).
--- Clean up data structures.
--- Return success with this path as result.
-- Else:
--- Mark this node as visited.
--- Add all the neighbors of this node to that have not yet been visited to the visitable nodes (along with their reaching cost and optionally total cost estimate)
(update the cost values of neighbors that were already visitable).
--- Remove this node from the nodes that can be visited next.
- Clean up data structures.
- Return failure.

In your case, you could do the following:
- Have a representation for nodes.
2 options:
- Use grids and no node object.
There would be a grid of booleans, telling you whether a certain node is reachable.
There would be a grid of booleans telling you which nodes have been visited.
There would be a grid of floating point numbers telling you the reaching costs of every visitable (and visited) node.
There would be a grid of integers telling you from which direction/node a visitable node has been reached.
A node would have 2 representations: its grid coordinates (X, Y) and a number X*H + Y, with H being the grid height.
- Use a node object, which has all of the above grids as variables instead.
They would also have variables containing the instance is of their neighbors (along with the cost to recah them).
This node representation may be more efficient, as you can remove nodes that only have neighbors left and right or below and on top, reducing the search space.
In these cases, there is only 1 way to go anyway, so why make a pitstop and start investigating other paths?
This node representation also allows more flexibility, as they are easily extended to allow movement in any direction, instead of only 8
and they can be more precise with obstacles and they are easier to extend to allow movement outside the grid.

- Have a way to determin starting nodes (with their starting costs) and goal nodes
(there might be multiple, a shooting enemy might be happy already if there's only a fence between them and the player,
whereas a melee enemy might need to get to 1 of the neighbouring squares of the player,
there might also be multiple starting nodes if the player does not get represented as a node and is inbetween multiple nodes, so he can start moving to any of those).
In case of a grid representation, this should be pretty clear: determin which grid square the player's on and which grid square they want to reach.
In case of an object representation, you'll want to search for all directly reachable nodes first.

The simplest way, is to loop over every node instance and check if you can reach it in a straight line.
An alternative would be, assuming nodes are placed appropriately,
to keep track of the closest directly reachable node in a variable of the player object.
Every step, the player updates this variable by looking at the neighbors of the previous closest node.
Of all the neighbors that are directly reachable in a straight line, the closest one to the player is searched for.
If a directly reachable neighbor is found that is closer to the player than its previous closest node, the variable is updated.
Starting nodes are then found by searching for every neighbor of the variable that are directly reachable by the player in a straight line.

A goal node is any node that can reach the target coordinate in a straight line.

- Have a way to keep track of which nodes have already been visited (in constant time).
I've already mentioned this.

- Have a way to keep track of which nodes can be visited next (visitable nodes).
You can have a priority queue that stores the nodes (integer representation in case of grid representation) under the priority of their total cost estimate.
This queue may contain duplicates (under a different priority) or already visited nodes.

- Have a way to keep track of the cost of the path to reach a visitable node (reaching cost).
Also figure out how you deal with updating this cost if a shorter path is found.
I've already mentioned this.

- Have a heuristic that makes a quick estimate on how costly it will be from a given node to reach a goal node with the smallest cost.
This heuristic must be optimistic (never make an estimation that exceeds the actual cost), but also realistic (never a negative cost and as high an estimate as possible through quick calculations).
The eucledian distance works very well for this.
As estimate to reach the target coordinate (TX, TY) from a node with coordinates (NX, NY), you use sqrt((TX - NX)² + (TY - NY)²).

- Have a way to determin this heuristic value and/or the total cost estimate (the sum of the cost of the path to the node + the heuristic value) for every node
(you could recalculate the heuristic value every time if it is cheap enough calculation wise or you could store the result in a data structure otherwise).
The eucledian distance is cheap enough to recalculate every time when calculating the priority of a new visitable node.

- Have a way to find the visitable node with the smallest total cost estimate in constant time.
- Have a way to find all neighbors of a given node in a linear time with respect to the amount of neighbors.
- Have a way to reconstruct the path taken to reach a given node in the visitable nodes in linear time with respect to the path length.
I've already mentioned this.

I hope this helps!

EDIT:
As an extra, if you're not afraid of looking at some messy code of mine, have a read at this thread:
https://forum.yoyogames.com/index.php?threads/recursive-problem.36634/
It showcases how A* can be used in a more abstract setting.
 
Last edited:

sv3nxd

Member
Looks nice.

To implementing an A* algorithm, you first have to do the following:
- Have a representation for nodes.
- Have a way to determin starting nodes (with their starting costs) and goal nodes
(there might be multiple, a shooting enemy might be happy already if there's only a fence between them and the player,
whereas a melee enemy might need to get to 1 of the neighbouring squares of the player,
there might also be multiple starting nodes if the player does not get represented as a node and is inbetween multiple nodes, so he can start moving to any of those).
- Have a way to keep track of which nodes have already been visited (in constant time).
- Have a way to keep track of which nodes can be visited next (visitable nodes).
- Have a way to keep track of the cost of the path to reach a visitable node (reaching cost).
Also figure out how you deal with updating this cost if a shorter path is found.
- Have a heuristic that makes a quick estimate on how costly it will be from a given node to reach a goal node with the smallest cost.
This heuristic must be optimistic (never make an estimation that exceeds the actual cost), but also realistic (never a negative cost and as high an estimate as possible through quick calculations).
- Have a way to determin this heuristic value and/or the total cost estimate (the sum of the cost of the path to the node + the heuristic value) for every node
(you could recalculate the heuristic value every time if it is cheap enough calculation wise or you could store the result in a data structure otherwise).
- Have a way to find the visitable node with the smallest total cost estimate in constant time.
- Have a way to find all neighbors of a given node in a linear time with respect to the amount of neighbors.
- Have a way to reconstruct the path taken to reach a given node in the visitable nodes in linear time with respect to the path length.

The algorithm itself then goes as follows:
- Initialize data structures.
- Determin all the starting nodes and add them to the visitable nodes (along with their starting cost and optionally their total cost estimates).
- As long as there are visitable nodes, do the following:
-- Find the visitable node with the smallest total cost estimate.
-- Check if this node is a goal node.
-- If so:
--- Find the path of nodes leading up to this node (including the node itself).
--- Clean up data structures.
--- Return success with this path as result.
-- Else:
--- Mark this node as visited.
--- Add all the neighbors of this node to that have not yet been visited to the visitable nodes (along with their reaching cost and optionally total cost estimate)
(update the cost values of neighbors that were already visitable).
--- Remove this node from the nodes that can be visited next.
- Return failure.

In your case, you could do the following:

2 options:
- Use grids and no node object.
There would be a grid of booleans, telling you whether a certain node is reachable.
There would be a grid of booleans telling you which nodes have been visited.
There would be a grid of floating point numbers telling you the reaching costs of every visitable (and visited) node.
There would be a grid of integers telling you from which direction/node a visitable node has been reached.
A node would have 2 representations: its grid coordinates (X, Y) and a number X*H + Y, with H being the grid height.
- Use a node object, which has all of the above grids as variables instead.
They would also have variables containing the instance is of their neighbors (along with the cost to recah them).
This node representation may be more efficient, as you can remove nodes that only have neighbors left and right or below and on top, reducing the search space.
In these cases, there is only 1 way to go anyway, so why make a pitstop and start investigating other paths?
This node representation also allows more flexibility, as they are easily extended to allow movement in any direction, instead of only 8
and they can be more precise with obstacles and they are easier to extend to allow movement outside the grid.


In case of a grid representation, this should be pretty clear: determin which grid square the player's on and which grid square they want to reach.
In case of an object representation, you'll want to search for all directly reachable nodes first.

The simplest way, is to loop over every node instance and check if you can reach it in a straight line.
An alternative would be, assuming nodes are placed appropriately,
to keep track of the closest directly reachable node in a variable of the player object.
Every step, the player updates this variable by looking at the neighbors of the previous closest node.
Of all the neighbors that are directly reachable in a straight line, the closest one to the player is searched for.
If a directly reachable neighbor is found that is closer to the player than its previous closest node, the variable is updated.
Starting nodes are then found by searching for every neighbor of the variable that are directly reachable by the player in a straight line.

A goal node is any node that can reach the target coordinate in a straight line.


I've already mentioned this.


You can have a priority queue that stores the nodes (integer representation in case of grid representation) under the priority of their total cost estimate.
This queue may contain duplicates (under a different priority) or already visited nodes.


I've already mentioned this.


The eucledian distance works very well for this.
As estimate to reach the target coordinate (TX, TY) from a node with coordinates (NX, NY), you use (TX - NX)² + (TY - NY)².


The eucledian distance is cheap enough to recalculate every time when calculating the priority of a new visitable node.


I've already mentioned this.

I hope this helps!

EDIT:
As an extra, if you're not afraid of looking at some messy code of mine, have a read at this thread:
https://forum.yoyogames.com/index.php?threads/recursive-problem.36634/
It showcases how A* can be used in a more abstract setting.
Hey there!
Again - thank you so much for your answer.

Though I gotta say - I implemented a heuristic already before you wrote this, when I got up today ... and it was fairly simple actually. It was literally 2 lines of code.
It goes along with the simplest way you descriped.


When checking for neighbours I added distance-to-the-goal ( sqrt(sqr(x2 - x1) + sqr(y2 - y1)) ) onto the cost, so the prioritylist would prefer nodes closer to the target.
And ... well - that solved it.

Code:
with(obj)
            {
                //Set cost , set as child and add heuristic onto cost
                cost = cost_ + 1.5;
                parent = other;
                heuristic = sqrt(sqr(x2_ - x ) + sqr(y2_ - y));
                ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
               
                //Check if neighbour is a goal-node
                if(id == oDjikstra.goal.id)
                {
                    oDjikstra.goal_reached = true;
                    exit;
                }
            }
Or would this not be an A*? What actually defines A*? Only the heuristic, right?

@Simon Gust @jo-thijs
If one of you guys gives me their blessing and I actually did it right there,then I'd mark this topic resolved.


 

jo-thijs

Member
Hey there!
Again - thank you so much for your answer.

Though I gotta say - I implemented a heuristic already before you wrote this, when I got up today ... and it was fairly simple actually. It was literally 2 lines of code.
It goes along with the simplest way you descriped.


When checking for neighbours I added distance-to-the-goal ( sqrt(sqr(x2 - x1) + sqr(y2 - y1)) ) onto the cost, so the prioritylist would prefer nodes closer to the target.
And ... well - that solved it.

Code:
with(obj)
            {
                //Set cost , set as child and add heuristic onto cost
                cost = cost_ + 1.5;
                parent = other;
                heuristic = sqrt(sqr(x2_ - x ) + sqr(y2_ - y));
                ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
              
                //Check if neighbour is a goal-node
                if(id == oDjikstra.goal.id)
                {
                    oDjikstra.goal_reached = true;
                    exit;
                }
            }
Or would this not be an A*? What actually defines A*? Only the heuristic, right?

@Simon Gust @jo-thijs
If one of you guys gives me their blessing and I actually did it right there,then I'd mark this topic resolved.


That is right.
I just gave the entire overview of A*, including the parts it has in common with Dijkstra's algorithm.
I also hinted at an alternative approach, although it probably won't add too much value in your example.

There's more than just the heuristic that defines A*, but the heuristic is the only thing that differentiates it from Dijkstra's algorithm.

This thread can be marked as resolved.
 

Simon Gust

Member
Hard to find some improvements, we don't know in what object that code is in.
Code:
var list_ = openlist;
var goal_ = oDjikstra.goal.id;
with (obj)
{
    //Set cost , set as child and add heuristic onto cost
    cost = cost_ + 1.5;
    parent = other;
    heuristic = point_distance(x, y, x2_, y2_);
    ds_priority_add(list_, self, cost + heuristic);
   
    //Check if neighbour is a goal-node
    if (id == goal_)
    {
        oDjikstra.goal_reached = true;
        exit;
    }
}
Generally, I think point_distace() is faster than the sqrt(sqr(x2-x1)+sqr(y2-y1)).
 

Simon Gust

Member
Hard to find some improvements, we don't know in what object that code is in.
Code:
var list_ = openlist;
var goal_ = oDjikstra.goal.id;
with (obj)
{
    //Set cost , set as child and add heuristic onto cost
    cost = cost_ + 1.5;
    parent = other;
    heuristic = point_distance(x, y, x2_, y2_);
    ds_priority_add(list_, self, cost + heuristic);
  
    //Check if neighbour is a goal-node
    if (id == goal_)
    {
        oDjikstra.goal_reached = true;
        exit;
    }
}
Generally, I think point_distace() is faster than the sqrt(sqr(x2-x1)+sqr(y2-y1)).
I want to add that if you can get away with this
Code:
heuristic = abs(x - x2_) + abs(y - y2_2);
It would be even faster.
The difference between the 2 is that the sqr version and the point distance version check in a circular range and
this one checks in a diamond shaped range (diagonal ranges are generally farther away than linear ranges).
 

NightFrost

Member
You probably don't want diagonals on your A-star because, as you've noticed, it makes the enemies clip through inner walls of the path's turns. I've also noticed that with larger enemy counts and larger dungeons, A-star can quickly become unwieldy due to processing times required (tested on 1.4 though so bit dated results). However, you also probably don't want the enemies being omniscient and always know where player is, so in general you can refine their movement as: 1) when not pursuing player, they default to random or random-ish movement, 2) when having direct line-of-sight to player they move directly towards player instead of doing pathfinding, 3) when pursuing player after losing line-of-sight they use pathfinding towards probable location, where they either regain LOS or give up and default back to random moves.

If A-star is becoming too much but the enemies all have a single point to converge - the player - you may tryswitching to flow field. Avoiding dynamic obstacles (other enemies) and in general anything smaller than a grid square is not very viable on A-star, so overlapping enemies is unavoidable. For such you may have to use steering behaviors, but that's not a fast solution either.
 

sv3nxd

Member
find_path()
Code:
///find_path(x1,y1,x2,y2,diagonal)
//This is the function the user will be using in the end


//Arguments
var x1_ = argument0;
var y1_ = argument1;
var x2_ = argument2;
var y2_ = argument3;
var diagonal_ = argument4;

with(oDjikstra)
{

    //Set reference
    diagonal = diagonal_;
    x1 = x1_;
    y1 = y1_;
    x2 = x2_;
    y2 = y2_;
    
    //Initialize variables with instance-ID's for easier use later
    goal = grid[#x2 div SIZE, y2 div SIZE];
    start = grid[#x1 div SIZE,y1 div SIZE];
    
    //Check for wrong path
    if(goal == -1) return -1;
    
    //Reset variables for new search
    with(oNode)
    {
        cost = -1;
        parent = -1;
    }
    
    with(start) cost = 0;
    ds_priority_add(openlist,start,0);//Set cost of startnode to 0 so the loop has a startingpoint
    goal_reached = false;
    
    //LOOP
    while(!ds_priority_empty(openlist) and goal_reached == false)
    {
        with(ds_priority_delete_min(openlist))
        {
            check_neighbours(x div oDjikstra.SIZE,y div oDjikstra.SIZE);
        }
    } 
    ds_priority_clear(openlist); //End search and reset openlist

    //Create path if it has been found
    if(goal_reached)
    {
        var djikstras_path = path_add();
        
        with(goal)
        {
            path_add_point(djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
            set_parent_as_path(djikstras_path);
        }
                
        path_reverse(djikstras_path);
        return djikstras_path; //If a goal has been found return path
    }
    
    return -1; //If no goal has been found return -1
}
check_neighbours()
Code:
///check_neighbours(gridx,gridy)
var gridx = argument0;
var gridy = argument1;
var cost_ = cost;
var x2_ = oDjikstra.x2;
var y2_ = oDjikstra.y2;
var SIZE = oDjikstra.SIZE;
diagonal = oDjikstra.diagonal;

//Check only if DIAGONAL is allowed
if(diagonal == true)
{
    //Check: BOTTOM - LEFT
    if(gridx - 1 >= 0 and gridy + 1 < oDjikstra.grid_h)
    {
        obj = oDjikstra.grid[#gridx - 1,gridy + 1];
        if(obj.cost == -1)
        {
            with(obj)
            {
                //Set cost , set as child and add heuristic onto cost
                cost = cost_ + 1.2;
                parent = other;
                heuristic = abs(x - x2_) + abs(y - y2_);
                ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                
                //Check if neighbour is a goal-node
                if(id == oDjikstra.goal.id)
                {
                    oDjikstra.goal_reached = true;
                    exit;
                }
            }
            
        }
    }
    
    //Check: BOTTOM - RIGHT
    if(gridx + 1 < oDjikstra.grid_w and gridy + 1 < oDjikstra.grid_h)
    {
        obj = oDjikstra.grid[#gridx + 1,gridy + 1];
        if(obj.cost == -1)
        {
            with(obj)
            {
                //Set cost and set as child
                cost = cost_ + 1.2;
                parent = other;
                heuristic = abs(x - x2_) + abs(y - y2_);
                ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                
                //Check if neighbour is a goal-node
                if(id == oDjikstra.goal.id)
                {
                    oDjikstra.goal_reached = true;
                    exit;
                }
            }
        }
    }
    
    //Check: TOP - LEFT
    if(gridx - 1 >= 0 and gridy - 1 >= 0)
    {
        obj = oDjikstra.grid[#gridx - 1,gridy - 1];
        if(obj.cost == -1)
        {
            with(obj)
            {
                //Set cost and set as child
                cost = cost_ + 1.2;
                parent = other;
                heuristic = abs(x - x2_) + abs(y - y2_);
                ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                
                //Check if neighbour is a goal-node
                if(id == oDjikstra.goal.id)
                {
                    oDjikstra.goal_reached = true;
                    exit;
                }
            }
        }
    }
    
    //Check: TOP - RIGHT
    if(gridx + 1 < oDjikstra.grid_w and gridy - 1 >= 0)
    {
        obj = oDjikstra.grid[#gridx + 1,gridy - 1];
        if(obj.cost == -1)
        {
            with(obj)
            {
                //Set cost and set as child
                cost = cost_ + 1.2;
                parent = other;
                heuristic = abs(x - x2_) + abs(y - y2_);
                ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                
                //Check if neighbour is a goal-node
                if(id == oDjikstra.goal.id)
                {
                    oDjikstra.goal_reached = true;
                    exit;
                }
            }
        }
    }
}


//Check: LEFT
if(gridx - 1 >= 0)
{
    obj = oDjikstra.grid[#gridx - 1,gridy];
    if(obj.cost == -1)
    {
        with(obj)
        {
            //Set cost and set as child
            cost = cost_ + 1;
            parent = other;
            heuristic = abs(x - x2_) + abs(y - y2_);
            ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                    
            //Check if neighbour is a goal-node
            if(id == oDjikstra.goal.id)
            {
                    oDjikstra.goal_reached = true;
                    exit;
            }
        }
    }
}


//Check: RIGHT
if(gridx + 1 < oDjikstra.grid_w)
{
    obj = oDjikstra.grid[#gridx + 1,gridy];
    if(obj.cost == -1)
    {
        with(obj)
        {
            //Set cost and set as child
            cost = cost_ + 1;
            parent = other;
            heuristic = abs(x - x2_) + abs(y - y2_);
            ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                    
            //Check if neighbour is a goal-node
            if(id == oDjikstra.goal.id)
            {
                    oDjikstra.goal_reached = true;
                    exit;
            }
        }
    }
}


//Check: TOP
if(gridy - 1 >= 0)
{
    obj = oDjikstra.grid[#gridx,gridy - 1];
    if(obj.cost == -1)
    {
        with(obj)
        {
            //Set cost and set as child
            cost = cost_ + 1;
            parent = other;
            heuristic = abs(x - x2_) + abs(y - y2_);
            ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                    
            //Check if neighbour is a goal-node
            if(id == oDjikstra.goal.id)
            {
                    oDjikstra.goal_reached = true;
                    exit;
            }
        }
    }
}


//Check: BOTTOM
if(gridy + 1 < oDjikstra.grid_h)
{
    obj = oDjikstra.grid[#gridx,gridy + 1];
    if(obj.cost == -1)
    {
        with(obj)
        {
            //Set cost and set as child
            cost = cost_ + 1;
            parent = other;
            heuristic = abs(x - x2_) + abs(y - y2_);
            ds_priority_add(oDjikstra.openlist,self,cost + heuristic);
                    
            //Check if neighbour is a goal-node
            if(id == oDjikstra.goal.id)
            {
                    oDjikstra.goal_reached = true;
                    exit;
            }
        }
    }
}
set_parent_as_path()
Code:
//Recursive Function - Execute until there is no parent to be added
//This function backtracks the route and adds it to a predetermined path
var path_ = argument0;

if(parent == -1) exit;

with(parent)
{
    path_add_point(path_,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
    set_parent_as_path(path_);
}
@jo-thijs I'm really sorry that I kind of jumped over your post. But I actually saved it as a .txt, because I wanna try it again with a gridbased approach to see how much of a difference there is. So again - I thank you very much for your answers. You put so much effort in them, I appreciate it.

Hard to find some improvements, we don't know in what object that code is in.
I actually forgot that, ups. Mostly I just refined with the tips of yours and got rid of unnecessary variables.

The difference between the 2 is that the sqr version and the point distance version check in a circular range and
this one checks in a diamond shaped range (diagonal ranges are generally farther away than linear ranges).
I'm really sorry - But I don't quite understand that. How does that change actually affect the shape of the search?
I mean it works - Yes. But I would actually know more background if you were so kind to tell me.

You probably don't want diagonals on your A-star because, as you've noticed, it makes the enemies clip through inner walls of the path's turns. I've also noticed that with larger enemy counts and larger dungeons
I actually meant to fix that with ... well .... with depth = -y;
But yes, I get your point.

when having direct line-of-sight to player they move directly towards player instead of doing pathfinding
This is really really interesting - haven't thought of that. Thank you.

If A-star is becoming too much but the enemies all have a single point tto converge - the player - you may try to switch to flow field. Avoiding dynamic obstacles (other enemies) and in general anything smaller than a grid square is not very viable on A-star, so overlapping enemies is unavoidable
There I thought A* and/or Djikstra would be enough - argh.
Esecpially the overlapping I noticed and already was thinking on how to even fix that ... man :D
 

Simon Gust

Member
I'm really sorry - But I don't quite understand that. How does that change actually affect the shape of the search?
I mean it works - Yes. But I would actually know more background if you were so kind to tell me.
It fakes the results a bit.
For example if you are away from your goal in a straigth line of say 100 pixel.
The equasion returns 100 in all versions.

If you are away from your goal 70 pixels down and 70 pixels right.
point_distance and the sqrt version return 100
while the abs version returns 140.

It may happen that a shorter diagonal distance is farther away than a single longer linear distance.
upload_2018-6-1_15-20-56.png
The blue target is clearly farther away than the red target, point_distance and sqrt will agree with that.
But the abs version will see this instead:
upload_2018-6-1_15-21-18.png
The red target is farther away.

What I meant with circular shape vs diamond shape is this:
Consider you're trying to fill a square with pixels so you use the same math.
With the sqrt() and point_distance() version it looks like this
upload_2018-6-1_15-24-2.png
but with the abs() version you can only get results like these
upload_2018-6-1_15-25-19.png
Now you might not be statisfied with this solution but it is similar and faster.
 

sv3nxd

Member
It fakes the results a bit.
For example if you are away from your goal in a straigth line of say 100 pixel.
The equasion returns 100 in all versions.

If you are away from your goal 70 pixels down and 70 pixels right.
point_distance and the sqrt version return 100
while the abs version returns 140.

It may happen that a shorter diagonal distance is farther away than a single longer linear distance.
View attachment 18757
The blue target is clearly farther away than the red target, point_distance and sqrt will agree with that.
But the abs version will see this instead:
View attachment 18758
The red target is farther away.

What I meant with circular shape vs diamond shape is this:
Consider you're trying to fill a square with pixels so you use the same math.
With the sqrt() and point_distance() version it looks like this
View attachment 18759
but with the abs() version you can only get results like these
View attachment 18760
Now you might not be statisfied with this solution but it is similar and faster.
Oh! Okay - Now I understand.
That explanation was perfect. Thank you very much!
(Especially thanks for the effort in the answer)
 

jo-thijs

Member
Hard to find some improvements, we don't know in what object that code is in.
Code:
var list_ = openlist;
var goal_ = oDjikstra.goal.id;
with (obj)
{
    //Set cost , set as child and add heuristic onto cost
    cost = cost_ + 1.5;
    parent = other;
    heuristic = point_distance(x, y, x2_, y2_);
    ds_priority_add(list_, self, cost + heuristic);
 
    //Check if neighbour is a goal-node
    if (id == goal_)
    {
        oDjikstra.goal_reached = true;
        exit;
    }
}
Generally, I think point_distace() is faster than the sqrt(sqr(x2-x1)+sqr(y2-y1)).
Correct.
At least, it was for windows target in GM:S 1.4.
Not sure about YYC or GM:S 2, but it definitely won't be slower.

I want to add that if you can get away with this
Code:
heuristic = abs(x - x2_) + abs(y - y2_2);
It would be even faster.
It is called the manhatten distance.
I'm not so sure about your statement of it generally being more performant than euclidean distance.
It sounds likely, because manhatten distance always provides higher estimates.
However, if you come accross a large open field you have to cross diagonally (for example, there are no obstacles and the target is at relative position (100,100)),
then manhatten distance will give every path that only moves to the right or downwards the same total cost estimate.
As a result, depending on the datastructures that provide the next node to visit, you might end up investigating every possible solution before finally returning a path.
The euclidean distance will prioritize going in something that closely ressembles a straight line, investigating way less possible solutions before returning a path.
Of course, depending on level layout, such situations may never occur.

Another thing to consider is that the manhatten distance doesn't work with diagonal movement.

The difference between the 2 is that the sqr version and the point distance version check in a circular range and
this one checks in a diamond shaped range (diagonal ranges are generally farther away than linear ranges).
What do you mean with "check in a ... range", "diagonal ranges", "linear ranges" and "... ranges are generally farther away than ... ranges"?

If you consider equidistant points with 1 fixed point, then you'll get a circle for euclidean distance and a diamond
(more specifically a square where the carriers of the sides make a 45° angle with the axises the manhatten distance is defined for).
The A* algorithm won't check in these kind of shapes though, as the distances get updated with each new visited node along the way,
so you would generally move towards the goal instead of search in a specific shape.

Is range A generally farther away than range B if B is a subset of A with A and B being defined as the sets of all points that are up to a distance D away from a fixed point P using 2 different metrics?

You probably don't want diagonals on your A-star because, as you've noticed, it makes the enemies clip through inner walls of the path's turns.
That's not a consequence of the A* algorithm, you can easily say that an empty space at relative position (1,1)
is only a neighbor if both spaces at relative positions (1,0) and (0,1) are free as well using the A* algorithm.

Although, sv3nxd's implementation does apparently have this issue.

I've also noticed that with larger enemy counts and larger dungeons, A-star can quickly become unwieldy due to processing times required (tested on 1.4 though so bit dated results). However, you also probably don't want the enemies being omniscient and always know where player is, so in general you can refine their movement as: 1) when not pursuing player, they default to random or random-ish movement, 2) when having direct line-of-sight to player they move directly towards player instead of doing pathfinding, 3) when pursuing player after losing line-of-sight they use pathfinding towards probable location, where they either regain LOS or give up and default back to random moves.

If A-star is becoming too much but the enemies all have a single point to converge - the player - you may tryswitching to flow field. Avoiding dynamic obstacles (other enemies) and in general anything smaller than a grid square is not very viable on A-star, so overlapping enemies is unavoidable. For such you may have to use steering behaviors, but that's not a fast solution either.
Those are good tips.
I originally thought sv3ncd was trying to do something else:
getting the player to move to a place the user clicked on.

check_neighbours()
Code:
///check_neighbours(gridx,gridy)
var gridx = argument0;
var gridy = argument1;
var cost_ = cost;
var x2_ = oDjikstra.x2;
var y2_ = oDjikstra.y2;
var SIZE = oDjikstra.SIZE;
diagonal = oDjikstra.diagonal;

//Check only if DIAGONAL is allowed
if(diagonal == true)
{
//Check: BOTTOM - LEFT
if(gridx - 1 >= 0 and gridy + 1 < oDjikstra.grid_h)
{
obj = oDjikstra.grid[#gridx - 1,gridy + 1];
if(obj.cost == -1)
{
with(obj)
{
//Set cost , set as child and add heuristic onto cost
cost = cost_ + 1.2;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}

}
}

//Check: BOTTOM - RIGHT
if(gridx + 1 < oDjikstra.grid_w and gridy + 1 < oDjikstra.grid_h)
{
obj = oDjikstra.grid[#gridx + 1,gridy + 1];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1.2;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}

//Check: TOP - LEFT
if(gridx - 1 >= 0 and gridy - 1 >= 0)
{
obj = oDjikstra.grid[#gridx - 1,gridy - 1];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1.2;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}

//Check: TOP - RIGHT
if(gridx + 1 < oDjikstra.grid_w and gridy - 1 >= 0)
{
obj = oDjikstra.grid[#gridx + 1,gridy - 1];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1.2;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}
}


//Check: LEFT
if(gridx - 1 >= 0)
{
obj = oDjikstra.grid[#gridx - 1,gridy];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}


//Check: RIGHT
if(gridx + 1 < oDjikstra.grid_w)
{
obj = oDjikstra.grid[#gridx + 1,gridy];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}


//Check: TOP
if(gridy - 1 >= 0)
{
obj = oDjikstra.grid[#gridx,gridy - 1];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}


//Check: BOTTOM
if(gridy + 1 < oDjikstra.grid_h)
{
obj = oDjikstra.grid[#gridx,gridy + 1];
if(obj.cost == -1)
{
with(obj)
{
//Set cost and set as child
cost = cost_ + 1;
parent = other;
heuristic = abs(x - x2_) + abs(y - y2_);
ds_priority_add(oDjikstra.openlist,self,cost + heuristic);

//Check if neighbour is a goal-node
if(id == oDjikstra.goal.id)
{
oDjikstra.goal_reached = true;
exit;
}
}
}
}
There's actually a lot wrong with this script now that you're using heuristics.

First of all, when you find a neighbor that is the goal node, it does not mean you found a solution.
You only found a solution when you visit the goal node itself.

Secondly, your heuristic isn't scaled correctly.
x, x2_, y and y2_ are the room coordinates, not the grid coordinates and the path costs are expressed in terms of grid coordinates.
They should all be in grid coordinates.
Currently you don't have an optimistic heuristic.

Thirdly, the trick Simon Gust proposed doesn't work with diagonal movement, so use euclidean distance instead.

Fourthly, you allow to clip through corners of walls, as NightFrost warned you for.

Fithly, the cost for moving to a diagonally adjacent space should be sqrt(2), not 1.2.

Sixthly, you never check if a value in the grid is -1, you just (falsely) assume it never is (so you assume no obstacles occur).
The reason this hasn't given you trouble yet so far, is because you only do stuff with the instance you take out of the grid if its variable "cost" is -1.
Now, GameMaker has the keyword "self", which you can use to refer to the executing instance.
This keyword is actually just the value -1.
This means that if you try to use the value -1 as an instance id, you will refer to the executing instance.
As a consequence (-1).cost refers to the cost of the executing instace, which is a node which already had been visited and thus has a cost different from -1.

Seventhly, you check if a node has been visited by checking if it has a cost different from -1.
However, you give a node a cost different from -1 as soon as it becomes visitable.
This makes it so you don't allow to update distances of visitable nodes.
This will actually result in wrong (suboptimal) results.

Eighthly, you should really refactor your object name oDjikstra to oDijkstra or oAstar.
Dijkstra is a Dutch name. In Dutch, "ij" is normal sound, whereas "ji" never really occurs.

And finally, you have way too much repetition in your code, which is never a good thing.

Fixing all of the above results in this script:
Code:
///check_neighbours(gridx,gridy)
var gridx = argument0;
var gridy = argument1;
var cost_ = cost;
var x2_ = oDjikstra.x2;
var y2_ = oDjikstra.y2;
var SIZE = oDjikstra.SIZE;
var diagonal = oDjikstra.diagonal;

if id == oDijkstra.goal {
    oDijkstra.goal_reached = true;
    exit;
}

checked = true;

for(var dx = -1; dx < 2; dx++) {
    for(var dy = -1; dy < 2; dy++) {
        if abs(dx) + abs(dx) == 1
        || (diagonal && abs(dx) + abs(dy) == 2) {
            if gridx + dx >= 0
            && gridx + dx < oDijkstra.grid_w
            && gridy + dy >= 0
            && gridy + dy < oDijkstra.grid_h {
                var node = oDijkstra.grid[# gridx + dx, gridy + dy];
                var nodeX = oDijkstra.grid[# gridx, gridy + dy];
                var nodeY = oDijkstra.grid[# gridx, gridy + dy];
                if node != -1 && nodeX != -1 && nodeY != -1 && !node.checked {
                    with node {
                        var newcost = cost_ + point_distance(0, 0, dx, dy);
                        if newcost < cost {
                            cost = newcost;
                            parent = other;
                            var newheuristic = point_distance(x, y, x2_, y2_) / SIZE;
                            ds_priority_add(oDijkstra.openlist, self, cost + heuristic);
                        }
                    }
                }
            }
        }
    }
}
You'll also need to reset checked to false in the find_path script.

@jo-thijs I'm really sorry that I kind of jumped over your post. But I actually saved it as a .txt, because I wanna try it again with a gridbased approach to see how much of a difference there is. So again - I thank you very much for your answers. You put so much effort in them, I appreciate it.
No problem, thank you and you're welcome!

However, I originally forgot 2 things in my reply, which I later corrected in an edit.
You might want to save it as a txt file again.

Also, the grid based approach is basically what you are alreay doing.
The object based approach is the alternative.

I actually meant to fix that with ... well .... with depth = -y;
But yes, I get your point.
That won't work, depth controls the order in which draw events are performed and has nothing to do with this.

Oh! Okay - Now I understand.
That explanation was perfect. Thank you very much!
(Especially thanks for the effort in the answer)
I still don't understand though. :(
 
T

TimothyAllen

Guest
I've also noticed that with larger enemy counts and larger dungeons, A-star can quickly become unwieldy due to processing times required (tested on 1.4 though so bit dated results). However, you also probably don't want the enemies being omniscient and always know where player is, so in general you can refine their movement as: 1) when not pursuing player, they default to random or random-ish movement, 2) when having direct line-of-sight to player they move directly towards player instead of doing pathfinding, 3) when pursuing player after losing line-of-sight they use pathfinding towards probable location, where they either regain LOS or give up and default back to random moves.

If A-star is becoming too much but the enemies all have a single point to converge - the player - you may tryswitching to flow field. Avoiding dynamic obstacles (other enemies) and in general anything smaller than a grid square is not very viable on A-star, so overlapping enemies is unavoidable. For such you may have to use steering behaviors, but that's not a fast solution either.
Those are good tips.
I originally thought sv3ncd was trying to do something else:
getting the player to move to a place the user clicked on.
If this is his primary use (multiple enemies path-finding to the player), it will probably be more efficient to simply use Dijkstra's from the player outward a specific number of cells. The algorithm could be ran by the player, anytime it changes location, and cache the results in a data-structure that the enemies can read from. The enemies would simply generate the path by access the cell that they are currently in (via the cached results). You could use a scan-line algorithm instead of the usual flood-fill (in Dijkstra's), and get even more efficiency.

EDIT: Also i would probably opt for an array to represent a node... rather than instances [array (or grid) of arrays]. Should be faster (especially if using a scan-line algorithm) and definitely would be more memory efficient.
 

Simon Gust

Member
Correct.
At least, it was for windows target in GM:S 1.4.
Not sure about YYC or GM:S 2, but it definitely won't be slower.


It is called the manhatten distance.
I'm not so sure about your statement of it generally being more performant than euclidean distance.
It sounds likely, because manhatten distance always provides higher estimates.
However, if you come accross a large open field you have to cross diagonally (for example, there are no obstacles and the target is at relative position (100,100)),
then manhatten distance will give every path that only moves to the right or downwards the same total cost estimate.
As a result, depending on the datastructures that provide the next node to visit, you might end up investigating every possible solution before finally returning a path.
The euclidean distance will prioritize going in something that closely ressembles a straight line, investigating way less possible solutions before returning a path.
Of course, depending on level layout, such situations may never occur.

Another thing to consider is that the manhatten distance doesn't work with diagonal movement.


What do you mean with "check in a ... range", "diagonal ranges", "linear ranges" and "... ranges are generally farther away than ... ranges"?

If you consider equidistant points with 1 fixed point, then you'll get a circle for euclidean distance and a diamond
(more specifically a square where the carriers of the sides make a 45° angle with the axises the manhatten distance is defined for).
The A* algorithm won't check in these kind of shapes though, as the distances get updated with each new visited node along the way,
so you would generally move towards the goal instead of search in a specific shape.

Is range A generally farther away than range B if B is a subset of A with A and B being defined as the sets of all points that are up to a distance D away from a fixed point P using 2 different metrics?
What are you trying to say? This is not the kind of language I speak, I didn't go to uni.
I understood the first part.
Based on math, the more diagonal the target is from the centre the farther the manhatten distance is compared to the euclidean distance or whatever it's called.
The reason I call shapes is because I only know this comparison from shapes and it's visually easy to explain the difference with shapes, if you look at my example.
 

jo-thijs

Member
If this is his primary use (multiple enemies path-finding to the player), it will probably be more efficient to simply use Dijkstra's from the player outward a specific number of cells. The algorithm could be ran by the player, anytime it changes location, and cache the results in a data-structure that the enemies can read from. The enemies would simply generate the path by access the cell that they are currently in (via the cached results).
I only just quickly googled the flow field algorithm, but I thought that it kinda was what you explained here.

You could use a scan-line algorithm instead of the usual flood-fill (in Dijkstra's), and get even more efficiency.
Can you elaborate?
I'm not sure what you exactly mean with a scan-line algorithm (or I just don't see how it would be more efficient).

EDIT: Also i would probably opt for an array to represent a node... rather than instances [array (or grid) of arrays]. Should be faster (especially if using a scan-line algorithm) and definitely would be more memory efficient.
Why would an array be faster?

What are you trying to say? This is not the kind of language I speak, I didn't go to uni.
I understood the first part.
Probably got nothing to do with me going to uni, but just me being bad at explaining things.
Which part did you not understand?

It was mainly me questioning if manhatten distance would indeed be more efficient than euclidean distance
and me asking what you were saying at the end of your post.

Based on math, the more diagonal the target is from the centre the farther the manhatten distance is compared to the euclidean distance or whatever it's called.
Oh ok, yup, that's true.

The reason I call shapes is because I only know this comparison from shapes and it's visually easy to explain the difference with shapes, if you look at my example.
Those shapes are often use to give an intuition of what the distances mean, but I don't see how it relates to the A* algorithm.
 

Simon Gust

Member
Probably got nothing to do with me going to uni, but just me being bad at explaining things.
Which part did you not understand?

It was mainly me questioning if manhatten distance would indeed be more efficient than euclidean distance
and me asking what you were saying at the end of your post.
I don't know the answer to that, I've done neither of these pathfinding algorithm.

Those shapes are often use to give an intuition of what the distances mean, but I don't see how it relates to the A* algorithm.
It doesn't. It has to do with how you measure a distance and if you try to shape a square, you either get a circle or a diamond.
Signalising the balance between speed and precision. A diamond is just an imprecise circle if you will.
 
T

TimothyAllen

Guest
Can you elaborate?
I'm not sure what you exactly mean with a scan-line algorithm (or I just don't see how it would be more efficient).
Scan-line is another polygon-fill algorithm that tends to be more cache friendly because you access array elements that are next to each other in memory.
Why would an array be faster?
Related to above answer. Because (1) it would be more memory efficient, it should be more cache friendly. (2) Because you can better control how the arrays are in memory, you can make better use of the cache by accessing (and iterating) data that are next to each other in memory.
 

NightFrost

Member
The above mention on caching reminded me - there's no need to redo pathfinding as long as player remains in same grid cell, so previous paths remain valid and can be reused. Flow fields work in similar manner as the idea about calculating djikstra from player outwards: first you generate a heatmap that pulses outwards from player to specified distance, then generate a flow field from the result. You need to do this only once, and not repeat until player moves to another cell. Every enemy within the specified distance can then just reference the flow field and know which way to move within their current grid cell. A flow field extending 20 steps outwards was, on my tests on 1.4, pretty fast and I would assume enough for most player-seeking purposes.
 

jo-thijs

Member
Scan-line is another polygon-fill algorithm that tends to be more cache friendly because you access array elements that are next to each other in memory.
I still don't understand.
How do you use a polygon-fill algorithm for path finding?

(1) it would be more memory efficient
Grids are just as large as arrays, if you ignore the bit that's necessary to keep track of the second dimension size
and whatever GameMaker uses to maintain datastructures as opposed to arrays.
Furthermore, grids use 2 coordinates, but the amount of coordinates we store and pass around is constant,
so the memory consumption would be slightly higher (a matter of bytes) and would be constant.

(2) Because you can better control how the arrays are in memory, you can make better use of the cache by accessing (and iterating) data that are next to each other in memory.
Sure, but I feel like cache misses won't be the bottleneck, as opposed to the sheer size of the search space.
Currently I can't think of a way to use arrays to optimize cache hits without growing the search space significantly.
 
T

TimothyAllen

Guest
I still don't understand.
How do you use a polygon-fill algorithm for path finding?
Dijkstra's is nothing more than flood-fill.

Grids are just as large as arrays, if you ignore the bit that's necessary to keep track of the second dimension size
and whatever GameMaker uses to maintain datastructures as opposed to arrays.
Furthermore, grids use 2 coordinates, but the amount of coordinates we store and pass around is constant,
so the memory consumption would be slightly higher (a matter of bytes) and would be constant.
I was not comparing arrays to grids, I was comparing arrays to instances. That being said, I would still prefer an array over a grid (when iterating a bunch) because I'm not sure if grids are row or column major.

Now that I think about it more, nodes don't need much data, so I would probably just use a real value to represent the nodes and just use bit operations to extract the data... so my choice would be an array of reals.

Currently I can't think of a way to use arrays to optimize cache hits without growing the search space significantly.
Not sure what you mean here.

Edit: and to clarify, I'm not saying that I have implemented Dijkstra's using a scanline algorithm. It might not even be feasible. My main point was to use Dijkstra's to create a flow field (if lots of entities tracking one instance) and to consider not using instances to represent your nodes.
 
Last edited by a moderator:

jo-thijs

Member
Dijkstra's is nothing more than flood-fill.
Sure, but that doesn't answer my question.
I don't see the relation between a polygon-fill algorithm and path-finding algorithms and it sounds interesting.

I was not comparing arrays to grids, I was comparing arrays to instances. That being said, I would still prefer an array over a grid (when iterating a bunch) because I'm not sure if grids are row or column major.

Now that I think about it more, nodes don't need much data, so I would probably just use a real value to represent the nodes and just use bit operations to extract the data... so my choice would be an array of reals.
Oh ok, my bad.
In that case your statement would be correct if you'd place an instance on every cell of the grid, but you can often do with way less nodes.
If you can remove 90% of the nodes by representing them as object instances, it will probably be preferable above using the grid representation.

Not sure what you mean here.
I worded what I wanted to say incorrectly.
I meant growing the part of the search space that is visited rather than the search space itself.

Basically, I was just saying I still didn't understand how to use the polygon-fill algorithm for path finding.

Edit: and to clarify, I'm not saying that I have implemented Dijkstra's using a scanline algorithm. It might not even be feasible. My main point was to use Dijkstra's to create a flow field (if lots of entities tracking one instance) and to consider not using instances to represent your nodes.
I still don't know what the scanline algorithm means and I'm curious.
I get how Dijkstra's algorithm can be used to generate a flow field and why it is good if there are a lot of entities tracking one instance.
Using instances to represent nodes is sometimes the better way to go (probably not for the example discussed in this thread, but definitely so in other situations).
 

Joe Ellis

Member
Flagging is a really useful thing with this kind of thing, You can flag a node, so that you mark it as read, and then the loop can ignore this if it's already been used\read\and flagged, you wouldnt believe how much time this saves
Btw, I didnt have time to read all the posts on this, so someone mightve mentioned it before, but its just a tip I know.,
They used to do flagging alot in basic from what I've heard, and I've been using it loads in my saving and loading functions for my thing
 
Top