Dijsktra Maps
Dijsktra maps, also known as flow fields, are a super interesting concept that are very prevalent among roguelikes and, I would imagine, other grid-based games. There aren't many good tutorials or explanations on them floating around the Internet, so I'm hoping I can help fill that gap.
Dijkstra's Algorithm
Dijkstra's algorithm is pretty straightforward. First, we fill our cost array with some high number. I set a maximum number of steps we traverse to limit the algorithm, and I set the initial values to twice the maximum. Then we pick our target spots, add them to our queue, and set their costs to zero or whatever initial value we want. From here, we pull the next item out of the queue, and compare the cost of traveling from it to each of its neighbors. If the cost of travelling to our current node plus the cost of travelling to a particular neighbor is less than the cost we already have for that neighbor, we update it to our new cost and add it to our queue. If it isn't less, or if the new cost is greater than our maximum, we move on.
Once we've emptied our queue, we should have a map of distances! The primary way that the map diverges from the normal Dijkstra's Algorithm, is by keeping each cost. Normally with Dijkstra's Algorithm, you only follow the neighbor that has the lowest cost and you quit once you've reached your target. In our instance, we continue until we've touched every location and have found every location's optimal cost.
- Decide on limit for number of steps.
- Fill cost array with number larger than limit.
- Select initial nodes.
- Set cost of initial nodes on cost array.
- Insert initial nodes into queue, either in order for a Breadth-First Search or as priority queue for Dijkstra's Algorithm or A* Search.
- While there's a node available in the queue:
- Extract next node.
Dijkstra's Map
When you run Dijsktra's Algorithm, but just let it go until it self-balances.
Applications!
Some of the interesting things you can do with Dijkstra's Algorithm and associated maps.
Base Case: Distance
Distance! That's fundamentally what we're calculating with this algorithm, the distance from any given node to its nearest target node.
Enemy Pathfinding
Because we're calculating distances, if we use our player(s) as our target nodes, an enemy can just find the lowest cost adajcent to itself, and surf the gradient right towards the nearest enemy.