Dijkstra Map

[Azathotep]

I can't figure out the safety behavior from:
http://roguebasin.roguelikedevelopment.org/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

m is a monkey that needs to flee the approaching player.

So first I do this:
"Start with a Dijkstra map calculated around goal points at the player's location and at any player allies from which your monsters will also want to flee."
Which produces this:

Code: [Select]

#   #  #   #  #  #   #   #  #

@  1   2   3   4   5   6   m  #
                         
#  #   #  #    #   6   #  #  #

               #   7   #

Then it says:
"Multiply every value in the map by a negative number somewhere in the neighborhood of -1.2"

Code: [Select]

#    #    #     #     #    #   #   #   #

@ -1.2 -2.4 -3.6 -4.8 -6 -7.2  m   # 
                         
#   #    #    #   #  -7.2  #   #   #

                  #  -8.4  #


"Take the result and pass it back through the Dijkstra scanning function. "

That's what I am stuck on. The scanning function involves:
"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."

But how will that ever be true? How will any tile be at least 2 greater than its lowest-value floor neighbour when I have multiplied them all by 1.2?

As it stands the monkey is just going to sit in that dead end as the player approaches rather than jump out and flee to the south.

I suspect I've misread something and got the wrong end of the stick concerning the -1.2 multiplication and the rescan. But I've read it again and again and nothing springs to mind.

[guest509]

I have no idea what the multiplication or the resetting of values does. Maybe that adds some variability to the movement or something. No idea.

I can see the problem on your map though with your monkey. You want the monkey to move towards the greatest value on the player map (I think). Right now the monkey is already on the greatest valued spot on that map. Sitting on the 7. The player can march right at the monkey and the monkey wouldn't move, because there is no safer place. Only if that lower tunnel goes further, with spaces being 8 or more moves away, will the monkey want to go there.

So you want to pathfind to the greatest value on the 'player map'. You can do this by noting that spot and then running the algorithm again from the perspective of that spot, then have the monkey run downhill...you can create a map from the monkey perspective but what if you had 10 monkeys?

A better programmer should look at this, but since no one was responding I thought I'd give it a crack.

Map from the player looks like this. With an added space on the bottom tunnel.

Code: [Select]

@ 1 2 3 4 5 6 m
                6
                7
                8

8 is the furthest spot, so then creating the map from the furthest spot looks like this.

Code: [Select]

@765434m
                      2
                      1
                      0
Now make the monkey run down hill, move to the adjacent space if the adjacent space has a lower value.

EDIT: Okay, code fail, but you can see that 2 spaces left of the monkey is the split in the corridor.

[pat]

I've got to admit that I've looked over that algorithm previously and also never quite wrapped my head around the negative multiplication aspect of it. I just assumed the problem was me and moved on to a long history of never writing an AI with the ability to make clever short-term decisions like you're talking about.

[dscreamer]

Code: [Select]

#   #  #   #  #  #   #   #  #

@  1   2   3   4   5   6   m  #
                         
#  #   #  #    #   6   #  #  #

               #   7   #

Then it says:
"Multiply every value in the map by a negative number somewhere in the neighborhood of -1.2"

Code: [Select]

#    #    #     #     #    #   #   #   #

@ -1.2 -2.4 -3.6 -4.8 -6 -7.2  m   # 
                         
#   #    #    #   #  -7.2  #   #   #

                  #  -8.4  #


"Take the result and pass it back through the Dijkstra scanning function. "

That's what I am stuck on. The scanning function involves:
"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."

But how will that ever be true? How will any tile be at least 2 greater than its lowest-value floor neighbour when I have multiplied them all by 1.2?

As it stands the monkey is just going to sit in that dead end as the player approaches rather than jump out and flee to the south.

I suspect I've misread something and got the wrong end of the stick concerning the -1.2 multiplication and the rescan. But I've read it again and again and nothing springs to mind.

Stick to integers when you multiply by -1.2. That is, multiply by -6 and then divide by 5, dropping any decimals as usual in integer math.
Let's change the diagram to demonstrate, by moving the player and extending that corridor:

Code: [Select]

  #    #    #    #   #    #    #   #   #

