A* Pathfinding is necessary afterall?
Todd Page
decided to implement it in my RL. (As of now a nameless "sandbox" RL
written in python)
Up until now, it has worked great. Starting at the player square, you
can do a simple recursive crawl via adjacent squares and fill them
with decreasing values of "smelliness". Since it is blocked by
obstacles and flows down corridors it is simple for a monster to use
it to find the player. Just look for the "smelliest" near-by square
and walk to it. As an added bonus I read an older "collaborative
diffusion" article and made other monsters smell-blocking as well. Now
monsters were surrounding the player without me having to tell them to
do that.
So, naturally this is great, and I figured I could get away without
any kind of explicit pathfinding like A*. But now that I look at
making some more robust AI things get tricky. What if the monster
wants to walk somewhere where the player isn't? I can think of a few
examples of this:
1. walk to a random room (wander mode)
2. walk to the place you last saw the player (this is somewhat
mitigated by the floodfill nature of the "smell path")
3. walk towards a non-smelly player (e.g. they just teleported in)
Most importantly to me is #1. I'd like to have different basic
behaviors for "idle" monsters. Some will sleep, some will wander
randomly, and others will "patrol" -- pick a random room and walk to
it.
So, am I right in that explicit pathfinding is required? Or am I
missing something here?
PS: the FOV/scent-based pathfinding thread I am referring to is:
https://groups.google.com/group/rec.games.roguelike.development/browse_thread/thread/bf4b9d4d7f18c42f?tvc=2
Gelatinous Mutant Coconut
There are a lot of techniques you can use for this. The most simple is
to just have the monster move into an unoccupied adjacent square each
turn; this behavior doesn't look that natural if the player can
observe it (with, say, telepathy), but is enough if all you want is
for monsters clumped together in a single room to eventually diffuse
across the entire dungeon. Another very simple wandering technique is
to have monsters follow walls; this is enough to get your monsters to
visit all rooms as long as your dungeon has no loops. If your dungeon
DOES have loops, you could give monsters following walls a % chance
each turn of leaving the wall they are currently following, and let
them random-walk until they bump into a new wall to follow.
There are plenty of other methods, of course.
> 2. walk to the place you last saw the player (this is somewhat
> mitigated by the floodfill nature of the "smell path")
Do you recalculate the scent map entirely each turn? If you instead
have the player set the scent value of the tile they are on each turn,
and then have scent values diffuse from tiles with stronger scent
values to adjacent tiles with weaker scent values (with some % scent
lost), then the monster will follow the scent to where the unseen
player last was, even if the player teleported away after ducking
behind a corner. (Kind of similar to a fox jumping onto a fence or
across a stream to put foxhounds off it's trail.)
If you explicitly want to go to where the player was last "seen",
you'd need to have each monster remember the tile where the player was
last seen, and go towards that tile if the player isn't within line-of-
sight.
> 3. walk towards a non-smelly player (e.g. they just teleported in)
If the monsters can see the player, they don't need to smell the
player. Any time a monster has a direct line-of-sight to the player,
just have the monster move in a direction that takes it closer to the
player. (You may want to experiment with making other monsters count
as blocking the line-of-sight as well as wall tiles, so that monsters
still use the smarter scent-swarming paths if there isn't a direct
line to the player.)
There shouldn't be any need to implement A* pathfinding to do anything
you want to do; in fact, you'll probably get more interesting monster
behavior, since their paths WON'T always be mathematically optimal.
You will want to have some form of line-of-sight testing capability,
though; you COULD add a scent for every room, door, item and stairway
that monsters might be interested in, but it might become
computationally burdensome. (If you do go that way, the first
optimization you'd want to do is to only calculate the scents of
things that monsters currently in your dungeon are actually interested
in.)
Jotaf
<gelatinousmutantcoco...@gmail.com> wrote:
> ... you COULD add a scent for every room, door, item and stairway
> that monsters might be interested in, but it might become
> computationally burdensome. (If you do go that way, the first
> optimization you'd want to do is to only calculate the scents of
> things that monsters currently in your dungeon are actually interested
> in.)
I just thought of a method to make them wander the rooms using scent
diffusion. Have a single scent map, and the center of each room
diffuses smell. A monster can have two states: going "uphill" or
"downhill" (in the direction of more or of less scent). When a local
minimum (all adjacent tiles higher) or maximum (all adjacent tiles
lower) is reached, switch states.
They'll sometimes just go to the middle of the corridor between two
rooms and turn back, like they're just checking, but half the time
they'll move on to the other room.
Also the rooms don't change places so after about (max
(map_width,map_height) iterations you can stop updating the scent map,
making this perhaps one of the most lightweight wandering algorithms
of all times :)
Jotaf
Mingos
You'd have to be careful not to let the monster wander away from the
room's center towards a wall with no doors in it. In the room's
corner, it'll hit a local minimum and get back to the room's centre
again. They should know where to go to find a corridor. Apart from
that, it's an interesting idea.
Mingos
Nathan Stoddard
> 1. walk to a random room (wander mode)
There are some algorithms that would work for this on
http://www.astrolog.org/labyrnth/algrithm.htm. The algorithms there are
meant for generating and solving mazes, but some of the maze solving
algorithms might do what you want.
> 2. walk to the place you last saw the player (this is somewhat
> mitigated by the floodfill nature of the "smell path")
> 3. walk towards a non-smelly player (e.g. they just teleported in)
You might be able to use some of the maze solving algorithms here, too,
but you might need actual pathfinding. If you want to learn how to
implement A*, look at
http://www.policyalmanac.org/games/aStarTutorial.htm.
--
Nathan Stoddard, http://nathanstoddard.com
Gelatinous Mutant Coconut
> You'd have to be careful not to let the monster wander away from the
> room's center towards a wall with no doors in it. In the room's
> corner, it'll hit a local minimum and get back to the room's centre
> again. They should know where to go to find a corridor. Apart from
> that, it's an interesting idea.
What if you have "doorways" (which may or may not have doors, but I
can't think of a better term for "tiles that can be used to enter and
exit a room") as the scent sources, instead?
(Simplified model, rendered in ASCII)
##########
#66666678#
#55555678#
#4444#####
#33333334#
#32222234#
#32111234#
####+########
#321112321#1#
#322222321+1#
#321112321#1#
####+########
#3211123#
#3222223#
#3333333#
#########
That looks like it should work pretty well, actually; here are the
behaviors I predict (using the rule that a monster flips whether it is
going up or down gradient when there are no moves available that will
place it on a tile with a strictly greater / lesser scent value,
respectively):
- A monster that enters a dead-end room will go walk towards a wall,
then head back to the doorway.
- A monster that enters a room connected to other rooms will sometimes
visit a wall and then go towards a doorway (possibly the one it
entered from), and sometimes head towards a midpoint between the door
it entered from and another doorway, and then go towards one of those
doorways.
Honestly that seems like a pretty sensible patrol pattern.
One final thought: You might want to make hidden doors not give off a
scent, or at least give off a significantly reduced scent compared to
obvious doors and doorways. Monsters patrolling using scent gradients
will still sometimes have a chance to discover these hidden doors if
they happen to wander towards the wall that contains the hidden door,
which I think would be kind of cool. (You could even do something
similar in reverse, like an illusionist monster that hides doors that
it encounters.)
rdc
> So, am I right in that explicit pathfinding is required? Or am I
> missing something here?
>
Not necessarily.
http://rickclark58.googlepages.com/implementingroutingnodes
Yeah, I know, I keep bringing that up. :)
--
Rick Clark
Clark Productions: http://rickclark58.googlepages.com/
Mingos
Sensible. A simple and CPU-efficient solution (precalculation would
only take place upon loading the map), and the monster movement would
be pretty natural too. I would suggest a certain level of randomness
though. A single tile might have more than one neighbour with a higher/
lower scent value. The monster might consider all such cells, not only
just the highest/lowest one, and choose a random one from the eligible
set. This way, it will always reach the absolute minimum/maximum
tiles, but following slightly different routes.
Another idea that's just hit me is the drunken/confused monster
effect. Before each move, shift the current tile's scent value up or
down by a random number and then check the surrounding cells. The
monster might take a step in the wrong direction and possibly continue
towards the scent source, or believe it has reached the absolute
minimum/maximum and start walking (trying to walk) in the opposite
direction. The larger the shift value, the more visible the "drunken
monster" effect. With large shift values, the monster will end up
staggering around randomly.
Mingos
Todd Page
Hrm... that's an interesting idea. I'm wondering if it would be more
or less interesting if you used random points on the map to diffuse
from instead of doors. (Maybe this is getting into rdc's "nodes"? I
can't get to the link from my current site) Or perhaps you could do
both. Basically you'd just be doing a giant flood-fill once per level
to set up a inherent scent pattern, and monsters could use that to
wander when they don't have anything better to do (e.g. go towards the
player).
Responding to Gelatinous Mutant Coconut: currently I am re-calculating
the scent grid each time the player moves, and decrementing it each
turn where he does not move. Your idea might work better for me. Just
set each new square the player lands on to '100' and then each turn
run some sort of algorithm each turn that diffuses this property. I'm
not sure if the CPU would end up doing more, less, or about the same
amount of work though; I'll have to think through it.
Thanks for the ideas so far guys. Looks like I will have plenty of fun
things to noodle on this weekend!
Mingos
> Responding to Gelatinous Mutant Coconut: currently I am re-calculating
> the scent grid each time the player moves, and decrementing it each
> turn where he does not move. Your idea might work better for me. Just
> set each new square the player lands on to '100' and then each turn
> run some sort of algorithm each turn that diffuses this property. I'm
> not sure if the CPU would end up doing more, less, or about the same
> amount of work though; I'll have to think through it.
This might be a big task for the CPU if your maps are big enough and
there are enough other calculations, such as FOV, light sources,
perhaps some advanced mob AI. On a small map with no light sources,
you'll probably note no speed decrease, unless of course you happen to
make the diffusion code inefficient enough to be too slow on its own,
but that seems unlikely (there isn't much philosophy behind it). You
might also consider the possibility of recalculating and diffusing the
scent once per X turns only.
In my case, for instance, I have a serious obstacle in the form of an
extremely CPU-heavy display routine. Any extra calculations might
result in a visible slowdown, so I try to avoid them. If I ever
implement scent tracking, I'll recalculate it every 5 or 10 turns,
probably. The player won't notice anyway :).
Mingos
Kusigrosz
> Another very simple wandering technique is to have monsters
> follow walls;
algorithms that rely on wall following, google "bug algorithms".
They usually navigate in R2 without any grid, as they are used for
robot navigation. Examples:
Bug1, Bug2: classical wall followers that make ugly paths.
VisBug: Uses vision for shortcuts (Where would Bug2 go from here?
Lets go straight there), quite nice paths,
TangetBug: Also uses vision, also nice paths,
I-bug: No vision needed, I think this is related to scent navigation.
Both Visbug and TangentBug require at least partial FOV (or LOS
towards N cells, where N is of the order of the vision range) for
the navigating monster each turn.
A nasssty problem which I encountered implementing a relative
of VisBug (reinventing the wheel, of course...) on a grid is that,
with Bresenham LOS, it is possible to lose sight of the goal while
taking a step towards it.
--
Kusi...@AUtorun.itvk.pl To send mail, remove 'AU' from the address
You see here a scroll labeled "Q-e0fHUoKD8"
Pender
maps generated with cellular automata methods as described here:
http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
With the right settings, those maps are beautiful, interesting, good
for gameplay and don't adhere to a bunch of map generation method
quirks that let the player predict what things will look like around
the next corner. The downside is that, as the developer, you can't
seed it with metadata as it is generated. So unlike with a room-and-
corridor dungeon, you (the developer) don't know in advance where the
doors will be, or even if the map will have any features that you
could conceptualize as doors.
So it's hard to make monsters wander randomly but purposefully on one
of those. Unless you want to just pick a random spot on the map, have
the monster A* its way over to it, and then repeat (which offends my
sensibilities), you have to either come up with a really clever
solution or grind out a beast of an algorithm.
I did the latter. It's a waypoint system. Start with a single
waypoint. Draw a FOV map from that point outward, probably with a
fairly low max radius. Mark which of the squares that are now visible
are on the "edge" of visibility -- i.e. have a floor tile that has not
yet been seen next to it. Mark that one as a waypoint, augment your
existing FOV map with another FOV sweep from that point, and repeat
until there are no more floor tiles that haven't been marked as seen.
Now every floor tile in your map is visible from at least one
waypoint. Then you can either have each waypoint keep track of the set
of waypoints that are visible from it or you can have monsters
calculate that on the fly when they stand on a waypoint based on their
own movement constraints. Obviously this latter approach is necessary
when the monster isn't starting from a waypoint. The waypoint
generation itself has to be done with the lowest common denominator
monster movement -- chasms, lava etc. should block waypoint LOS even
if there are some monsters that can cross them. Have monsters keep
track of where they are going AND where they are coming from, and
whenever they reach their destination waypoint, choose a new one at
random with a strong bias against returning to the one they're coming
from.
Then you have to tinker with their movement algorithm so it more or
less matches a Bresenham line or they'll get stuck on the way. I also
did a monte carlo sample to determine which squares on the map were
visible from the most other squares and biased my random selection of
"edge" visible tiles to prefer more prominent tiles so that fewer
paths would brush dangerously against complicated wall surfaces and
risk getting the monster stuck. If a monster does get stuck -- and
they always will at least sometimes -- it should pick a new waypoint
from where it is standing or pick a random tile it can see (using
passability as a visibility constraint) and have it move to that
square and try again.
Then if you have classical dungeon rooms interwoven with the CA
cavern, and if you pre-generate waypoints in doorways, which I do to
make dungeon wandering smoother, and if doorways can form on opposite
sides of the CA cavern without connecting tunnels, then you have to do
further tricks to make sure the entire waypoint network is connected.
After all that it works pretty well, but I bet there are simpler and
more efficient approaches. That VisBug thing looks pretty interesting,
and I'd be curious to hear if anyone's gotten it to work.
Joshua Day
> Up until now, it has worked great. Starting at the player square, you
> can do a simple recursive crawl via adjacent squares and fill them
> with decreasing values of "smelliness".
>
>
> So, naturally this is great, and I figured I could get away without
> any kind of explicit pathfinding like A*. But now that I look at
> making some more robust AI things get tricky. What if the monster
> wants to walk somewhere where the player isn't? I can think of a few
> examples of this:
You aren't limited to one smell or one type of diffusion. The first
thing to notice is that diffusion is a variant of Dijkstra's algorithm.
Dijkstra's and A* are at two ends of a spectrum: Dijkstra's finds all
paths from one point and A* finds one path between two points.
Anything you can find with one of them, you can find with the other.
If you think you can make A* do something you can't make diffusion do,
ask yourself: what are you telling your A* implementation that you
aren't telling your diffusion? For instance, if you want diffusion
to wander around rooms, you'd better tell it about rooms! Make your
data structures line up with what you're interested in, or you'll get
hokey results.
> 1. walk to a random room (wander mode)
There was a discussion not long ago about wander mode. Given a network
of rooms and corridors, how could a collection of monsters
collaboratively patrol the dungeon? My suggestion was this: When a
monster visits a room it clears the stench in that room to zero, but
over time the stench both rises and diffuses. With nothing more
complicated than that (and a few traffic rules to keep halls from
jamming up), every room in your dungeon will be patrolled in a timely
fashion.
> 2. walk to the place you last saw the player (this is somewhat
> mitigated by the floodfill nature of the "smell path")
Why have monsters walk to where the player was? You're not limited to
that kind of reasoning! If the player disappears from sight, wipe every
cell in the monster's FOV. Now, places where the player might have gone
start to radiate their smell back in, and the monster will go the most
convincing direction. As a general rule, your scent map represents two
things: one, how to get to the player; two, where the player could be.
If you want, you could actually split them into two separate diffusion
maps. Conceptually, it's just like the wander mode: when a monster
checks whether the player could be there, you clear it; when the player
is actually found, you clear everything else.
> 3. walk towards a non-smelly player (e.g. they just teleported in)
Rather than diffuse one step every turn, or some fixed number of steps
every turn, you can diffuse until the diffusion is 'good enough'. If
someone teleports, change the number of iterations. If you need to
speed it up, you can keep a list of dirty edges, as per Dijkstra's
algorithm. You don't need to speed it up, though. Seriously, try
running it a few hundred times every turn the player takes. You
probably won't notice it. Worry about speed once speed becomes a
problem.
This stuff is limited by imagination. You can have a diffusion map for
exploration, a map for player-catching, a map for treasure-gathering, a
map that represents that an area of the board is controlled tactically,
etc.
--
Joshua
Gelatinous Mutant Coconut
> I think the true test of any wandering system is whether it can handle
>
> With the right settings, those maps are beautiful, interesting, good
> for gameplay and don't adhere to a bunch of map generation method
> quirks that let the player predict what things will look like around
> the next corner. The downside is that, as the developer, you can't
> seed it with metadata as it is generated. So unlike with a room-and-
> corridor dungeon, you (the developer) don't know in advance where the
> doors will be, or even if the map will have any features that you
> could conceptualize as doors.
That's a very valid criticism of my doorway-scent proposal. :)
How about something a bit more general: The navigation scent of a
dungeon square is the shortest distance from that square to any wall.
(ASCII sketch below.)
############################################################
#####################################################11#####
#####11111##################111###############111111111111##
#####122211###########1####1121########11111111222222222211#
#####1232211#########11###11211###############1111233332211#
####1123322111111####11###1211###################123443211##
###122222222222211###1####121####################12344321###
##11232211112232211##1####121####################12344321###
##1222211##112222211#1###11211##################112344321###
##122211####1111222111##1122211################11223443211##
##12111########11222211112232211#######11######11223333221##
##111###########1122222222233211######111#######1122233211##
#########11######12111111122321######1121########11122321###
########111111111111#####112321#####11221##########112221###
#######112221#############123211111112221###########11221###
#######1223211############123221###1223211###########12211##
#######1232211###########1123321###1123221###########12221##
######1123211####11######1223321####1233211#########112211##
#####1122321####1111#####1123321####122222111111111112221###
####11222221####122111####123221####12111122221#####11221###
####121111211###1122211###123211####111##111221######11211##
####111##11211###1111211#1123211###########1221#######11211#
#####1####12211#####11211122321############1221########1111#
##########12221######1222223321############1221#########11##
#########1123211#####12333333211##########11221#############
#########1122221####112222222221111#####11122211############
##########112211####1222111111112211###11222222111##########
###########1111#####11111######11211####11111122211#########
################################111##########11111##########
############################################################
Here are some simple AI routines to go with this system:
"Get Within N Squares of a Wall": Each turn, if on a cell with a nav-
value greater than N, move into a cell with a smaller nav-value; else,
callback some kind of "behavior finished; requesting new monster
behavior" function.
"Get M Squares Away from Walls if Possible": Each turn, if on a cell
with a nav-value less than M, move into a cell with a greater nav-
value; else, callback "behavior finished".
"Wander cells with nav-values between bounds NEAR and FAR": If cell
nav-value is less than NEAR, get NEAR squares away from walls; if cell
nav-value is greater than FAR, get within FAR squares of a wall;
otherwise, choose a random adjacent cell with nav-value between NEAR
and FAR and enter it.
"Hug Walls": As above, with NEAR = FAR = 1.
You could implement things like player scent and attraction or
repulsion from light source, holy auras, food, treasure, etc in the
same way, just using different distance maps. (For point-source
distance maps that change frequently or aren't shared between
monsters, you might get speed improvements by calculating a distance
by running A* paths to the item of interest as needed, rather than
generating a full distance map in memory; this is just an
optimization, however, so don't feel like you need to implement A* if
you're able to get acceptable speeds using a method you're more
comfortable with.)
Kusigrosz
> After all that it works pretty well, but I bet there are simpler and
> more efficient approaches. That VisBug thing looks pretty interesting,
> and I'd be curious to hear if anyone's gotten it to work.
kinda-sorta working, a few moths ago. I didn't know about VisBug then:
http://tinyurl.com/cobnzv
It is a relative of VisBug, as the 'bug' part uses a bit different
criterion. I'm not sure if it is complete (guaranteed to find a path
if one exists) as VisBug is. The code is a bit convoluted, and
the implementation I currently have in the game is simplified,
although it suffers (a bit) from the problem I mentioned in the
previous posting - so it is not complete is any sense of the word...
Pender
<gelatinousmutantcoco...@gmail.com> wrote:
> "Wander cells with nav-values between bounds NEAR and FAR": If cell
> nav-value is less than NEAR, get NEAR squares away from walls; if cell
> nav-value is greater than FAR, get within FAR squares of a wall;
> otherwise, choose a random adjacent cell with nav-value between NEAR
> and FAR and enter it.
I think this would result in a sort of purposeless brownian motion,
and I'm not sure what the distance from the nearest wall really adds.
If you look at the ASCII map you drew, the only really valid way to
have monsters wander purposefully around the map is to have them hug
the wall; any further out and there are areas that they will not enter
because they are too narrow. And having all the monsters walk with one
hand along the wall would look pretty weird, I think -- as if they
were attached to some sort of sliding leash or something.
Gelatinous Mutant Coconut
> I think this would result in a sort of purposeless brownian motion,
> and I'm not sure what the distance from the nearest wall really adds.
> If you look at the ASCII map you drew, the only really valid way to
> have monsters wander purposefully around the map is to have them hug
> the wall; any further out and there are areas that they will not enter
> because they are too narrow. And having all the monsters walk with one
> hand along the wall would look pretty weird, I think -- as if they
> were attached to some sort of sliding leash or something.
My thinking was that monsters that don't get within N squares of walls
would wander within a section of relatively open dungeon, and not
leave their 'territory'. (The sizes of those regions of connected
cells 2 or more squares from any walls do vary greatly in cellular
automata maps, but if monsters are placed randomly you should end up
with roughly the same monster densities in such open regions. Larger
open areas are going to give such monsters a greater opportunity to
swarm the player, though, so they will probably be more dangerous.)
Still, you're absolutely right that the behavior of any individual
monster is going to look relatively purpouseless; they need to at
least LOOK like they're not just jittering back and forth while
accomodating their odd love/hate relationships with dungeon walls. How
about if the choice of which cell to enter was strongly biased towards
moving in a similar direction to the direction of the monster's
previous move?
For example, say that in the previous move, the monster moved north.
This turn, if the monster can move north according to the current
behavior rules, it does so.
If it can't, it sees if it can move northwest or northeast and tries
to choose one of those.
If it can't, it sees if it can move west or east and tries to choose
one of those.
If it can't, it sees if it can move southwest or southeast and tries
to choose one of those.
If all of those options aren't available, the monster will backtrack
south.
You'd have to experiment with the exact rules (maybe following a north
move you'd have a 50% chance of first trying a north move and a 25%
chance each of trying a northwest or northeast move).
Ray
> So, naturally this is great, and I figured I could get away without
> any kind of explicit pathfinding like A*. But now that I look at
> making some more robust AI things get tricky. What if the monster
> wants to walk somewhere where the player isn't? I can think of a few
> examples of this:
> 1. walk to a random room (wander mode)
First of all, what's a room? With some dungeon generators it's
really obvious - with others, not so much. I mention it because
if you can come up with a criterion where you can find "rooms"
for wandering purposes in random caves, it would be extra-sweet.
The best way I can think of is using regions discovered via a
"floodfill with constraints" algorithm; they may not exactly
map to rooms.
> 2. walk to the place you last saw the player (this is somewhat
> mitigated by the floodfill nature of the "smell path")
Are you talking about marking the player's seen squares
with (turn_number * max_sight_range) - distance as you
do the player's FOV? That makes a good followable path
that will lead the monster straight to the point on which
the player stood last time there was LOS between monster
and player, but it doesn't go around corners etc unless
the player has peeked around those corners etc.
> 3. walk towards a non-smelly player (e.g. they just teleported in)
Just teleported in and around a corner or two, right?
Otherwise, the monster gets LOS on the player as soon as the
player has the monster in FOV. I dunno about this; I like
monsters not knowing exactly where you are right after you
teleport - it makes 'porting more tactically significant.
> Most importantly to me is #1. I'd like to have different basic
> behaviors for "idle" monsters. Some will sleep, some will wander
> randomly, and others will "patrol" -- pick a random room and walk to
> it.
> So, am I right in that explicit pathfinding is required? Or am I
> missing something here?
Well, if you have large dungeons, and you want monsters to be
able to navigate them competently (like picking a room on the
other side of the dungeon and walking there with reasonable
efficiency) you need to have some way for them to find their
paths. But it doesn't need to be A* or anything like it. There
are a lot of less computationally expensive ways to find a
good (not necessarily optimal) path, especially if you're
willing to do some precalculation.
The FOV/Scent method is good for chase-and-following the player,
but if you have more general navigation tasks you might want to
also consider precalculating some waypoints/regions.
For navigation purposes, We want a monster to be able to say,
"I'm in this region; my goal is in that region; where should
I walk?" So we can tell already that all tiles are marked with
a number to say what region they're in, so the monster (or
the map) can immediately tell what region the monster and its
goal are in. Regions are contiguous sets of tiles, large
enough that the square of the number of regions in the map
isn't intractable and small enough that local navigation
inside a region isn't intractable (some tuning for the size
maps your game generates may be in order).
In the map you have a two-dimensional "region table" where
regtab[region1,region2] gives region3, where region3 is the
immediate subgoal for a creature moving from region1 to region2.
This means that the monster standing in region1 consults the
map and discovers that in order to get to region2 (which is
any distance away across the map from here), it must move
through region3 (which is one of the regions bordering its
current region).
Now the monster has a much simpler subproblem; how can it get
to region3? In order to do this it has to know the location
of a tile that borders region3, and it has to pathfind within
its own region.
In-region pathfinding is a capability you will need anyway.
It can even be a very reduced or simple capability depending
on how your regions are selected. If you pick regions that
have every point in mutual FOV and straight-line walkable
to each other, it's trivial.
As for finding a square that borders region3, that should be
a pretty simple operation; you can have region1 store a table
of neighboring squares indexed by region (which avoids
floodfilling to find it) or just do a local search whenever
you need one until you find a square marked "region3." Either
way, just move toward that square.
Bear
David Damerell
>>1. walk to a random room (wander mode)
>There are a lot of techniques you can use for this. The most simple is
>to just have the monster move into an unoccupied adjacent square each
>turn;
If there's a bias towards picking a direction and tending not to
backtrack, it'll look better and produce effects faster. In particular, a
monster in a normal one-space corridor will naturally march down it and
emerge at the other end.
--
David Damerell <dame...@chiark.greenend.org.uk> Distortion Field!
Yesterday was Monday, October.
Today is Tuesday, October.
Tomorrow will be Wednesday, October.
Pender
> > 1. walk to a random room (wander mode)
>
> There was a discussion not long ago about wander mode. Given a network
> of rooms and corridors, how could a collection of monsters
> collaboratively patrol the dungeon? My suggestion was this: When a
> monster visits a room it clears the stench in that room to zero, but
> over time the stench both rises and diffuses. With nothing more
> complicated than that (and a few traffic rules to keep halls from
> jamming up), every room in your dungeon will be patrolled in a timely
> fashion.
This is true as such but I think would be unsatisfying as a solution
for wandering specifically. Where a monster goes is a (continuous)
function of where it is already, so you'd never see monsters wander
past each other. (One benefit to this is that I don't think you'd see
any traffic problems, at least not between wandering monsters).
With a single monster on the map, this approach would work
beautifully. But with a bunch, monsters would tend to split up the map
into individual regions and never really leave their region. To see
why, imagine a 3x3 grid of rooms (as in Rogue) and 9 monsters with one
starting out in each room. As one wandered to and out the door, the
room would begin to emit stench which would exhibit a local
gravitational effect on nearby monsters. But the one that just left
would likely still be the closest, so it would get back there first
and quell the stench. When you consider that movement direction is
purely a function of monster location, it's easy to see that two
adjacent monsters would never swap rooms; even if they could get past
each other in the hallway (not a hard problem, really; just allow them
to swap places), they never would, since the "wanderlust gradient" in
that hallway could point in only one direction or the other.
(If I'm wrong about this particular emergent behavior, I think the
only alternative is that monsters would "clump" together into a
decreasing number of balls of wax of increasing size.)
All that said, I think your insights are generally extremely well
taken. Djikstra-scanning as a means of layering monster desires is a
brilliant tool that I've been playing with a lot since your post. But
wandering specifically is uniquely compromised by being derived solely
from a continuous function of location.
One thing you could do is use the "stench" map as a probability
distribution that a wandering monster will pick a particular location
as its next A*-calculated destination. You do have to use A* (ew) but
at some point even I am willing to consider that my aversion to it may
be irrational.
Joshua Day
> This is true as such but I think would be unsatisfying as a solution
> for wandering specifically. Where a monster goes is a (continuous)
> function of where it is already, so you'd never see monsters wander
> past each other. (One benefit to this is that I don't think you'd see
> any traffic problems, at least not between wandering monsters).
> With a single monster on the map, this approach would work
> beautifully. But with a bunch, monsters would tend to split up the map
> into individual regions and never really leave their region.
This was precisely the intention of the original. It was meant to make
monsters partition the dungeon without overtly organizing them. The
original also worked on a set of rooms very much like rogue's, so
pathfinding within a room or from one room to an adjacent room were both
solved fine by Bresenham.
If you're working from a graph of rooms (instead of grid cells), you can
get around this by giving each monster its own memory. If you expect
one monster to remember fewer than fifteen rooms (or so), you don't have
to worry about how you're storing it. I could imagine keeping a list,
and the longer the list grows the more uneasy the monster becomes about
entering a room it's never been to, and removing rooms that are
unimportant and have not been visited in a long time.
Using some variant of your FOV-to-approximate-rooms, this could be made
to work in any environment.
I love your term "wanderlust gradient". One thing it makes clear (to
me) is that we can have one gradient describing how much each place is
worth, by one measure or another -- that is, how much a monster should
want to go there -- and another gradient that describes the paths that
will lead to those desirable places. The wanderlust gradient does
something that A* cannot be made to do, because it represents reasoning
about the entire map, but the process of getting somewhere interesting
can be handled by A* just fine.
Interesting to ask what happens if you let flows block each other.
Imagine a desire map that can be blocked by a danger map (or possibly
transmuted into a hazard map by crossing it). It seems like some very
high-order decisions could be made this way. I'm trying to figure out
how to make an escape map -- something that warns a monster that it's
running into a dead end.
Dynamics like these cannot be added to a roguelike that was not designed
for them, of course. I don't want pillar dancing enemies in a game where
no one gets tired out, no one has better places to be, and no one can
charge or dash. There's got to be a reason that pillar dancing never
works in real life, and that's one point of realism that could make a
game more fun. And outside of a game like Dwarf Fortress, I don't
really care if the goblin I thwack had a favorite fountain to eat
beside.
This is getting me excited; I'll have to pick my projects back up.
> One thing you could do is use the "stench" map as a probability
> distribution that a wandering monster will pick a particular location
> as its next A*-calculated destination. You do have to use A* (ew) but
> at some point even I am willing to consider that my aversion to it may
> be irrational.
Diffusion methods seem better for purposeful wandering than purposeless.
If you really need strict purposelessness, you probably do need to
resort to something else.
--
Joshua
Pender
> Interesting to ask what happens if you let flows block each other.
> Imagine a desire map that can be blocked by a danger map (or possibly
> transmuted into a hazard map by crossing it). It seems like some very
> high-order decisions could be made this way.
Yes. I thought up a system that would maintain several universal
desire gradients for several different kind of desires, and then
monsters would add them all up to get their final decision gradient.
The hook is that while the gradients would all be universal to the map
and not customized to the monster, each monster would use different
coefficients (and, sometimes, threshold cutoffs) when adding them up.
So a monster that was low on HP would have a very high desire for
safety, which would mean the values of the neighboring squares in the
safety (escape) gradient would be weighted at (say) 2.0, whereas a
monster that was fearless and furious at the player would have a very
high coefficient for player chasing and very low for escape. Other
categories of attractors that could be measured on distinct gradients
that I brainstormed (or pulled from your post):
Treasure, the player, water (for amphibious monsters, or lava for
fiery monsters, or any impassible non-wall terrain for flying
creatures), suspicious sounds (sounds of combat, an opening door, a
banshee's shriek) and food tiles (you could even have a vegetarian
attractor type and a carnivore attractor type -- the former tracks
tiles with some sort of fruit-bearing fungus, and the later tracks
corpses). Hunger in particular would be handled with a hunger
coefficient that rose over time but dropped to zero when a monster
stepped on a food tile (presumably also triggering a change in the
terrain or a delay in the monster's further actions).
None of the other gradients would likely extend into the impassible
terrain, so you'd need a separate gradient for escaping back to
passible floor. The coefficient for that one would be the sum the
coefficients for all the desires that required not being on impassible
terrain to pursue -- so an acquatic monster that got hungry would
automatically seek out land and then walk from there to the food.
The cool thing is that monsters wouldn't really have "states," or at
least, each state would blend smoothly into all the others. So a
monster that was fleeing but was also interested in picking up
treasure and finding food might choose to flee away from the player to
the top-left instead of the top-right, since that's the path that
would ultimately lead to the edible fungus. On the way, its path might
skew slightly leftward so that it could grab the treasure lying
slightly off the beeline path.
> I'm trying to figure out
> how to make an escape map -- something that warns a monster that it's
> running into a dead end.
Interesting you should mention this. After your first post inspired
me, I spent several hours designing just such an algorithm, and (in
all modesty) it works to a degree that is borderline frightening. Here
is the algorithm, with comments throughout and an explanation plus
pictures afterwards:
void updateSafetyMap() {
short i, j;
char passMap[DCOLS][DROWS];
creature *monst;
for (i=0; i<DCOLS; i++) {
for (j=0; j<DROWS; j++) {
safetyMap[i][j] = 30000; // safetyMap is a global variable: short
safetyMap[DCOLS][DROWS]
if ((cellHasTerrainFlag(i, j, (OBSTRUCTS_PASSABILITY)) && !
cellHasTerrainFlag(i, j, (IS_SECRET))) // monsters allowed to use
secret doors in my game
|| cellHasTerrainFlag(i, j, (TRAP_DESCENT | IS_DF_TRAP |
LAVA_INSTA_DEATH | IS_DEEP_WATER))) { // stuff for the monst to avoid
passMap[i][j] = false; // remember that this cell is impassible
} else {
if (pmap[i][j].flags & HAS_MONSTER) {
monst = monsterAtLoc(i, j);
if (monst->creatureState == MONSTER_SLEEPING) {
passMap[i][j] = false; // only sleeping monsters act as
obstacles, not wandering/attacking/fleeing monsters
continue;
}
}
passMap[i][j] = true;
}
}
}
safetyMap[player.xLoc][player.yLoc] = 0; // first step is to get a
gradient directing to the player
djikstraScan(safetyMap, passMap); // run the djikstra scan so that
each cell is lowered to one greater than its lowest neighbor,
repeating until no further changes
for (i=0; i<DCOLS; i++) {
for (j=0; j<DROWS; j++) {
if (!passMap[i][j]) {
continue;
}
if (safetyMap[i][j] == 30000) { // terrain that couldn't be reached
by any path
safetyMap[i][j] = 150; // don't want huge numbers hanging around
-- generally makes things too fragile
}
safetyMap[i][j] = 50 * safetyMap[i][j] / (50 + safetyMap[i]
[j]); // if you plot this, it's monotonically increasing but
approaches a horizontal asymptote.
// Otherwise the really long distances will overpower the entire map,
making it too difficult to tune the desired short-range behavior
safetyMap[i][j] *= -3; // invert the entire gradient, so that the
places furthest away from the player become the most desirable.
}
}
passMap[player.xLoc][player.yLoc] = false; // For the final step,
consider the player an obstacle so that the fleeing creature does not
try to path through him.
djikstraScan(safetyMap, passMap); // This is where the magic happens.
Explained below.
}
OK. So the basic idea is to start with a map leading towards the
player and then invert it by multiplying by a negative number. Now it
leads away from the player. The problem is that it will lead away from
the player stupidly -- straight into the nearest local minimum
(generally a corner of the room they're starting in). The idea is that
you want some tradeoffs between how good the local minimum is and how
much further the monster would have to run to get there. That's why
the negative multiplier is -3 instead of -1 -- so that when we run
another djikstra scan on the result, really awesome local minima
overpower less impressive local minima that are sufficiently close.
There's one problem left, though, and that is that it's too dependent
on the size of your map. If you doubled the size of your map, that
would qualitatively affect the behavior of fleeing monsters in the
vicinity, since it would make the now twice-as-distant global minimum
twice as attractive relative to other compelling local minima. So
that's the purpose of the horizontal asymptote -- it levels all that
out so that further is always better but not linearly so.
Here are some pictures of the resulting gradient. More intense colors
means more safety from the monster's perspective, and it will roll
mindlessly in the direction of more safety.
http://img18.imageshack.us/img18/3933/95754534.jpg
http://img3.imageshack.us/img3/9895/60969179.jpg
http://img4.imageshack.us/img4/4198/30939130.jpg
Notice how in the first picture, there is a gradient in the corners of
the room the player is in; in that situation, monsters will remain
cowering in the corner. But look at how it flips around in the second
picture -- that is when the monster decides it is worthwhile to make a
break for it and will try to run past the player to a better place
elsewhere on the level. Of course, if the player steps back to block
the door, the gradient will reappear in the corners and the monster
will retreat to its old hiding place.
The third pic just shows one of those cellular automata levels.
(Unshaded squares are hidden traps.)
Sometimes monsters will pillar-dance, but not conspicuously so -- and
will usually dodge off to run down a nearby corridor.
The biggest problem with the map is that multiple monsters will tend
to stick together if they start together, since the gradient is a
continuous function of location. I am currently trying to think of a
seamless way for the monster to bias its movements toward purposeful
but random wandering as it gets further away from the player and is
out of the player's field of view.
Gelatinous Mutant Coconut
> The biggest problem with the map is that multiple monsters will tend
> to stick together if they start together, since the gradient is a
> continuous function of location. I am currently trying to think of a
> seamless way for the monster to bias its movements toward purposeful
> but random wandering as it gets further away from the player and is
> out of the player's field of view.
If you want monsters to split up, you could have a field that is the
sum of the fields-of-view of all monsters. (At each tile, for each
monster add zero if the monster can't see it, otherwise add one. You
could alternatively experiment with adding something like an inverse
square distance.) When monsters want to split up, have them start down
line-of-sight paths to a tile within their FOV with the least field-of-
view value of the tiles in their FOV. That should cause them to get
out of sight of each other if possible.
Once they're separated you'll need to think of some other wandering
method, but that should solve the clumping issue.