Hi guys,

Am working on a very basic game, somewhat Diablo-like, and could use a little help deciding on how to implement the pathfinding.

The GameWorld consists of Player/NPC/monster "units", each one represented by a circle of various sizes. There are also rectangular "do not enter" areas(walls, chasms, etc.). Parts of the Game World will be randomly generated.

At any point in time, Units will either be stationary, or have a movement target of a (x,y) point in the GameWorld(which may be another Unit), but not a "do not enter" area.

How can I get the Units to avoid one another when travelling across the land? (collision detection is easy, as they're all circles, but not sure what to DO when I detect an imminent collision)

Also, what's the best way to stop Units from getting stuck in the dreaded "U" trap? (assuming a random map of rectangular obstacles that still contains a path)


Ideally I'd like to scale this up to something akin to a set of school hallways, where (for example) 500 or so students suddenly start trickling in from every classroom, each bound for a different classroom. If this will be ridiculously complicated, I don't mind "cheating" by letting students squeeze themselves smaller when going through crowds, or losing crowd collision detection for a second or two.

Thanks in advance to anyone who can point me(and my units) in the right direction.