FOV/scent-based pathfinding

378 views
Skip to first unread message

Da-Breegster

unread,
Apr 5, 2009, 12:41:38 PM4/5/09
to
It's rather pitiful: I've spent 3 years at school doing science fairs
on methods of mass movement, but when it comes time to make enemies
chase the player, all of them seem to break down in some way.

I'm currently investigating a suggestion I've seen crop up here many
times: using line-of-sight calculations to set a scent. Right now my
FOV is laughable -- I draw a rectangle of light around the player that
permeates through all obstacles. Every tile I light, I set set its
scent equal to: turn_counter * (max_distance - euclid_dist(tile_y,
tile_x, player_y, player_x)) and then have monsters choose the best
adjacent node, scored by highest scent. Unfortunately I run into the
local minima problem constantly -- monsters will enter a loop and
oscillate between two or three nodes because they have the highest
scores.

I have a feeling that my scent calculation is off; in the past I've
experimented with negatively weighting nodes recently visited, but it
doesn't solve the problem well, and people here have never mentioned
having to do anything like that.

My other plan is to use a custom algorithm I came up with called
blockmap -- it's basically chunking/waypoints. The map is "zoomed out"
or compressed into a smaller set of rooms that heuristically guess
their permeability by looking at the enemies lined up inside. This'll
be my fallback plan, but I'd like something simpler first.

My final idea is collaborative diffusion -- a fancy word for diffusing
a scent from the goal through the map. The scent doesn't pass through
other agents, so two enemies will take two different narrow hallways
and surround the player. The problem is that this diffusion map is
incredibly slow to calculate -- I start at the goal and recursively
add adjacent nodes, everytime the player moves. Does anybody have a
faster way?

Ray Dillinger

unread,
Apr 5, 2009, 1:17:19 PM4/5/09
to
Da-Breegster wrote:

> I'm currently investigating a suggestion I've seen crop up here many
> times: using line-of-sight calculations to set a scent. Right now my
> FOV is laughable -- I draw a rectangle of light around the player that
> permeates through all obstacles.

That'll be a problem. Monsters will get stuck on the other side of
a barrier they can't figure out how to get around, and never move
again.

> Every tile I light, I set set its
> scent equal to: turn_counter * (max_distance - euclid_dist(tile_y,
> tile_x, player_y, player_x)) and then have monsters choose the best
> adjacent node, scored by highest scent. Unfortunately I run into the
> local minima problem constantly -- monsters will enter a loop and
> oscillate between two or three nodes because they have the highest
> scores.

Well, there's your "local minima" problem. Instead of

turn_counter * (max_distance - euclid_dist(t_y, t_x, p_y, p_x))
use
(turn_counter * max_distance) - euclid_dist(t_y, t_x, p_y, p_x)

That should fix that symptom right up.

> I have a feeling that my scent calculation is off;

Yep.

Bear

ben...@gmail.com

unread,
Apr 5, 2009, 1:21:00 PM4/5/09
to
On Apr 5, 12:41 pm, Da-Breegster <dabreegs...@gmail.com> wrote:

> Does anybody have a faster way?

Scent in Wayfarer is calculated thusly:
scent of player grid = 100.
each turn, set the scent of each walkable grid to the (maximum
neighbor scent) - 1. Neighbors are only cardinal directions
(otherwise you end up with bands of equal scent value, producing the
the oscillating behavior you describe). This way you can be certain
that no two adjacent grids have equal scent values, and that greater
values always lead to the player.

As for pathfinding cost, the best tip I've seen is from Jotaf, here:
http://groups.google.com/group/rec.games.roguelike.development/browse_thread/thread/30eee2a1991f2086

Not sure why you'd want to combine the two calculations, unless it
simplified things (and it seems to do the opposite?)

--Ben

Jotaf

unread,
Apr 5, 2009, 3:05:02 PM4/5/09
to
Hey thanks Ben :) I had completely forgotten about that technique. I
decided it would be worthwhile to add it to Roguebasin (practically
unedited though), it's filed under Articles>AI.

Jotaf

Mingos

unread,
Apr 5, 2009, 3:15:58 PM4/5/09
to
On 5 Kwi, 19:21, benh...@gmail.com wrote:
> On Apr 5, 12:41 pm, Da-Breegster <dabreegs...@gmail.com> wrote:
>
> > Does anybody have a faster way?
>
> Scent in Wayfarer is calculated thusly:
> scent of player grid = 100.
> each turn, set the scent of each walkable grid to the (maximum
> neighbor scent) - 1.  Neighbors are only cardinal directions
> (otherwise you end up with bands of equal scent value, producing the
> the oscillating behavior you describe).  This way you can be certain
> that no two adjacent grids have equal scent values, and that greater
> values always lead to the player.
>
> As for pathfinding cost, the best tip I've seen is from Jotaf, here:http://groups.google.com/group/rec.games.roguelike.development/browse...

>
> Not sure why you'd want to combine the two calculations, unless it
> simplified things (and it seems to do the opposite?)
>
> --Ben

Set the PC's status to PC_STATUS_STINKY and make the monsters use
simple A* to find him, without actual scent propagation. If the PC
takes a shower, his status changes to PC_STATUS_CLEAN and the monsters
stop tracking him using scent, but rather sight and/or hearing. The
player won't notice anyway.

Mingos

Brigand

unread,
Apr 5, 2009, 5:55:38 PM4/5/09
to
> Mingos- Hide quoted text -
>
> - Show quoted text -

Yeah, I thing Mingos hit it on the head. Designing an intricate,
detailed, completely bug-free algorithm for tracking may be quite an
acomplishment, a step towards realism which should be applauded...
but, unfortunately, without expressly telling the player what's going
on, they are going to be largely oblivious to it. The average person
isn't going to consider why a monster moves the way he does, only in
how he moves. 95% of the time you're probably better served
(especially in computer calculating resources) by If Player_X >
Monster_X then Monster_X=Monster_X - 1 type tracking, with more
complicated pathfinding only coming into play if the creature gets
stuck.

But, I realize this wasn't your original question - I still like the
ideas posted about scent tracking, and have been seriously mulling
over whether to use it or not.

dabre...@gmail.com

unread,
Apr 5, 2009, 9:07:52 PM4/5/09
to

It's always something simple. Order of operations makes all the
difference. Thanks!

Ray Dillinger

unread,
Apr 6, 2009, 11:14:50 AM4/6/09
to
dabre...@gmail.com wrote:

>> Well, there's your "local minima" problem.  Instead of
>>
>> turn_counter * (max_distance - euclid_dist(t_y, t_x, p_y, p_x))
>> use
>> (turn_counter * max_distance) - euclid_dist(t_y, t_x, p_y, p_x)
>>
>> That should fix that symptom right up.
>>
>> > I have a feeling that my scent calculation is off;
>>
>> Yep.
>>
>> Bear
>
> It's always something simple. Order of operations makes all the
> difference. Thanks!

You're welcome! I invented that algorithm, so of course it's way
easy for me to see things like that. Heh. I'm just pleased that
folks are getting good use out of it. Makes me feel good.

Bear


pende...@gmail.com

unread,
Apr 6, 2009, 12:54:27 PM4/6/09
to
On Apr 5, 5:55 pm, Brigand <markash...@hotmail.com> wrote:
> Yeah, I thing Mingos hit it on the head. Designing an intricate,
> detailed, completely bug-free algorithm for tracking may be quite an
> acomplishment, a step towards realism which should be applauded...
> but, unfortunately, without expressly telling the player what's going
> on, they are going to be largely oblivious to it. The average person
> isn't going to consider why a monster moves the way he does, only in
> how he moves.

I also use a form of Ray's algorithm, and it was simpler to implement
than A*. It's not supposed to simulate realistic bloodhound-like
monsters -- at least I don't use it to simulate that -- but rather
monsters who see you and chase you intelligently, whom you can't lose
by ducking around a corner. In fact the whole "scent" metaphor is a
bit misleading; since when after all does scent depend on line of
sight? I'm afraid people see the word "scent" and assume it's a
misguided effort to import a pointless degree of realism. It's not;
it's a simple, low-overhead, purely functional algorithm to make
monsters chase you.

