Pathfinding Code Performance

Kezarus

Endless Game Maker
Hi! I'm making a pathfind code and I'm wondering if there is anything that I could do to reduce the impact of it.

I am already using some shenanigans to reduce it. Those are:
  • Manhattan heuristics
  • Max distance allowance
  • Lookup lists
I'm starting to think about on making some kind of queue where the objects requests a pathfind and another object process the queue, ten or so items per step. (there will be a lot of objects on the screen, +500).


Here is my full code:
GML:
//THE CLASS
function Pathpoint(_cellX, _cellY, _score, _heuristic, _cameFrom) constructor{
    cellX = _cellX;
    cellY = _cellY;
    Score = _score;
    Heuristic = _heuristic;
    CameFrom = _cameFrom; //an array of Pathpoints
  
    static Value = function(){
        return Score+Heuristic;
    }
}

GML:
//https://en.wikipedia.org/wiki/A*_search_algorithm
function Pathfind(iniX, iniY, endX, endY){
    var mapWidth = ds_grid_width(global.grdBiome);
    var mapHeight = ds_grid_height(global.grdBiome);
  
    //CHANGE COORD TO CELL
    iniX = clamp(iniX div CELL_SIZE, 0, mapWidth-1);
    iniY = clamp(iniY div CELL_SIZE, 0, mapHeight-1);
    endX = clamp(endX div CELL_SIZE, 0, mapWidth-1);
    endY = clamp(endY div CELL_SIZE, 0, mapHeight-1);
  
    //MAX DISTANCE
    var maxDist = 25;
    if( point_distance(iniX, iniY, endX, endY) > maxDist ){
        var dir = point_direction(iniX, iniY, endX, endY);
        endX = floor(iniX + lengthdir_x(maxDist, dir));
        endY = floor(iniY + lengthdir_y(maxDist, dir));
    }
  
    //PREPARING VARIABLES
    var result = [];
    var iterations = 0;
    var lstOpen = ds_list_create();
    var lstOpenLookup = ds_list_create();
    var lstCloseLookup = ds_list_create();
    var wScore = 1;
    var wHeuristic = 0;
    var wCameFrom = [];

    //FIRST NODE
    ds_list_add(lstOpen, new Pathpoint(iniX, iniY, wScore, wHeuristic, []));
    ds_list_add(lstOpenLookup, string(iniX) + "*" + string(iniY));


    //REAL PATHFINDING
    var pointNow, posX, posY, point, arr, lookup;
    while( !ds_list_empty(lstOpen) ){
        iterations++;
      
        //FIND SMALLEST SCORE IN OPEN LIST
        var lesserScore = 1000000, lesserIndex=0;
        var lstSize = ds_list_size(lstOpen);

        for(var i=0; i<lstSize; i++){
            point = lstOpen[| i];
            if( point.Value() < lesserScore ){
                lesserScore = point.Value();
                lesserIndex = i;
            }
        }
        pointNow = lstOpen[| lesserIndex];
              
        posX = pointNow.cellX; //THIS IS THE CURRENT NODE X
        posY = pointNow.cellY; //THIS IS THE CURRENT NODE Y
      
      
        //CHECK IF ARRIVED
        if( posX == endX && posY == endY ){
            //THEN CONSTRUCT THE RETURN
            //ADD THE CURRENT POINT
            array_push(pointNow.CameFrom, [posX, posY]);
          
            //INVERT THE ARRAY
            for(i=array_length(pointNow.CameFrom)-1; i>0; i--){ //DISCARD THE FIRST POINT
                array_push(result, pointNow.CameFrom[i]);
            }

            break; //BREAK THE LOOP
        }else{
            //REMOVE FROM OPEN LIST
            ds_list_delete(lstOpen, lesserIndex);
            ds_list_delete(lstOpenLookup, lesserIndex);
              
            //ADD TO CLOSE LIST
            lookup = string(posX) + "*" + string(posY);
            ds_list_add(lstCloseLookup, lookup);
          
            //ADD NEIGHBORS
            var Neighbors;
            Neighbors[0] = [posX+1, posY+0];
            Neighbors[1] = [posX-1, posY+0];
            Neighbors[2] = [posX+0, posY+1];
            Neighbors[3] = [posX+0, posY-1];
  
            var wx, wy, pointNeighbor;
            for( var i=0; i<array_length(Neighbors); i++ ){
                //VERIFY BOUNDARIES
                arr = Neighbors[i];
                wx = arr[0];
                wy = arr[1];
                if( wx < 0 ){ continue; }
                if( wy < 0 ){ continue; }
                if( wx >= mapWidth ){ continue; }
                if( wy >= mapHeight ){ continue; }
      
                //DON'T ADD IF ALREADY IN CLOSE LIST
                lookup = string(wx) + "*" + string(wy);
                if( ds_list_find_index(lstCloseLookup, lookup) != -1 ){
                    continue;
                }

                //CALCULATE SCORE AND HEURISTIC
                wScore = pointNow.Score + PathfindGetScore(wx, wy);
                wHeuristic = PathfindGetHeuristic(wx, wy, endX, endY);
              
                //DUPLICATE AND PATH TO HERE AND ADD POINT
                wCameFrom = array_duplicate(pointNow.CameFrom);
                array_push(wCameFrom, [pointNow.cellX, pointNow.cellY]);
              
                //CREATE PATH POINT
                pointNeighbor = new Pathpoint(wx, wy, wScore, wHeuristic, wCameFrom);

                //IF NOT IN OPEN LIST
                var indexInOpen = PathfindSearchPointIndex(lstOpenLookup, pointNeighbor);
                if( indexInOpen == -1 ){
                    //ADD TO OPEN
                    ds_list_add(lstOpen, pointNeighbor);
                    ds_list_add(lstOpenLookup, string(wx) + "*" + string(wy));
                }else{
                    //FIND THE OPEN SCORE
                    var pointInOpen = lstOpen[| indexInOpen];
          
                    //IS THIS PATH SHORTER?
                    if( pointInOpen.Value() > pointNeighbor.Value() ){
                        //SUBSTITUTE
                        lstOpen[| indexInOpen] = pointNeighbor;
                    }
                }
            } //END OF FOR NEIGHBORS
        } //END OF IF ARRIVED
    } //END OF WHILE
  
    ds_list_destroy(lstOpen);
    ds_list_destroy(lstOpenLookup);
    ds_list_destroy(lstCloseLookup);

    //alert("iterations", iterations);

    return result;
}

