Asset - Scripts Fast Optimized GM Pathfinding *FREE* By James222

James222

Member
Hi everyone!

So for the past few months I have been having a little competition with my friend to write a fast simple pathfinder that can work with multiple units while always returning the optimal path.
after a lot of trial and error I have finally simplified my work down to this tiny asset for the GM community :), The asset uses my custom path finding engine which uses a pre unrolled Dijkstra based flood fill.
it is optimized with early exits and is really easy to use. 100% pure GML :)

the grid object simply takes one script in its create event
scr_OPF_INIT_Grid();

with usage being as simple as
scr_OPF_GenerateSpider_EarlyExit(mouse_x,mouse_y,global.PathfindingGrid,obj_block,5,obj_Unit);

and then to make a unit move to the goal
scr_OPF_GetPath_Helper();

simple :)
very easy to modify also and mostly commented code :)

feel free to check out this thread where I have been posting results and comparisons

YYG Marketplace link pending (asset submitted)
DOWNLOAD GMZ - GMS 1.4.999

capable of 100x100 test map with all its obstacles, here are the results!
Grid gen: 0.89 milliseconds, Path: 0.33 milliseconds for a total of 1.22 milliseconds :)



and the same with 1002 units.
4.37 milliseconds for the grid and 147.97 for the pathing total: 152.34 milliseconds


The speed of it crushes Game makers inbuilt pathfinding speed and to the best of my knowledge beating all other GM pathfinding DLL's in raw speed,
getting comparable results to a direct C++ Flood fill implementation... in pure GML :).

DOWNLOAD GMZ - GMS 1.4.999


Enjoy guys and any questions feel free to ask :)
James
 
Last edited:

James222

Member
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 :)
 

WilloX

Member
Pretty insane how fast it stays even with that scale. I imported it to 2.3+ as well and with the mentioned semicolons added it works (almost) perfect (i had an error one time "maleformed variable..." but i couldnt replicate it since).

I was working on a super simple implementation of A* that could be used in all my future projects (only one pathfinding script that takes ([start_x, start_y], [end_x, end_y], underlying grid, max_step_length) and returns the path as an array - it doesnt even need an specified object) buuut it scaled terribly with small lags even at a grid of 64x64.

Your version seems really advanced in comparison and it might take a while for me to grasp all components. But it seems to be worth the effort.
 

James222

Member
Pretty insane how fast it stays even with that scale. I imported it to 2.3+ as well and with the mentioned semicolons added it works (almost) perfect (i had an error one time "maleformed variable..." but i couldnt replicate it since).

I was working on a super simple implementation of A* that could be used in all my future projects (only one pathfinding script that takes ([start_x, start_y], [end_x, end_y], underlying grid, max_step_length) and returns the path as an array - it doesnt even need an specified object) buuut it scaled terribly with small lags even at a grid of 64x64.

Your version seems really advanced in comparison and it might take a while for me to grasp all components. But it seems to be worth the effort.
Awesome mate :) hope it works well for ya. Send me a dm any time you need help and ill ensure we can implement it in your projects :) fortunately you only need to know how to use 2 or 3 scripts which are called similarly to the mp functions :)
 

WilloX

Member
Yeah the floodfill method is the way to go. I changed some parts and made it more modular (only one script to make importing into projects easier) and got it to support weighted grids (here visualized as "the darker the tile - the bigger the cost")Screenshot (3).png
Really lucky to find your solution - i probably would have given up on pathfinding related game ideas otherwise.
Thanks a lot.
 

James222

Member
Yeah the floodfill method is the way to go. I changed some parts and made it more modular (only one script to make importing into projects easier) and got it to support weighted grids (here visualized as "the darker the tile - the bigger the cost")View attachment 38072
Really lucky to find your solution - i probably would have given up on pathfinding related game ideas otherwise.
Thanks a lot.
Oh man thats AWESOME this is what I wanted people to do with it :) take it and modify it to their needs. Biggest smile on my face right now :). How does the weighted grids effect the performance out of curiousity?
 

WilloX