> 95% of the time you're probably better served
> (especially in computer calculating resources) by If Player_X >
> Monster_X then Monster_X=Monster_X - 1 type tracking, with more
> complicated pathfinding only coming into play if the creature gets
> stuck.

Except that you do need the more complicated pathfinding algorithm to
take over in the 5% of the time when the player ducks around a corner,
because if you don't have it, the player is going to start ducking
around corners a lot more than 5% of the time. And if you do have it,
then you have to code the alternative pathfinding algorithm, code a
method of detecting when a monster needs to switch over to the more
complicated algorithm, embed that information into the monster so it
remembers from turn to turn that it's following the complicated
algorithm, etc. Ray's algorithm, on the other hand, is a single
approach for having monsters chase you (around corners *and* in line
of sight) that avoids the need to run dual pathfinding algorithms in
parallel. It's a lot simpler. Of course if you want your monsters to
wander, flee, etc. in addition to chasing the player, then you need
parallel algorithms, but one fewer is always easier.

David Damerell

unread,
Apr 6, 2009, 3:28:38 PM4/6/09
to
Quoting <pende...@gmail.com>:
>I also use a form of Ray's algorithm, and it was simpler to implement
>than A*. It's not supposed to simulate realistic bloodhound-like
>monsters -- at least I don't use it to simulate that -- but rather
>monsters who see you and chase you intelligently, whom you can't lose
>by ducking around a corner.

Much of that could be fixed in a computationally cheap way by having a
monster which loses sight of you proceed to where it lost sight of you.

Slightly cleverer; it then moves in the direction you did, and as long as
it can only move in one direction without backtracking, it keeps moving.
(Some cleverness needed if you have 2-space-wide corridors, else this
gives up in them. I suggest a combination of "keep going straight" and
"avoid backtracking".)

Combine this with monsters just knowing where you are if you are very
close - rationalise it as hearing or smell or whatever, I don't care - and
you have a foe who is reasonably hard to evade without doing any flood
fills of the map.
--
David Damerell <dame...@chiark.greenend.org.uk> Distortion Field!
Today is Second Oneiros, April.

Jotaf

unread,
Apr 6, 2009, 5:00:09 PM4/6/09
to
On Apr 6, 8:28 pm, David Damerell <damer...@chiark.greenend.org.uk>
wrote:
> <snip little piece of obviousness that everyone in the world seems to have missed>

Damn how didn't I ever think of that?! It's simple. It's also how
people usually do "tracking", when there's no prior information to
make predictions (prior information of the type "if he went this way,
then he must be going to that place", or "we can cut him off at that
point"). Imagine yourself in a chasing position, in real life, could -
you- do any better?

You know what, I probably won't have A* in my RL after all. Or scent-
based. Monsters that you can try to shake loose are much, much more
interesting!

Jotaf

pende...@gmail.com

unread,
Apr 6, 2009, 6:12:53 PM4/6/09
to
On Apr 6, 3:28 pm, David Damerell <damer...@chiark.greenend.org.uk>
wrote:

> Much of that could be fixed in a computationally cheap way by having a
> monster which loses sight of you proceed to where it lost sight of you.
>
> Slightly cleverer; it then moves in the direction you did, and as long as
> it can only move in one direction without backtracking, it keeps moving.
> (Some cleverness needed if you have 2-space-wide corridors, else this
> gives up in them. I suggest a combination of "keep going straight" and
> "avoid backtracking".)

This is a lot harder than it sounds, particularly when your dungeon is
fairly complicated. 2-space-wide corridors are not the end of the
story; you also need to account for rooms with only two doors, which
are analogous to corridors. And then there are rooms with three
entrances, one of which is filled with lava and only passable if the
player has quaffed a potion of levitation or fire immunity within the
past few turns -- should we treat that analogously to a two-entrance
room? Then there are cave levels generated by cellular automata, where
the definition of "room" is a lot less clear but the same principles
should theoretically apply. I'd posit that the strategy you've
suggested is in fact very hard to implement satisfactorily in such a
complex dungeon -- definitely too hard for me, and much harder than
Ray's algorithm.

> Combine this with monsters just knowing where you are if you are very
> close - rationalise it as hearing or smell or whatever, I don't care - and
> you have a foe who is reasonably hard to evade without doing any flood
> fills of the map.

Ray's algorithm does not require any flood fills; it is
computationally extremely cheap, especially when it piggy-backs on the
existing line-of-sight scans. The only fair critique that I can think
of is that it permits some degree of monster omniscience unless you're
willing to indulge the imperfect scent metaphor. But if you're willing
to grant monsters short-range omniscience, it seems to me that even
that criticism does not apply.

rdc

unread,
Apr 6, 2009, 8:59:46 PM4/6/09
to
Jotaf wrote:

> Damn how didn't I ever think of that?! It's simple. It's also how
> people usually do "tracking", when there's no prior information to
> make predictions (prior information of the type "if he went this way,
> then he must be going to that place", or "we can cut him off at that
> point"). Imagine yourself in a chasing position, in real life, could -
> you- do any better?
>
> You know what, I probably won't have A* in my RL after all. Or scent-
> based. Monsters that you can try to shake loose are much, much more
> interesting!

In my Deep Deadly Dungeon game (and in my current Sword of Light game) I
used a simple, easy to code method without resorting to A* path finding that
is much like this method. (I personally think A* path finding is both
unnecessary and "unnatural"; I consider it programmer cheating. I feel that
my monsters should behave more like natural beasts rather than
computer-trained agents.)

My method in order of execution:

1) If the player character (pc) is in sight, a) remember position b) move
towards player.
2) If pc is not is sight, listen for pc. If pc detected follow sound.

I generated a sound map based on what the pc was doing, what they were
wearing as far as armor, what weapons they were carrying and the type of
terrain they were walking over. The sound was a simple flood fill algorithm
with a linear diminishing value based on distance. The sound map was
generated each move.

3) If pc not heard, and pc previously sighted, move to last position of pc.
4) If at last position of pc and pc not detected, continue in direction of
pc's last sighted movement.
5) Else: roam using right hand method.

The only thing any of these require is a simple pick next closest tile to
target in the non-sound case, and pick next tile with highest sound value in
the sound map case. Does it work? It worked extremely well. Once a monster
locked onto you, it was quite difficult to shake, even if you dodged through
rooms or moved around corners. I came up with this after watching a show
about lions hunting, and felt it was a good approximation of how a
generalized creature would hunt its prey.

Now, before you all tell me that a formal pathfinder is needed in cases
where monsters bunch up or navigating varying terrain types, I will tell you
that you just can't convince me. :) This is why: 1) Most animals use a
flocking behavior to deal with bunch ups. Birds do it, lions do it, herd
animals do it, even fish do it. It works in all cases. 2) Bunching up is a
natural behavior of animals, both for defense and offense. Bunching up in
the case of defense minimizes the chance that a particular animal will be
eaten; it makes the individual bigger by association with the herd. In
offense, bunching up allows the predators to strike more often and again
minimizes the chance that an individual will be damaged in the case of a
defensive attack.

I implemented flocking behavior in DDD among different types of monsters
that allowed monsters to move past one another when needed, but also allowed
bunching, especially in the case where the pc was foolishly standing in a
corner or along a wall of just standing there tempting fate. The monsters
would surround the pc and bunch up, with ranged monsters naturally behind
melee monsters according to the flocking rules. The pc didn't last long in
these cases.

Personally, I feel that this is much more "fair" to the player than a
monster that can path-find its way to the pc from clear across the dungeon.
It also makes the monsters appear more "natural" within the context of the
game world.
--
Rick Clark
Clark Productions: http://rickclark58.googlepages.com/

