I thought I was happy about my monster movement, till I got a lot of
them together in a tight space.  When I have a pack of monsters that
have moved close together, it's obvious to me that my movement AI
needs some work.  The monsters are all in a linked list that I
traverse, and each then moves based on whatever criteria.  The problem
is that depending on where in the list there are, they might be
blocked from what would normally be a valid move.

It's been a long day, so I'm just sort thinking out loud here, and I'm
sure this has been solved hundreds of times before, but I'm not sure
the best way to handle this.  Do you do some kind of multi-pass
movement, where you see where each will move to, then adjust on the
second pass?  Do you go with a more realistic approach where different
monsters have "speed" values and if a slow moving sloth blocks a
doorway, then so be it?  

Seems like they should just pour through a doorway like sands out of
an hourglass, and I'm not thinking about it right.  

Also....  Does your @ get first move each turn?  

-spag

On Jul 1, 9:01 am, spag <spagtho...@gmail.com> wrote:

Obstructed movement is a realistic occurrence, not a malfunction of
your turn system. It can become a problem if monsters behave too
stupidly or if they lose so many turns that gangs of monsters are
weaker than intended; both kinds of problem can be addressed with less
radical measures (like generating monsters with less crowding, giving
them better ranged attacks, and adding doors and passages).

If you have a system in which every monster acts every turn, in some
order, monsters might decide to wait to see if some space opens
instead of failing to move; if you use a queue, the next-acting
monster that is pulled from the queue can go into next turn's queue if
it acts or to the back of the current turn's queue if it tries to
wait. Note that this waiting doesn't imply a significant passage of
time, only an hesitation until the monster's neighbour moves.
During the first pass through the queue monsters that are not
obstructed act freely (presumably moving forward); during the second
pass, monsters that waited once can walk into freshly vacated squares
or wait more, and so on until no monster can move or until they have
waited too many times. Note that this procedure has the side effect of
approximately sorting the monsters in the order in which they "should"
act next turn.

Please don't say "realistic" when you discuss attributing arbitrary
durations and delays to a coarse quantization of artistic abstractions
of fantasy stuff.
An absolute "calendar" of events is rather incompatible with turns.
Are you implying that you haven't selected either approach for your
game?
I suppose obstructed monsters should suffer a very short delay (a
small fraction of the cost of walking a step), maybe adjusted by their
agility, before having another chance to move; the net result would be
that obstructed monsters are delayed until someone in front of them
vacates a square or until they decide to do something other than
walking ahead, much like in the other case.

The hourglass effect would be mitigated by not having all monster
funnel through a small door. An obstructed monster might decide to
guard the rear of the formation, or just walk into a random free
square, instead of pushing forward.

Apart from the first turn of the game, it shouldn't matter much. It's
always everyone else both before and after the player; the turn is an
artificial boundary.

The placement of turn-based effects and events might be more
important.
If effects like hunger and poison are scheduled before the player's
action, doing something about them might be impossible: after a
monster poisons the player, can he drink one of his lovingly collected
cure potions or will he fall dead before acting?

Regards,

Lorenzo Gatti

On Jul 1, 3:01 am, spag <spagtho...@gmail.com> wrote:

I do use this, but that's not really the manner in which I end up
compensating for the problem you describe. Basically, whenever I have
a monster that gets stuck (cannot move in any way), it takes a special
sort of 'wait' action that only eats up half of the normal time that
creature would take to move. I don't use passes or turns in the way
that you describe...I queue everything up, and whoever's at the front
of the queue gets to act. Once they do, they get shoved a certain
distance backwards into the queue based on how much 'time' their
action used. Repeat. Combined with the half-turn thing just mentioned,
it means that a creature that's blocked in by its fellows is champing
at the bit to get free, and will do so ASAP. Good pathfinding helps
with this, too; critters will end up taking small detours to flank the
PC through another door, when the first door is blocked. I do get a
side-effect of creatures sort of milling around in packs, but I find
it adds an air of realism to their activity.

In article <10a489b2-450e-4c60-99c1-d0bed1754ea5
@j22g2000hsf.googlegroups.com>, Nah...@gmail.com says...

Indeed - they are monsters after all!  Perhaps they should occasionally
bite each other if blocked.

- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>

On Jul 1, 9:01 am, spag <spagtho...@gmail.com> wrote:

I run through the list of monsters (the PC gets the first move), but
instead of giving each processed monster (or the PC) an opportunity to
move, I add the speed value to the "energy" value and determine
whether it's time to move or not (energy => 1000). Now, if it's a
monster's turn to move (in theory, since monsters aren't fullly
implemented yet in my game) and there are no free cells in the PC's
direction, a monster may decide to skip the turn (wait, just like
pressing '5'), which costs less than a normal move. That way, monsters
still are slower when in a tight formation, but still move rather
fast.

Lorenzo Gatti described a similar method above (going to the end of
the queue, just like in Heroes of Might and Magic), which could work
fine as well.

