Dungeon Crawl Movement AI/Steering/Flocking this time :)

Game Mechanics Artificial Intelligence
#1

So, I’m still pushing ahead with this dungeon crawl. I’ve got the networking side working happily, and the renderer looks pretty neat. I’ve reached the point where I’ve got my player (or players) running round the random dungeon with monsters (skaven for those interested) coming after the player.

I’m using DJK or A* depending on mood for the path finding. When my player clicks the character moves to the appropriate location. Equally, as my player moves round I have a AI framework that finds light-of-sight from monster to player and causes the monster to choose a path to the player and attempt to follow him/her (eventually to attack).

The problem - my path finding chooses the best path (account for other monsters getting in way optionally). If the monster gets blocked (by other entity or wall) the path is recomputer. The problem is I’m getting the effect of a swarm of monsters approach the player and then sort of lining up on approach.

I’ve been reading about flocking/steering and seems like its the sort of thing I need to push the monsters away from each other. However, I’m finding they get in loops like:

  1. Monsters move close enough to have steering effect, hence they don’t follow their path perfectly
  2. Next cycle, monsters are far enough away from each other that steering has no/little effect, they now move along the path as before
  3. The monsters have now moved back close to their original positions and hence get pushed away from each other again…

and round and round… giving a horrible little jitter.

I started here: http://www.red3d.com/cwr/steer/gdc99/

Does anyone know of any more in depth resources about the subject or knows how to resolve these steering vs pathfinding conflicts.

Kev

#2

I remember reading this once: http://www.theparticle.com/applets/swarm/index.html
might want to check the flocking swarms applets.

#3

I think you might just be stuck with tweeking the weights and such between the two behaviours. Increasing the stearing range (but reducing the affect) could do it. And add a little damping/smoothing to the whole thing so you don’t get the horrible twitching when the two almost cancel each other out.

Surely though your pathfinding is just another steering behaviour? Just a very specific and data-driven one. So tweeking it to produce the results should work like most other behaviours (ie. quite tricky IMHO).

#4

Thanks for that guys, interesting useful stuff. For anyone interested this is what I’ve done:

  1. Remove the concept of path finding from the monsters

In my world I have “Actors”. At any given time an Actor is driven by a “Action”. I’ve implemented a “SteeringAction” which contains a set of “Steer” implementations and combines them based on their weights to work out the direction of movement each cycle. I then have a StandardMonsterSteeringAction subclass that configures a particular set of “Steers” for monsters.

To get reasonable results I’ve combined :-

MoveToTargetSteer - just tends the Actor to a particular target. In this case this causes the monsters to move towards the targeted player.

AwayFromFriendsSteer - this causes monsters to tend away from each other (but not players, hence the reference to friends). This is a seperation steering algo. There are two subclasses that each use different priorities to determine which Actor in a conflict will move (one picks an arbitary one, one chooses based on the distance from the current target)

TendFromWallsSteer - this causes monsters to tend away from walls and hence they’re more likely to reach the player.

These 3 combined give me almost as good as path finding results while maintaining a steering framework which means interactions given relatively decent results.

All in all, its pretty cool - I need to think how to make the swarm around the player a bit more obvious, just changing the weighting isn’t having the desired effect.

Thanks for the pointers,

Kev