dabre...@gmail.com

unread,
Apr 6, 2009, 9:22:53 PM4/6/09
to
On Apr 6, 7:59 pm, "rdc" <rickclar...@gmail.com> wrote:
> Jotaf wrote:
[snip sound map stuff]
This sounds great -- google "collaborative diffusion." It's the same
idea, simple, natural, effective. The problem is speed. If you
regenerate your sound map regularly, how big is your map? Especially
in large, open caverns, this technique is painfully slow.

Gelatinous Mutant Coconut

unread,
Apr 6, 2009, 10:11:12 PM4/6/09
to

I don't think you would ever want to regenerate your sound-map; just
add sound intensity (or scent, or whatever your metaphor is) to a tile
when a sound event occurs there, and then perform some number of
diffusion ticks on each map tile every game turn.

It is quite a lot of operations, but it's very well suited to being
performed in a massively parallel way. It would probably be a task
well suited to being offloaded to the GPU, actually. (I don't imagine
that GPU processing time is the limiting factor in most roguelikes.) I
don't have enough (any) experience with GPU libraries to really say
how easy doing things like that portably would be, however. You could
probably perform the calculations by cleverly hijacking OpenGL, but
I'm not an expert on that either.

Paul Donnelly

unread,
Apr 6, 2009, 10:42:53 PM4/6/09
to
dabre...@gmail.com writes:

Even if you're filling a full 80x24 map, a flood fill should be plenty
fast. I mean, think about it: in the old days 3d games would flood fill
a whole 320x200 screen full of polygons, in addition to doing a whole
bunch of other calculations, every single frame. If your sounds only
propagate for 10 squares or so (which is reasonable), it will be even
faster.

rdc

unread,
Apr 7, 2009, 4:22:26 AM4/7/09
to
Paul Donnelly wrote:
>>> Jotaf wrote:
>> [snip sound map stuff]
>> This sounds great -- google "collaborative diffusion." It's the same
>> idea, simple, natural, effective. The problem is speed. If you
>> regenerate your sound map regularly, how big is your map? Especially
>> in large, open caverns, this technique is painfully slow.
>
> Even if you're filling a full 80x24 map, a flood fill should be plenty
> fast. I mean, think about it: in the old days 3d games would flood fill
> a whole 320x200 screen full of polygons, in addition to doing a whole
> bunch of other calculations, every single frame. If your sounds only
> propagate for 10 squares or so (which is reasonable), it will be even
> faster.

Yes, speed is not a problem. The flood-fill technique is both simple and
fast, even in open areas. Inside the dungeon, you have the added benefit of
blocking tiles which decrease the actual area you need to fill with "sound"
making the technique even faster, since a blocking tile is one of the exit
conditions of the algorithm. The maximum extent of my map was about 10 tiles
(good call Paul :)) in open areas which seemed to be a good range and
generated a good response. The sound map was only part of the overall
hunting algorithm and primarily came into play when the monster had lost
sight of the pc, but was nearby and could follow the sound.

I don't see a problem generating larger maps though. It is a simple integer
operation and a good compiler can optimize the operation. Integers are also
the native data type on 32 bit CPUs so it is a quick operation there as well
(which is why I favor integers over other data types even though they may
waste a bit of space). Even on my old NT box, there was no noticeable
performance issues.

One way to view the sound map is a localized path finding algorithm, since
the values of the map point to the pc location, with higher sound values
being closer to the pc. Following the map is just a walk across these
values, always picking the higher (or equal) values. You can see that this
prevents backtracking, since lower valued tiles will always be away from the
pc and higher or equal values will always be toward the pc. Even though this
is in reality a path finding algorithm, I don't consider it "programmer
cheating" since the sound map is generated as a by the actions of the pc,
and therefore a natural consequence of actions within the game world. If the
player chose to be stealthy (or just stood still for a while resting) the
extent of the sound would be reduced by a factor equal to the pc's stealth
ability or lack of movement balancing the effect.

Just to clarify, I am not opposed to path finding. I am opposed to giving
the program more knowledge than it should have. If the pc does something,
then the program is allowed to use that knowledge. And to give the player
the same access to information, you could just post a quick message like
"You hear something nearby." when monsters are moving about as well.

David Damerell

unread,
Apr 7, 2009, 3:22:39 PM4/7/09
to
Quoting <pende...@gmail.com>:
>On Apr 6, 3:28=A0pm, David Damerell <damer...@chiark.greenend.org.uk>

>>Slightly cleverer; it then moves in the direction you did, and as long as
>>it can only move in one direction without backtracking, it keeps moving.
>>(Some cleverness needed if you have 2-space-wide corridors, else this
>>gives up in them. I suggest a combination of "keep going straight" and
>>"avoid backtracking".)
>This is a lot harder than it sounds, particularly when your dungeon is
>fairly complicated.

Absent digging tools - and yes, that's a big assumption - you might have
a lot of meta-information about the dungeon at level generation time.

>2-space-wide corridors are not the end of the
>story; you also need to account for rooms with only two doors, which
>are analogous to corridors.

Depends how smart you want your monsters to be. After all, if you're
implementing a "real" tracking setup, rather than a straight A* beeline
for the player, it is because you want the player to be able to fool the
monster and evade.

I think with a bit of lookahead you can solve most of the problems with
2-space corridors and smallish caves, and with meta-information about
rooms you can solve the problems there.
--
David Damerell <dame...@chiark.greenend.org.uk> Oil is for sissies
Today is Second Mania, April.

rdc

unread,
Apr 7, 2009, 5:50:04 PM4/7/09
to
dabreegster wrote:

> This sounds great -- google "collaborative diffusion." It's the same
> idea, simple, natural, effective. The problem is speed. If you
> regenerate your sound map regularly, how big is your map? Especially
> in large, open caverns, this technique is painfully slow.

Interesting. I had not heard of collaborative diffusion before. The Pac-man
example on Wikipedia is pretty much my sound map code, without the
differential equations. :)

As far as speed, the flood-fill technique is much faster than A* path
finding, even on complicated maps. Actually, it is probably much faster on
complicated maps. Using flood-fill you only visit a tile once per
generation. Using A*, you will have to visit some tiles multiple times to
determine the best path depending on how long the tile remains in the open
list. Even if only a small percentage of tiles are looked at multiple times,
that is still more than once.

Jotaf

unread,
Apr 7, 2009, 9:01:08 PM4/7/09
to
On 6 Abr, 23:12, penderpr...@gmail.com wrote:
> This is a lot harder than it sounds, particularly when your dungeon is
> fairly complicated. 2-space-wide corridors are not the end of the
> story; you also need to account for rooms with only two doors, which
> are analogous to corridors. And then ... <other examples>

A classic mobile robotics problem... "keep this heading and avoid
obstacles". Just cast rays outwards, creating a list of distances, one
for each ray (ie, radar readings). Sample 180º in front of the robot.
Then follow the direction where distance is largest. (So it doesn't go
towards walls, but the "end of the tunnel".) This is pretty dumb,
since it can get trapped in local minima. The problem can be minimized
if the angle between rays is small enough and there's no distance
restriction when casting (or it's large enough). When in a local
minima (ie, still in the same general position after a long time),
that would be tough for a robot, but not for a monster; just give up
and go back to wandering behavior. The player rejoices! :)

No concerns about rooms, corridors or caves. You could also brag that
your game performs an actual simulation of the monsters' senses; they
don't use global knowledge at all :)

> <Ray's algorithm> The only fair critique that I can think


> of is that it permits some degree of monster omniscience unless you're
> willing to indulge the imperfect scent metaphor.

Yes, it's the main reason against A*. It can kill any creativity on
the part of the player; since it's an optimal algorithm, once it locks
on, the player might as well just give up. The other one is fallible
under conditions where a reasonable creature would also be fallible;
so it provides more interesting choices for the player. It's also the
reason why I decided to elaborate a bit on the "robot simulation"
approach.

