Dijkstra Maps Visualized – RogueBasin
Dijkstra maps are superior. They’ll educate your AI some intelligent new tips – and cheaply, too, as a result of the identical map can be utilized for any variety of actors. And AI is just the start: Dijkstra maps can facilitate computerized exploration, pathfind-to-cursor, and dungeon era, too.
So, what’s a Dijkstra map? Have a look:
At its most simple, it signifies distances. Within the above picture, the map reveals how removed from the participant (‘@’) every cell is. (The colours listed here are only for demonstrative functions. The numbers are the necessary half.) Some notes on the implementation will be discovered here.
Now, I would prefer to encourage you to learn this fantastic article by Pender(Brian Walker), the creator of Brogue. This text relies closely on the concepts offered there, and I am going to go into extra element on how they are often achieved.
Completed studying that one? Sounds wonderful, proper? Let’s examine if we will get these examples working.
— The fundamentals —
One of many easiest purposes of Dijkstra maps is making enemies beeline for the participant, taking the shortest path always. The picture above is all you want. These goblins –
– can, every flip, merely test every cell adjoining to them, and step to any that has the bottom worth.
This map solely must be up to date when the participant strikes, like this:
— A number of sources —
They work nice! In case you have a number of sources, the ensuing map will lead towards whichever is closest. On this instance, we add gold. Goblins now wish to assault the participant AND acquire gold:
(The map might be up to date at any time when the participant strikes or gold is collected, so the goblins do not goal for a goal that is now not there.)
— Variable strengths, and what distance actually means —
So, within the earlier instance, our goblins have been glad to gather gold or assault the participant, whichever was closest, simply by in search of decrease values on the map. However what if we wish our goblins to be exceptionally grasping, keen to stroll farther to achieve gold even when the participant is definitely nearer? Here is how.
As an alternative of beginning all of our sources at a price of 0, give the extra fascinating ones a decrease worth – let’s use -4 for the gold whereas maintaining the participant at 0. Like this:
(These grey numbers are negatives, so a goblin in search of decrease values would transfer from a 0 to a -1 and so forth.)
Why does this work? By beginning the gold at a price of -4, we’re treating it as if it have been nearer than it truly is. If a goblin is 7 cells away from gold, and three cells away from the participant, the -4 modifier signifies that the goblin will see them as equidistant, and be equally more likely to method both one.
— Fleeing AI —
Now that we all know the right way to make enemies method, let us take a look at making them flee. What occurs if we take the method map and have them transfer towards greater numbers? (i.e., darker colours?)
They simply find yourself within the corners, and may’t escape even when the participant is true subsequent to them. Here is the right way to repair that:
First, take the prevailing method map and multiply every worth by a quantity near -1.2. This successfully flips the map in order that transferring towards the decrease numbers (lighter colours) takes you away from the supply(s) as a substitute of towards the supply(s).
Then, we rescan that map. It is the identical as the essential scan, however we use no matter values occur to be within the map already. After that, we find yourself with this:
Observe what occurred to the areas round corners and doorways.
Be aware additionally that what we have successfully performed is to create a brand new map utilizing the farthest tiles because the sources, and giving them a bonus for being farther away – the bonus is the 0.2 a part of the -1.2 multiplication.
Altering that coefficient from -1.2 to a stronger quantity can have an enormous impact on the outcome: The larger the coefficient, the “nearer” a distant cell might be, and the extra it will “pull” fleeing monsters towards it. Here is what a coefficient of -1.6 appears to be like like:
If the coefficient is simply too excessive, probably the most distant cells will dominate the entire map – a fleeing monster will ONLY wish to transfer to the FARTHEST cell if this occurs. If the coefficient is simply too low, the map will not change very a lot from the “stumble upon corners” model. Experiment with completely different values to see which you want!
— Computerized exploration —
Autoexplore is very easy! Simply use each unseen cell as a supply, and also you get this:
The participant can now transfer towards decrease values and routinely uncover new territory. Preserve doing this every flip till a secret’s pressed or till one thing occurs (an enemy comes into view; a message is generated; the participant takes harm).
(Be aware that this even accounts for the additional flip required to open a door (‘+’) earlier than you progress by way of it, by assigning it a value of two as a substitute of 1.)
— Low-cost mouse pathing —
For example you wish to present a visual path onscreen because the participant strikes the mouse (or different) cursor throughout the map. Dijkstra maps can present an optimization so that you needn’t run a traditional pathfinder (like A* or common Dijkstra pathfinding) each time the cursor strikes to a brand new cell.
By calculating a single Dijkstra map when the cursor strikes onto the map (for the primary time on every flip), you may merely roll from the cursor to the participant to discover a path (then, in fact, reverse that path so it leads from the participant to the cursor).
(I like to recommend having a manner to make sure that the trail you see is the trail you are taking – I favor a deterministic pathfinding routine for the participant, and a randomized one for enemies.)
Like autoexplore, this one treats unexplored cells like they’re common flooring, so it is attainable to decide on an inconceivable path. That is high-quality – you will simply must cease the participant as soon as it is clear that the chosen path leads right into a wall.
— Shifting into optimum vary —
Need your ranged enemies to remain at a sure vary? Begin with a Dijkstra map from the participant, after which create one other one – the supply cells would be the cells on the primary map with the specified vary:
However, you in all probability wish to go one step additional, and say that the supply cells would be the cells on the primary map with the specified vary…to which the participant has line of sight:
— Hazard avoidance —
If the participant can swim, however just for a couple of turns, you should utilize a map like this one, calculated simply as soon as when the map is created. Monitor the remaining swimming turns, and if the participant tries to maneuver to a cell with a price higher than the remaining turns, you may forestall that transfer and provides a warning.
I hope these examples assist as an instance simply how helpful Dijkstra maps will be. Good luck!