Does anybody have a fast implementation of A* pathfinding?

D

DirectOrder

Guest
The built-in pathfinding is nice, but very limited (can't move through diagonally blocked paths, can't weight movement, etc). So I'll just write my own implementation of A*, right? Well I did. And it works. But it's sloooow. So I figured maybe these new structs that I used to track nodes are super slow, so I went online to find other people's implementations. I found a tutorial on-line (here) that is much more optimized than mine (and uses maps instead of structs) so I tried that one out. Good news: It's like 4-5x faster than mine. Yay! Bad news: It's still like 15-20x slower than the built-in pathfinding from my calculations. Maybe even slower. :oops:

I don't know how YoYo has implemented their pathfinding, but it is FAST! Of course it's also strangely limited. Here's a post from someone else running into the same problem as me: link

I see this thrown around a lot here: "Well if the built-in pathfinding isn't working for you, just write your own!" I'd love to. And I did. But I've tried several different implementations of A*, and they don't even hold a candle to the built-in pathfinding (performance-wise). And I need that performance. With the algorithm I wrote, my player character takes 3-4 real-time seconds to calculate some longer paths. And I have 70-100 enemies that need to do the same. The built-in pathfinding does ALL of that in less than a second.

Does anybody have a FAST implementation of A* they wouldn't mind sharing? Or has anybody else run into this and figured out why their A* implementations were so slow? I might just be missing something here. Please tell me I'm just missing something here lol

Thank you very much for any help you can provide!
 

Yal

🐧 *penguin noises*
GMC Elder
There's a bunch of different details that could be worth considering:
  • Nested loops get really slow, so try to minimize loops over 2D structures (e.g. looping over the entire room to check for something)
  • Don't use collision checking functions to check for cell validity, they're slow. Definitely don't use loops over all instances (with, etc). If possible, create a grid / 2D array of collision data ahead of time and check that instead, and reuse it instead of recreating it every time. (All enemies could use the same collision data, for instance, and if all your obstacles are static, you could just have a global collision data grid that you never destroy/recreate)
  • Don't recompute paths for realtime objects every step, do it every second or so. You can get much smoother CPU usage distribution if you set the alarm used for this to a random range instead of all objects created the same step checking in unison.
  • Nothing's stopping you from using GM's pathfinding to get a "general idea" path and then manually process it a bit (e.g. do a custom A* on every 5x5 tile region to find the least-cost path).
  • If there's no obstacle between two points (e.g. collision_line check) you could just move directly towards the target without having to pathfind at all.
 

GMWolf

aka fel666
A while back I wrote a game for a jam with pathfinding, and even though i came up with a fairly efficient solution for GML, I was still very disappointed by the performance compared to my previous java implementations. It was a good 50-100x slower. Barely usable for what I was doing.
The unfortunate truth is that all the dynamic typing of GML makes for some really inifecient c++ code that's very hard for the compiler to optimize.

I think with 2.3 it should be possible to improve on my previous implementation, but I don't forsee it ever getting close to the built in implemention written in native code.

If you need that performance, I would recommend you write an external library for it in native code.

Other tricks involve spreading the calculations over multiple steps.
Path finding is a naturally iterative process. So you can have a function to carry out one step of the algorithm, and then determine how many steps you can run per frame.
If you need the results immediately however you are in bad shape.


If you have multiple agents pathfinding from many sources to the same point (a tower defense game for example), then a* is not the most efficient. A better solution is to use Dijkstra's to make a flowfield that represents paths from any source to a destination.

It's actually these sorts of things that make GM hard to use for some projects. As much as we like to say that PCs are powerful, and GML is fast enough for game logic, that's really only true for some games. The truth is there is a reason a lot of games are written in native code, and that's an area I think GM could improve in.
 
D

DirectOrder

Guest
Thank you all for the replies!

Thanks for posting this. I had found this thread earlier in my searching, but I had forgotten about it. Now that I look at it with fresh eyes, there's some really good info in there.


There's a bunch of different details that could be worth considering:
  • (1) Nested loops get really slow, so try to minimize loops over 2D structures (e.g. looping over the entire room to check for something)
  • (2) Don't use collision checking functions to check for cell validity, they're slow. Definitely don't use loops over all instances (with, etc). If possible, create a grid / 2D array of collision data ahead of time and check that instead, and reuse it instead of recreating it every time. (All enemies could use the same collision data, for instance, and if all your obstacles are static, you could just have a global collision data grid that you never destroy/recreate)
  • (3) Don't recompute paths for realtime objects every step, do it every second or so. You can get much smoother CPU usage distribution if you set the alarm used for this to a random range instead of all objects created the same step checking in unison.
  • (4) Nothing's stopping you from using GM's pathfinding to get a "general idea" path and then manually process it a bit (e.g. do a custom A* on every 5x5 tile region to find the least-cost path).
  • (5) If there's no obstacle between two points (e.g. collision_line check) you could just move directly towards the target without having to pathfind at all.