BTW: Interesting article on collaborative diffusion/anti-objects, the
paper is nice, too!

Jotaf

pende...@gmail.com

unread,
Apr 8, 2009, 12:13:44 PM4/8/09
to
On Apr 7, 9:01 pm, Jotaf <jota...@hotmail.com> wrote:
> The other one is fallible
> under conditions where a reasonable creature would also be fallible;
> so it provides more interesting choices for the player. It's also the
> reason why I decided to elaborate a bit on the "robot simulation"
> approach.

Have you actually implemented this robot ray-casting algorithm you
describe? I'm not trying to be a party-pooper, but I think it would
substantially underperform even the realistically-fallible ideal
you're going for. In a big room with two doors and kinks in the
hallways connected to the doors, I can imagine a lot of situations --
perhaps the majority of situations -- where the monster will simply
walk in circles near the center of the room instead of finding the
other door -- and to the extent that it does eventually find a door, I
don't know why it wouldn't pick the one by which it entered the room
in the first place.

I'm all about cool emergent behaviors, smart AI through cleverly-
chosen but simple rules, but I like to hear about ones that have been
demonstrated to work. Ray's scent-casting algorithm is a great
example: it's simple, low-overhead, and it actually works to create
intelligent following behavior. If you can (or have) set up a demo of
your proposed algorithm, I'd be interested to see the results. I'd be
happy to be proven wrong.

In any case, to the extent that this counter-proposal was originally
suggested as a simpler alternative to scent-casting, I think we've
long passed that threshold.

Ray Dillinger

unread,
Apr 8, 2009, 1:49:23 PM4/8/09
to
Jotaf wrote:

> You know what, I probably won't have A* in my RL after all. Or scent-
> based. Monsters that you can try to shake loose are much, much more
> interesting!

It's true, monsters that track inerrantly aren't as interesting as
monsters you can try to lose.

It's even more true that monsters that all behave alike aren't as
interesting as monsters that all behave differently.

You can solve both problems the way I do; Handle it by having
different monsters use the information with different constraints
and limitations.

Most can't "see" the gradients if they're more than N turns old, for
N that depends on the intelligence level or senses of the monster.

Stupid undead and stupid golems have an alternate stupid chase
mode which simply tries to move toward the player regardless of
obstacles in the way.

Some move more slowly when following the gradients, so you can
outrun them.

Most have some events or terrains that, if encountered, interrupt
chasing mode, like hounds encountering any form of liquid terrain
(water or lava). For a lot of monsters, it's a chase interrupting
event just to go for N turns without seeing/hearing you.

Most don't go into chasing mode unless the PC is actually in view
or makes a loud noise near them. (hounds and other powerful scent
trackers are an exception...)

On my idea list is another constraint, where traversing "door
spaces" (spaces where a door could be located occur at room
doorways and corridor branchings) eventually ends chasing.
The idea is that crossing enough door spaces without actually
catching sight of you should interrupt chasing mode for some
monsters.

Anyway, in order to win you learn what each kind of creature's
tracking limitations are, and then you have some idea what you
need to do to lead them or lose them in a chase. And there is
a magical effect that allows you to go straight through solid
walls every once in a while, which is another very good way to
make an escape if you've got the right item or the right spell
(and the chaser doesn't).

Bear

rdc

unread,
Apr 8, 2009, 2:41:17 PM4/8/09
to
Ray Dillinger wrote:
> Jotaf wrote:
>
>> You know what, I probably won't have A* in my RL after all. Or scent-
>> based. Monsters that you can try to shake loose are much, much more
>> interesting!
>
> It's true, monsters that track inerrantly aren't as interesting as
> monsters you can try to lose.
>
> It's even more true that monsters that all behave alike aren't as
> interesting as monsters that all behave differently.
>

This is why I added the flocking algorithm as part of the hunting strategy.
By assigning different parameters to different monsters, you get some nice
distinct emergent behavior for each type of monster. The bonus is automatic
cooperative strategies as well as the occasional species conflict, both of
which contribute to a more "natural" looking monster. The real plus about
all of these techniques is that they are simple to program, yet can result
in some complex and interesting behavior.

rdc

unread,
Apr 8, 2009, 3:05:38 PM4/8/09
to
penderprime wrote:

> This is a lot harder than it sounds, particularly when your dungeon is
> fairly complicated. 2-space-wide corridors are not the end of the
> story; you also need to account for rooms with only two doors, which
> are analogous to corridors. And then there are rooms with three
> entrances, one of which is filled with lava and only passable if the
> player has quaffed a potion of levitation or fire immunity within the
> past few turns -- should we treat that analogously to a two-entrance
> room? Then there are cave levels generated by cellular automata, where
> the definition of "room" is a lot less clear but the same principles
> should theoretically apply. I'd posit that the strategy you've
> suggested is in fact very hard to implement satisfactorily in such a
> complex dungeon -- definitely too hard for me, and much harder than
> Ray's algorithm.

The only realistic, computationally cheap method to handle this is to use
nodes. Nodes offer a lot of flexibility which is why they are ubiquitous in
games that have complex routing. They cost next to nothing in computation;
the agent simply moves toward the nearest node and once at the node, moves
toward the next node in the chain. You can also bias nodes so that node A
points to B and C with a slight bias toward B for example. This way the
agent won't always take the same route. Unreal does this better than anyone
I think.

One thing I am going to use nodes for in SOL is to set up patrol points for
sentries. You can create synchronized sentries, closed loop sentries,
backtracking sentries, the list goes on. It is extremely easy to implement
and very low overhead, yet works remarkably well. It is also fairly easy to
implement a node system procedurally, since you know when you are creating
the dungeon where each dungeon element is located, so you can place and link
the nodes as you build the dungeon.

Jotaf

unread,
Apr 8, 2009, 3:07:18 PM4/8/09
to
On Apr 8, 5:13 pm, penderpr...@gmail.com wrote:
> Have you actually implemented this robot ray-casting algorithm you
> describe?

Yes, but as an actual robot. And as a simulation. Not in RLs, but as I
recall the simulation was tremendously easy to code. Ray-casting was
done with a pre-existing Bresenham line drawing function; as trivial
as a function call. Cast rays and take note of the longest; then move
in that direction. There aren't many LOCs involved. It may be harder
than scent-based tracking, but not by much. It's just that it's not
the "usual" way of coding RLs; I come from a slightly different
background so I don't find this too eccentric.

Of course that with meta-information about rooms and doors all you'd
have to do would be to choose the door in the room that is in a
specific direction, as David suggested. But I prefer the other
approach since it has the potential to work - or fail - in many more
situations.

Ray Dillinger wrote:
> You can solve both problems the way I do; Handle it by having
> different monsters use the information with different constraints
> and limitations.

Yes, but those are artificial. Don't get me wrong, I'd always prefer a
game with those than one where all monsters use plain A*; but the fact
is that the designer has to code those limitations specifically. The
AI still has unfair global knowledge, and to loose it you have to know
what the designer had in mind, like hounds loosing scent in liquids.
Then every time the same hounds are found you just need to remember
where is the nearest pond in the level.

Jotaf

pende...@gmail.com

unread,
Apr 8, 2009, 3:29:55 PM4/8/09
to
On Apr 8, 3:05 pm, "rdc" <rickclar...@gmail.com> wrote:
> It is also fairly easy to
> implement a node system procedurally, since you know when you are creating
> the dungeon where each dungeon element is located, so you can place and link
> the nodes as you build the dungeon.

If your dungeon is constructed by piecing together simple primitives
-- rooms and hallways, for example -- then this is certainly the case.
But can you think of a way to do it in a cavern that was generated by
cellular automata or another similar procedure? (I couldn't --
monsters wander very fluidly in room-and-hallway parts of the dungeon
but turn into total idiots when they enter the cavern areas.)

pende...@gmail.com

unread,
Apr 8, 2009, 3:33:01 PM4/8/09
to
On Apr 8, 3:07 pm, Jotaf <jota...@hotmail.com> wrote:
> On Apr 8, 5:13 pm, penderpr...@gmail.com wrote:

> > Have you actually implemented this robot ray-casting algorithm you
> > describe?

> Yes, but as an actual robot. And as a simulation. Not in RLs, but as I
> recall the simulation was tremendously easy to code.

I know it wouldn't be tremendously difficult to code, but I'm curious
to see if its results in practice measures up to your expectations. If
you code it up and try it out, please post the results. I'm not so
much concerned that it would be difficult to implement or
computationally expensive as I am that the monster would act like an
idiot :)

