c# - Pathfinding for a lot of units, mostly random movement

I'm using a uniform cost eight-directional grid as a map, with buildings that represent unpassable terrain - the map tries to simulate a top-down flat city. I'm trying to fill the city with randomly walking citizens, and with player units with controlled paths.

So far, for the random walking I've just chosen a direction and set a direct line on it ( using berensham's line algorithm), until the unit strikes a wall, but even this slows down the game with 200 units, and that's before more complex routes are looked for by the player.

So, I need:

1. An algorithm to quickly compute a lot of simple routes.


2. A good pathfinding algorithm - so far I've read about HPA* and A* with JPS, but to both I haven't managed to find an implementation, which is a problem because the articles are a bit too theoretical for me.

For illustration, the situation is somewhat similar to the movement in Atom Zombie Smasher - there are uncontrolled civilians that walk randomly / run away from a threat, and few player units that walk on prescribed paths, only in my game the player can't affect the path mid-walk.

So, to summarize - I'm looking for a system for pathfinding for a couple of hundred of units which is as quick as possible.

Answer

You may want to look at flocking systems. This way you can just calculate paths for a few objects and have others follow them instead of the path.

You can also check out this link to help you create a basic implementation of the A* path-finding algorithm.