GML:
function PathfindGetScore(wx, wy){
    switch( global.grdBiome[# wx, wy] ){
        case MapGenBiomesEnum.Void: return 1; break;
        case MapGenBiomesEnum.Ocean: return 5; break;
        case MapGenBiomesEnum.River: return 4; break;
      
        case MapGenBiomesEnum.Grass:
        case MapGenBiomesEnum.Desert: return 1; break;
      
        case MapGenBiomesEnum.ForestBoreal:
        case MapGenBiomesEnum.ForestTemperate:
        case MapGenBiomesEnum.ForestTropical: return 2; break;
      
        case MapGenBiomesEnum.Alpine:
        case MapGenBiomesEnum.Mountain:
        case MapGenBiomesEnum.Mesa: return 3; break;
      
        default: return 1;
    }
}

GML:
//http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-distance
function PathfindGetHeuristic(nowX, nowY, endX, endY){
    var deltaX = abs(nowX - endX);
    var deltaY = abs(nowY - endY);
    var factor = 1.75;
    return factor*(deltaX+deltaY);
}

GML:
function PathfindSearchPointIndex(list, point){
    return ds_list_find_index(list, string(point.cellX)+"*"+string(point.cellY));
}

GML:
function array_duplicate(arraySource){
    var len = array_length(arraySource);
    var arrayDest = [];
    array_copy(arrayDest, 0, arraySource, 0, len);
  
    return arrayDest;
}
 

Kezarus

Endless Game Maker
Well, I fix a mistake that I made on the queue but even then it's not good.


I tried the Profiler, but what is consuming the most resources is the ds_list_find_index. o_Ô


Is there a way to ease the processing or should I just ditch A* and let the instances walk freely and on ocasion enforce a path?
 

GMWolf

aka fel666
creating and destroying structs is expensive, and adds lots of extra hidden costs in form of the GC.
In tour path finding loop, you are creating a new path point. Don't. Find another way to store that data. You could for instance use a ds_list for each field of the struct and use an index into those lists instead.

Rather than doing the path finding loop in on go, you can split it up over multiple steps. I dont mean only do it once every X steps, i mean doing X iterations every step. (so doing path finding could take multiple steps).

Try to use a hierarchical approach, use a very coars grid to do a quick path find, and then refine it with a finer grid.


I implemented my own path finding a while back, and ran into performance issues with YYC. i just couldn't get it to run in real time even on a modestly sized map.
I just dont think GML is up to the task to be perfectly honest. I hope someone else can prove me wrong and demonstrate some good real time multi agent path finding.



Assuming your world is mostly open, and not like a maze, you can also choose to find shorter paths that get you closer to your destination. The smaller the paths, the faster path finding will be and the more spread out over time it will be, but the less accurate it will be.
 
Last edited:

Padouk

Member
Ahoy!
It's been a while since I last coded an A*... Maybe 15 years... So I won't be of much help for fine tuning and micro details with code. I'm sure you know how the profiler in GMS2.3 works and you are already using a reasonable implementation so you don't have to worry about the algorithm order...

So my tips here will be more on the macro level on how to use that PF instead of how to implement it.

I'm starting to think about on making some kind of queue where the objects requests a pathfind and another object process the queue, ten or so items per step. (there will be a lot of objects on the screen, +500).
I mean... you can't go wrong with that kind of Process Manager... an Object with a Create and a Step who's responsability is to process X items per step... . To me that's the right way to break CPU bound long running process...
This is a good general approach so.. why not...

(there will be a lot of objects on the screen, +500).
It's hard for me to imagine a situation where you really need 500 long paths found at the same time.

So I would probably try and convince you not to do that ;)
--

Ok what do we know...
- The longer the path, the more chance many instances will converge to the same path fragment.
To reduce the workload, you can recycle some path segments. Depending on how dynamic the map some path segment can be precomputed or cached for a few minutes
For example here you would find 9 small paths (size 5 ish each... which is not so long to procses) and 3 longer ones (more than 25)
Tips 1: Use some partial match and caching.
1608500090548.png


- The longer the path = the longer the process time. To reduce your workload it's best to reduce the path size.
I'm not saying to reduce the distance. I'm saying to reduce the path size. You can achieve that with a 2 tier grid system.

First you run your PF on a grid 8 time bigger. Let's call that the Zone Path...
Since we have 9 actors moving.. that's 9 PF of side 5
-
Then your run your PF for each actors up to the edge of that zone.
Since each zone have a size of 8... your longest path here is 8.
1608500358947.png


- Fixed path size
We have now established the longest path possible is 8.
If your destination is further away than 8, you go with a 2 grid system.
If your destination is further away than 64, you go with a 3 grid system.
If your destination is further away than 4096, .. you got the idea,

You can use that new truth and assume ALL path to be EXACTLY 8 long. Knowing all path have a fixed size. You can use some micro optimization hardcoding the array size, pre allocating your resources removing if conditions or even unrolling some for loops instead of using flexibles lists and structures. Again.. that's micro and I don't go here, but you get the idea
 
Last edited:

Kezarus

Endless Game Maker
@GMWolf and @Padouk, wow! Thanks for the explanations!

creating and destroying structs is expensive, and adds lots of extra hidden costs in form of the GC.
In tour path finding loop, you are creating a new path point. Don't. Find another way to store that data. You could for instance use a ds_list for each field of the struct and use an index into those lists instead.
Ok, I think it's easy enough to just ditch the structs I'm using and use an array or lists, right? It seems that this is a low hanging fruit that I can easily collect. =]

It's hard for me to imagine a situation where you really need 500 long paths found at the same time.

So I would probably try and convince you not to do that ;)
Yeah, it's more of a stress test than anything else. I will have troops that will gravitate around a Town and look for enemies. Those will not need a real Pathfind. But the Player, Merchants and War Parties will need that. So I broke them down by distance.