These are all great points. #1 and #2 I've already taken into account. I do have an array mapped out that I keep and reuse so I don't have to re-build it for each check. #3 is a good point, and I tried using it, but when it takes 500-600 frames to calculate one path, and I have 100 paths to calculate, I don't gain much by spreading them out. I'm still dead in the water. #4 and 5 have been part of my band-aid solution up to this point. I have an extremely simplistic algorithm calculating moves that are very far away just to get the enemies moving in the correct direction, then when they get within a certain range of the target I switch over to the built-in A* (mp_grid) pathfinding, and then when they are very close, I switch over to my custom (and super slow) A* implementation which will allow me to move diagonally. It somewhat works (but not well enough), and it's "hacky" and dirty and inefficient, and made me think there's got to be a better way!


A while back I wrote a game for a jam with pathfinding, and even though i came up with a fairly efficient solution for GML, I was still very disappointed by the performance compared to my previous java implementations. It was a good 50-100x slower. Barely usable for what I was doing.
The unfortunate truth is that all the dynamic typing of GML makes for some really inifecient c++ code that's very hard for the compiler to optimize.

I think with 2.3 it should be possible to improve on my previous implementation, but I don't forsee it ever getting close to the built in implemention written in native code.

If you need that performance, I would recommend you write an external library for it in native code.

Other tricks involve spreading the calculations over multiple steps.
Path finding is a naturally iterative process. So you can have a function to carry out one step of the algorithm, and then determine how many steps you can run per frame.
If you need the results immediately however you are in bad shape.


If you have multiple agents pathfinding from many sources to the same point (a tower defense game for example), then a* is not the most efficient. A better solution is to use Dijkstra's to make a flowfield that represents paths from any source to a destination.

It's actually these sorts of things that make GM hard to use for some projects. As much as we like to say that PCs are powerful, and GML is fast enough for game logic, that's really only true for some games. The truth is there is a reason a lot of games are written in native code, and that's an area I think GM could improve in.
So you've pretty much answered my question of "how did YoYo write such blazing fast pathfinding?"
Answer: They didn't do it in Game Maker!

I'm really frustrated that the built-in pathfinding is crippled in a common use-case (moving diagonally across blocked squares) with no good way to fix it, and implementing your own is 100x slower. It's a bit shocking that they don't have a more robust pathfinding solution built-in when it's such an insanely important part of so many types of games. This is like having a game engine that doesn't have a really good way of displaying graphics on the screen. You'd think that would be a priority. (I know this is hyperbole, but you know what I'm saying...). Like you said, it makes Game Maker....just not a good game maker for certain types (many types?) of games.

I've been leaning towards implementing flow fields, and with your suggestion of it (and everything else I've been able to confirm), I think that has pretty much solidified my decision to move in that direction. It's not an ideal solution, but I really don't see another choice as I'm not advanced enough to write my own extensions.


Thank you all for your helpful responses! I really do appreciate it!
 
Last edited by a moderator:

rytan451

Member
A good idea might be to implement a modified Theta* algorithm on top of GMS2's A* implementation. After all, GMS2's A* returns a path, which you can modify using path functions (it may also be useful to look at mp_grid_get_cell).
 

NightFrost

Member
Another method to speed up A* is hierarchical pathfinding. Simply put, you divide your grid into sectors (left image) and a higher hierarchy graph describes connections between these sectors (right image).


You'd have multiple graphs generated that each describes connections inside a sector, and the 2nd hierarchy of connections between sectors. As A* is essentially graph traversal it can handle this, as a grid is just an edge case where the graph describes a grid. GMS can't though as it expects to be working on that edge case.

When you have to pathfind from point S(tart) to point G(oal), you first pathfind on the top hierarchy, and for actual movement, A* pathfind only one sector at a time. For super-cheaty approach you precalculate all the paths between all exits within a sector, so the only runtime pathfinding you do is from S to appropriate exit, and from final exit to G. Although this route means that 1) same paths are always taken so movement may seem as on rails and 2) any need for dynamic avoidance requires extra work.
 
D

DirectOrder

Guest
...but the built-in pathfinding does allow moving diagonally??
View attachment 32404

It allows diagonal movement when moving between empty spaces (in other words, 8-directional movement instead of 4-directional), but not through diagonal breaks between obstacles (in other words, from one empty space to another diagonally adjacent empty space).

allowdiag = true would allow the enemy to take diagonal steps towards point c, but it will not allow the enemy to move up-right diagonally across the break in the wall from the empty square on one side to the diagonally adjacent empty square on the other. It would only see a path that takes it all the way around the wall to get to point g.

e = enemy
g = goal
X = wall

--------------------
--------X-----------
--------X-----------
--c-----X---g------
-----e----X--------
----------X---------
----------X---------
--------------------
 
Last edited by a moderator:
D

DirectOrder

Guest
Thank you NightFrost! I'm not sure I would be able to implement that (lack of skill, not lack of effectiveness of the solution), but I'll give it some thought.
 
A while back I wrote a game for a jam with pathfinding, and even though i came up with a fairly efficient solution for GML, I was still very disappointed by the performance compared to my previous java implementations. It was a good 50-100x slower. Barely usable for what I was doing.
The unfortunate truth is that all the dynamic typing of GML makes for some really inifecient c++ code that's very hard for the compiler to optimize.
This should be yoyo's only priority right now. Making GML practical to use. Just bite the bullet guys! People aren't going to be satisfied with remaking games from the 1980's forever.

