The Incredible Power of Dijkstra Maps

These things are REALLY POWERFUL and can pretty easily give rise to behavior that is eerie in its seeming intelligence. I wanted to share a few techniques I’ve come up with for Brogue.

I don’t know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth- first search from a single point or set of points, I mean doing the following:

To get a Djikstra map, you start with an integer array representing your map with some set of goal cells set to a value of 0 and all the rest set to a very high number. Iterate through the map’s ????floor???? cells -- skip the impassable wall cells. If any floor tile has a value that is at least 2 greater than its lowest value floor neighbor, set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made.

The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where you’re starting from, you can just ????roll downhill???? on the Djikstra map and you will reach the goal in an optimal number of moves.

But there is SO MUCH MORE that these things can do. Here are the revelations I’ve had while making Brogue:

1) Safety maps. Everyone likes monsters that know how to flee. The problem is that it’s not easy to get them to flee intelligently. If they just run away from the player, they’ll just bang their heads against the nearest corner of the room that they start in. This happens even if you use a Dijkstra map and try to roll uphill instead of downhill. Solution: Start with a Dijkstra map calculated around goal points at the player and any player allies that your monsters will also want to flee. Treat monsters that haven’t moved since last turn as obstacles. Multiply it by a negative number somewhere in the neighborhood of -1.2. Take the result and pass it back through the Djikstra scanning function. Rolling downhill on the result (recalculated each time the player moves) will cause monsters to flee for the nearest door. If cornered, they will try to sprint past the player and escape. If you think of the amount of ????safety???? that a cell has as the distance it is from the player, the negative coefficient determines how much the monsters will prefer a global safety maximum to a local safety maximum -- e.g. how close the player has to get before the monster tries to make a break for it. Using more negative numbers (i.e. negative numbers with a greater absolute value) will also make monsters very likely to exploit large loops in the level geometry and ????pillar dance???? as the player chases it. You can have as many fleeing monsters as you like, and they can all share this same map so that it needs to be updated only once per turn.

2) Autoexplore. We’ve all watched the Angband Borg, right? And the Crawl autoexplore feature? With these methods, you can add an autoexplore feature in 20 minutes. For the goal points, use every tile that the player has not discovered. Pretend that undiscovered wall tiles are really floor tiles. Run the scan every turn. When the player rolls downhill on this continually updated map, he will automatically blaze around the level until there are no more unexplored tiles that he can reach. Have the function stop whenever a message appears on the screen or whenever a previously unseen monster comes into view so that the player can use it without extreme risk. Want him to collect items along the way? Set items that the player has not yet stepped on to be goal points along with the undiscovered tiles. Now your player can skip through mindless exploration with a single keystroke and get control back the moment something interesting occurs. In fact, it’s trivial to take this a step further: cut out all of the interruptions and have the player attack any monster adjacent to him. When there is no more exploration to be done, set the downstairs as a goal point. When that is the case and he is standing on the downstairs tile, have him use the stairs and continue on the next level. In less than an hour, I had a single keystroke that would make the computer start playing automatically -- collecting items and fighting bad guys and descending -- until interrupted or killed.

3) ????Fuel low???? warnings. Brogue features Potions of Levitation, which cause the player to fly for a limited number of turns. It also features deadly lakes of lava that the player can fly over. It also features various automation features such as auto-travel and auto- explore that will plot routes based on what kinds of terrain are currently passable for the player. The problem was that a levitating player can pass over lava, so would get routed over a lava lake 20 spaces wide -- even when his levitation had only 10 turns left. What to do? Use a Dijkstra map, calculated once at level generation, to keep track of how many turns it takes to get out of a lava lake and back to solid ground from any given space in the lake -- trivial to do by treating all land tiles as goals. If the number of turns to escape from the lake is equal to or one greater than the number of turns remaining in the levitation effect, a very stern warning pops up, and that interrupts autotravel.

4) Desire-driven AI. Most of the things a monster will do involve moving toward something or moving away from it. Here are some examples:

• The player: approach or flee.
• Treasure: collect it.
• Other monsters: approach to aggregate into packs, flee to keep monsters by themselves.
• Food: Go to it and eat it.
• Water: Go to it and drink it.
• Sounds: Investigate them, or avoid them.
• Hive queen: Stay near her.
• Stealth: Prefer to be in cells that the player can’t currently see.

Etc. Create one Dijkstra map for each of the above items updated each turn (and another one if fleeing behavior is also relevant to that item using methods I described in (1) above). Now for each monster, keep track of how much it desires to be near that item; higher numbers indicate a desire to be near that item, zero indicates complete indifference, and negative numbers indicate a desire to be far away from that item. These numbers can change dynamically each turn. A monster’s desire for food might steadily rise every turn and be set back to zero if the monster is on a tile that contains food. A monster that sees the player might start out indifferent but want to approach the player if it sees the player do something it doesn’t like. Or if it sees the player reduce another monster to a smoldering crater with a single-syllable incantation, perhaps the monster will want very much not to be near the player and its number will go sharply negative. Each of these values should be set independently.

Now, the key insight is that Djikstra maps can be added together. To calculate how much a monster desires to move in a given direction, take each desire, multiply the monster’s coefficient for that desire by the value of the cell of the Djikstra map that is in that direction, and sum over all desires. For positive desires, use the desire number as the coefficient; for negative numbers, turn the number positive and use it for the ????fleeing???? map of the same desire. Do this for each possible direction and let the monster move in the most desirable direction overall. With nine weighted sums, you will have a monster intelligently weighing conflicting ideas: ????can’t stay near the queen because the player is too powerful for that to be a useful fight, and while east is a slightly more efficient escape route, west will take me past water (I am very thirsty) and also toward another of my compatriots -- so I’ll go West.????

Want even more intelligence? Use more Djikstra maps. Can a monster use wands but not swords? Instead of a single ????items???? map, have a separate ????wands???? map and ????swords???? map -- then you can have wizard monsters, tank monsters, and even gold-hording greedy monsters. The technique is very scalable since (1) a Djikstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped and not every turn, and (2) the Djikstra maps will work for all monsters at the same time; the individual monster is cheap to add because it only differs from other monsters in how much it weighs each map in its assessment of its nine movement possibilities each turn.