-4.8 -3.6 -2.4 -1.2  @  -1.2 -2.4  m   #  (monkey is at -3.6)
                         
  #    #    #    #   #  -2.4   #   #   #

                     #  -3.6   #                       (the scale is a little stretched here)

                     #  -4.8 -6.0 -7.2 -8.4 -9.6 -10.8 -12.0 -13.2 -14.4 -15.6 -16.8 -18.0  #


Which is actually this, since we're dealing with integers only:

Code: [Select]

  #    #    #    #   #    #    #   #   #

-4   -3   -2    -1    @  -1   -2    m   #  (monkey is at -3)
                         
  #    #    #    #   #  -2     #   #   #

                     #  -3     #

                     #  -4   -6   -7   -8   -9   -10   -12   -13   -14   -15   -16   -18    #


And which turns into this once you run the scan again:

Code: [Select]

  #    #    #    #   #    #    #   #   #

-4   -3   -2    -2    @  -4   -3    m   #  (monkey's tile is now -2)
                         
  #    #    #    #   #  -5     #   #   #

                     #  -6     #

                     #  -7   -8   -9   -10   -11   -12   -13   -14   -15   -16   -17   -18    #


Now you can kinda see what the multiplier does as the distances grow. Parts of the dungeon that are very far from the player will look more attractive - in this diagram, the monkey would now make a break for it because that -3 is lower than the monkey's current -2 (and therefore safer).


Notice, in the above diagram, what would happen if we had cut the corridor off 1 tile earlier. The tile that ended up as -17 would be -16 instead, and the floor right next to the monkey would be -2. The monkey wouldn't have a lower tile to step to. What if we want the monkey to run sooner, or with less space? The next diagram shows what happens if we increase the -1.2 multiplier to -1.5:

Code: [Select]

  #    #    #    #   #    #    #   #   #

 @   -1   -3    -4  -6   -7   -9    m   #  (monkey's tile is -10)
                         
  #    #    #    #   #   -9    #   #   #

                     #  -10    #

                     #  -12   -13   -15   -16   -18   -19   -21   -22   -24   -25   -27   -28    #


And the final result:

Code: [Select]

  #    #    #    #   #    #    #   #   #

 @   -10  -11  -12 -13  -14   -13  m   #  (monkey's tile is -12)
                         
  #    #    #    #   #  -15    #   #   #

                     #  -16    #

                     #  -17   -18   -19   -20   -21   -22   -23   -24   -25   -26   -27   -28    #


The monkey was just barely deciding to flee before (-3 vs -2) - even though the player was much closer in that instance! - but with a bigger multiplier, the monkey will start fleeing much sooner.

Hope this helps. Good luck.

[guest509]

Couldn't you just have the monkey move toward the furthest point away from the player whenever the monkey is within x spaces of the player. Spaces are determined by the player's dijkstra map. I don't understand why all the multiplication and number fiddling.

[dscreamer]

Couldn't you just have the monkey move toward the furthest point away from the player whenever the monkey is within x spaces of the player. Spaces are determined by the player's dijkstra map. I don't understand why all the multiplication and number fiddling.

If you mean that the monkey (using the original map with the player as the source) would look at the tiles directly around itself and pick the biggest number, that's one of the main things the dijkstra map technique avoids - the monkey would always flee directly away from the player, getting stuck in corners or against walls. (the Dijkstra safety map fixes this when it makes distant tiles more attractive by giving them lower numbers)

If you mean that the monkey would find the furthest point from the player on the entire map, that would involve searching the entire map and then figuring out how to get there - which would involve either bumping its head on walls, or more pathfinding. (the Dijkstra map only requires examining the local surroundings at each step - cheap even for TONS of monsters)

Hope that helps. Let me know if I said anything confusing.

[george]

Which is actually this, since we're dealing with integers only:

Code: [Select]

  #    #    #    #   #    #    #   #   #

-4   -3   -2    -1    @  -1   -2    m   #  (monkey is at -3)
                         
  #    #    #    #   #  -2     #   #   #

                     #  -3     #

                     #  -4   -6   -7   -8   -9   -10   -12   -13   -14   -15   -16   -18    #


And which turns into this once you run the scan again:

Code: [Select]

  #    #    #    #   #    #    #   #   #

