I am currently working on a pedestrian simulation, in which I simulate people walking from one place to another. It is discrete and pretty basic and models every person as a single entity.

Currently, the algorithm I use to decide in which direction to walk, is a simple one: It compares 5 possibilities (North, East, West, South and staying put) and chooses whichever option is closest to the target in a straight line. (Through Pythagoras.) For empty rooms, this is a pretty decent algorithm, but for more complex areas, with walls, the people get stuck behind them quite quickly.

Now, I'd like to implent a smarter algorithm, which finds the shortest path. Dijkstra's came to mind. However, I would also like to implent crowd evasion, such that people consider other, slightly longer, routes if their shortest one is too crowded.

I'd really appreciate a couple of suggestions on the kind of algorithm to use and/or how to adapt it to this simulation, as this is nearly completely new ground for me.

I have added a picture of what the exterior looks like. Blue squares are people, red is wall, purple ones are spawn points and the pink ones are exits.

Attached Thumbnails