A Lazy Man Does Dijkstra's Algorithm in GameMaker (kinda sorta)

GameMaker Studio has excellent and very fast built in pathfinding. However sometimes you want to have areas where things can move faster/slower. For example you might want grass and pavements with different travel speeds.

Pathfinding on a hex grid where yellow tiles are faster than green and red tiles

I wanted some NPCs to try and keep to footpaths unless it was vastly superior to cut across the grass. It also meant that if there wasn’t a pavement all the way from their start location to the end location they would cut across the grass in those places.

Follow along:

Download the project here: daves_pathfinding.yyz (v0.1.3)

Some of the features this has (I will explain them more later)
  • Node based pathfinding
  • Almost similar to Dijkstra’s Algorithm
  • Guaranteed to find the mathematically shortest path.
  • Can toggle on/off diagonals
  • Doesn’t have to be square grids, will do any tessellating and non-tessellating world (hex, rectangle, rhombus, triangular, isometric, voronoi etc).
  • Grids can be any size without slowdown.
  • Caches paths so it doesn’t have to recalculate them in the future.
  • You could add teleporters to jump from one place to another.
  • Load balances.
  • If a path takes too long to process it spreads it over many frames.
  • Debug console to see how long it is taking, how many are in queue/cache etc.
  • Could be modified to have different speeds in different directions (like hills that are faster to go down than up or a conveyor belt that goes one way much quicker)
Getting Started

I start off with a grid of terrain speeds, this is like the mp_grid_create you would normally start with.

Lower numbers are faster to move on. For me I used 20 for grass, 5 for roads and 99 for buildings. This means for one grass tile it can travel 4 road tiles.

You can have as many types of terrain each with their own numbers, you can even change these on the fly.

Usage:

There are two functions to use:

find_path – just give it the grid start x/y and the grid end x/y and it will do the rest, you can give a callback object which I will talk about later but it’s an event that gets run once the pathfinding is finished in case it takes more than one frame to process.

find_path_clear_db – I store the paths in a database once they have been found, this function removes all cached paths, this is helpful if you want to change the speed of some terrain or build something which invalidates all the paths it has already cached.

How it Works

It’s actually pretty basic. From the starting cell it checks all the cells around this that it can move to and works out how quick it can get to those, it will then take the least explored location and repeat the process there. This gets repeated until it finds the final location. If it goes to a location it has been to before but this time has a better way of getting to that cell it will be updated with the new speed.

Image slowed down so you can see how the system spreads out internally.

I’m technically using nodes rather than a grid so this will support any tessellating and non-tessellating pattern. As long as you can somehow store what speed each cell is you can get it to work. I have easily modified it to do: hexagonal, square, rectangle, rhombus, triangular, isometric, voronoi patterns but you could do any shape you want even abstract ones like rooms around a house.

This is the code for checking all the locations next a cell on a square grid (diagonal movement allowed):

pathing_checkcell(h+0,v-1,1)
pathing_checkcell(h+1,v-1,PF_DIAGONALMULTIPLIER)
pathing_checkcell(h+1,v+0,1)
pathing_checkcell(h+1,v+1,PF_DIAGONALMULTIPLIER)
pathing_checkcell(h+0,v+1,1)
pathing_checkcell(h-1,v+1,PF_DIAGONALMULTIPLIER)
pathing_checkcell(h-1,v+0,1)
pathing_checkcell(h-1,v-1,PF_DIAGONALMULTIPLIER)
	

PF_DIAGONALMULTIPLIER is set at 1.41 in this example because that is a good approximation of how much further it is to move diagonally across a square. But you could do something dynamic here like if you wanted to have hills or conveyor belts.

You can see how this could easily be swapped out to any code that selects the cells next to it to have any type of grid you want.

Pathfinding around Voronoi Polygons where the forest and mountain are much slower than the grass
The Database of Cached Paths

For my usage I thought it was likely most of my NPCs would be walking back and forth between the same buildings so rather than calculating the path each time I wanted to store it and grab it from the database which is much faster. I was worried about the ram this would use up however in my test version I had 10,000 paths in the database and the application only used up <30mb of ram (this includes the engine and everything)

Spread Over Many Frames

The size of the grid does not impact the performance because it only looks at the local area (walking 100 cells across will take the same amount of time on a 200x200 board as it would on a 10000x10000 board), however if the start and destination are a long way apart a vast number of cells can become involved which does impact performance.

Because of this it is able to load balance pathfinding over many frames so the player does not see any lag spikes when checking for a path. You can use many criteria to stop processing this frame however I like just using raw CPU time, this way you can allocate as much of the frame as you want to pathfinding and it will never go over that. For example you could allocate 10% of each frame to do pathfinding and if it goes over it will just stop and resume at the start of the next frame.

Queues

If multiple paths are needed at the same time it is far more efficient to do them back to back rather than calculate them all simultaneously, so if a path isn’t in the database it will be put in a queue to be solved. You might need to suddenly do 100 paths and if those were to be done concurrently it would take many seconds to even get the first one back.

Callbacks

One thing I’ve added to help with load balancing over many frames is Call Backs, often an object will ask for pathfinding to be done but it needs to wait until it is finished before it can start moving, hopefully this isn’t going to be more than a few frames but it still breaks the flow of the code so you pass in an Object ID when you initiate the pathfinding and it will run a User Event when the path has been found. This way you can place the movement code there and know it will always be triggered.

Rhombus tiles for isometric games or other camera angles.
Teleporters

While this isn’t shown in any of the images it would be very easy to add portals that link one cell to another and allow units to instantly travel between them. I think this would be a very cool mechanic to add into a game

Not Actually Dijkstra's Algorithm

So ok, I know, you are not fooled. It’s not technically fully Dijkstra. Dijkstra is a very well-known and optimised pathfinding algorithm. The subtle difference between this and Dijkstra is that Dijkstra does the weights on the path between nodes and I just do it on the actual node is self. Basically everything else is the same after that, the reason for this is GameMaker is much quicker at reading grids so storing the list of visited nodes, travel time to nodes and terrain of nodes all in similar grids made the processing much faster, however everything else after this is the same even down to what order it would select to do paths.

Not Greedy

It’s not greedy – If you are familiar with pathfinding terms this means it is more likely to go down a “juicy” path to find the exit, while this is more efficient to process it means you are not guaranteed to find the optimal path. You might have a crazy fast motorway that you need to backtrack to get to, my system will find that motorway! This system WILL find the mathematically shortest path.

No Impossible Terrain

No impossible terrain, this means that if a character is dropped ontop of a building or something they wouldn’t normally walk through it will still pathfind out, but walk around this otherwise.

Yoyo Games Marketplace

It’s not a big system so I will not be putting it on the Yoyo Games Marketplace, its just 3 or 4 short scripts and an object to hold the data. There are a few other scripts used to queue up many paths to find, check to see if this path has already been found and spread checks over many frames if it takes too long.

Many objects requesting paths (in slow-mo to see the checked areas spread out)
Get the Project Here:

Download the project here: daves_pathfinding.yyz (v0.1.3)



Advanced Difficulty
GameMaker
By David Strachan