rdc

unread,
Apr 8, 2009, 6:12:35 PM4/8/09
to
penderprime wrote:

> If your dungeon is constructed by piecing together simple primitives
> -- rooms and hallways, for example -- then this is certainly the case.
> But can you think of a way to do it in a cavern that was generated by
> cellular automata or another similar procedure? (I couldn't --
> monsters wander very fluidly in room-and-hallway parts of the dungeon
> but turn into total idiots when they enter the cavern areas.)

Even using a CA, there should be distinct phases to the cavern building
routine, otherwise how would you get open areas and passageways? CAs are
state machines, so you should know the state the CA is in at any given
moment. I have written quite a few CAs and looked at a few more, and all of
them enter and exit distinct states during whatever process they are
programmed to accomplish.

When the CA selects an area as a candidate for a cavern room, just determine
the approximate center point of the room, or a point that is in line of
sight to the entries and drop the node there. You could this a number of
ways. Keep track of the current dimensions of the room and determine the
midpoint, for example. If the CA builds a room from the center point
outward, use the starting point. There are probably a dozen other ways as
well.

When the CA transitions to the passageway phase of the process, it can drop
nodes whenever it crosses the boundary from open area to passageway, or when
there is a significant change of direction in the passage. All of these
conditions cause a change in state, so you know when they occur and could
take advantage of it.

However, my approach would be to make node dropping part of the rules of the
CA. The cavern rooms would be built based on a node location and passageways
would start and end at node points, with significant direction changes node
points as well. This way there is no elaborate scheme needed to determine
where to place a node.

The only difficulty in this would be if the CA is multithreaded and
different sections of the cavern complex are being created at the same time.
In that case I would still drop nodes, but after the complex is built, use
Dijkstra's path finding algorithm to link nodes, with nodes reciprocally
linked just to keep things simple. You could also link nodes in each section
as they are built, then just link the sections in the post process phase,
rather each individual node. And I am sure someone could come up with a
better approach than this.

There is always a way to do something; it just depends if it is worth the
effort to implement and maintain.

Jeff Lait

unread,
Apr 9, 2009, 9:23:10 AM4/9/09
to
On Apr 6, 10:11 pm, Gelatinous Mutant Coconut

<GelatinousMutantCoco...@gmail.com> wrote:
> It is quite a lot of operations, but it's very well suited to being
> performed in a massively parallel way. It would probably be a task
> well suited to being offloaded to the GPU, actually.

No, it wouldn't. You need the sound map back in main memory. Thus
your computation would be entirely bounded by the time to transfer to
and from the GPU. In that time window, I'm pretty sure you could
easily complete the calculation on the CPU directly, especially if you
use some SSE.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

Jeff Lait

unread,
Apr 9, 2009, 9:36:00 AM4/9/09
to

The goal is to have sufficient nodes that any square is in sight on of
one node. Or, more precisely, given any square, there exists a node
for which it is cheap to do path finding to. You then can do your
longer routing by using the nodes alone.

A simple greedy algorithm to generate nodes presents itself:

1) Create one node per walkable dungeon square.
2) Put these nodes in the "unfixedlist"
3) Each walkable dungeon square gets a node pointer to the node on it.
4) while (1)
a) Pick a unfixedlist node, N, at random, remove from said list.
b) For all squares, S, which point to N,
i) Find another node, N(S) != N, that they could path to quickly
c) if some square didn't have an alternative node, N is a fixed
node.
d) If all squares had an alternative, update their node pointers to
the alternative, and remove N as a redundant node.

This will naturally discover hall & room layouts without any apriori
knowledge. I'd be wary about how stringent you are on what consitutes
a valid path to avoid little cupboards all getting their own nodes,
but this is something that could clearly be tweaked.

Jeff Lait

unread,
Apr 9, 2009, 9:44:43 AM4/9/09
to
On Apr 5, 5:55 pm, Brigand <markash...@hotmail.com> wrote:
> On Apr 5, 3:15 pm, Mingos <dominikmarc...@gmail.com> wrote:
>
> > Set the PC's status to PC_STATUS_STINKY and make the monsters use
> > simple A* to find him, without actual scent propagation. If the PC
> > takes a shower, his status changes to PC_STATUS_CLEAN and the monsters
> > stop tracking him using scent, but rather sight and/or hearing. The
> > player won't notice anyway.
>
> Yeah, I thing Mingos hit it on the head. Designing an intricate,
> detailed, completely bug-free algorithm for tracking may be quite an
> acomplishment, a step towards realism which should be applauded...
> but, unfortunately, without expressly telling the player what's going
> on, they are going to be largely oblivious to it.

FOV based tracking has some notable advantages over just running A*.
The first is efficiency - provided everyone is trying to track the
player (a common safe assumption in a roguelike) there is no cost to
adding additional trackers. A* requires a separate path for every
would be tracker.

The second is that it doesn't create information. What I like about
it is that if the player teleports they leave behind an old maxima
that creatures will naturally track to, leaving them milling about the
old location. This I think is pretty important in POWDER in lower
levels when you are Tracked by kobold assassins. This spell causes
all creatures on the map (not just the kobold assassin!) to know where
you are, resulting in you being mobbed. However, some teleporting can
clear out your sent track leaving monsters heading to where you *were*
rather than your new location.

A similar thing occurs when you explore a new level. Creatures who
can sense you from far away can't immediately swarm you until you have
created a pathway by exploration.

> The average person
> isn't going to consider why a monster moves the way he does, only in
> how he moves. 95% of the time you're probably better served
> (especially in computer calculating resources) by If Player_X >
> Monster_X then Monster_X=Monster_X - 1 type tracking, with more
> complicated pathfinding only coming into play if the creature gets
> stuck.

Yes, you definitely want a hierarchical approach. You also want to
track "last known location" to handle people running around corners.
And, as pointed out, you want more senses than just sight. POWDER
handles hearing as a simple random function of the distance to the
target and the noise the target makes. No attempt is made to care
about walls, etc, the whole point of adding a "hearing" sense was to
make a sense orthogonal to dungeon layout, after all. It falls off
very quickly in POWDER, however, so really is mostly just used to
detect invisible creatures and to "see" through doors.

pende...@gmail.com

unread,
Apr 9, 2009, 1:10:22 PM4/9/09
to
On Apr 8, 6:12 pm, "rdc" <rickclar...@gmail.com> wrote:

> penderprime wrote:
> Even using a CA, there should be distinct phases to the cavern building
> routine, otherwise how would you get open areas and passageways? CAs are
> state machines, so you should know the state the CA is in at any given
> moment. I have written quite a few CAs and looked at a few more, and all of
> them enter and exit distinct states during whatever process they are
> programmed to accomplish.

I think we're talking past each other...? I'm talking about the
technique described here:
http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels

The algorithm doesn't know what a passage or room is -- all it does is
count cell neighbors and toggle cell states accordingly, five times
(after which I eliminate unconnected pieces).

> There is always a way to do something; it just depends if it is worth the
> effort to implement and maintain.

I'd be interested to see a polynomial-time algorithm that solves the
traveling salesman problem in that case :)

Jeff: Thanks, that looks like exactly the algorithm I need.

rdc

unread,
Apr 9, 2009, 3:44:34 PM4/9/09
to
penderprime wrote:

> I think we're talking past each other...? I'm talking about the
> technique described here:
> http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
> The algorithm doesn't know what a passage or room is -- all it does is
> count cell neighbors and toggle cell states accordingly, five times
> (after which I eliminate unconnected pieces).

I see what you mean. Aside from the fact that I don't think this is a very
good algorithm for generating cavern structures (I know, easy for me to say,
:) ), Jeff's algo sounds workable. Another method that comes to mind is to
simply section the cavern into a logical grid with squares of size X and
place nodes within squares that contain Y open spaces. X and Y would have to
be determined through some experimentation. You would probably end up with
more nodes than you really need, but they are cheap and it wouldn't hurt
anything.

Caverns will be in SOL so this is a topic I am going to visit soon. Just to
put back up some of what I am saying here, I'll work up a cavern algorithm
(maybe I'll play with this one) and a node system as well.

>> There is always a way to do something; it just depends if it is worth the
>> effort to implement and maintain.
>
> I'd be interested to see a polynomial-time algorithm that solves the
> traveling salesman problem in that case :)
>

Heh. My only defense here is to refer to my "worth" comment. :)

pende...@gmail.com

unread,
Apr 9, 2009, 4:08:18 PM4/9/09
to
On Apr 9, 3:44 pm, "rdc" <rickclar...@gmail.com> wrote:

> Aside from the fact that I don't think this is a very
> good algorithm for generating cavern structures (I know, easy for me to say,
> :) ),

I highly recommend it. It takes some tweaking but I've got it to
generate consistently high-quality levels with interesting geometry
that subvert the player's typical room-and-hallway expectations.
Here's a screenshot of one of the levels: http://img21.imageshack.us/img21/4740/44183476.png

I also like that this kind of layout does not put easy chokepoints
everywhere on the map. It makes fighting two monsters at once more
challenging than separately, which is as it should be IMO. In Rogue,
it's too easy to back into a doorway and fight only one at a time.

rdc

unread,
Apr 9, 2009, 7:00:19 PM4/9/09
to

That does look quite good. Very organic. When I get to caverns in SOL, I'll
will add this to my experiments and see how it works out.

David Damerell

unread,
Apr 10, 2009, 9:10:03 PM4/10/09
to
Quoting rdc <rickc...@gmail.com>:
>The only realistic, computationally cheap method to handle this is to use
>nodes. Nodes offer a lot of flexibility which is why they are ubiquitous in
>games that have complex routing.

Aren't digging / wall creation tools going to mess you up, if the game has
them?
--
David Damerell <dame...@chiark.greenend.org.uk> Distortion Field!
Today is Monday, April.

Jotaf

unread,
Apr 10, 2009, 9:27:23 PM4/10/09
to
On 11 Abr, 02:10, David Damerell <damer...@chiark.greenend.org.uk>
wrote:

> Aren't digging / wall creation tools going to mess you up, if the game has
> them?

Not if the game doesn't have them :)

I've never seen a hero preferring a pickaxe over a good ol' sword!

Jotaf

David Damerell

unread,
Apr 15, 2009, 1:42:30 PM4/15/09
to
Quoting Jotaf <jot...@hotmail.com>:
>On 11 Abr, 02:10, David Damerell <damer...@chiark.greenend.org.uk>
>>Aren't digging / wall creation tools going to mess you up, if the game has
>>them?
>Not if the game doesn't have them :)

I'm certainly inclining towards none and having a bunch of
meta-information about the map generated by the creation process, but they
are a popular kind of thing.

Of course magical digging tools that do a bunch at once might be allowed -
dig a whole fresh corridor, if one makes sense, and update the
meta-information.
--
David Damerell <dame...@chiark.greenend.org.uk> flcl?
Today is Friday, April.

pende...@gmail.com

unread,
Apr 15, 2009, 3:05:57 PM4/15/09
to
On Apr 15, 1:42 pm, David Damerell <damer...@chiark.greenend.org.uk>
wrote:

> Of course magical digging tools that do a bunch at once might be allowed -
> dig a whole fresh corridor, if one makes sense, and update the
> meta-information.

Or just recreate the meta-information from scratch every 100 turns
with the algorithm Jeff described above.

Gelatinous Mutant Coconut

unread,
Apr 15, 2009, 5:21:18 PM4/15/09
to

Couldn't that create odd behavior, where monsters continue moving
assuming the old geometry, until an arbitrary time cycle finishes, at
which point they suddenly all change their behavior? The meta-
information pathing system is already going to produce omniscient
monster behavior (they will never take a wrong turn down a dead-end,
for instance, although such behavior could be explicitly added); I
suppose some players might not really care all that much.

pende...@gmail.com

unread,
Apr 15, 2009, 5:42:57 PM4/15/09
to
On Apr 15, 5:21 pm, Gelatinous Mutant Coconut

I suppose so, but the only change in behavior is that they will become
aware of the tunnel that the player has dug within the past 100 turns
-- not the sort of change that should be noticeable. I guess the rest
of the nodes might change slightly since Jeff's description of the
algorithm involved some random numbers, but the contours of the paths
they describe would remain roughly invariant, so again I doubt any
change would be noticeable to the player.

The meta-information need not produce omnicience; it is not a pathing
algorithm but rather a set of data that a pathing algorithm can use
however you choose. If you use the nodes to optimize a Djikstra
pathing algorithm towards the player every turn for monster behavior,
that will produce omnicience. But if you use the scent-casting
algorithm for player chasing and use the nodes only to enable
wandering or fleeing behavior, there's no such problem.

One primitive wandering algorithm that works quite well is as follows:
A monster moves toward the nearest node. When it gets there, it
chooses between the attached nodes randomly (although choosing the
node from which it came only if it is the only option). Repeat this
and you get a monster that wanders the level in much the same way a
player might. A primitive fleeing algorithm with satisfying results:
same as the wandering algorithm, except that if the monster can see
the player, it should add up the distances between it and its possible
nodes, and also add up the distances between the player and its
possible nodes, and then choose the one with which it has the greatest
proximity advantage over the player.

And beyond that, I think it's quite intuitive that monsters would have
omniscience with respect to the layout of the level they live on. They
live there, after all. It's only when you give them the player's
location as well that things start to feel unfair.

rdc

unread,
Apr 16, 2009, 9:34:58 AM4/16/09
to
David Damerell wrote:
> Quoting rdc <rickc...@gmail.com>:
>>The only realistic, computationally cheap method to handle this is to use
>>nodes. Nodes offer a lot of flexibility which is why they are ubiquitous
>>in
>>games that have complex routing.
>
> Aren't digging / wall creation tools going to mess you up, if the game has
> them?
> --


Seems I missed this post somehow. I don't see digging as any problem to
using nodes. Since digging changes the map structure and requires an update
to the map, you could handle this in two ways.

1) Drop a node when the player starts to dig and connect to nearest node.
Since digging is a special process, it should be apparent when the player
starts to dig. When the player changes direction (easily detected) drop a
node and connect to previous node. When the player emerges onto a passable
tile, drop a node and connect to nearest node. You could use Djikstra to
find the nearest node.

2) As tiles are dug, add to a "dig list". Once the player has completed the
new feature, go through the dig list and add nodes as appropriate.

I think 1 would be easier to implement as well have a smaller impact on game
performance. 2 however would ensure that the player has actually created a
new passage and not just a dead end. You could modify 1 to ensure a complete
passageway by adding the new nodes to a node list and then marking each node
as a through point if the player actually breaks out onto a passable tile.