-4   -3   -2    -2    @  -4   -3    m   #  (monkey's tile is now -2)
                         
  #    #    #    #   #  -5     #   #   #

                     #  -6     #

                     #  -7   -8   -9   -10   -11   -12   -13   -14   -15   -16   -17   -18    #



I don't see how the monkey's tile goes to -2 -- aren't none of those tiles 2 or more different from their lowest-value neighbor, except the 0 at the player, which just turns into a -1 and doesn't affect the other tiles near the monkey? Nevermind, I wasn't thinking of the numbers peeling back from right to left like that.

[IBOL]

I've been using dijkstra maps for years, based on the same article you mentioned.
but what I do for running away is this:
1. set all dijkstra values very high.
2. set all cells that are a certain distance away from the players as goal cells (zero(0))
3. process the dijkstra map.

you can just generate this once per loop, and every monster will be able to find a good place to run away.
and if you keep all tiles that block movement as that very high number, they'll follow the perfect path,
just choosing the smallest number adjacent to them.

I just did preliminary monster AI in my game, Approaching Infinity using dijkstras. Enemy spaceships will stay a nice distance away from you and fire, while monsters on planets will mostly charge you.

I also just did 'right click on map to move to' last night in an hour. it's awesome. I<3Dijkstra

[Paul Jeffries]

I use Dijkstra maps quite a lot, although my implementation is a bit different to the one suggested by that article.  My understanding of what he's doing with the safety maps is that he's essentially creating a Dijkstra map of a Dijkstra map.  The first pass based on proximity to enemies gives the initial goal weightings for the second pass based on movement cost.  The -1.2 is just a weighting factor for the distance from an enemy verses the movement cost - i.e. it is 1.2 times as important that a tile is further away from an enemy than it is that it's easy to get to.

I'm not sure that using integers is actually important for the algorithm to work as dscreamer is suggesting (I could be wrong), but it is generally good advice to use integers for Dijkstra maps just because integer maths operations are usually a lot faster than floating point ones.  For example rather than using 1.0 as a basic move cost and -1.2 as a weighting I would tend to use 10 and -12.

[guest509]

For KlingonRL I tried to figure this out for my ships running away, but my space maps never had corners. Blocking objects (planets and starbases and stars) were never created next to each other diagonally or orthogonally.

So I was able to do:
  If Player is Right then Run_Left
  If Player is Left then Run_Right
  etc...

:-)

[King Ink]

Dijkstra mapping is a fantastic way to "solve" the rogue-style game (as beautifully exhibited in Brogue) but does it make sense in a simulationist context?

Real animals get trapped in box canyons (ask a hunter.)

efficiency in pathing  (or much clean maximization at all) does not seem to happen in the real world.

does anyone have any experience  Dijkstra + noise or heuristic solutions to the pathing issue?

p.s. I am about 3 inches away from implementing Dijkstra pathing to goblin men.

[miki151]

You can throw a dice to decide if the creature takes a primitive "move away from" strategy or uses a dijkstra map. You can take into account the personality, how afraid it is, etc.

You can make the shortest paths look more plausible if you randomize the order of analyzed tiles in the inner loop of the Dijkstra, they will seem more randomized, while still being the shortest.

[King Ink]

my problem (and this only because I come from academic agent-based modeling)
is that the use of a Dijkstra assumes that the agent has a complete map of the area and the instantaneous skill to calculate shortest distances (IRL a hard task).

a critter is more likely to use a "primitive" or heuristic strategies.
for example dogs rarely use an open gate that is farther away from its target but instead stare blankly through the chain-link.
 
perhaps a personal Dijkstra mini-map of the square 3 steps or less away?
a 7 X 7 matrix generated for each critter or if they have directionality a 7 x 3.

this way they would zip around trees and rocks but not have total landscape mastery. 

[miki151]

In most terrain types Dijkstra runs very locally, in case of the reversed version the creature usually runs for the door or something. In my game rarely do I see elaborate pathfinding. If you use a lot of obstacles that don't obscure view maybe it will be different.

BTW, I assume that the creatures dwell in the dungeon or wherever, therefore they know their way around. Otherwise you can give them terrain memory just like the player has and run Dijkstra on that, pretty straightforward.

[guest509]

Intelligence Score = Range of Dijkstra map?