Alternatively, they might do pathfinding and determine whether there
is another way to reach the PC (if there's another connection with the
place where the PC is, you might get monsters entering simultaneously
through all the doors, surrounding the PC).

Mingos.

If the game difficulty setting is on "easy":
Monsters that are blocked must do something besides movement or
they lose their turns.  This means a lot of turns lost, but some
may be able to use them for spellcasting, quaffing, intelligent
weapon switching after the player's demonstrated a resistance, etc.

If the game difficulty setting is on "medium":
allow monsters a "wait" action that waits for some fraction of a
turn for others to get out of their way.  Smaller fractions of a
turn waiting mean less wasted time.  

if the game difficulty setting is on "hard":
Monsters set a "blocked" status and record the time whenever
they are blocked by other monsters. Whenever they move, they
check the squares around them for blocked monsters, and give
the longest-blocked monster a turn (unblocking it).  The now-
unblocked monster's action completes at the time it would have
completed if it had started when the monster was blocked, or
instantly, whichever is later.  You may want to allow this
only for movement actions.  Functionally this is like a "wait"
action that takes zero time, and will result in monsters
moving in lockstep in tight formation.  It will also result
in tight packs that the player has no chance to maneuver
through and damned few chances to tactically divide.

if the game difficulty setting is on "hurt me more":
Add a "no-push" flag to each monster.  clear the flag whenever
the monster takes a turn.  Let monsters blocked by weaker or
more wounded monsters whose "no-push" flag is clear "push"
them - either shoving them forward into an empty space or
if there's no empty space, swapping places with them.  
Whenever a monster gets pushed, set its no-push flag again.  
Optionally, let the "pushing" monster move forward at the
same time as it pushes someone else.  This results in some
monsters reaching the player (or the exit, if retreating)
faster than they could have run there themselves, and also
in continually cycling "fresh" or relatively undamaged
creatures to the front when the player is engaged in meelee
with a pack of things s/he can't one-shot.

What?? Every monster, including the @, moves first whenever it
has a turn.  Whatever between-turn processing is relevant for
that monster is done at the start and end of that monster's
turn.

                                Bear

On Jul 1, 2:02 pm, Ray Dillinger <b...@sonic.net> wrote:

Welcome to UnAngband: http://roguelikedeveloper.blogspot.com/2007/10/unangband-monster-ai-p...
.

http://roguelikedeveloper.blogspot.com/2007/10/unangband-monster-ai-p...

Not exactly the same, but yes, similar.  The above proposal is
different from the UnAngband solution in that it doesn't allow
weaker or more wounded monsters to push others, and it does allow
pushing to result in positive movement rather than just a position
swap.  The emergent properties would be different.

                                Bear

Some good food for thought here.  I had been doing some rather
simplistic monster movement, as I consider the monsters in my RL to be
exceptionally stupid, so I'm not sure I wanted to have them do
pathfinding.  I do have a A* module that I wrote for a hexagon-based
combat game that I can modify to do a grid.  Even if the monster
doesn't have sophisticated tracking ability, at least it should be
able to move around some blocking monsters to get to the player if
there is a way.  

I do like the queing of turns idea, but I'm going to have to play with
it a bit.  I actually really like the idea that weaker monsters would
push others out of the way to get to something.  Definitely going to
read those Unangband monster AI articles as well and see what sparks.

I'd always had NPCs spread out enough that this had not become a
problem, but I envision that large groups of monsters will be common
in this scenerio.

-spag

<clip>

Another "hurt me more" option:

Let monsters use one or two "free" swaps on their turn, allowing
them to trade places with other monsters of the same type as a
zero-turn or small-fractional turn action. They swap forward and
arrive still with a full turn, or most of one, to act.

This would also make fighting packs insanely difficult, because
every time any member of the pack within two or three squares of
you had a turn, it could just swap its way forward and hit you.

kkkkk   The net effect of this is that this poor @,   kkkkkkk
kkkkk   surrounded in the open by kobolds, would get  kkkkkkk
kk@kk   attacked every turn by 24 kobolds (scenario   kkkkkkk
kkkkk   at left) if they had one free swap, or by     kkk@kkk
kkkkk   48 kobolds (scenario at right) if they have   kkkkkkk
        two free swaps.  This would make even weak    kkkkkkk
        creatures with this ability very dangerous    kkkkkkk
        in packs.

And yes, I'm thinking of this now as a "special ability" for
selected monster types, rather than a general movement pattern.
One free swap could possibly be a general movement pattern, but
two would seem a little too blatantly unfair except as a special
ability for a few types of monsters.

It might be an analogue to the "size" thing in some P&P combat
systems that limit attacks according to the relative size of
the individuals fighting. Intuitively, you can be surrounded
by twelve small goblins or a hundred lilliputians all with the
ability to attack you, but you can only be stomped by giants
from two sides, because there's no room for a third giant to
be in range.  So maybe tiny monsters have more free swaps
than larger ones to simulate the ability to maneuver more
individuals in the same space.

                                Bear