A point here that was mentioned in a following post. Nodes do not impart
omniscience knowledge. The monster travels from node to node, so it must
discover the next node location by travelling to the current target node.
Compare that to A* where the monster has an explicit list of tiles to
travel. Of course you could use A* to travel from node to node, but I don't
see that as necessary since the nodes should be in line of sight of each
other. If terrain is a factor (a monster can't cross water for example),
then the monster could backtrack the node system to find another route.

However, you can also use nodes for much more than routing. A node is a
decision point, a place where the AI must take a different evaluation path.
For example, in Unreal and other games, switches are node points. A bot can
use a switch to activate a lift or use a trap. In Quake 2, there is a point
where if a monster sees you, it will walk over to a panel and activate an
alarm, alerting the other monsters to your presence (although sadly id never
really exploited the event).

Whether you like the idea of nodes or not, you are already using them. Any
time a corridor bends you have an implicit node point, since the AI must
make a decision on how to proceed around the bend. If your monster can open
a door, the door is an implicit node, since you must make a change in
monster behavior to open the door. Nodes aren't some foreign data object
that is forced upon the map, they arise naturally as a consequence of coping
with the complexity of the map structure.

David Damerell

unread,
Apr 16, 2009, 1:31:02 PM4/16/09
to
Quoting <pende...@gmail.com>:
>On Apr 15, 1:42=A0pm, David Damerell <damer...@chiark.greenend.org.uk>

>>Of course magical digging tools that do a bunch at once might be allowed
>>dig a whole fresh corridor, if one makes sense, and update the
>>meta-information.
>Or just recreate the meta-information from scratch every 100 turns
>with the algorithm Jeff described above.

It might work, but I'll bet if you allow the level to become enough of a
mess, it's not going to work all that well; consider the Angband-style
effects that replace a chunk of dungeon with a completely random mess.
Pretty soon every node is a single space of the dungeon and you haven't
really got any meta-information at all.


--
David Damerell <dame...@chiark.greenend.org.uk> Oil is for sissies

Today is Saturday, April - a weekend.

pende...@gmail.com

unread,
Apr 16, 2009, 3:58:16 PM4/16/09
to
On Apr 16, 9:34 am, "rdc" <rickclar...@gmail.com> wrote:
> I think 1 would be easier to implement as well have a smaller impact on game
> performance.

Hard to see how performance could be an issue as between these two
options unless you're developing the game to run on an abacus.

> 2 however would ensure that the player has actually created a
> new passage and not just a dead end. You could modify 1 to ensure a complete
> passageway by adding the new nodes to a node list and then marking each node
> as a through point if the player actually breaks out onto a passable tile.

I'd posit that "if the player actually breaks out onto a passable
tile" is harder to code than it sounds -- and while this problem is
not insurmountable, I wonder what is gained by using the method given
its complexity.

> The monster travels from node to node, so it must
> discover the next node location by travelling to the current target node.

This really depends on the algorithm you use. Moreover I'm not sure
why you'd artificially restrict the monster's knowledge of the nodes
on the level. I think most players will forgive monsters for being
able to find their way around the level they are on; it's only when
they have automatic knowledge of the player's position that it starts
to feel like they're cheating.

> Compare that to A* where the monster has an explicit list of tiles to
> travel. Of course you could use A* to travel from node to node, but I don't
> see that as necessary since the nodes should be in line of sight of each
> other. If terrain is a factor (a monster can't cross water for example),
> then the monster could backtrack the node system to find another route.

I think the suggestion is not to use Djikstra to navigate from a node
to a connected node, but rather to decide which route to take through
the nodes on the way to the ultimate target. If you abstract away the
underlying level architecture and consider only the nodes, they are a
connected graph, and if you want the monster to travel efficiently
from Node A to Node B, it's a pathfinding problem for which some
flavor of Djikstra is ideal. If you want nearly-perfect pathfinding
and are concerned about performance, this is a good way to optimize --
though as usual I'd suggest first trying Djikstra without nodes to see
if performance is actually an issue.

Also, I don't think it's quite right to say that the nodes should be
in line of sight with one another. More accurately, they have to be
accessible from one another with the use of a simpler movement
algorithm. For example, given a movement algorithm of "if (x < x1) x+
+; else if (x > x1) x--; if (y < y1) y++; else if (y > y1) y--;,"
sibling nodes could be around a convex corner with no problem even
though they are not within line of sight of one another. Similarly,
even nodes that are within line of sight of one another (though not
along one of the eight cardinal directions) may not be accessible with
this simple movement algorithm if there is complicated terrain around
the edges.

> However, you can also use nodes for much more than routing. A node is a
> decision point, a place where the AI must take a different evaluation path.
> For example, in Unreal and other games, switches are node points. A bot can
> use a switch to activate a lift or use a trap. In Quake 2, there is a point
> where if a monster sees you, it will walk over to a panel and activate an
> alarm, alerting the other monsters to your presence (although sadly id never
> really exploited the event).

I'm not sure I follow this. It sounds pretty hand-wavy and assumes a
LOT more underlying architecture than the nodes we've been talking
about. Anyway, I don't understand why the switch itself should be a
decision point; shouldn't a bot decide whether to use a switch before
running over to it? Once it makes the decision to use the lift, it
should plot a course that goes to the switch and then to the lift with
no further decisions necessary. That decision should be made no later
than the last node that is a parent both of the switch path and of the
alternative path, and there's no reason it can't be made *between* two
nodes prior to that point.

> Whether you like the idea of nodes or not, you are already using them. Any
> time a corridor bends you have an implicit node point, since the AI must
> make a decision on how to proceed around the bend.

I don't think that's right. It's pretty easy to code up a simple
corridor-following routine that basically says "if there are exactly
two passable squares adjacent to me in the four cardinal directions,
and I came from one of them, then move towards the other of them." In
this case there needs be no more meta-data attached to a corner point
of a corridor than any other point in the corridor -- indeed, no
metadata at all is necessary from the time the monster enters the
corridor to the time it emerges.

> If your monster can open
> a door, the door is an implicit node, since you must make a change in
> monster behavior to open the door.

Again, I don't think this is right. Whether there is a door on a
square needs not influence whether the monster wishes to move onto
that square. All you need to do is augment the monster-move routine so
that if there is a closed door on the square the monster is trying to
move to, it will open the door and move on the next turn. Not sure
what nodes have to do with this.

> Nodes aren't some foreign data object
> that is forced upon the map, they arise naturally as a consequence of coping
> with the complexity of the map structure.

The way we are talking about them, they are definitely a foreign data
object that is forced upon the map. They have to be programmed
explicitly. You yourself talked about "dropping nodes" during digging
routines.


On Apr 16, 1:31 pm, David Damerell <damer...@chiark.greenend.org.uk>
wrote:


> Quoting   <penderpr...@gmail.com>:
>
> >On Apr 15, 1:42=A0pm, David Damerell <damer...@chiark.greenend.org.uk>
> >>Of course magical digging tools that do a bunch at once might be allowed
> >>dig a whole fresh corridor, if one makes sense, and update the
> >>meta-information.
> >Or just recreate the meta-information from scratch every 100 turns
> >with the algorithm Jeff described above.
>
> It might work, but I'll bet if you allow the level to become enough of a
> mess, it's not going to work all that well; consider the Angband-style
> effects that replace a chunk of dungeon with a completely random mess.
> Pretty soon every node is a single space of the dungeon and you haven't
> really got any meta-information at all.

True enough, I suppose -- as the map becomes more chaotic, the node
structure will approach the underlying map structure and there will be
no gains realized. One might similarly critique a file compression
algorithm on the ground that truly random data cannot be compressed.
If you don't want the chaotic area to be node-mapped, it'd be pretty
simple to flag those tiles as exempt from the noding process at the
same time as you are replacing the area with a completely random mess,
and then, when using the algorithm Jeff Lait described above, do not
generate unfixed nodes on flagged tiles.

rdc

unread,
Apr 16, 2009, 5:36:58 PM4/16/09
to
pende...@gmail.com wrote

> I'd posit that "if the player actually breaks out onto a passable
> tile" is harder to code than it sounds -- and while this problem is
> not insurmountable, I wonder what is gained by using the method given
> its complexity.

Not at all. You just examine the underlying map data to determine if the
player has emerged on a passable tile. A simple flag will suffice in this
case.

>> The monster travels from node to node, so it must
>> discover the next node location by travelling to the current target node.
>
> This really depends on the algorithm you use. Moreover I'm not sure
> why you'd artificially restrict the monster's knowledge of the nodes
> on the level. I think most players will forgive monsters for being
> able to find their way around the level they are on; it's only when
> they have automatic knowledge of the player's position that it starts
> to feel like they're cheating.

Granted. What I meant here was that a node points to the next or previous
node. This way a monster doesn't have to carry around a list of nodes.

> I think the suggestion is not to use Djikstra to navigate from a node
> to a connected node, but rather to decide which route to take through
> the nodes on the way to the ultimate target. If you abstract away the
> underlying level architecture and consider only the nodes, they are a
> connected graph, and if you want the monster to travel efficiently
> from Node A to Node B, it's a pathfinding problem for which some
> flavor of Djikstra is ideal. If you want nearly-perfect pathfinding
> and are concerned about performance, this is a good way to optimize --
> though as usual I'd suggest first trying Djikstra without nodes to see
> if performance is actually an issue.

I mentioned Djikstra only in reference to connecting nodes in the case where
nodes are dynamically generated when you dig a new path. Navigating is
simply going from one node to the next.

> Also, I don't think it's quite right to say that the nodes should be
> in line of sight with one another. More accurately, they have to be
> accessible from one another with the use of a simpler movement
> algorithm. For example, given a movement algorithm of "if (x < x1) x+
> +; else if (x > x1) x--; if (y < y1) y++; else if (y > y1) y--;,"
> sibling nodes could be around a convex corner with no problem even
> though they are not within line of sight of one another. Similarly,
> even nodes that are within line of sight of one another (though not
> along one of the eight cardinal directions) may not be accessible with
> this simple movement algorithm if there is complicated terrain around
> the edges.

You use nodes to path around complicated terrain. It is the whole point in
using routing nodes. Line of sight simplifies the process to move toward the
next node by reducing the movement code to a basic movement pattern. Every
game I have looked at that uses nodes, uses line of sight for this reason.

>> However, you can also use nodes for much more than routing. A node is a
>> decision point, a place where the AI must take a different evaluation
>> path.
>> For example, in Unreal and other games, switches are node points. A bot
>> can
>> use a switch to activate a lift or use a trap. In Quake 2, there is a
>> point
>> where if a monster sees you, it will walk over to a panel and activate an
>> alarm, alerting the other monsters to your presence (although sadly id
>> never
>> really exploited the event).
>
> I'm not sure I follow this. It sounds pretty hand-wavy and assumes a
> LOT more underlying architecture than the nodes we've been talking
> about.

Why is it hand-wavy? A switch is simply a node with a boolean condition. It
is either on or off, and generates an event when changing states. It is a
node since the ai must change state in response to using the switch; I.e.,
the bot gets on the lift when it comes down in response to the switch being
thrown.

>Anyway, I don't understand why the switch itself should be a
> decision point; shouldn't a bot decide whether to use a switch before
> running over to it? Once it makes the decision to use the lift, it
> should plot a course that goes to the switch and then to the lift with
> no further decisions necessary. That decision should be made no later
> than the last node that is a parent both of the switch path and of the
> alternative path, and there's no reason it can't be made *between* two
> nodes prior to that point.

Sounds good in theory, not so good in practice. Why? Because you are relying
on a prediction of a state that may or may not exist. If the lift doesn't
respond for some reason, your bot will wait like an idiot for a lift that
will never come. The decision to move to the lift should be taken after the
list has responded to the switch.

>> Whether you like the idea of nodes or not, you are already using them.
>> Any
>> time a corridor bends you have an implicit node point, since the AI must
>> make a decision on how to proceed around the bend.
>
> I don't think that's right. It's pretty easy to code up a simple
> corridor-following routine that basically says "if there are exactly
> two passable squares adjacent to me in the four cardinal directions,
> and I came from one of them, then move towards the other of them." In
> this case there needs be no more meta-data attached to a corner point
> of a corridor than any other point in the corridor -- indeed, no
> metadata at all is necessary from the time the monster enters the
> corridor to the time it emerges.

Your explanation proves my point: You are using an IF statement, hence a
decision point that necessitates a change in evaluation.

>> If your monster can open
>> a door, the door is an implicit node, since you must make a change in
>> monster behavior to open the door.
>
> Again, I don't think this is right. Whether there is a door on a
> square needs not influence whether the monster wishes to move onto
> that square. All you need to do is augment the monster-move routine so
> that if there is a closed door on the square the monster is trying to
> move to, it will open the door and move on the next turn. Not sure
> what nodes have to do with this.

Again, an IF situation constituting a change in evaluation.

>> Nodes aren't some foreign data object
>> that is forced upon the map, they arise naturally as a consequence of
>> coping
>> with the complexity of the map structure.
>
> The way we are talking about them, they are definitely a foreign data
> object that is forced upon the map. They have to be programmed
> explicitly. You yourself talked about "dropping nodes" during digging
> routines.
>

In the case of explicit nodes, yes. The point here is that any map will
contain implicit nodes even if they do not contain explicit nodes since
every map will have decisions points that will require a different execution
paths. Call them what you want, the result is the same. This isn't my idea,
it is one of the basic principles of computing. I am just relating the idea
to the physical entity we call a map, where a certain set of conditions (a
bend in a corridor) causes a change of state in the program. You could just
as easily say, if the head reads symbol A, change state to X.

Rick Clark

David Damerell

unread,
Apr 17, 2009, 9:27:29 AM4/17/09
to
Quoting <pende...@gmail.com>:
>On Apr 16, 1:31=A0pm, David Damerell <damer...@chiark.greenend.org.uk>

>>It might work, but I'll bet if you allow the level to become enough of a
>>mess, it's not going to work all that well; consider the Angband-style
>>effects that replace a chunk of dungeon with a completely random mess.
>>Pretty soon every node is a single space of the dungeon and you haven't
>>really got any meta-information at all.
>True enough, I suppose -- as the map becomes more chaotic, the node
>structure will approach the underlying map structure and there will be
>no gains realized. One might similarly critique a file compression
>algorithm on the ground that truly random data cannot be compressed.

Well, yes, one might, if someone had blithely assumed 1) that compression
will reduce disc space requirements and 2) that we could store a lot of
random data.

