Aquila - A* Pathfinding for GameMaker
GameMaker has some really nice built-in pathfinding in the form of mp_grids; in fact, I often go as far as saying they're my favorite built-in system of GameMaker. They're great if you want to be able to navigate through a grid-based structure like a maze, but sometimes they're not quite the right tool for the job. Did you ever want to implement Google Maps in GameMaker? Probably not, but bear with me.
Enter the pathfinding algorithm known as A*! mp_grids actually use A* under the hood, but they're set up in a special way such that each node is automatically connected to its neighbors, creating a grid rather than a generic mesh. This way, the network is defined only by the connections between each node (see: graphs), rather than their physical location in space.
This requires GameMaker Studio 2.3.3 in order to work. It relies heavily on the new language features.
Performance
The system performs pretty well, at least within reason. Graph traversal in general tends to get expensive on bigger networks with more connections, so try not to do anything like running this consistantly in the Step event, but you can get an idea for the amount of time each navigation takes in the status message. Naturally, the YYC yields much better performance than the VM.
Eventually I want to write a DLL version of this to make it even speedier, but for the time being I want to work on some other things.
Documentation
is available here. Github wikis are the best thing ever.
Price
As usual, the asset is free as-is. I'll fix simple or game-breaking bugs but more involved support requires payment via either Itch or Patreon. I get the final say in what constitutes "game-breaking." With that said, it passes all of the test cases I can think of so there shouldn't be any problems.
Credits
- The demo makes use of Emu (also by me), which uses Scribble by @jujuadams
- Icon is Bald Eagle by Icons Producer from the Noun Project
Download
Click download now to get access to the following files:
Development log
- A small update addressing nodes being removed7 days ago
- A small update to allow nodes to be disabled67 days ago
- HTML5 demo72 days ago
- Small bug fixes (already), and the documentationSep 12, 2021
Comments
Log in with itch.io to leave a comment.
If a node is removed, other nodes will keep their connections to that node. If navigation happens to try to use a connection to a node that doesn't exist, it causes a crash.
Looping through a to-be-removed node's connections and disconnecting them before removal is easy enough, but it took me quite a while to figure out where that crash was coming from, so I might recommend including a note about that in the documentation
That’s weird, I thought I fixed that already. Anyway I uploaded a version with the fix, let me know if it works.
Yep, all good now 👍
Very clean and understandable implementation, thanks for this!
I added a “DisableNode” method, which removes not only **all ** local connections from a node but also all connections, where this node is the destination, so no route can contain this node. Useful for moving obstacles, so you can take a node out of pathing with one line of code. This is especially important, as the current “RemoveNode” implementation in your code does not disconnect the node, so it’s removed from the graph, but their connections stay as ghosts, as they are. RemoveNode now also calls DisableNode to clean up the connections.
The difference between “DisableNode” and “RemoveNode” is, that with “Disable”, it stays in the graph, but does not have any connections, so for a map with moving objects, you may add all nodes when setting up your grid, and just connect/disable them as you need without creating new instances all the time through AddNode, when a map field becomes available again.
Contact me on discord, if you want the function for your implementation, or let me know, if I misunderstood anything in your code :-)
Cheers, Gris
Hmm, that’s probably a useful idea. I’ll get around to adding something like that to the project hopefully soon.
If one try to get the eagle to travel back to it's last node while he's travelling he'll stop another node and he reaches it. Also while the eagle is traveling if you switch the eagles path to a path that involves the last node the eagle will skip that node within the path.
Hmm, I’d initially done that intentionally but honestly I can see how that would be more annoying than anything else. I’ve disabled changing course during transit, new version should be good now!