Member
It's considerably slower right now (but only by a linar factor of 6~8) on equal grid size. I guess that is because it has to look up each weight for every tile several times and it isn't optimized. As far as i have tested it also slows faster now with more units - but i dont yet know why.

It's good enough for me right now and will be a great asset to have for game jams with libraries allowed.
 

James222

Member
It's considerably slower right now (but only by a linar factor of 6~8) on equal grid size. I guess that is because it has to look up each weight for every tile several times and it isn't optimized. As far as i have tested it also slows faster now with more units - but i dont yet know why.

It's good enough for me right now and will be a great asset to have for game jams with libraries allowed.
Feel free to send me the modified source. My job basically revolves arround making code run as fast as possible now days :)
 

James222

Member
Cool - i commented it a bit and loaded it to gitlab (https://gitlab.com/NikifFleser/ptf_2.1).
But it's 2.3 so not compatible with 1.4 anymore...
if your running in YYC mode replace any +1 and -1 with this:
instead of:

GML:
//LEFT
    counter_add = counter + grid[# goalx - 1, goaly]
    if f_grid[# goalx - 1, goaly] > counter_add
        {
        f_grid[# goalx - 1, goaly] = counter_add
        var leftside = f_grid[# goalx - 2, goaly] > counter_add + grid[# goalx - 2, goaly];
        var lefttop = f_grid[# goalx - 1, goaly - 1] > counter_add + grid[# goalx - 1, goaly - 1];
        var leftbot = f_grid[# goalx - 1, goaly + 1] > counter_add + grid[# goalx - 1, goaly + 1];
use this:

GML:
//LEFT
// IN YYC mode, this creates between a 50% to 120% performance increase,
//Howver in VM MODE this causes roughly a 35% slowdown
var goalxN1 = --goalx;
++goalx;
////
    counter_add = counter + grid[# goalxN1, goaly]
    if f_grid[# goalxN1, goaly] > counter_add

        {
        // IN YYC mode, this creates between a 50% to 120% performance increase,
        //Howver in VM MODE this causes roughly a 35% slowdown
        var goalyN1 = --goaly;
        var goalyP1 = ++goaly;
        ++goalyP1;
        var goalxN2 = --goalyN1
        ++goalyN1
        /////    

        f_grid[# goalxN1, goaly] = counter_add
        var leftside = f_grid[# goalx - 2, goaly] > counter_add + grid[# goalxN2, goaly];
        var lefttop = f_grid[# goalxN1, goalyN1] > counter_add + grid[# goalxN1, goalyN1];
        var leftbot = f_grid[# goalxN1, goalyP1] > counter_add + grid[# goalxN1, goalyP1];


and here is a simple speed test, just chuck it into a new object on a new project in the create event and run in YYC mode, tested on GMS 1.4.9999
Results avg over 1,000,000 iterations: (MICROSECONDS) Speed Normal: 59190 ---- Speed Optimized: 40240
Code for test:
GML:
var t_start1=get_timer();

var xx = 15;
var xx1 = 0;
var xx2 = 0;

for (i = 0; i < 1000000; ++i)
{  
    xx2 = xx + 1;
    xx1 = xx - 1;
}


var t_end1=get_timer();
//TIMER END
var microseconds1=t_end1-t_start1;
var milliseconds1 = microseconds1 / 1000;


var t_start2=get_timer();

var xx = 15;
var xx1 = 0;
var xx2 = 0;

for (i = 0; i < 1000000; ++i)
{
    xx1 = --xx;
    xx2 = ++xx;
    ++xx2;  
}


var t_end2=get_timer();
//TIMER END
var microseconds2=t_end2-t_start2;
var milliseconds2 = microseconds2 / 1000;

show_message("(MICROSECONDS)  Speed Normal: " + string(microseconds1) + " ---- " + "Speed Optimized: " + string(microseconds2));
this is why I had that funky odd looking code in there, it aint pretty but its much faster and does the same thing.
Let me know what you think :)
 

WilloX

Member
Cool. I thought that there was an optimisation behind it but as i customized it more it just got lost in the rewrite process.
 
Top