Likewise, if you say 1) nodes will improve monster pathfinding and 2) we
are going to let the map become a chaotic mess, something has got to give;
either accept that the nodes aren't always going to provide a benefit (and
then you'd have to say that other approaches are looking more attractive)
or restrict effects that chew the map up - and giving the player a digging
tool is definitely one of those, especially if it is usable indefinitely,
and especially if the player also has a Tomb Of Dorolokhe style tool for
creating rock from empty space.


--
David Damerell <dame...@chiark.greenend.org.uk> flcl?

Today is Sunday, April - a weekend.

pende...@gmail.com

unread,
Apr 17, 2009, 11:38:55 AM4/17/09
to
On Apr 17, 9:27 am, David Damerell <damer...@chiark.greenend.org.uk>
wrote:

> Likewise, if you say 1) nodes will improve monster pathfinding and 2) we
> are going to let the map become a chaotic mess, something has got to give;
> either accept that the nodes aren't always going to provide a benefit (and
> then you'd have to say that other approaches are looking more attractive)
> or restrict effects that chew the map up - and giving the player a digging
> tool is definitely one of those, especially if it is usable indefinitely,
> and especially if the player also has a Tomb Of Dorolokhe style tool for
> creating rock from empty space.

It's a pretty rare game, I'd imagine, in which the entire map devolves
into pure chaotic noise in the course of ordinary gameplay. To the
extent that it does, nodes aren't substantially LESS efficient than
dealing with the map structure directly. And to the extent that it
doesn't, nodes will generally be an improvement.

Reply all
Reply to author
Forward
0 new messages