The incredible power of Dijkstra maps
Pender
behavior that is eerie in its seeming intelligence. I wanted to share
a few techniques I've come up with in 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 my Roguelike:
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. 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.
Any other cool techniques with Dijkstra maps?
Ryan Szrama
if I hate having to spend a few minutes here and there chasing down a
thieving monkey. : P
I'm going to have to play with this idea, as I've actually never
implemented actual pathfinding in any of my games... just the classic
"move toward the player if you see him" AI. Thanks for the tips!
And on a side note... while I've never used a potion of levitation, I
did get a handy wand of blinking and was using it to zip across
impassable areas. Then I found out the wand has a range limitation
when I tried to fly over a lava lake. Shame, as it was my best run
yet... I had rescued an ogre on the second level, a mighty fine tank.
-Ryan
Nolithius
news:7577d801-1189-454e...@e1g2000yqh.googlegroups.com...
<snip>
This is a great idea and I will steal it. :)
Do you have a demo of this in action?
More importantly, is there an up to date Windows binary of the latest Brogue
build that uses this system? ;)
Cheers!
Ebyan "Nolithius" Alvarez-Buylla
http://www.nolithius.com
Pender
Yes, monkeys are horrible and I hate them too. It's a good idea to
stand in the room's only exit when you fight them, and remember that
you have darts to throw if they start getting away. Sorry to hear
about your mishap with the blinking staff. If you use a scroll of
identify on a staff, its charges and max charges are displayed, and
the yellow targeting line will show you exactly how far it will let
you blink. Let me know if you can think of a good interface cue that
the blinking staff has limited range even if the player doesn't know
what the range is. (Also, staffs recharge over time but wands don't --
is that apparent, or do I need to make it more obvious somehow?) Don't
feel too bad, though -- if your ogre pet was still a useful ally, your
character was just getting started :)
On Mar 17, 4:22 pm, "Nolithius" <nolith...@gmail.com> wrote:
> This is a great idea and I will steal it. :)
>
> Do you have a demo of this in action?
>
> More importantly, is there an up to date Windows binary of the latest Brogue
> build that uses this system? ;)
Please do steal it! As to your questions, it depends on which feature
you're asking about. The version of Rogue that is currently released
(1.0.1) has #1. The version I'm working on and plan to release soon
has ##2 and 3.
I haven't done #4 yet. I'm not convinced it's a good match for Brogue
since I decided not to let monsters use items and since monster
complexity is basically wasted effort if the player isn't aware of it.
I briefly considered making some sort of kobold tribe simulator for
the 7DRL challenge -- like an ant farm for kobolds -- but work was
very busy that week and I also wasn't sure how to make it into a game
as opposed to a passive simulation. It would be pretty cool to set up
a one-level map with a kobold tribe on one side and a warring goblin
tribe on the other, with computer-controlled adventurers periodically
appearing using the autoplay feature described above and dropping all
their equipment when they were killed... but again, what role would
the player have? I suppose he could sort of possess various kobolds
and beat up on goblins and adventurers, but I'm not convinced that
would be fun.
As to the ever-present question of a Windows port for Brogue... it's
sad and frustrating. Given that the game code is all in C, it would be
SO EASY to port if either a windows user would do it with the libtcod
or tinyCurses library or if I could get libtcod to work on Xcode on my
Mac, but so far neither has happened. Someone did put together a Linux
and Windows port from scratch. I linked to them from the Brogue
homepage but have heard conflicting reports about their speed and
can't vouch for them. There is also a libtcod port for OS X on the
libtcod homepage, but I don't know how to get it to work in Xcode.
Again, frustrating, because Brogue doesn't have a single platform-
dependent function in it that isn't also pre-rolled in libtcod, and
I've even documented them all --
http://sites.google.com/site/broguegame/Broguemachdepguide.pdf?attredirects=0
-- but I'm at the mercy of strangers on this one.
hmp
Not so much about Dijkstra maps, but pathfinding in general: I found
it very useful in generating dungeons. A quick-and-dirty algorithm is:
Start with Wall squares everywhere.
Place N non-overlapping rooms randomly, putting Floor and RoomWall
squares on the map.
For each pair of rooms (1,2), (2,3) .. (N-1, N):
Find a path between that two rooms, assigning different costs to
different square types.
Carve that path into the map as a new corridor (Floor).
Now, depending on how you assign costs to (Floor, RoomWall, Wall)
squares:
Low Floor, medium Wall, high RoomWall cost = nice interconnected
dungeon.
Very high Wall cost = as few cells carved as possible, lots of reused
corridors, possibly very roundabout paths.
High Floor cost = no reuse, so lots of redundant corridors, lots of
double-spaced corridors.
Low RoomWall cost = irregular, cave-like rooms because of walls
getting "eaten" in some places.
Pender
> Great article! Please add it to RogueBasin wiki for posterity :)
Added it here: http://roguebasin.roguelikedevelopment.org/index.php?title=The_Incredible_Power_of_Dijkstra_Maps
Very clever dungeon generation algorithm. Have you used it? Do you
have pictures of the various levels it creates?
hmp
> Very clever dungeon generation algorithm. Have you used it? Do you
> have pictures of the various levels it creates?
It's used in my 7DRL, Madness: http://students.mimuw.edu.pl/~pm262952/madness/
(look for mapgen.py, feel free to play with it :) ).
The game even uses different path costs for different levels, so they
look a bit varied.
----
http://humpolec.pastebin.com/R95AC25Y if you can't see the following
in a fixed-width font.
Here are some maps generated by Madness mapgen. Corridors
have no walls drawn around them to differentiate between
ordinary wall and room wall (in the game the first is grey,
the second brown).
In Madness levels 1-3 are of the first, 4-7 the second,
and 8-10 the third variety.
1. Wall cost = 5, RoomWall cost = 40, Floor cost = 1
############### #####
##### #......##.....# #...#
#...# #.............# ######...#
#...# ##############......>.....##........ #...##...#
#.................... . ############### .. #...##...#
#...# #............#.##.####### .... #...##.###
##### #............#.#........# ####.# .. #...#..
#............#.#........# #....# ..#...#.
##############.#........# #....# .#...#.
..#........# #....# .##.##.
##### #########.##........# ###### .......
#...# #.........##........# ############.#####
#...# #.........##........# #................#
#.................########### #..........# #...#
#...# #.........# #..........# #...#
#...# ########### ############ #...#
##### #####
2. Wall cost = 5, RoomWall cost = 1, Floor cost = 2
(some room walls are destroyed by corridors)
#####
............#...#
............#...#
#######....... ................#
#............. ...........##...#
#..................... ...............##
#............##....... ............
#######........>.............#. .
. ........ ........ .
######...... ........ ........ #......#####
#..........# #......# ........ #..........#
#..........# #......# ........ #..........#
#..........# #......# #......# #..........#
#..........# ######## #......# #..........#
#..........# ######## ############
#..........#
############
3. Wall cost = 5, RoomWall cost = 40, Floor cost = 40
(now we won't reuse existing corridors)
################### #####
...........#...........##....# #...#
#####........ ...................# #...#
#...#..#####. #.................#..........#...#
#...#..#...#. #...........#.#####. #######.......
........#...#. #................... #......##...#.
.#...#..#...#.. #############...............##...#.
.#...#..................##############.#......######.
..#####..#...#..........................######## .
.##### ..#...# #####..#............###############.
.#...# ..#...# #...#..#............##............#.
.#...# ..##### #...#..#............##............#.
..................#.................................#.
#...# .#...#...........######............#.
##### .#####.......................#######.
.....................................
Ryan Szrama
> stand in the room's only exit when you fight them, and remember that
> you have darts to throw if they start getting away. Sorry to hear
> about your mishap with the blinking staff. If you use a scroll of
> identify on a staff, its charges and max charges are displayed, and
> the yellow targeting line will show you exactly how far it will let
> you blink. Let me know if you can think of a good interface cue that
> the blinking staff has limited range even if the player doesn't know
> what the range is. (Also, staffs recharge over time but wands don't --
> is that apparent, or do I need to make it more obvious somehow?) Don't
> feel too bad, though -- if your ogre pet was still a useful ally, your
> character was just getting started :)
>
Great to know about staffs! I actually didn't know that before, but
lo and behold I just played my deepest run yet and found a staff of
firebolt early on. Helped me off a lot of enemies, and I finally
figured out why there's grass in dungeons. Flash fires! Very nice
touch, really. There's a lot of depth to this game. I also scored
some weapons I could use early on, too.
As for the monkeys, I'd figured that out and can usually get them
stuck in a room where some simple repetitive movements will off 'em in
a few hits.
Here's the screenie of my latest death... sandwiched between a spider
and two dar blademasters. :-/
http://skitch.com/rszrama/n4tbc/death-by-dar
Gonna have to add that one to my review post. : D
Oh, and I actually rather enjoyed finding out the staff of blinking
had a limited range. I'm in this for the pain. >: )
-Ryan
Björn Ritzl
> 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 in 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.
>
Won't this be computationally expensive? Aren't we talking about a lot
of iterations of the map to build a full Djikstra map? And if you want
to make several maps, as suggested in your example, it will be a lot of
iterations. Or maybe this isn't a big deal on a modern computer?
/Bj�rn
Jeff Lait
> Pender skrev 2010-03-17 19:39:
>
> > 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 in 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.
>
> of iterations of the map to build a full Djikstra map? And if you want
> to make several maps, as suggested in your example, it will be a lot of
> iterations. Or maybe this isn't a big deal on a modern computer?
His description is unusual. I use what I think are the equivalent
maps, but call them "distance maps" since they effectively store the
distance to your goal point in every square.
A more efficient computation is just to use a dequeue of grid cell
locations.
1) Set all your map squares to -1, a marker for not-set.
2) Set your goal squares to distance 0, append them to the dequeue
3) While dequeue is not empty:
a) Take a position from the front of the dequeue
b) Load its distance from the map, "d"
c) Look at all neighbours of that position
i) If impassable, skip
ii) If their distance -1
1) Set their distance to d+1
2) Append their position to the dequeu
Whether you look at all 4 or all 8 neighbours depends on if your
allowing diagonal movement.
Note that since all your distances between cells are 1, you don't need
a priority queue. If you want variable distance costs (terrain costs,
etc) you'd have to replace that dequeue, and you'll have to test if
the new distance is smaller or not.
Also, if you have a maximum distance you need to build the map for,
you can just stop the loop when the read map distance hits that
maximum distance.
Even as described, this is *still* an expensive operation. It fills
the entire map, unlike A* which tries to minimize its search in the
correct direction. However, it has the advantage that so long as your
walls don't move, it remains correct allowing you to path find to the
goal in O(1) time from any map location.
In Smart Kobolds, I use this quite extensively. Since there might be
multiple active goals (different groups of kobolds may be traveling to
different rooms, etc), I build a distance map cache layer. Each time
someone wants a distance map to a location, they call the
getDistMap(pos) function. The map then stores 100 distance maps in
its cache, ejecting little used maps when it fills up.
I still ran into a performance issue where, when the kobolds first
started running to pick up all the items, they'd have to build a whole
bunch of maps within a few turns, making for a noticeable lag in play
on slow machines. In this case, I know that any square with an item
on it is a potential goal location for some creature, so after level
building I just invoke getDistMap(item->pos()) on all items, thus
ensuring the cache is warm. The initial delay can then be shown with
a progress bar and, more importantly, there won't be a shudder in game
play.
(One problem is that it is rather expensive to find all adjacent
squares in Smart Kobold and Jacob's Matrix because of the potential
for map-linking portals everywhere)
--
Jeff Lait
(Smart Kobold: http://www.zincland.com/7drl/kobold)
Kusigrosz
> 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 in 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.
and propagate it, decreased somewhat, to its neighbours, and then to
theirs? One can then set a limit how far the signal has to propagate -
and for some applications this can be much less than the whole map.
I use a sound propagation algorithm, which I think is related to what
you describe. It uses a higher propagation cost for diagonal moves, so
in the open the affected areas look more like (octagonal) circles.
An example of a gradient map, showing at each cell the direction from
which the sound seems to be coming (0 means right, then clockwise):
http://tinyurl.com/ye2abw5
In the example above, the walls are blocking the sound; it is also
possible to make them attenuate it (but then it is obviously possible
that the apparent source direction may point to a wall).
I'm also going to use this algorithm if I implement smells.
>
> 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 my Roguelike:
>
> 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.
Will they make for the hole in the wall that the player made around
the corner (so they can't see it) a few turns ago with his spell of
silent digging?
--
Kusi...@AUtorun.itvk.pl To send mail, remove 'AU' from the address
You see here a scroll labeled "3jFxeO63fj8"
Pender
Yes, the official Dijkstra algorithm uses a breadth-first search like
you describe. But how could you use it to set goal tiles to different
weights? For example, with autoexplore, I set items to have a goal
value of -10, while unexplored terrain has a goal value of 0. This is
so that the character will make a beeline for the items before
continuing with level exploration.
Also, I am not sure how to implement the fleeing behavior with a
breadth-first search. To get the initial distance map to the player,
sure. But the next step is to multiply by a number between -1 and -2
and run the result back through the algorithm, which means that the
further a tile is from the player, the more tempting of a goal it is
-- indeed, the strength of the algorithm is the interplay between
local and global maxima that the different goal weights enable. If
there is a way to do it with the more efficient algorithm, I'd be
interested to hear it.
Yes, this is a somewhat expensive operation as far as these things go.
I guess my philosophy is that as a developer, I would rather have a
great gameplay experience than a less interesting one that can run on
decades-old computers, but this is a matter of taste and development
priorities, and I'd likely feel differently if I had a user base on,
say, the gameboy advance.
I've also profiled my game repeatedly and the draw routine takes 90%+
of the resources demanded by the game, so that is where I have focused
my limited optimization efforts.
steev
> You see here a scroll labeled "3jFxeO63fj8"
I actually used a similar system at two points in my 7DRL
(Ravenous).
First: every square on the map stores a number representing the amount
of the player's smell that resides on it. When the player occupies a
square, its smell count is set to a high number (80 i believe). Each
turn this smell is spread out to all adjacent squares (unless they
already contain a higher smell count) and then reduced. Enemies have
a couple tiers of AI, first they randomly wander, then if they occupy
a square who's smell count is higher then their threshold they begin
following it by moving to the adjacent square with the highest smell
count. It works well, if the player waits in one room too long there
s good chance their smell will travel and draw enemies towards them.
Additionally there are ways to falsify the scent trail using certain
items to through off enemies you don't want to fight.
Second: If the enemy can see you then it creates what I called a
priority map, but its basically what has been described above. It
creates an array the size of the enemy's vision field and initializes
it to a high number. It then sets the player's position as 0 and
begins iterating over this map. Every time it finds an entry equal to
the iteration count, it looks at that spot's adjacent squares. If
their current value is higher than the iteration count, it set them to
the iteration count + 1. If the space is impassable, it does nothing.
It stops iterating over the map once the enemies position on the map
contains a value not equal to the default. The enemy then just moves
to the adjacent square with the lowest value.
This map is generated every turn (because other enemies are read as
impassable, and thus the path previously calculated can become
blocked) but only for enemies that can see the player. Additionally
the map is fairly small because enemies do not have a large vision
field. In fact the enemy can often not 'see' the player even if they
are in the same room, but they can still smell him so they approach,
just not along an optimal path.
Pender
> On 2010-03-17, Pender <penderpr...@gmail.com> wrote:
> Isn't it computationally cheaper to start with a high value at the goal
> and propagate it, decreased somewhat, to its neighbours, and then to
> theirs? One can then set a limit how far the signal has to propagate -
> and for some applications this can be much less than the whole map.
I'm not sure why propagating a high number downward should be cheaper
than propagating a low number upward. If the goal is to limit the
depth of the search, you can do that in any case by limiting the
difference between the goal cells and the ground state; it shouldn't
matter which number is high and which is low.
As Jeff said, a breadth-first search is also much more efficient. If
someone can come up with a way to implement different goal strengths
in the breadth-first search algorithm -- and I've learned never to
underestimate Jeff's algorithmic cleverness -- then that is a superior
method. I am certainly not wedded to the particular algorithm for
generating a Dijkstra map, and frankly I don't claim to know very much
about writing highly efficient code at all; the motivation for this
thread was the applications of the maps, which are capable of a lot
more than I had initially realized.
> I use a sound propagation algorithm, which I think is related to what
> you describe. It uses a higher propagation cost for diagonal moves, so
> in the open the affected areas look more like (octagonal) circles.
> An example of a gradient map, showing at each cell the direction from
> which the sound seems to be coming (0 means right, then clockwise):http://tinyurl.com/ye2abw5
> In the example above, the walls are blocking the sound; it is also
> possible to make them attenuate it (but then it is obviously possible
> that the apparent source direction may point to a wall).
>
> I'm also going to use this algorithm if I implement smells.
Yes, keeping track of the direction of the next step from each cell is
a valid way to store the results of a pathfinding sweep. I'd submit
that it's a little less powerful, depending on the application, since
you lose information when you switch from keeping track of the number
of steps to the target to keeping track only of the direction of the
next step. If you keep the numbers, you could, for example, set a
perception threshold for each monster such that a bat could track a
sound from across the level while an orc might only hear things that
originate within 30 spaces away.
In calculating a scent map, you might consider running only a couple
of passes of the Dijkstra scan per turn so that the smell diffuses
outward slowly. You'd also have to have it decay over time so that
fresher scents are more desirable to monsters. You could do that
either by lowering the scent values in all cells every turn or by
increasing the amount of scent that the player drops every turn,
depending on how badly you want the fastest possible code. That would
also be possible only if you store the numbers instead of just the
direction.
> Will they make for the hole in the wall that the player made around
> the corner (so they can't see it) a few turns ago with his spell of
> silent digging?
Yes, I suppose they will. Would that really bother you? I don't know
how to avoid it besides keeping track of each monster's level
knowledge and calculating a different safety map for every fleeing
monster every turn. To the extent that you're worried about speed, I
doubt you'll find that an impressive solution. But I wouldn't worry
about this issue. I don't think it will look unnatural to the player,
and in my opinion, that's all that should matter.
If you're worried about monster omniscience, a bigger problem is that
fleeing monsters will always know where the player is since the safety
map is updated every turn and every fleeing monster uses the same
safety map. I fixed that problem last night by giving the monster a
personal copy of the current safety map whenever it leaves the
player's field of view, which it uses until it re-enters the player's
field of view. I suppose you could also then avoid updating the
universal safety map unless a fleeing monster was currently in the
player's FOV.
Pender
> Second: If the enemy can see you then it creates what I called a
> priority map, but its basically what has been described above. It
> creates an array the size of the enemy's vision field and initializes
> it to a high number. It then sets the player's position as 0 and
> begins iterating over this map. Every time it finds an entry equal to
> the iteration count, it looks at that spot's adjacent squares. If
> their current value is higher than the iteration count, it set them to
> the iteration count + 1. If the space is impassable, it does nothing.
> It stops iterating over the map once the enemies position on the map
> contains a value not equal to the default. The enemy then just moves
> to the adjacent square with the lowest value.
> This map is generated every turn (because other enemies are read as
> impassable, and thus the path previously calculated can become
> blocked) but only for enemies that can see the player. Additionally
> the map is fairly small because enemies do not have a large vision
> field. In fact the enemy can often not 'see' the player even if they
> are in the same room, but they can still smell him so they approach,
> just not along an optimal path.
You could generate a single map to the player every turn and have all
monsters that can see the player use that map. One nice advantage of a
distance map over A* is that for a given set of goal points, the same
map works for all starting points.
Jeff Lait
> On Mar 18, 9:44 am, Jeff Lait <torespondisfut...@hotmail.com> wrote:
>
> > Note that since all your distances between cells are 1, you don't need
> > a priority queue. If you want variable distance costs (terrain costs,
> > etc) you'd have to replace that dequeue, and you'll have to test if
> > the new distance is smaller or not.
>
> Yes, the official Dijkstra algorithm uses a breadth-first search like
> you describe. But how could you use it to set goal tiles to different
> weights? For example, with autoexplore, I set items to have a goal
> value of -10, while unexplored terrain has a goal value of 0. This is
> so that the character will make a beeline for the items before
> continuing with level exploration.
To confirm: wouldn't that cause the player to ignore an item 20
squares away if there is an unexplored square 5 squares away?
(I'd personally reserve negative numbers for uninitialized, but you
could always do MAX_INT or something if you want.)
As to how to do that: switch to a priority queue instead of dequeue.
Take all your goals, add them to the queue with their distances.
When you pull something off the queue, re-check the distance you
stored for it. If its current map distance is less than the value you
put on the queue, throw it out as already processed. Otherwise, check
neighbour squares. If they are uninitialized, set and add to the
queue the distance. If they have a distance, compare with your new
computed distance (your square + 1). If the new distance is better,
store it on the map and add to the priority queue.
> Also, I am not sure how to implement the fleeing behavior with a
> breadth-first search. To get the initial distance map to the player,
> sure. But the next step is to multiply by a number between -1 and -2
> and run the result back through the algorithm, which means that the
> further a tile is from the player, the more tempting of a goal it is
> -- indeed, the strength of the algorithm is the interplay between
> local and global maxima that the different goal weights enable. If
> there is a way to do it with the more efficient algorithm, I'd be
> interested to hear it.
Start with the player as a goal. Run the algorithm to build a
distance map.
Now, build a new distance map. But set as a "goal" every value from
your old distance map times the magic number. (Ie, your priority
queue starts with every touched tile in your game) Run the algorithm.
> Yes, this is a somewhat expensive operation as far as these things go.
> I guess my philosophy is that as a developer, I would rather have a
> great gameplay experience than a less interesting one that can run on
> decades-old computers, but this is a matter of taste and development
> priorities, and I'd likely feel differently if I had a user base on,
> say, the gameboy advance.
I'm no fan of premature optimization. However, as I understood the
algorithm, you may run into serious issues on large maps or with lots
of independent maps. This may be fine for your game, but since these
maps are incredibly powerful, I'd want to help ensure they are
available for all types of games.
My optimization attempts on distance maps came first from in
Fatherhood, where I added large 500x500 maps and saw performance
plummet. The second round was Smart Kobold, where I had every kobold
all decide to build a distance map to the nearest item within a few
turns of each other.
The advantage of the priority queue approach would, I think, be
relatively significant. Giving a map that is N x N, and with a
maximum path length of D, I would expect your algorithm to take D
passes to converge, so be O(D N^2). The priority queue search touches
each cell once, for N^2, but its cost is only a log term on the length
of the queue. Obviously bounded by N^2, so lg(N^2), or O(lg(N)). For
an empty map, D == N, so your best case for iterations is O(N^3) vs
O(lgN N^2). (The dequeue based approach is a plain O(n^2)) For a
labyrinth map, D can be much higher, right up to O(N^2) itself, so
your worst case is O(N^4).
Interestingly, on the gameboy advance one of my path find approaches
better mirrored your system. Since the maps are 32x32, I used 32
integers to store a collison mask of doors. Then I had another set of
32 integers to store where the avatar was. I started with 1 bit at
the avatars location. Then I repeated bitshift and bit-wise or
operations to grow the avatar map, each time bitwise-anding it against
the collision mask, until my goal bit was set. Then the previous
version of the avatar map could be tested to see which direction was
the best one to the goal. The 32x multiplier of working with an
entire row at a time I hoped would outweigh the higher O notation.
And I thought the approach was cute :>
I eventually disabled it as too slow, replacing instead with a
distance map. I used, I think it was Bear's suggestion, of building
the distance map when building FOV. Whenever a square is potentially
visible to the avatar, you update it with the timestamp minus the
distance to the avatar. People who want to follow the avatar just go
up hill on this map. It has the nice effect that creatures don't
learn of your new wand digging, and that when you teleport they don't
know your new location but head to your old one. And there is no
speed cost as it comes for free during FOV building.
> I've also profiled my game repeatedly and the draw routine takes 90%+
> of the resources demanded by the game, so that is where I have focused
> my limited optimization efforts.
I really think it is important to profile your engine separate from
the draw speed. The draw speed is a frame-to-frame number, and so
tends to dominate just because of keyboard delays, etc. The reason
why you want your actual game engine taking as close to 0 time as
possible is to ensure there is no latency from the user hitting a key
and the @ moving.
Distance map computation, especially if you are caching it, can appear
to be 1% on the profile yet be quite significant on the gameplay if it
introduces "stutters" where suddenly the @ delays 1/10th of a second
when it normally moves instantly.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
Ray
> My optimization attempts on distance maps came first from in
> Fatherhood, where I added large 500x500 maps and saw performance
> plummet. The second round was Smart Kobold, where I had every kobold
> all decide to build a distance map to the nearest item within a few
> turns of each other.
That's actually a fairly interesting problem on a large map. But
I think there's a reasonably effective solution to the multi-pathfinding
effect you want. I guess first you have to decide what the goal is.
If the goal is for each kobold to pick up one thing as quickly as
possible (and having picked up one thing let other kobolds grab
the other things) then it's fairly tractable. Here's my proposed
solution.
There's a distance map for each and every item. You let each item
be the "goal point" of one map, and expand their gradients (in
synchronized fashion, one step at a time) until, in any map, you
find one kobold. Whichever item's expanding field encounters
whichever kobold, that is the kobold who can get to that particular
item first (and that item is the first one he can get to). You
then run the gradient downhill from the kobold to the item, and
store the resulting path as the kobold's movement plan.
You now know that this kobold will get his item so you ignore him
from now on. Also, that item is accounted for so you have no need
to continue to expand its gradient. In practice most of these
maps will wind up being quite small; probably all of them, assuming
the number of items and kobolds is not close to equal. You continue
until you run out of items or run out of kobolds.
Note: This is the more efficient way if there are more kobolds on
the map than items. If you have more items than kobolds, you would
start with a distance map from each kobold (to an item) rather than
from each item (to a kobold). But going the "wrong" direction
shouldn't make a huge difference in efficiency, and either way as
long as the number of kobolds and items isn't close to equal it will
be quite efficient.
At this point every kobold has a planned route to whichever item he
can actually be the first one to get to. The effect is to minimize
the average (turn count * item count) of items left lying on the
floor, although if the number of items and kobolds is about equal,
the last few items may stay on the floor for a longish time as
their claimant treks halfway across the dungeon past sites where
other kobolds nabbed items that he couldn't have been the first to
reach. And kobolds that can't be the first to get to any item know
they can't (don't have planned routes to "their" item), which frees
them to pursue other goals.
This algorithm also has the nice property that the planned routes
will never conflict on the map; you won't ever have two different
kobolds on their planned routes trying to go in opposite directions
in the same corridor.
Of course this semi-elegant solution disregards possible interference
by the player. :-)
> The advantage of the priority queue approach would, I think, be
> relatively significant. Giving a map that is N x N, and with a
> maximum path length of D, I would expect your algorithm to take D
> passes to converge, so be O(D N^2). The priority queue search touches
> each cell once, for N^2, but its cost is only a log term on the length
> of the queue. Obviously bounded by N^2, so lg(N^2), or O(lg(N)). For
> an empty map, D == N, so your best case for iterations is O(N^3) vs
> O(lgN N^2). (The dequeue based approach is a plain O(n^2)) For a
> labyrinth map, D can be much higher, right up to O(N^2) itself, so
> your worst case is O(N^4).
I think your analysis is correct, where N is the radius of the map.
> I eventually disabled it as too slow, replacing instead with a
> distance map. I used, I think it was Bear's suggestion, of building
> the distance map when building FOV. Whenever a square is potentially
> visible to the avatar, you update it with the timestamp minus the
> distance to the avatar. People who want to follow the avatar just go
> up hill on this map.
Yep, that was me.
> It has the nice effect that creatures don't
> learn of your new wand digging, and that when you teleport they don't
> know your new location but head to your old one. And there is no
> speed cost as it comes for free during FOV building.
Right. Another nice thing, IMO, is that there's no need to update
squares that are out of sight (obstacle or radius) from the player;
that puts a pretty close limit on the amount of work you have to do
per turn, regardless of the size of your map. When the player arrives
on the map if you want nightmare mode, or when the player does
something that specifically sets off an alarm otherwise, you can
iterate through the whole dungeon creating a distance map to the
player. Then ordinary FOV calculations will keep the monster
pathfinding updated pretty well. If you don't want nightmare mode,
just start with a zeroed distance map and the player will get more
exposed to monster pathfinding the more he explores, which I like.
Bear
Pender
> > Yes, the official Dijkstra algorithm uses a breadth-first search like
> > you describe. But how could you use it to set goal tiles to different
> > weights? For example, with autoexplore, I set items to have a goal
> > value of -10, while unexplored terrain has a goal value of 0. This is
> > so that the character will make a beeline for the items before
> > continuing with level exploration.
>
> To confirm: wouldn't that cause the player to ignore an item 20
> squares away if there is an unexplored square 5 squares away?
Yes. Now that I think about it, I actually use -100.
> (I'd personally reserve negative numbers for uninitialized, but you
> could always do MAX_INT or something if you want.)
Yep, I use 30,000 -- that way using my algorithm there is no need to
distinguish between uninitialized cells and cells that have been
marked by an inferior route. I definitely want to leave negative
numbers available for use: these Dijkstra maps are so useful that I
want to keep the option open of running all kinds of crazy operations
on them without having to sanitize them afterwards. Multiplying by a
negative number to calculate safety maps is a perfect example.
> The advantage of the priority queue approach would, I think, be
> relatively significant. Giving a map that is N x N, and with a
> maximum path length of D, I would expect your algorithm to take D
> passes to converge, so be O(D N^2). The priority queue search touches
> each cell once, for N^2, but its cost is only a log term on the length
> of the queue. Obviously bounded by N^2, so lg(N^2), or O(lg(N)). For
> an empty map, D == N, so your best case for iterations is O(N^3) vs
> O(lgN N^2). (The dequeue based approach is a plain O(n^2)) For a
> labyrinth map, D can be much higher, right up to O(N^2) itself, so
> your worst case is O(N^4).
I think this assumes that each pass in my method commits its changes
to the map only once the entire pass is complete, as would be the case
with a cellular automata program in which each generation needs to be
segregated from the next. In fact, changes can cascade across the map
in a single pass. The best case for me would be an empty map with a
goal point in the upper-left, in which case a single pass would fill
the entire map and a second pass would confirm that no further changes
were needed. I've leveraged these cascade savings in Brogue by having
every other pass reverse the direction -- even passes go top to bottom
within each column and left to right across the screen, and odd passes
go bottom to top within each column and right to left across the
screen. I'm not sure how that affects your conclusion; at least, the
savings aren't quite as high as you suggest, but I'd venture that your
method is probably still substantially superior.
> I eventually disabled it as too slow, replacing instead with a
> distance map. I used, I think it was Bear's suggestion, of building
> the distance map when building FOV. Whenever a square is potentially
> visible to the avatar, you update it with the timestamp minus the
> distance to the avatar. People who want to follow the avatar just go
> up hill on this map. It has the nice effect that creatures don't
> learn of your new wand digging, and that when you teleport they don't
> know your new location but head to your old one. And there is no
> speed cost as it comes for free during FOV building.
Yes, I use the same method -- it's a great little innovation.
Unfortunately, I don't know how to translate its advantages to other
problems like fleeing that require monsters to have some understanding
of the dungeon layout apart from what the player has seen.
> I really think it is important to profile your engine separate from
> the draw speed. The draw speed is a frame-to-frame number, and so
> tends to dominate just because of keyboard delays, etc. The reason
> why you want your actual game engine taking as close to 0 time as
> possible is to ensure there is no latency from the user hitting a key
> and the @ moving.
I'm not sure I understand this. It's pretty easy in my profiler to
distinguish between cycles spent drawing and cycles spent waiting for
keyboard input. Drawing still takes 90%+ of the time between when the
game registers an input and when the results appear on the screen.
Sure, all else equal, a fast game engine is better than a slow game
engine -- but there's tons more room for improvement in drawing than
in pathfinding, programmer time isn't costless, etc. And I don't think
there are any cases where a freakish number of maps would suddenly
need to be calculated in a single turn. Item maps, as you say, should
be generated when the level is created and updated only when an item
moves.
Anyway, if pathfinding inefficiency stresses you out, witnessing the
atrocities I commit to calculate lighting every turn would probably
give you a stroke :)
jice
> Mac, but so far neither has happened. Someone did put together a Linux
> and Windows port from scratch. I linked to them from the Brogue
> homepage but have heard conflicting reports about their speed and
> Again, frustrating, because Brogue doesn't have a single platform-
> I've even documented them all --http://sites.google.com/site/broguegame/Broguemachdepguide.pdf?attred...
> -- but I'm at the mercy of strangers on this one.
The svn trunk version of libtcod now features a cmake compilation
system that is said to be able to compile an XCode compatible libtcod.
But this apart, I've no idea how. You should try to see if Chris can
help you on this. His blog is :
http://iferrorthrownewbrick.blogspot.com/
--
jice
Pender
> The svn trunk version of libtcod now features a cmake compilation
> system that is said to be able to compile an XCode compatible libtcod.
> But this apart, I've no idea how. You should try to see if Chris can
> help you on this. His blog is :http://iferrorthrownewbrick.blogspot.com/
Thanks -- I will take a look tonight.
Kusigrosz
> On Mar 18, 10:01 am, Kusigrosz <Kusigr...@AUtorun.itvk.pl> wrote:
>> On 2010-03-17, Pender <penderpr...@gmail.com> wrote:
>
>> Isn't it computationally cheaper to start with a high value at the goal
>> and propagate it, decreased somewhat, to its neighbours, and then to
>> theirs? One can then set a limit how far the signal has to propagate -
>> and for some applications this can be much less than the whole map.
>
> I'm not sure why propagating a high number downward should be cheaper
> than propagating a low number upward. If the goal is to limit the
> depth of the search, you can do that in any case by limiting the
> difference between the goal cells and the ground state; it shouldn't
> matter which number is high and which is low.
limited to the neighbours, not whether the value goes up or down.
Only cells that need visiting are touched - with typical sound range
of 10 and level size 160x128 I prefer to avoid scanning it all.
> As Jeff said, a breadth-first search is also much more efficient. If
> someone can come up with a way to implement different goal strengths
> in the breadth-first search algorithm -- and I've learned never to
> underestimate Jeff's algorithmic cleverness -- then that is a superior
> method.
I'm not sure if I understand what you mean by different goal strengths.
Can it be represented by something like scalar potentials in physics,
each depending only on the distance from its point source, but possibly
in a different way? If that is right, one could only build distance
maps to each source in the fastest way, and then use the different
formulae for each of the potentials only when finding the gradient
at the monster's cell. Calculating for the current cell and each of
its 8 neighbours the sum:
sum[cell] = foo_desire(foo_dist[cell]) + bar_desire(bar_dist[cell]) + ...
and finding the direction in which this sum increases fastest.
> I am certainly not wedded to the particular algorithm for
> generating a Dijkstra map, and frankly I don't claim to know very much
> about writing highly efficient code at all; the motivation for this
> thread was the applications of the maps, which are capable of a lot
> more than I had initially realized.
>
>> I use a sound propagation algorithm, which I think is related to what
>> you describe. It uses a higher propagation cost for diagonal moves, so
>> in the open the affected areas look more like (octagonal) circles.
>> An example of a gradient map, showing at each cell the direction from
>> which the sound seems to be coming (0 means right, then clockwise):
http://tinyurl.com/ye2abw5
>> In the example above, the walls are blocking the sound; it is also
>> possible to make them attenuate it (but then it is obviously possible
>> that the apparent source direction may point to a wall).
>>
>> I'm also going to use this algorithm if I implement smells.
>
> Yes, keeping track of the direction of the next step from each cell is
> a valid way to store the results of a pathfinding sweep. I'd submit
> that it's a little less powerful, depending on the application, since
> you lose information when you switch from keeping track of the number
> of steps to the target to keeping track only of the direction of the
> next step. If you keep the numbers, you could, for example, set a
> perception threshold for each monster such that a bat could track a
> sound from across the level while an orc might only hear things that
> originate within 30 spaces away.
Oh, I do keep the intensities, in fact the direction map is generated
from the intensity map. I just thought the direction numbers are going
to give a more readable picture; the test program displays intensities
encoded as letters, so it looks like a player surrounded by a lot of
various monsters.