It is not acceptable to expect people to write external libraries just because gml is too slow to do basic tasks.
 

NightFrost

Member
A clarification; I realized I phrased a statement in post above very vaguely. When I said GMS can't handle the pathfinding, I was referring to the upper hierarchy graph. It is not grid-shaped so it cannot be traversed by mp grid as it uses grid-shaped data. The bottom hierarchy sectors however are grids, so mp grid obviously can handle them. In fact if you only need path shapes that mp grid can produce, using it is likely much faster than writing your own A* as pointed out above.

I agree that GML needs a generic A* solution, and while we're at it let's add Dijkstra and breadth-first ("flood fill"). All are based on the same iterative loop method, and I would think would run much faster in C++ than GML-based solution can hope to achieve.
 

GMWolf

aka fel666
This should be yoyo's only priority right now. Making GML practical to use. Just bite the bullet guys! People aren't going to be satisfied with remaking games from the 1980's forever.

It is not acceptable to expect people to write external libraries just because gml is too slow to do basic tasks.
I don't think that's fair.
Yes, a lot of things are made impractical due to GML being slow but the vast majority of games don't need that level of performance.

GM was always geared towards real time action games, that's just how it's general model is designed (with highly decoupled objects and events).
You don't see very many turn based games or RTS games made in GM, I suspect because of the programming model.


I don't think GML can be saved tbh. They are already cross compiling it to C++, and the generated code isn't all that terrible.
What would be great is allowing us to write C/c++ directly in project (no DLLs). This could target every platform, including JavaScript through wasm/emscriptm
 
D

DirectOrder

Guest
I've implemented flow fields and they are doing the trick for me (in combination with A*). They also give a lot of other benefits that I wasn't even aware of which is really nice. And, the main benefit, it's literally thousands of times faster than A*. I was struggling before with A* to get ONE enemy to pathfind on my large maps without slowing the game down to annoying levels. Today I tested the flow field pathfinding with two thousand enemies at once and got no major slow down, and I could probably go higher. :)

I wish GMS had more support for this type of thing though. I don't know how people without a lot of coding experience could work their way through this stuff with how bare-bones the built-in pathfinding is.

Anyway, just wanted to give an update, and suggest flow fields for anybody else that stumbles across this thread with the same issues as me. Thanks for all the help guys!
 

kburkhart84

Firehammer Games
Flow fields seem like they will work best if you have bunches of enemies. In your case you seem to have it going faster even for just one enemy, but as multiple enemies can use the same field(if they have the same goal) you suddenly have massive re-usage and speed gains.

The last time I heard of anything with fields of Vectors was involving simulations and/or particle systems, applying forces to those based on a field of vectors instead of a single vector at a time.
 

NightFrost

Member
I've implemented flow fields
Ah, somehow I had come under the impression that you needed to pathfind to multiple destinations. But yes, if you have a for example dungeon crawl-y setup where many need to pathfind to single point, flow field is in my experience perhaps the fastest method to use. Technically flow field works like breadth-first when it sets up cell distances, using a frontier and a while-loop, so it too should benefit were it implemented as native GML command.

However, here's a few optimizations that can be used with flow field, in case your source material hasn't mentioned them. Firstly, you only need to regenerate the field when the target (usually player) moves to another cell. Otherwise, it remains valid. Second, you don't need to precalculate the direction of the field in every cell before using it. Have a direction array prefilled to -1 and save the direction there when an enemy needs to move and the direction in its cell has not yet been calculated. You can use 1d array as grid storage, using x + y * GridWidth as index. Arrays are faster than DSes and 2d arrays are get deprecated in V2.3.
 

Yal

🐧 *penguin noises*
GMC Elder
Arrays are faster than DSes and 2d arrays are get deprecated in V2.3.
Arrays of arrays will replace them seamlessly (arr[a,c] --> arr[a][c])... the conversion would just be a text replacement (2D arrays already work as arrays of arrays under the hood, subarrays can be different lengths and 2D arrays are not guaranteed to be rectangular unless you initialize every row manually) so there's very little work involved. Speed might be a concern, though, but this already works under the hood, so I think it's just a syntax upgrade (now you don't need to use intermediate variables for every step when you want to reference something deep in a nested structure, but they work the same as in 2.2)
 

NightFrost

Member
Although, in the field of micro-optimizations, 1d array would be better as you could initialize the direction array for say 40x40 flow field by array_create(40 * 40, -1), whereas arrays-in-array would require 41 calls. The array would beed to be reset only whenever flow field changes, so once every few steps on the average if player is moving, so an incidental speedup at best.
 

Yal

🐧 *penguin noises*
GMC Elder
You know, nothing's stopping you from deleting a post if you posted it by accident. Erasing the contents makes it impossible to tell if you once said something meaningful that could be useful to someone later (and more importantly makes such things impossible to google in the future), and is generally frowned upon.
 
Top