- Fixed path size
We have now established the longest path possible is 8.
If your destination is further away than 8, you go with a 2 grid system.
If your destination is further away than 64, you go with a 3 grid system.
If your destination is further away than 4096, .. you got the idea,
That's quite something for me to wrap my head around. I kinda understand it but I have no idea on how to implement this. You both recommend it. I will see what I can do here. 😅

Mates, thanks a ton! 😁
 

Padouk

Member
That's quite something for me to wrap my head around. I kinda understand it but I have no idea on how to implement this. You both recommend it. I will see what I can do here. 😅

Same code.. same everything... just /8 on your x,y width and height...


The only difference is in your global.grdBiome
global.grdBiome[# wx, wy] is your fine map
global.grdBiome[# wx*8, wy*8] is slightly coarser
global.grdBiome[# wx*64, wy*64] is as coarse as you'll need
same thing for width/8 and height/8




Code:
function PathfindGetScore(wx, wy){
    switch( global.grdBiome[# wx, wy] ){  //<------------- For a coarser map you simply need to get the Min/Max/Avg of all 64 weight
 
Last edited:

GMWolf

aka fel666
will have troops that will gravitate around a Town and look for enemies.
If they are all goind towards the same point, then dont use A*, use dijkstra's instead. You only need to do dijkstras once for each destination, and you can reuse that data to get paths from any point on the map. That's how a lot of, ie, tower defence games do it.
 

Kezarus

Endless Game Maker
The only difference is in your global.grdBiome
global.grdBiome[# wx, wy] is your fine map
global.grdBiome[# wx/8, wy/8] is slightly coarser
global.grdBiome[# wx/64, wy/64] is as coarse as you'll need
same thing for width and height
HUahuahuah, you really made something complicated VERY simple to understand. Awesome! XD

So I just have to tweek the PathfindGetScore() to get the average instead of the single cell? I could have the values pre-calculated on a coarse grid the ease the processing of averages. But how can I get the exact path? Should I run again on the finer grid after I run in the coarse? Hmmmmm. Still trying to picture the details on my head, mate, but sure that light some lamps in my head! 😄


If they are all goind towards the same point, then dont use A*, use dijkstra's instead. You only need to do dijkstras once for each destination, and you can reuse that data to get paths from any point on the map. That's how a lot of, ie, tower defence games do it.
Hmmm, so I have to store a path for all points in a single point...? Isn't it too heavy on memory? Did I understood that wrong?
 

GMWolf

aka fel666
Hmmm, so I have to store a path for all points in a single point...? Isn't it too heavy on memory? Did I understood that wrong?
if you are going to a single point, then all you need is a single grid, where each cells holds the next cell to go to. That grid essentially holds the path information for every possible source.
Think of the grid you build when running A*/Dijkstras: i think its the cameFrom DS in your code.
You keep that around, and use it to build all your other paths.

check out this page it explains it really well: https://www.redblobgames.com/pathfinding/tower-defense/

Also having another look at you code, you arte storing coordinates using arrays. Thats going to be slow, each array is allocated on the heap and is garbage collected.
Instead, since you know the size of your grid, you can use a single integer instead. ( x + y * WIDTH).
 

Kezarus

Endless Game Maker
Well, removing the Struct and using ( x + y * WIDTH) already helped a LOT. Still not ideal though.

In the next episode: Coarse to Finer Approach. Could I understand the concept? Will I destroy my code doing so? Will GMS drop some shenanigans and drives me insane? Stay tuned for the next episode. 😁

(now let me stay a little with my family 'cause I spent all day coding 😅)
 

vdweller

Member
Hi Kezarus,

First, please consider altering the thread's title to something involving "Pathfinding", in order to provide more context to future visitors and people who search for answers to similar problems.

Your pathfinding implementation can benefit from several optimizations and, as it is, is very slow. Now, GML is very slow by itself, so your pathfinding is very very slow lol. But seriously, here are a couple things to consider:

  • You don't need open and closed lists. You only need a ds_priority data structure in which to store nodes based on their f score. Open and closed lists are more like concepts and you don't need to literally implement them as iterating through them will make things unnecessarily slow.
  • A way to do away with them is to simply add a list property to each node (ie what "list" it belongs to). If a node is decided to go to the open list, add it to the ds_priority and set its list property eg to 1. If it goes to the closed list, set its list property to 0. Belonging to neither list can be something like -1.
  • An even better way to implement this to also never, ever have to do any kind of cleanup per node afterwards, is to keep the aforementioned values stored in a global variable and each time the algorithm is run, increment them by 2. So, with an initial list property value of -1, the first time the algorithm is run, you get:
Code:
var node_belongs_to_closed=0;

var node_belongs_to_open=1;
Any node with a list property value not 0 or 1 is neither in the open or closed list yet.

The second time (increment these values by 2):

Code:
var node_belongs_to_closed=2;

var node_belongs_to_open=3;
Any node with a list property value not 2 or 3 is neither in the open or closed list yet. And guess what, because the time before all these values could be were either 0, 1 or -1, all nodes now are "neither here nor there" and have to be properly explored, as they should.

Etc etc.

This saves you from having to do any value resetting per node, you will have to only reset the start node's properties each time the algorithm is run.
  • You can store each node's neighbors so that you won't have to look them up every time the algorithm is run. Even in a dynamic environment where passability can change, it's trivial to recalculate each neighbor for a node and its surrounding ones.
  • In general, try to think in nodes connected with each other, not grid squares. For instance, a check of
Code:
if (node_current == node_goal) {}
Is probably more efficient than

Code:
if (nodex == endx && nodey==endy) {}
That's all for now, I may add more if I remember anything important.
 

Kezarus

Endless Game Maker
The name of the game is Hierarchical Pathfinding or HPA*! I will try to do the following:
  • if too close to start or finish, use a finer approach
  • if not, use a coarser grid with averages of 10x10 square chunks
I can prepare that coarse grid in advance, if the mai grid is 300x300 the coarse will be 30x30, shoudn't be too difficult.

I don't know if that will solve the problem though. Or if that is what you guys pointed me out to.


@vdweller, I already read what you write 3 times. I will give it more tries to really understand what you pointed out.

You guys are being of great help. I'm sorry if I can't keep up with the logic and knowledge. But I will improve! Thanks! =]
 
Last edited:

vdweller

Member
The name of the game is Hierarchical Pathfinding or HPA*! I will try to do the following:
  • if too close to start or finish, use a finer approach
  • if not, use a coarser grid with averages from 8 to 64
I can prepare a coarse grid in advance, shoudn't be too difficult. I don't know if that will solve the problem though.


@vdweller, I already read what you write 3 times. I will give it more tries to really understand what you pointed out.

You guys are being of great help. I'm sorry if I can't keep up with the logic and knowledge. But I will improve! Thanks! =]
Don't worry, my first implementation of the A* was much like yours, it's only natural to find it hard and, to be fair, it's not the simplest algorithm out there... I've seen quite atrocious implementations on the net from people pretending to know about it and teaching others... But! You can expect at least an order of magnitude better performance if you optimize it, so it's a very worthy goal. You can do it!

About HPA*: HPA* can make your pathfinding very, very fast... the only issue I can find is that it may produce irregular paths because each region, as you will read in the relevant papers, has its own entry/exit points which may not be exactly aligned with those of the region below and so on. There are "smoothing" techniques but I haven't studied them tbh, allegedly they can smooth out a path to look like 99% of the original.

If you manage to go that deep, may I also suggest going for a region-based Dijkstra like in Rimworld, it is like HPA* but paths look better, it's very very fast and you may also use regions to store other data (like rooms etc). This video from the creator of Rimworld elaborates on regions and it can be quite enlightening.

Lastly, for a strategy game I believe flow fields are also a good solution as they are well suited for a "multiple agents need to go to X" scenarios. Look it up!
 

Kezarus

Endless Game Maker
@vdweller, thanks a lot for the help!

On the accelerators of Open/Close lists, I think I can do a ds_map to look for nodes exactly. I have a unique key of (x + (y * 10 000)). I can't understand how can I use a ds_priority to do that search. Is that aligned with what you said?

What if I told you that this is an RPG and not a Strategy Game? 😅 This is part of the "Living World" concept. The Towns will grow and attack each other, the world will change and the Player is right in the middle. I did that before here. But the map was 100x100 and GM was 1.4. I copied almost all of my algorithm from there and it's slow on GM 2.3.1. Go figures... o.Ô?


Lastly, for a strategy game I believe flow fields are also a good solution as they are well suited for a "multiple agents need to go to X" scenarios. Look it up!
I got Floyd-Warshall and Johnson’s Algorithm but I couldn't understand them, let alone make an implementation of it. x_X


If you manage to go that deep, may I also suggest going for a region-based Dijkstra like in Rimworld, it is like HPA* but paths look better, it's very very fast and you may also use regions to store other data (like rooms etc). This video from the creator of Rimworld elaborates on regions and it can be quite enlightening.
YES! Rimworld! That will be a good one. Gonna have a look, maybe it helps. Thanks! =D
 
Be careful using a ds_map with an integer key, AFAIK, it converts the real to a string, which is yet another bottleneck area (string conversion can be quite slow when running hundreds or even thousands of times in a step). Might be better to use an array or something that naturally uses integers.
 

vdweller

Member
@vdweller, thanks a lot for the help!

On the accelerators of Open/Close lists, I think I can do a ds_map to look for nodes exactly. I have a unique key of (x + (y * 10 000)). I can't understand how can I use a ds_priority to do that search. Is that aligned with what you said?

What if I told you that this is an RPG and not a Strategy Game? 😅 This is part of the "Living World" concept. The Towns will grow and attack each other, the world will change and the Player is right in the middle. I did that before here. But the map was 100x100 and GM was 1.4. I copied almost all of my algorithm from there and it's slow on GM 2.3.1. Go figures... o.Ô?



I got Floyd-Warshall and Johnson’s Algorithm but I couldn't understand them, let alone make an implementation of it. x_X



YES! Rimworld! That will be a good one. Gonna have a look, maybe it helps. Thanks! =D
In A*, you put candidate nodes in a list along with their f score, and in the next iteration you pull out to examine the node with the lowest f score. A priority list is precisely the data structure you need for this job. You DON'T need any other data structures, no maps, no arrays, no lists...trust me on that! Any required data, like a node's parent during pathfinding, can be stored in a node's properties, along with its neighbors, terrain cost, coordinates, which group it belongs to (open or closed) etc. Take a look at the simplest, bare bones A* pseudocode (I repeat, pseudocode, not implementations) to figure out the bare minimum you have to do to make it work.
 

Kezarus

Endless Game Maker
I already made so many changes to my code that I really should update it here. 😅

Mostly deals with string transformations and Structs to arrays changes.

I'm watching that sweet Rimworld video. Maybe it can help me understand what's up.

If ds_maps is a no go.... hmmm, how can I use the ds_priority?
 

Kezarus

Endless Game Maker
@vdweller, yes, ds_prior seems to be "the tool for the job". But I will have to iterate it just like I do in an open/close list to find if a node is on a list or in another.

To pop the min/max results, ok! I can understand that. (yey! \o/) But I will have to run throughout the list to find if the cell is on open/close and that is slow.

Gonna try to look at the wiki pseudocode again (I based my code on that) and see what I can figure out. What I get is that my "lookup accelerators" are dragging me down.

Thanks again, mate! =]
 

Padouk

Member
Ahoy @Kezarus, I hope I didn't induce you in error by over simplifying my drawings yesterday
I was just introducing the Finer / Coarser reality.
Encouraging you to finetune your A* Algorithm for short paths. No cache, no fuss, just plain old cpu optimized A*. Keep up the good work on that you are on the right track for success.

Run your stress test on 500 instances running 8 tiles away.

For an RPG, I still believe your patrols should follow predefined paths (and you can refine those for local collision using your short path optimized A*).


--
For longer path: consider a second algorithm slightly less CPU instensive and slightly more Memory driven with cache and such.
--
If you don't want / can't use pre-defined path, than you need to manage a Coarser grid.
global.grid_fine // size width, height
global.grid_coarse //size width/8, height/8

Theta* : Minor improvment over A* using line of sight optimization. Instead of resolving the parent node, you try to resolve the grandparents in a linear way.
The hope is to use a straight line to eventually hit cached paths.
I personnaly don't see the value but you might want to read on it...


A*: yes you can use A* on averaged grid (as if you were scaling down an image, and applying the same A* algorithm)
As soon as you do that, you need to to account for directional weight (just like you would do if you wanted to account for wind or water movement)
PathFind shouldn't be dependant on a grid.. so you can hotswap it for another one.function Pathfind(grid, iniX, iniY, endX, endY)
PathFindScore must account for direction function PathfindGetScore(wx, wy, direction)

Code:
global.grid = your grid
global.grid_coarse = scaled down version of your grid with averaged weights. + Flood fill algorithm to find the connection with neighbours

PathFindScore(global.grid_coarse, indX/8, indY/8, endX/8, endY/8) //for long runs
PathFindScore(global.grid, indX, indY, endX, endY) //for short runs.
1608576396720.png

--
HPA* use pre-determined entries for each regions.
You still only have 1 weight per region + 4 additional connectors.
The PathFinding is equivalent to the A* in all aspect, except you need to keep 4 "yes gates" bit with coordinates
This one is usually easy to understand / implement since you basically reuse your A* implementation, adapting it to support the gates.
Your path will look like this
1608574786170.png

--
Dijkstra use the graph theory and store weight per-edge instead of per-tiles.
Meaning you need 4 (to 8 time) weight per region depending on implementation..
This one has a bigger memory footprint, so it's usually recommended for coarser grids.
Since there's no traversal position, your path usually follow the edges a little bit better.
The cons here is you will need to learn and implement a completly different path finding solution for the long run.
1608576800789.png
 

Attachments

Last edited:

Director_X

Member
Or.....if pathfinding is not 100% critical, you could skip all the A* code, and simply use a 1 line code in the step event:

GML:
mp_potential_step(my_target.x, my_target.y, speed, false);
If the step event is too heavy for the system, then you could throttle it further via a slower but self-looped alarm[0] = 30 event instead.

😁
 

Kezarus

Endless Game Maker
Ahoy @Kezarus, I hope I didn't induce you in error by over simplifying my drawings yesterday
On the contrary! It was I that coudn't wrap my head around it. I'm starting to comprehend it and your drawings are helping me a LOT!

Keep up the good work on that you are on the right track for success.
Thanks to all of the good people here. =]

For an RPG, I still believe your patrols should follow predefined paths (and you can refine those for local collision using your short path optimized A*).
Yeeeeahhhhh, about that... it's a very random experience. Towns will cease to exist and will appear. Troops will chase one another. I could do that on GM 1.4 on a 100x100 map with no lag at all on a commercial game. It's baffling to me that it's that difficult on GM 2.3. o_Ô


About the amazing explanations, hmmmm, I'm thinking I got the hang on this... there are a couple of specific problems:
  • My map is not blocked ever, troops can travel even by water. I think that could make the gates impossible, isn't it?
  • On a coarse grid, the final points will be at the center of the grid? For example on a 1x1 coarse corresponding to 8x8 finer we will have a point that is in the middle like 4,4, right?

A priority list is precisely the data structure you need for this job. You DON'T need any other data structures, no maps, no arrays, no lists...trust me on that! Any required data, like a node's parent during pathfinding, can be stored in a node's properties, along with its neighbors, terrain cost, coordinates, which group it belongs to (open or closed) etc. Take a look at the simplest, bare bones A* pseudocode (I repeat, pseudocode, not implementations) to figure out the bare minimum you have to do to make it work.
Ok, I trust you, I'm just trying to understand. 😁 I can put the nodes (that are arrays indexed by enums now) in a prior_list. The thing is that I don't know how could I verify if a node is on that prior_list or not. It doesn't give me the functions to iterate over it. I could easily convert what I made to use just a list and have an open/close attribute but this is a bit too slow to iterate over as I already do that at the beginning of my function. I'm really really sorry if I'm not understanding something basic. But I spent the day reading papers and the GM Manual. I even got another pseudocode to read and I'm kinda doing exactly that. o_Ô

My job shift just ended, I'm gonna tackle the algo right now.
 

vdweller

Member
Ok, I trust you, I'm just trying to understand. 😁 I can put the nodes (that are arrays indexed by enums now) in a prior_list. The thing is that I don't know how could I verify if a node is on that prior_list or not. It doesn't give me the functions to iterate over it. I could easily convert what I made to use just a list and have an open/close attribute but this is a bit too slow to iterate over as I already do that at the beginning of my function. I'm really really sorry if I'm not understanding something basic. But I spent the day reading papers and the GM Manual. I even got another pseudocode to read and I'm kinda doing exactly that. o_Ô
Bro...it's simple. Add a property to each node that indicates what group ("list") it belongs to. Name it whatever you want to, it doesn't matter, let's call it "group" here. Okay? Like, each node has x/y coordinates and various other properties, let's add this one too and initialize it to -1.

Suppose that we arbitrarily define the number 1 as a node state of being "open" and 0 as a node state of being "closed". So if for a given node n we read n.group and it returns 0, it is in the "closed" group. If n.group returns 1, it is in the "open" group. If it returns any other value, it is neither in the "open" or the "closed" group. See? It's like we "flag" any node as being in the open, closed, or neither state!

Alright so the algorithm runs and the first thing we do is add the start node to the ds_priority (let's call it plist_open) with an f score of zero and a parent of "no parent" (I used -1 IIRC).

So, while the size of plist_open is > 0 ...

Grab the node with the lowest f score (this will be the start node in the first iteration). Let's name this node node_current

(Do checks for goal etc, you know the drill)

For each neighbor of this guy (let's call each neighbor simply node)...

GML:
If node is in the "closed" group { => Pay attention here! Essentialy you read the node.group property and check if it's flagged as "closed" (in this example -> if node.group==0)

   continue;

} else {

    If the node is in the "open" group { =>Similarly, if node.group==1

        Do stuff with the node as per the algorithm (look up ds_priority_change_priority(), you'll prob need it here IIRC)

    } else {

       Also do stuff with the node as per the algorithm

    }

}
When you add a node to the plist_open priority queue, you change its group flag to 1 to indicate it's in the "open" group. Similarly, any time you retrieve the lowest node from the priority queue, you then have to "put it to the closed list", this merely means in our case that you change its flag from 1 (open) to 0 (closed).

Hope this helps!
 

Padouk

Member
My map is not blocked ever, troops can travel even by water. I think that could make the gates impossible, isn't it?
Never blocked is key here. That's what I tough in the first place and that's why I was talking about A* AVG instead of HPA*.
Not that your gates are impossible... they would simply always be open.. becoming useless.
You can drop that part from your brain and remove some complexity to save a bit.

On a coarse grid, the final points will be at the center of the grid? For example on a 1x1 coarse corresponding to 8x8 finer we will have a point that is in the middle like 4,4, right?
Yes / No / Not important.

On the finer grid, the intermediate point can be any point in the next region ... You know nothing about that next region (by design you averaged it's complexity).
Gate coordinate (0,4), Center (4,4), Closest Edge (0,y), Those are all viable intermediate point and they are all subject to different Breaking Edge cases.


I'm lazy... And I often go with the easiest solution possible...

I've already harcoded 8 in my mind... And your are trying to get your A* to work well for 8 tiles... How about you go 8 tiles on whatever direction the next zone is...
Here we have the coarse A* dotted. and the fine A* 8 tiles away in the right direction.

You'll have to refresh you A* from time to time anyway so on the long run the path would look smooth.
1608583762168.png
GML:
coarsePath = FindPath(coarse_grid, incX/8, incY/8, endX/8, endY/8);

if coarsePath length is 0
  //You've reached the right zone... it's time to look for the exact destination
  finer_endX = endX;
  finer_endY = endY;
else if coarsePath[1] is north
  //You just need a path into your next zone.. Any arbitraty path really... Fat chances this path will be a straight line anyway
  finer_endX = incX
  finer_endY = incY - 8
   ...

finePath = FindPath(fine_grid, incX, incY, finer_endX, finer_endY)
Using that approach you are less subject to breaking cases near the edge of each regions

You can also use the grand parent's center to smooth things up for diagonals. that would violate my 8-tiles-longest-path rules but that's probably an even easier solution to adopt.
1608584872470.png
GML:
coarsePath = FindPath(coarse_grid, incX/8, incY/8, endX/8, endY/8);

if coarsePath length is 0 OR 1
  //You've reached the right zone... it's time to look for the exact destination
  finer_endX = endX;
  finer_endY = endY;
else
  finer_endX = coarsePath[2].x*8 + 4;
  finer_endY = coarsePath[2].y*8 + 4;
   ...

finePath = FindPath(fine_grid, incX, incY, finer_endX, finer_endY)
 
Last edited:

Kezarus

Endless Game Maker
@vdweller, ok I will point exactly where my problem is with the solution that you proposed.

Below I have the code to add Neighbors. I need to know if the neighbor, not the current (that one is easy), is on close or open list. I cannot iterate over a ds_priority and I understood that all the added nodes will be on the ds_priority marked with a group property (open=1, closed=0, nothing=-1). How can I fish an already added node from a ds_priority? Unless you are telling me that I should add the neighbor without that check. If so, how can the algorithm could make a better path if it took a wrong turn? It will be duplicated too.

I comprehend all the other places that I have to change, but this one is challenging for me.

GML:
            //ADD NEIGHBORS
            ds_list_clear(lstNeighbors);
            ds_list_add(lstNeighbors,
                            PathfindCoordToNumber(pointNowPosX+1, pointNowPosY+0),
                            PathfindCoordToNumber(pointNowPosX-1, pointNowPosY+0),
                            PathfindCoordToNumber(pointNowPosX+0, pointNowPosY+1),
                            PathfindCoordToNumber(pointNowPosX+0, pointNowPosY-1));
    
            var wx, wy, pointNeighbor, wNumb;
            for( var i=0; i<ds_list_size(lstNeighbors); i++ ){
                //VERIFY BOUNDARIES
                wNumb = lstNeighbors[| i];
                wx = PathfindNumberToX(wNumb);
                wy = PathfindNumberToY(wNumb);
                if( wx < 0 ){ continue; }
                if( wy < 0 ){ continue; }
                if( wx >= mapWidth ){ continue; }
                if( wy >= mapHeight ){ continue; }
        
                //DON'T ADD IF ALREADY IN CLOSE LIST
                lookup = PathfindCoordToNumber(wx, wy);
                if( ds_list_find_index(lstCloseLookup, lookup) != -1 ){ <----------------------------- HOW CAN I DO THIS ON A DS_PRIORITY
                    continue;
                }

                //CALCULATE SCORE AND HEURISTIC
                wScore = pointNow[PathpointEnum.Score] + PathfindGetScore(wx, wy);
                wHeuristic = PathfindGetHeuristic(wx, wy, endX, endY);
                
                //DUPLICATE AND PATH TO HERE AND ADD POINT
                wCameFrom = array_duplicate(pointNow[PathpointEnum.CameFrom]);
                array_push(wCameFrom, PathfindCoordToNumber(pointNowPosX, pointNowPosY));
                
                //CREATE PATH POINT
                pointNeighbor = PathpointCreate(wx, wy, wScore, wHeuristic, wCameFrom);

                //IF NOT IN OPEN LIST
                var indexInOpen = PathfindSearchPointIndex(lstOpenLookup, wx, wy); <----------------------------- HOW CAN I DO THIS ON A DS_PRIORITY
                if( indexInOpen == -1 ){
                    //ADD TO OPEN
                    ds_list_add(lstOpen, pointNeighbor);
                    ds_list_add(lstOpenLookup, PathfindCoordToNumber(wx, wy));
                }else{
                    //FIND THE OPEN SCORE
                    var pointInOpen = lstOpen[| indexInOpen];
            
                    //IS THIS PATH SHORTER?
                    if( pointInOpen[PathpointEnum.Value] > pointNeighbor[PathpointEnum.Value] ){
                        //SUBSTITUTE
                        lstOpen[| indexInOpen] = pointNeighbor;
                    }
                }
            } //END OF FOR NEIGHBORS
 

Kezarus

Endless Game Maker
@Padouk, yeah!! Got it! Brilliant! \o/

I think I can do some implementation that can ease and automate some processes.
  1. Create the coarse grid with a 10th of the original, average each cell to the sum of averages of each 10x10 group on the finer grid;
  2. On Pathfind
    1. if current distance equal or less than 10 run the regular pathfind on the finer grid, mark point as finer
    2. if current distance is greater than 10, run the pathfind on the coarse grid, mark point as coarse
  3. On Troop move
    1. If the point is marked as finer, business as usual
    2. If not, run the pathfind again to get the best path
That way it stays as correct as possible. You see any problems with that idea?

Thanks a ton! =D
 

Padouk

Member
Sound fair. I'll stop following this thread, spent too much time in it ;P Poke me when you have results!
Just one last time.. I'll still come back to my first comment encouraging you to use predefined paths ;) And I would encourage you to return a path, instead of an array of custom struct Pathpoint. It will be easier for you to follow the path using default's from gms.
 
Hey mate :), sounds like a flow field or dijkstra would suit your needs better :)
I think ive shown you my pathfinder before that uses this method and bitshifting optimizations to get optimal speeds for GML.
Someone has pointed out a weird bug that exists on my final release version that DOESNT exist in the debug version I posted in

I might get arround to fixing whatever that issue is today :)
 
@James222, it's been a while! I just finished the coarse grid that Padouk told me about. Hahaha.

Nice, I would love to read and understand your code.

Thanks a lot, mate! =]

Allrighty!!!!
So I took my older version of my pathfinder and cleaned the code up a bit, It shouldnt have any bugs :)
Fastest GM Pathfinder EVER Reupload Mega

heres a screenshot with 500+ units, it can easily handle 5000+ units with minimal loss to performance, its designed to scale up and perform better as more units are added :)
1.PNG
As you can see it took a total of 4.71 milliseconds to generate the pathing grid and 39.4 milliseconds to calculate all the paths for a combined TOTAL time of 44.11 milliseconds.
this algorithm will always return the most optimal path, the stats of the above test are:
Room_Size = 3264x3264
Cell_Size = 32

and just to really hammer the scaling home, here it is with 3000+ units:
2.PNG
Again you can see it took a total of 4.69 milliseconds to generate the pathing grid and 194.49 milliseconds to calculate all the paths for a combined TOTAL time of 199.18 milliseconds.



let me know how you go, theres a few things to note, the cells can only be a power of 2, ie. cell sizes = 2,4,8,16,32,64,128,256,512 ect you cannot have a cell size of 22 for example.

in the macros you will find a few details like
WallID: this is the number used to identify walls in the grid
CellSize: Self explanatory again can only use a power of 2!
CellSizeHalf: Just half of the above cell size

BitshiftSize: this number is the bitshift size of your cell size, for example if your cell size is 32, this value would be 5, 16 would be 4 IE
CELL SIZE : BITSHIFTNUMBER
256 : 8
128 : 7
64 : 6
32 : 5
16 : 4
8 : 3
4 : 2
2 : 1


Ect. Inbox me anytime :)
 
Last edited:

GMWolf

aka fel666
Have you checked that the code is actually faster with the priority list?
Usually it's used with something like a fib heap thats fast to update priorities, but GM requires you to remove and reinsert.
 

Kezarus

Endless Game Maker
I managed to change my code to use priority lists, but now I have a massive memory leak.

I pinpoint it to be on the Pathfind function and the ds_priority is beign destroyed for sure. It seems that the GC is not destroying arrays. Aaaaargh...

I will post the code as soon as I can, but me and @Rui Rosário was trying to see it yesterday if there was something wrong and we found nothing.
 

Kezarus

Endless Game Maker
So this is the code. I'm really sorry to just place it here, I would make a single project just to run it, but I'm in the middle of a workshift.

I tried to guess how could I update the values and I got an idea of making a 2d array to do that and a priority list.

I'm still making improvements to the code and I will make that 2d array a 1d array using (x + y + width) technique. Not to mention the coarse grid that @Padouk mentioned and I was working on that too (but that's another code).

Thanks a lot for your support, everyone!

GML:
//THE ENUM
enum PathpointEnum{
    CellX = 0,
    CellY = 1,
    Score = 2,
    Heuristic = 3,
    Value = 4,
    CameFrom = 5,
    InOpen = 6 //Open=1, Close=0
}

function PathpointCreate(_cellX, _cellY, _score, _heuristic, _cameFrom, _inOpen){
    return [_cellX, _cellY, _score, _heuristic, _score + _heuristic, _cameFrom, _inOpen];
}


//https://en.wikipedia.org/wiki/A*_search_algorithm
function Pathfind(iniX, iniY, endX, endY){

    //PERFORMANCE
    var measurePerformance = false;
    var iterations = 0;
    if( measurePerformance ){
        var timerIni = get_timer();
    }

    var Open = 1;
    var Close = 0;
    var mapWidth = ds_grid_width(global.grdBiome);
    var mapHeight = ds_grid_height(global.grdBiome);
    
    //CHANGE COORD TO CELL
    iniX = clamp(iniX div CELL_SIZE, 0, mapWidth-1);
    iniY = clamp(iniY div CELL_SIZE, 0, mapHeight-1);
    endX = clamp(endX div CELL_SIZE, 0, mapWidth-1);
    endY = clamp(endY div CELL_SIZE, 0, mapHeight-1);
    
    //MAX DISTANCE
    var distMin = 1;
    var distMax = 25;
    var distNow = point_distance(iniX, iniY, endX, endY);
    if( distNow <= distMin ){
        //IF YOU WANT TO RUN A MIN PATH BIGGER THAN ONE,
        //JUST REMEMBER THAT IT CHECKS IT'S SPEED FOR EACH NODE
        return [[endX, endY]];
    }else if( distNow > distMax ){
        var dir = point_direction(iniX, iniY, endX, endY);
        endX = floor(iniX + lengthdir_x(distMax, dir));
        endY = floor(iniY + lengthdir_y(distMax, dir));
    }
    
    //PREPARING VARIABLES
    var result = [];
    var lstOpen = ds_priority_create();
    var arrOpenClose = array_2d(mapWidth, mapHeight, 0);
    var wScore = 1;
    var wHeuristic = 0;
    var wCameFrom = [];

    //FIRST NODE
    var pointNow = PathpointCreate(iniX, iniY, wScore, wHeuristic, [-1, -1], Open);
    ds_priority_add(lstOpen, pointNow, wScore);
    arrOpenClose[iniX][iniY] = pointNow;

    //REAL PATHFINDING
    var pointNowPosX, pointNowPosY, arrLookup;
    while( !ds_priority_empty(lstOpen) ){
        iterations++;
        
        //FIND SMALLEST SCORE IN OPEN LIST
        pointNow = ds_priority_delete_min(lstOpen);
        
        pointNowPosX = pointNow[PathpointEnum.CellX]; //THIS IS THE CURRENT NODE X
        pointNowPosY = pointNow[PathpointEnum.CellY]; //THIS IS THE CURRENT NODE Y
        
        //CHECK IF ARRIVED
        if( pointNowPosX == endX && pointNowPosY == endY ){
            //CONSTRUCT THE RETURN
            var coord, wwx = pointNowPosX, wwy = pointNowPosY;
            result = [];
            while( wwx != -1 ){
                array_push(result, [wwx, wwy]);
                
                coord = arrOpenClose[wwx][wwy];
                wwx = coord[PathpointEnum.CameFrom][0];
                wwy = coord[PathpointEnum.CameFrom][1];
            }
            
            break; //BREAK THE LOOP
        }else{
            //REMOVE FROM OPEN LIST AND ADD TO CLOSE LIST
            pointNow[PathpointEnum.InOpen] = Close;
            arrOpenClose[pointNowPosX][pointNowPosY] = pointNow;
            
            //ADD NEIGHBORS
            var Neighbors = [
                [pointNowPosX+1, pointNowPosY+0],
                [pointNowPosX-1, pointNowPosY+0],
                [pointNowPosX+0, pointNowPosY+1],
                [pointNowPosX+0, pointNowPosY-1]
            ];
    
            var wx, wy, pointNeighbor, neighbor;
            for( var i=0; i<array_length(Neighbors); i++ ){
                //VERIFY BOUNDARIES
                neighbor = Neighbors[i];
                wx = neighbor[0];
                wy = neighbor[1];
                if( wx < 0 ){ continue; }
                if( wy < 0 ){ continue; }
                if( wx >= mapWidth ){ continue; }
                if( wy >= mapHeight ){ continue; }
        
                //DON'T ADD IF ALREADY IN CLOSE LIST
                arrLookup = arrOpenClose[wx][wy];
                if( arrLookup != 0 ){
                    if( arrLookup[PathpointEnum.InOpen] == Close ){
                        continue;
                    }
                }

                //CALCULATE SCORE AND HEURISTIC
                wScore = pointNow[PathpointEnum.Score] + PathfindGetScore(wx, wy);
                wHeuristic = PathfindGetHeuristic(wx, wy, endX, endY);
                
                //TELL WHERE YOU CAME FROM
                wCameFrom = [pointNowPosX, pointNowPosY];
                
                //CREATE PATH POINT
                pointNeighbor = PathpointCreate(wx, wy, wScore, wHeuristic, wCameFrom, Open);

                //IF NOT IN OPEN LIST
                if( arrLookup == 0 || arrLookup[PathpointEnum.InOpen] != Open ){
                    //ADD TO OPEN
                    ds_priority_add(lstOpen, pointNeighbor, wScore+wHeuristic);
                    arrOpenClose[wx][wy] = pointNeighbor;
                }else{
                    //IS THIS PATH SHORTER?
                    if( arrLookup[PathpointEnum.Value] > pointNeighbor[PathpointEnum.Value] ){
                        //SUBSTITUTE
                        ds_priority_add(lstOpen, pointNeighbor, wScore+wHeuristic);
                        arrOpenClose[wx][wy] = pointNeighbor;
                    }
                }
            } //END OF FOR NEIGHBORS
        } //END OF IF ARRIVED
    } //END OF WHILE
    
    ds_priority_clear(lstOpen); //???
    ds_priority_destroy(lstOpen);
    lstOpen = -1;
array_2d_destroy(arrOpenClose);
    arrOpenClose = 0;
    pointNow = 0;
    wCameFrom = 0;
    neighbor = 0;
    Neighbors = 0;
    coord = 0;
    

    if(measurePerformance){
        var timerEnd = get_timer();
        alert("iterations", iterations);
        alert("elapsed time: "+string((timerEnd-timerIni)/1000)+"ms");
    }

    return result;
}

function PathfindCoordToNumber(wx, wy){
    return wx+(wy*10000);
}

function PathfindNumberToX(wNumber){
    return wNumber mod 10000;
}

function PathfindNumberToY(wNumber){
    return wNumber div 10000;
}

function PathfindGetScore(wx, wy){
    switch( global.grdBiome[# wx, wy] ){
        case MapGenBiomesEnum.Void: return 1; break;
        case MapGenBiomesEnum.Ocean: return 5; break;
        case MapGenBiomesEnum.River: return 4; break;
        
        case MapGenBiomesEnum.Grass:
        case MapGenBiomesEnum.Desert: return 1; break;
        
        case MapGenBiomesEnum.ForestBoreal:
        case MapGenBiomesEnum.ForestTemperate:
        case MapGenBiomesEnum.ForestTropical: return 2; break;
        
        case MapGenBiomesEnum.Alpine:
        case MapGenBiomesEnum.Mountain:
        case MapGenBiomesEnum.Mesa: return 3; break;
        
        default: return 1;
    }
}

//http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-distance
function PathfindGetHeuristic(nowX, nowY, endX, endY){
    var deltaX = abs(nowX - endX);
    var deltaY = abs(nowY - endY);
    var factor = 1.75; //215
    return factor*(deltaX+deltaY);
}

function array_2d(width, height, value){
    var array2;
    for (var i=width-1; i>=0; i--) {
        array2[i] = array_create(height, value);
    }

    return array2;
}
 
Top