Getting monsters with A* pathfinding to behave!
Jotaf
monsters go around the longest way. Making A* think the monsters are
"passable" results in piles of monsters around entrances, when ideally
some of them should go around to avoid the "jam".
Most solutions are a bit convoluted; at least the ones I know about.
IIRC one of the arguments for the scent-based approach is that it
avoids this; but A* is more desirable for other reasons.
Here it is. Monsters have a simple counter for how long they've been
stopped in the same tile ("idle time"). This should be 0 when moving.
When pathfinding, if a walkable tile has a monster on it, its cost is
proportional to the monster's idle time.
That's it!
Emergent behavior is that some monsters flowing naturally through the
quickest path don't make others go around the longest way; the cost is
0. But as soon as a jam is formed, the idle monsters will make it an
undesirable path, and others will try to go for alternatives.
Jotaf
msa...@gmail.com
> Emergent behavior is that some monsters flowing naturally through the
> quickest path don't make others go around the longest way; the cost is
> 0. But as soon as a jam is formed, the idle monsters will make it an
> undesirable path, and others will try to go for alternatives.
It seems like a reasonable heuristic. I have three thoughts:
1. The idle counter can be applied to any temporary obstruction, like
a fire, force field, idle monster, etc.
2. Deciding when to take the alternate route probably reduces to the
'ski rental problem', with the number of extra turns for the alternate
route being the purchase cost.
3. Different strategies for deciding when to take the alternate could
give the appearance of different AI personalities--a desperate or
impatient monster like a rabid dog might take the alternate
immediately, while a patient monster like a golem might wait forever.
copx
I had the same problem my solution goes like this:
First attempt to find a path which ignores actors (assuming that they
might move long before we reach the tile they are blocking
right now)
If we have found a path but the first tile is blocked by an
actor fire up the pathfinder again not ignoring actors this
time.
This leads to pretty sensible looking movement behavior.
Well, actually if you use plain A* you have to add more
code to get some reasonable behavior. For example in a combat
situation a monster should only accept short paths, otherwise
it might simply "walk away" because the only path to the
target is one which leads all around the map.
Jeff Lait
This is a very clever simple solution to this problem. I will have to
keep it in mind.
You might need to pad it with some local heuristics for movement. For
example,
.......
.MMMM@.
.......
Here the M's, assuming four way movement, will initially pause for a
turn until the idle count promotes the alternate path.
Likewise, there is still the siege tank problem. A monster might be
blocking a path and not know it is causing everyone else to reroute.
This monster could end up with a large idle count so appear immovable,
but a more useful AI would be for the monster to be told it should get
out of the way to let people through. Conversely, a room full of
milling neutrals will look like a cheap path despite being practically
expensive. Consider pathfinding through ADoM's living forest, for
example, where the trees keep moving but fill the entire level.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
dominik...@gmail.com
> .......
> .MMMM@.
> .......
How about launching two A*'s for each monster? If the shortest path
(actors not taken into account) is only a cell or a few cells shorter
than the shortest UNOBSTRUCTED path, they might ignore the straight
line and walk this extra cell up or down to immediately surround the
PC. However, if the unobstructed path is considerably longer than the
obstructed one, the idle count might kick in...
Mingos
Jotaf
> 1. The idle counter can be applied to any temporary obstruction, like
> a fire, force field, idle monster, etc.
Instead of "idle time", the more general description should be:
"expected time duration of obstacle". Since predicting the future is
tricky business, the heuristic is: the more time something is stopped,
the more you expect it to stay stopped. (more or less how we humans
make predictions of this kind, when we don't have any previous
knowledge.)
Some effects could be predicted accurately, like the duration of a
force field, so they can just have a cost proportional to their time
duration. "Idle time" is an "educated guess" for less predictable
actors, like other AIs.
> 2. Deciding when to take the alternate route probably reduces to the
> 'ski rental problem', with the number of extra turns for the alternate
> route being the purchase cost.
I'm not familiarized with this, I'll have to check it out!
> 3. Different strategies for deciding when to take the alternate
Some flavor is always good :)
copx wrote:
> For example in a combat
> situation a monster should only accept short paths, otherwise
> it might simply "walk away" because the only path to the
> target is one which leads all around the map.
It's better to assess the situation and act accordingly. Even in
combat, when the monster reasonably expects the path to be blocked for
some time, it's better to go around.
Jeff Lait wrote:
> This is a very clever simple solution to this problem. I will have to
> keep it in mind.
Thanks I was hoping it would be a worthwhile contribution :)
> Here the M's, assuming four way movement, will initially pause for a
> turn until the idle count promotes the alternate path.
Of course. You could make going through a moving monster have a
minimum cost. IMO what's most important is that, eventually, they'll
settle; nothing is worse than recurring stupidity!
> This monster could end up with a large idle count so appear immovable,
> but a more useful AI would be for the monster to be told it should get
> out of the way to let people through.
Yes, but this is just a simple approach and has its limits. What you
suggest is not trivial and would have to be considered carefully. But
how many times would this case happen? That single monster must be
stopped there for a reason. Most AIs don't stand in a corridor for a
long time. And if it's fighting, it can't do much to get out of the
way. With this heuristic the monsters would eventually get tired of
waiting and go around it, which would be pretty acceptable in the eyes
of the player.
> Conversely, a room full of
> milling neutrals will look like a cheap path despite being practically
> expensive. Consider pathfinding through ADoM's living forest, for
> example, where the trees keep moving but fill the entire level.
Actually, it *is* cheap to traverse: if they are moving they must be
leaving plenty of vacant tiles around. Not a direct free path, but it
can be traversed. Otherwise some would stop, making the path
undesirable for this heuristic.
I was trying to model this more-or-less after observed human behavior:
when in doubt, you wait a bit, and if the thing that's blocking you
doesn't appear to be moving, go around it. If the alternatives are
costly, you wait more.
Jotaf
msa...@gmail.com
> Instead of "idle time", the more general description should be:
> "expected time duration of obstacle". Since predicting the future is
> tricky business, the heuristic is: the more time something is stopped,
> the more you expect it to stay stopped. (more or less how we humans
> make predictions of this kind, when we don't have any previous
> knowledge.)
>
> Some effects could be predicted accurately, like the duration of a
> force field, so they can just have a cost proportional to their time
> duration. "Idle time" is an "educated guess" for less predictable
> actors, like other AIs.
>
> > 2. Deciding when to take the alternate route probably reduces to the
> > 'ski rental problem', with the number of extra turns for the alternate
> > route being the purchase cost.
>
> I'm not familiarized with this, I'll have to check it out!
Do. Its a simple and well studied problem, with solutions that provide
provably optimal results for the concerns you posed in those first two
paragraphs.
Radomir Dopieralski
> Here it is. Monsters have a simple counter for how long they've been
> stopped in the same tile ("idle time"). This should be 0 when moving.
>
> When pathfinding, if a walkable tile has a monster on it, its cost is
> proportional to the monster's idle time.
It's very neat! I think it could be more accurate to use the cost of
moving to the next square as the monster's cost. This way they don't
even have to become idle to be an obstacle, the cost propagates through
any crowd.
--
Radomir Dopieralski, http://sheep.art.pl
Ray Dillinger
<clip>
> Emergent behavior is that some monsters flowing naturally through the
> quickest path don't make others go around the longest way; the cost is
> 0. But as soon as a jam is formed, the idle monsters will make it an
> undesirable path, and others will try to go for alternatives.
Consider this:
#####
....########
............
....########
@......fc...
....########
....#
#####
Here f is a fleeing monster and c is a charging monster. They
are deadlocked. Here's a problem with your heuristic; they stand
there staring at each other until one of them calculates that taking
the other path to (or away from) the character would be cheaper. Then
that creature takes a step, backing away on the first step of the
alternate path. Then the other creature, its way partly unblocked,
takes a step. Suddenly both have their "idle time" reduced to zero;
they have taken a step! So they step back onto the path that's now
"cheaper" and they're back to staring at each other again.
I think you need to ask yourself what's causing the jams to form in the
first place. There are a lot of different types of jams, and many/most
of them are preventable with a few tweeks to the AI code.
#####
....######
.@abcdefghij
....######
....#
....#
#####
Here's a case where you have a jam because: a is fighting the @, and
doesn't want to move. Assuming 4-way movement, b could step up or
down, but doesn't want to because both would be slightly further away
from @, and cdef etc have no options. In this case you can get better
behavior by making monsters who can't get closer to @ by moving in any
direction, move in a random direction. b moves up or down, and the
next turn b can move closer plus the line formerly behind b moves
forward. With your heuristic, it would take a turn before b decided
to move up or down.
Assuming 8-way movement, b or c could get closer to @ by moving
diagonally, so the line probably keeps moving for a few turns, but....
#####
..be######
.@adghij
..cf######
....#
....#
#####
presents the same problem again. a, b, and c don't want to move
because they're fighting the @, d didn't move because he couldn't get
closer by moving, e and f have moved diagonally because that got
them (uselessly) closer, and ghij are stuck. Your heuristic would
have f waiting 2 turns for c to get out of the way. Once again, you
can get better behavior by making monsters who can't get closer to @
by moving in any direction, move in a random available direction. In
this case that would make f move immediately into one of the two
available squares he can reach, giving the line room to continue
moving.
But another problem is with monsters a, b and c. They're oblivious
to the fact that they've formed a roadblock, and your pathfinding tweek
won't help that a bit. IMO, their AI should be aware of three basic
tactical facts:
1) their neighbors include @ and 3 or more other monsters.
2) their neighbors include an empty space adjacent to @.
3) @ has at least 3 empty-space neighbors.
When this happens they should have a significant chance (50%?) to
move to the aforementioned empty space on their move instead of
attacking. This allows other monsters to get through. After
all there are 8 squares @ can be attacked from, not just three, and
getting him surrounded sooner rather than later is good tactics.
Bear
Gerry Quinn
d71a03...@j38g2000yqa.googlegroups.com>, msa...@gmail.com says...
If it were, in situations that arise in typical gamese, games would have
no pathfinding issues.
- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>
Gerry Quinn
@l1g2000yqj.googlegroups.com>, dominik...@gmail.com says...
Sensible... and who can criticise the concept of AI that is reasonably
consistent with Real Intelligence?
msa...@gmail.com
> If it were, in situations that arise in typical gamese, games would have
> no pathfinding issues.
I'm not sure what you are saying.
The solutions to the ski rental problem are provably optimal (the A*
algorithm is too I believe). It also addresses exactly the problem he
was considering: how does an online algorithm with no a-priori
knowledge decide when to choose a permanent, expensive solution
(alternate path/ski purchase) over a low cost temporary one (waiting/
ski rental).
Being provably optimal at solving a specific part of the problem does
not, under any circumstance, mean that its going to solve *all* the
problems associated with a monster getting to a destination. Nor is it
any indicator of whether you are considering all the right problems in
the first place.
Did that clear it up?
David Ploog
[How to avoid traffic jams in the dungeon?
Picture not taken from bear.]
#####
..adg
.@beh
..cfi
#####
> But another problem is with monsters a, b and c. They're oblivious
> to the fact that they've formed a roadblock, and your pathfinding tweek
> won't help that a bit. IMO, their AI should be aware of three basic
> tactical facts:
> 1) their neighbors include @ and 3 or more other monsters.
> 2) their neighbors include an empty space adjacent to @.
> 3) @ has at least 3 empty-space neighbors.
>
> When this happens they should have a significant chance (50%?) to
> move to the aforementioned empty space on their move instead of
> attacking. This allows other monsters to get through. After
> all there are 8 squares @ can be attacked from, not just three, and
> getting him surrounded sooner rather than later is good tactics.
Since not a long time, Crawl uses this: if a monster that could attack the
player (is next to it), can make room for a comrade, it will do the
latter. We restricted this to monsters of the same genus (so it will work
for a group of rats, of among orcs of any type).
The idea was suggested by Derek Ray of Sporkhack and works wonders.
Monsters seem to be much more clever, and the change has interesting
tactical implications.
David
Gerry Quinn
@v38g2000yqb.googlegroups.com>, msa...@gmail.com says...
Yes.
I can't remember, possibly I read "Do!" as "Doh!" and reacted
instinctively :-)
msa...@gmail.com
>
> Yes.
>
> I can't remember, possibly I read "Do!" as "Doh!" and reacted
> instinctively :-)
Aight :)
pende...@gmail.com
> The solutions to the ski rental problem are provably optimal (the A*
> algorithm is too I believe). It also addresses exactly the problem he
> was considering: how does an online algorithm with no a-priori
> knowledge decide when to choose a permanent, expensive solution
> (alternate path/ski purchase) over a low cost temporary one (waiting/
> ski rental).
I don't think this is strictly accurate. The ski rental problem
assumes a non-adaptive adversary. In the context of Rogue, the
adversary can in some cases be the player, who can, e.g., wait to
unblock a passage (by opening a door, removing a scroll of scare
monster, killing the harmless monster in the way, or whatever else)
until he sees that the scary monster behind it has left to try another
route. In such a case, perhaps the right answer is for the monster
NEVER to try another route. You might argue that the proposed solution
is no better than the ski rental solution since both will have the
monster leave at some point, and you'd be right, but still both are a
far cry from provably optimal. A provably optimal response in this
kind of situation, if one even exists, would involve significant game
theory.
Practical upshot of my post? Probably not much -- but I always feel
compelled to respond when people assert mathematical truths about
things for which the mathematical axioms do not match up
(mathematically) with the real-world conditions.
msa...@gmail.com
> I don't think this is strictly accurate.
It is strictly accurate, but I agree its not enough to address all the
problems in getting a monster to find a player and poke him in the eye
with a pointy stick.
On Feb 9, 10:00 pm, msal...@gmail.com wrote:
pende...@gmail.com
> On Feb 10, 12:52 pm, penderpr...@gmail.com wrote:
>
> > I don't think this is strictly accurate.
>
> It is strictly accurate, but I agree its not enough to address all the
> problems in getting a monster to find a player and poke him in the eye
> with a pointy stick.
No. You were incorrect to say that it "it also addresses exactly the
problem he was considering." It does not; it addresses the problem he
was considering inexactly at best. The player can influence the
waiting time, and the player can and will adapt to the algorithm. The
ski rental problem assumes a non-adaptive adversary. Without this
assumption, the theorem (the optimality of the ski problem algorithm)
cannot be proved because it is in fact not true.
Maybe the ski problem algorithm would still be a good heuristic, but
it is not provably optimal.
msa...@gmail.com
> No. You were incorrect to say that it "it also addresses exactly the
> problem he was considering." It does not; it addresses the problem he
> was considering inexactly at best. The player can influence the
> waiting time, and the player can and will adapt to the algorithm. The
> ski rental problem assumes a non-adaptive adversary. Without this
> assumption, the theorem (the optimality of the ski problem algorithm)
> cannot be proved because it is in fact not true.
>
> Maybe the ski problem algorithm would still be a good heuristic, but
> it is not provably optimal.
No. My discussion was limited to two paragraphs, which were quoted.
The jist of those paragraphs was: how does a monster decide when to
take an alternate path when he doesn't know how long the temporary
obstacle will be there. There are plenty of other problems, that you
mention, that ski rental solutions won't solve. There are also plenty
of reasons not to use ski rental solutions. But for this specific
problem I quoted, if you are trying to learn more about how to solve
it, you should read up on ski rentals.
You clearly think I am saying something that I am not. I agree with
all the concerns you are raising, and I've been clear about that.
Ray Dillinger
> On Mon, 9 Feb 2009, Ray Dillinger wrote:
>
> [How to avoid traffic jams in the dungeon?
> Picture not taken from bear.]
>
> #####
> ..adg
> .@beh
> ..cfi
> #####
>
>> But another problem is with monsters a, b and c. They're oblivious
>> to the fact that they've formed a roadblock, and your pathfinding tweek
>> won't help that a bit. IMO, their AI should be aware of three basic
>> tactical facts:
>> 1) their neighbors include @ and 3 or more other monsters.
>> 2) their neighbors include an empty space adjacent to @.
>> 3) @ has at least 3 empty-space neighbors.
As I look at it, I think I need to revise the "magic numbers" here.
This would work better in more situtations:
1) Neighbors include @ and 2 or more other monsters
2) Neighbors include an empty space adjacent to @.
3) @ has at least 2 empty-space neighbors.
> Since not a long time, Crawl uses this: if a monster that could attack the
> player (is next to it), can make room for a comrade, it will do the
> latter. We restricted this to monsters of the same genus (so it will work
> for a group of rats, of among orcs of any type).
>
> The idea was suggested by Derek Ray of Sporkhack and works wonders.
> Monsters seem to be much more clever, and the change has interesting
> tactical implications.
Yeah. Monsters that fail to take advantage of an opportunity
to surround the player are too easy to cope with.
Bear
pende...@gmail.com
> No. My discussion was limited to two paragraphs, which were quoted.
> The jist of those paragraphs was: how does a monster decide when to
> take an alternate path when he doesn't know how long the temporary
> obstacle will be there. There are plenty of other problems, that you
> mention, that ski rental solutions won't solve. There are also plenty
> of reasons not to use ski rental solutions. But for this specific
> problem I quoted, if you are trying to learn more about how to solve
> it, you should read up on ski rentals.
No arguments that one should read up on it, but that's not what I was
objecting to. The ski rental solution is not "provably optimal" even
when constrained to the question of "how does a monster decide when to
take an alternate path when he doesn't know how long the temporary
obstacle will be there." It requires an additional assumption for
provable optimality: that the player cannot influence the duration of
the temporary obstacle. So the statement was wrong from a technical
perspective, and it was also wrong in the context of this thread,
since most of this thread has focused on the way monsters pile up
around players -- which is a temporary blockage whose duration the
player can usually influence!
Again, I have no particular beef with the idea that the ski rental
solution is a great heuristic in these situations. I take issue only
with the implication that its optimality is a mathematical truth
proceeding directly from the ski rental theorem. It is definitely not.
Matthew Allen
> No arguments that one should read up on it, but that's not what I was
> objecting to. The ski rental solution is not "provably optimal" even
> when constrained to the question of "how does a monster decide when to
> take an alternate path when he doesn't know how long the temporary
> obstacle will be there." It requires an additional assumption for
> provable optimality: that the player cannot influence the duration of
> the temporary obstacle.
o.O
If you say so. This is a semantics argument, and not a particularly
valuable one.
The A* algorithm provides an optimal path between two points. Clearly,
that doesn't mean that in a roguelike it's going to produce the
'right' path, or we wouldn't be having this discussion. If you want to
claim that, as a result, A* does not solve the path problem optimally
for roguelikes, I can't stop you. As far as I can tell, this argument
is no different from the one you are making about ski rental solutions
and deciding when to take an alternate route.
pende...@gmail.com
> The A* algorithm provides an optimal path between two points. Clearly,
> that doesn't mean that in a roguelike it's going to produce the
> 'right' path, or we wouldn't be having this discussion. If you want to
> claim that, as a result, A* does not solve the path problem optimally
> for roguelikes, I can't stop you. As far as I can tell, this argument
> is no different from the one you are making about ski rental solutions
> and deciding when to take an alternate route.
The two are very different. A* finds optimal paths in a connected
graph. Roguelike levels are connected graphs. Therefore, A* finds
optimal paths in Roguelike levels. (Obviously it is unknown whether
these paths will be optimal one frame later.)
The ski rental algorithm is an optimal algorithm when the duration of
the blockage is unknown AND is not influenced by an adaptive
adversary. Roguelike levels contain blockages whose duration is
unknown, but many of them are influenced by adaptive adversaries.
Therefore, you can draw no mathematically provable conclusions about
whether any particular application of the ski rental algorithm will be
optimal. Maybe it is still a great heuristic and maybe it isn't, but
regardless that's different from a claim of provable optimality.
Matthew Allen
> The two are very different. A* finds optimal paths in a connected
> graph. Roguelike levels are connected graphs. Therefore, A* finds
> optimal paths in Roguelike levels. (Obviously it is unknown whether
> these paths will be optimal one frame later.)
>
> The ski rental algorithm is an optimal algorithm when the duration of
> the blockage is unknown AND is not influenced by an adaptive
> adversary. Roguelike levels contain blockages whose duration is
> unknown, but many of them are influenced by adaptive adversaries.
> Therefore, you can draw no mathematically provable conclusions about
> whether any particular application of the ski rental algorithm will be
> optimal. Maybe it is still a great heuristic and maybe it isn't, but
> regardless that's different from a claim of provable optimality.
This is not remotely compelling.
A* will get a monster from point a to point b along an optimal path
*as long as nothing changes*. Ski rental solutions will get a monster
to make an optimal decision about how long to wait for a temporary
blockage to clear *as long as nothing changes* (not counting the
expected change in the blockage). In reality, change will happen, and
for both algorithms the player can cause changes that abuse the
respective algorithms. They are no different in this respect.
This discussion is not valuable, and I'm done. You can call them
optimal or not. You can believe they are different if you insist. I'm
going to go on believing my original claim was worded correctly--that
the ski rental solutions will be optimal for a specific problem of
limited usefulness to the actual game. You can go on believing
whatever you like.
pende...@gmail.com
> This discussion is not valuable, and I'm done. You can call them
> optimal or not. You can believe they are different if you insist. I'm
> going to go on believing my original claim was worded correctly--that
> the ski rental solutions will be optimal for a specific problem of
> limited usefulness to the actual game. You can go on believing
> whatever you like.
You said "provably optimal," which you are well aware means something
a lot stricter than the position to which you've backpedaled.
Agreed that this hasn't been a particularly valuable conversation; as
I said, it's just my pet peeve when people throw around claims of
mathematical truth when they are categorically incorrect. The great
thing about math is that generally a statement is either right or
wrong, and no amount of rhetoric can escape the outcome, which makes
it very satisfying to argue when I am right.
Matthew Allen
> You said "provably optimal," which you are well aware means something
> a lot stricter than the position to which you've backpedaled.
In fact, I have been making the same claim repeatedly--it was always
far more limited than you seem to think. You need to learn to read
more accurately if you want to play this game.
Here, so you can practice:
pende...@gmail.com
previous post would be your last, but I'm still game.
On Feb 10, 10:07 pm, Matthew Allen <msal...@gmail.com> wrote:
> In fact, I have been making the same claim repeatedly--it was always
> far more limited than you seem to think. You need to learn to read
> more accurately if you want to play this game.
>
> Here, so you can practice:
>
> On Feb 9, 4:46pm, msal...@gmail.com wrote:
>
> > On Feb 9, 4:38 pm, Jotaf <jota...@hotmail.com> wrote:
> > > Instead of "idle time", the more general description should be:
> > > "expected time duration of obstacle". Since predicting the future is
> > > tricky business, the heuristic is: the more time something is stopped,
> > > the more you expect it to stay stopped. (more or less how we humans
> > > make predictions of this kind, when we don't have any previous
> > > knowledge.)
> > > Some effects could be predicted accurately, like the duration of a
> > > force field, so they can just have a cost proportional to their time
> > > duration. "Idle time" is an "educated guess" for less predictable
> > > actors, like other AIs.
> > > > 2. Deciding when to take the alternate route probably reduces to the
> > > > 'ski rental problem', with the number of extra turns for the alternate
> > > > route being the purchase cost.
> > > I'm not familiarized with this, I'll have to check it out!
> > Do. Its a simple and well studied problem, with solutions that provide
> > provably optimal results for the concerns you posed in those first two
> > paragraphs.
The solution to the ski rental problem does not provide a provably
optimal result for either of the situations Jotaf raised. The first
situation is when a monster does not know how long an obstacle will
remain in its path. In that case, the ski rental algorithm can claim
provable optimality ONLY IF the player cannot influence the duration
of the temporary obstacle. Nearly every example of a temporary
obstacle discussed in this entire thread involves cases in which the
player manifestly CAN influence the duration. You were wrong, either
in claiming that the ski rental problem provides provably optimal
solutions or in claiming that it "exactly" addresses the situation
Jotaf raised. It absolutely does not; it is strictly inapplicable to
situations involving an adaptive adversary. At best, it can handle
only SOME of the cases that arise in a roguelike game in a provably
optimal manner. Your statement was like saying "integers are prime
numbers," which is wrong because even though SOME integers are indeed
prime numbers, others are not.
The other situation Jotaf raised is when the duration of the obstacle
is known. In that case, the ski rental algorithm is sub-optimal and
useless, since you can weigh the cost of renting against the cost of
buying perfectly and choose the cheaper option.
Matthew Allen
> I'm not sure why you're still arguing when you claimed that your
> previous post would be your last, but I'm still game.
Because I hate letting obtuse people have the last word. Its a
personal problem.
> The solution to the ski rental problem does not provide a provably
> optimal result for either of the situations Jotaf raised. The first
> situation is when a monster does not know how long an obstacle will
> remain in its path. In that case, the ski rental algorithm can claim
> provable optimality ONLY IF the player cannot influence the duration
> of the temporary obstacle. Nearly every example of a temporary
> obstacle discussed in this entire thread involves cases in which the
> player manifestly CAN influence the duration. You were wrong, either
> in claiming that the ski rental problem provides provably optimal
> solutions or in claiming that it "exactly" addresses the situation
> Jotaf raised. It absolutely does not; it is strictly inapplicable to
> situations involving an adaptive adversary. At best, it can handle
> only SOME of the cases that arise in a roguelike game in a provably
> optimal manner. Your statement was like saying "integers are prime
> numbers," which is wrong because even though SOME integers are indeed
> prime numbers, others are not.
Here is what you are getting wrong: those two paragraphs don't mention
the player once. If you are *actually* reading like a mathematician,
which you are trying to, its simply not part of the formulated
problem. Sure, it was brought up other times, but I was very clear
about what my statement was limited to. You need to learn to stick to
the statements that were made if you are going to play the pedantic
game. You can't just go inferring things that weren't there if you
want to read literally.
I agree and have agreed repeatedly that its not going to be the best
solution, and that its only optimal in a specific and limited context
that you are not going to experience in an actual game. I'm flat out
agreeing with 95% of what you say, so if you are going to carry on
with this nonsense you can save yourself the trouble of repeating it
over and over.
> The other situation Jotaf raised is when the duration of the obstacle
> is known. In that case, the ski rental algorithm is sub-optimal and
> useless, since you can weigh the cost of renting against the cost of
> buying perfectly and choose the cheaper option.
That wasn't a concern he raised. Unless you would define "this problem
is easy to solve if you know the duration" as a concern.
David Damerell
>I'm not sure why you're still arguing when you claimed that your
>previous post would be your last, but I'm still game.
He lies about that. Haven't you noticed?
--
David Damerell <dame...@chiark.greenend.org.uk> Kill the tomato!
Today is First Friday, February.
pende...@gmail.com
> Here is what you are getting wrong: those two paragraphs don't mention
> the player once. If you are *actually* reading like a mathematician,
> which you are trying to, its simply not part of the formulated
> problem. Sure, it was brought up other times, but I was very clear
> about what my statement was limited to. You need to learn to stick to
> the statements that were made if you are going to play the pedantic
> game. You can't just go inferring things that weren't there if you
> want to read literally.
Blockages IN THE CONTEXT OF ROGUELIKE GAMES was the formulated
problem. The player is necessarily part of a Roguelike game. It's not
a question of reading literally, it's a question of understanding what
you read.
And you know what? Even without the player, other monsters forming
blockages were expressly what the problem was about. And other
monsters are technically an adaptive adversary, since unless you have
separate AI modules, if you change the behavior of the monster
reacting to the blockage, you'll also change the behavior of the
monster doing the blocking. In that sense it's not clear that the ski
rental problem strictly applies even if the player were not involved
at all! (I'll be interested to see if your next claim is that you
obviously intended the ski rental algorithm to be applied to a single
monster on the map at a time.)
> I agree and have agreed repeatedly that its not going to be the best
> solution, and that its only optimal in a specific and limited context
> that you are not going to experience in an actual game. I'm flat out
> agreeing with 95% of what you say, so if you are going to carry on
> with this nonsense you can save yourself the trouble of repeating it
> over and over.
You said nothing of the kind. You said it "exactly" fits the
specifications of Jotaf's proposed problem, which was a problem set in
the context of a roguelike game, and that it yields a "provably
optimal" result. Your statements were not qualified like you are now
pretending they were.
> Because I hate letting obtuse people have the last word. Its a
> personal problem.
...which is why I will keep responding. You were wrong as a matter of
cold mathematical fact -- and you were pretty smug about it -- and now
you are trying to bluster your way around it and continue to insist
that you were right, including by calling me names and insulting my
intelligence. If you can't get there on the merits, you'll apparently
try to get there by attrition -- and all for the dubious purpose of
defending your internet reputation. It's obnoxious. I will continue to
point out, politely, how you were wrong until one of three things
happens: you admit it, you drop it, or one of us dies of old age.
Matthew Allen
Alright. I got frustrated that you kept missing my point, but I'm
sorry that I resorted to name calling. Let me start over:
From my perspective, the two paragraphs I quoted only covered one
limited facet of the discussion at hand, which was: how does a monster
figure out when to take an alternate route around a temporary
blockage. That is the only part of the problem the text explicitly
mention. My response was only directed at what I believe to be this
very limited aspect of the problem. In fact, I used the word
"specific" because it means "nothing more, and nothing less" than the
very limited part of the problem discussed in the quoted paragraphs,
and not the implicit parts of the problem you keep trying to include.
My only beef is that I felt it was clear that I did not make the
grandiose claim that you feel I did. I am aware that the actual
problem of how to make this decision in a roguelike is far more
complicated that the simple problem that I was addressing. From my
perspective, I made no claim that the ski rental solutions are
sufficient for making this decision in-game, and I made every effort
to clarify that. I don't know how you missed this, but its clear I
didn't do it well enough.
I'm sorry that I wasn't clear enough for you. I have always understood
that the actual problem as it occurs in game is more sophisticated
than the subset I was talking about. I made an effort to limit my
statement to a very specific element of the problem, but it clearly
wasn't enough. Please forgive me, because to me its still obvious that
I limited the scope of the problem so that my response was correct.
But I acknowledge and understand your position.
Ok?
David Ploog
[interrupting interesting flamewar very briefly]
> You were wrong as a matter of cold mathematical fact
I am a mathematician and I envision some mathematical truths (not all,
granted) as hot, a few of them being outright sexy.
David
pende...@gmail.com
> From my perspective, the two paragraphs I quoted only covered one
> limited facet of the discussion at hand, which was: how does a monster
> figure out when to take an alternate route around a temporary
> blockage. That is the only part of the problem the text explicitly
> mention. My response was only directed at what I believe to be this
> very limited aspect of the problem. In fact, I used the word
> "specific" because it means "nothing more, and nothing less" than the
> very limited part of the problem discussed in the quoted paragraphs,
> and not the implicit parts of the problem you keep trying to include.
The "very limited" problem we're talking about is temporary blockages
whose duration cannot be ascertained in advance. In Roguelikes, the
overwhelming majority of those cases -- if not 100% of them -- is
either blockages that the player controls (closed doors, scrolls of
scare monster, etc.) or other monsters loitering. For the reasons that
I have mentioned, the ski rental algorithm is not a "provably optimal"
solution. I'm not smuggling some pathological fringe case into an
otherwise simple concept; I'm talking about the majority of these
cases. This is not a question of opinions or perspectives or feelings;
it is a question of whether the assumptions of the theorem you cited
are in fact satisfied "exactly" by the problem we're talking about.
And they're not.
> I am a mathematician and I envision some mathematical truths (not all,
> granted) as hot, a few of them being outright sexy.
I was a lowly math major, and I totally agree. Still, THIS
mathematical truth is no Infinitude of the Primes :)
Matthew Allen
It is really unnecessary to repeat this over and over. I am well aware
of the difficulties that arise from a malicious adversary. I'm not
sure they are the source of 100% of blockages, but they are at least
the cause of a significant fraction of blockages. I'm not sure a
loitering NPC violates the assumptions of the ski rental formulation,
but I think you mean that to be 'loitering waiting to get to a
player'.
It seems that the source of our problems is this:
You, for some reason, believe the words 'exact' and 'specific' to be
inclusive terms that mean 'the problem stated and all related or
implied problems'. I, on the other hand, am using these words as
exclusive and limiting terms that mean 'only what was explicitly
stated'. Math is on my side here, but I will certainly entertain the
idea that I was not clear enough using them.
I've said it over and over, and I'll say it again: I do not believe
this solution will be optimal in-game. I do not believe it to be
generally optimal. I do not believe it to be realistically optimal. I
only believe it to be 'specifically' or 'exactly' optimal--when
applied to the very limited problem that was stated, and not its
implied or related problems.
Did this help? Again, I agree with 95% of what you say. From my
perspective, I used words like specific and exact to clearly limit the
scope of the problem. But it obviously wasn't clear enough for
everyone. Is the source of our confusion?
pende...@gmail.com
> I'm not sure a
> loitering NPC violates the assumptions of the ski rental formulation,
> but I think you mean that to be 'loitering waiting to get to a
> player'.
Not necessarily. Even ten monsters wandering randomly about the map
will frequently run into each other and occasionally have pile-ups.
Thus, any single monster will try to evaluate how long the pile-up
will last -- but how long the pile-up will last is a product of how
the other monsters are performing the same evaluation. In this sense
even the other monsters are adaptive (or at least "reactive")
adversaries, and therefore this kind of blockage does not fit the
assumptions of the ski rental problem.
> It seems that the source of our problems is this:
>
> You, for some reason, believe the words 'exact' and 'specific' to be
> inclusive terms that mean 'the problem stated and all related or
> implied problems'. I, on the other hand, am using these words as
> exclusive and limiting terms that mean 'only what was explicitly
> stated'.
You made a categorical statement about a set of problems. I pointed
out that the statement is false for at least some of the problems in
that class. These are not "related or implied problems"; they are
within the class of problems you were addressing. In math, this would
be considered disproof by counterexample. You apparently think your
statement should be considered true unless I can demonstrate that you
were wrong for EVERY problem in the class, which is ridiculous.
Matthew Allen
> Not necessarily. Even ten monsters wandering randomly about the map
> will frequently run into each other and occasionally have pile-ups.
> Thus, any single monster will try to evaluate how long the pile-up
> will last -- but how long the pile-up will last is a product of how
> the other monsters are performing the same evaluation. In this sense
> even the other monsters are adaptive (or at least "reactive")
> adversaries, and therefore this kind of blockage does not fit the
> assumptions of the ski rental problem.
I think all that is required by the Ski Rental Problem is that your
decision may be invalidated after a certain amount of time and you
have no a-priori knowledge of when or what the distribution is. As
long as each AI cannot read the others decision state, this
requirement is still met.
> You made a categorical statement about a set of problems. I pointed
> out that the statement is false for at least some of the problems in
> that class. These are not "related or implied problems"; they are
> within the class of problems you were addressing. In math, this would
> be considered disproof by counterexample. You apparently think your
> statement should be considered true unless I can demonstrate that you
> were wrong for EVERY problem in the class, which is ridiculous.
This is exactly the opposite of what I have been saying. From my
perspective, I made a limited statement about a small subset of the
problem. And I only think its true because I specifically didn't
consider the whole problem. My intention in my original statement, and
certainly in my many subsequent statements, was that I was *not*
regarding a "set of problems" or a "class of problems", but one
limited sub-problem. Do you understand yet?
Jeff Lait
> On Feb 13, 11:07 am, penderpr...@gmail.com wrote:
>
> > Not necessarily. Even ten monsters wandering randomly about the map
> > will frequently run into each other and occasionally have pile-ups.
> > Thus, any single monster will try to evaluate how long the pile-up
> > will last -- but how long the pile-up will last is a product of how
> > the other monsters are performing the same evaluation. In this sense
> > even the other monsters are adaptive (or at least "reactive")
> > adversaries, and therefore this kind of blockage does not fit the
> > assumptions of the ski rental problem.
>
> I think all that is required by the Ski Rental Problem is that your
> decision may be invalidated after a certain amount of time and you
> have no a-priori knowledge of when or what the distribution is. As
> long as each AI cannot read the others decision state, this
> requirement is still met.
Except in this problem domain we *do* have some knowledge of the
distribution. For example, the duration of the blocker is not
unbounded. In terms of ski rental, if renting skiis is $1 a day and
purchase is $10,000,000,000, the "optimal" solution will have a non-
zero chance to purchase on day one. However, despite our claims that
our holiday is unbounded, we can be quite confident it won't last 27
million years.
This is the heart of my objection of a characterization of
"optimality" of ski rental being anything more than a cute result. In
absolutely any practical situation you need a layer of heuristics on
top of it to make it at all sane or you'll hit these sorts of boundary
conditions.
> > You made a categorical statement about a set of problems. I pointed
> > out that the statement is false for at least some of the problems in
> > that class. These are not "related or implied problems"; they are
> > within the class of problems you were addressing. In math, this would
> > be considered disproof by counterexample. You apparently think your
> > statement should be considered true unless I can demonstrate that you
> > were wrong for EVERY problem in the class, which is ridiculous.
>
> This is exactly the opposite of what I have been saying. From my
> perspective, I made a limited statement about a small subset of the
> problem.
You, however, failed to clearly communicate this fact. Admonishing
people for not reading what you meant to say ignores the problem with
your original text.
> And I only think its true because I specifically didn't
> consider the whole problem. My intention in my original statement, and
> certainly in my many subsequent statements, was that I was *not*
> regarding a "set of problems" or a "class of problems", but one
> limited sub-problem. Do you understand yet?
You took two paragraphs out of context. You then said you had an
optimal solution to those paragraphs. The solution is optimal to the
out-of-context paragraphs. However, it is not optimal in the context
the paragraphs were written. The confusion of the readers is thus
justified. I know I had the same reaction as others: "What? How is
that optimal for our goal of "Getting monsters with A* pathfinding to
behave!"?"
As argued, the "optimality" of this algorithm feels like a no-true-
Scotsman situation. It is optimal provided we only consider cases for
which it is optimal...
The take away, I think, is to recognize that claims of optimality are
a hot button issue. Thus, when made, one should be careful to ensure
readers are aware you are aware of the limitations of said
optimality. For example, if you had said:
"The ski rental problem has an optimal solution to the exact problem
you describe. However, note in the context of an actual game one has
some domain specific knowledge which can provide better heuristics."
You wouldn't then have people jumping up and down to provide counter
examples, and at least if they did, they'd be in context of showing
how the optimality fails in certain game scenarios.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
Matthew Allen
> The take away, I think, is to recognize that claims of optimality are
> a hot button issue. Thus, when made, one should be careful to ensure
> readers are aware you are aware of the limitations of said
> optimality. For example, if you had said:
> "The ski rental problem has an optimal solution to the exact problem
> you describe. However, note in the context of an actual game one has
> some domain specific knowledge which can provide better heuristics."
> You wouldn't then have people jumping up and down to provide counter
> examples, and at least if they did, they'd be in context of showing
> how the optimality fails in certain game scenarios.
Yeah, saying anything is optimal means you will have a bunch of people
trying to come up with counterexamples because it low-hanging fruit. I
thought I cleared it up enough in my next post but obviously I did
not. I didn't mean to suggest that it was anything more than a cute
result that would teach you something about the problem. Certainly not
a solution that would work in game. I'll be more careful if I use that
phrase in the future.
Jeff Lait
> Yeah, saying anything is optimal means you will have a bunch of people
> trying to come up with counterexamples because it low-hanging fruit.
Guilty as charged :>
Pointless
> Most solutions are a bit convoluted; at least the ones I know about.
> IIRC one of the arguments for the scent-based approach is that it
> avoids this; but A* is more desirable for other reasons.
...
> Jotaf
I thought it would be helpful for some to post such a convoluted
approach, one that I know works and that I am satisfied with.
I saw someone mention running two A* algorithms, one counting other
characters, one not counting other characters. This is what I would
suggest. Here's a practical implementation of the algorithm that I've
programmed into MetaCollider.
I first run an A* algorithm that treats spaces occupied by other
actors as impassable. If a path is not found that is not sufficiently
short (like if it takes the character all around the map), another
iteration of the A* pathfinding algorithm is run, this time counting
non-adjacent spaces occupied by characters as passable. Instead of
standing dumbfounded, or running around the map, characters will move
in as close to the player as possible and wait there. I also use the
same algorithm for fleeing/withdrawing/maneuvering, so there were some
subtle benefits to this choice.
I at first wanted to make a shared pathfinding log, which would record
the future location of every character in a group (like a raiding
party of orcs), so that characters could find an optimum path _before_
the path was blocked. It proved to be unworkable, but I encourage
designers with more expertise to try it.
One other thing I implemented is maneuvering. When the player does a
certain amount of damage to a character (to a group of characters, to
be more specific), the character has a chance to maneuver into an
unoccupied space and let another character in the enemy party surround
the player. So for example:
1. could become 2.
###. ###.
#.aa #aa.
#@#. #@#.
#### ####
This creates an interesting terrain feature: some positions (like
corridors) are completely fortified from being surrounded, which other
positions (like standing in an open room, battling a monster standing
in a doorway) are only partially fortified, because there is a chance
of being surrounded.
Another idiosyncrasy that caused me great suffering was for fleeing
monsters. Take, for example, a monster fleeing into a dead end.
####
@.a#
####
If the next turn belonged to the 'a', it would move into the player's
attack radius, to be attacked, and then move back into the corner, ad
infinitum, until it is defeated! Since I did not want the hidden
gameplay complexity of a "turn and fight" algorithm like in Angband, I
made a condition that the character would stay put if the only
adjacent square was next to the player. This works well with my speed
system.
I hope this post helps anyone that is struggling with pathfinding, as
all the abstract possibilities can be endlessly challenging!
-Pointless
Jotaf
> I at first wanted to make a shared pathfinding log, which would record
This implies a time-variant state, bigger than just (x,y). It's doable
but probably overkill. I've considered it numerous times.
> ... the character has a chance to maneuver into an
> unoccupied space and let another character in the enemy party surround
> the player.
This makes a lot of sense, and may easily complement the heuristic I
suggested. One does not render the other useless! Having both makes
for a much better overall system.
> This creates an interesting terrain feature: some positions (like
> corridors) are completely fortified from being surrounded, which other
> positions (like standing in an open room, battling a monster standing
> in a doorway) are only partially fortified, because there is a chance
> of being surrounded.
This is pretty cool. I'd especially like to see dumb creatures pile up
to be slaughtered while smart creatures have the surrounding behavior.
> Another idiosyncrasy that caused me great suffering was for fleeing
> monsters. Take, for example, a monster fleeing into a dead end.
>
> ####
> @.a#
> ####
>
> If the next turn belonged to the 'a', it would move into the player's
> attack radius, to be attacked, and then move back into the corner, ad
> infinitum, until it is defeated! Since I did not want the hidden
> gameplay complexity of a "turn and fight" algorithm like in Angband, I
> made a condition that the character would stay put if the only
> adjacent square was next to the player. This works well with my speed
> system.
>
Hehe it's a smart 'a', right? :)
This means that it has good timing. The player can usually bend the
rules to gain initiative. Again, it would be awesome if smart
creatures were differentiated by this.
Jotaf
Erwin M.
In discussions of pathfinding and roadblocks, I've always found it
interesting that the roguelike model of grid locations puts bounding
boxes on all of the actors. If I'm fighting a giant or a dragon, how the
heck is that large entity keeping a rat or a kobold from running past it
and attacking me (or escaping) as well? Or non-corporeal beings that
have no problem walking through solid walls, but find that a fluttering
giant fruit fly forces them to find another way around?
Angband has its "push past/destroy weaker monsters" flag for certain
critters. Why not some sort of implementation of "slip past much larger
monsters" as well?
Martin Read
>In discussions of pathfinding and roadblocks, I've always found it
>interesting that the roguelike model of grid locations puts bounding
>boxes on all of the actors.
It does this because it is simple to write, and makes the user interface
for melee combat simple and unambiguous.
Oh, and Rogue wouldn't even allow two *items* to be in the same space
(other than in the player's inventory).
--
\_\/_/ turbulence is certainty turbulence is friction between you and me
\ / every time we try to impose order we create chaos
\/ -- Killing Joke, "Mathematics of Chaos"
Erwin M.
> "Erwin M." <erwi...@gmail.com> wrote:
>> In discussions of pathfinding and roadblocks, I've always found it
>> interesting that the roguelike model of grid locations puts bounding
>> boxes on all of the actors.
>
> It does this because it is simple to write, and makes the user interface
> for melee combat simple and unambiguous.
Definitely, yes. I wasn't implying that two critters should be able to
occupy the same space. What I was getting at was that making more
provisions for creatures to be able to move through/past each other,
instead of treating them as solid obstacles, may help with some issues
of pathfinding. (And doubtless introduce some new ones as well.)
> Oh, and Rogue wouldn't even allow two *items* to be in the same space
> (other than in the player's inventory).
Neither did Moria or earlier *bands, for that matter.
Jotaf
creature, and be stopped for the next turn! So it's as if it moved 2
spaces (wastes 2 turns).
Jotaf