# 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.

-
What does the profiler tell you is the bottleneck? – amitp May 15 '12 at 16:31

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.

-
Flocking and other group behaviours are always the way to go when moving dozens of actors. For information regarding them, look for Craig Reynolds' Boids or check Buckland's Programming Game AI by Example. There are implementation examples for most major programming languages all around the web. – Elideb Apr 27 '12 at 11:26

If the civilians just need to walk around randomly, I wouldn't have them "think ahead" at all. Simply pick a random direction for each civilian and have him walk in that direction until he bumps into something or a certain amount of time passes. That makes it a simple "for p in players: p.pos += p.direction" each frame, which you're doing anyway, with no complicated algorithms. Direction would just be a vector/2-item list representing a move in one of your eight directions.

Of course, that won't work for your soldier units if the player is going to set patrol routes. A* is the algo of choice, though I'd only compute one route a frame. Just set up a queue of routes to be computed and grab the top-most one each frame to maintain performance.

Amit's Game Programming has some great links to A* articles which will help you grasp the theory. This one is especially good. Surprisingly, though, the Wikipedia article on A* has the best pseudocode!

-

I can't understand how moving 200 units around could slow down any modern system... I guess you need to revise your algorithms.

How much it "slows down" of course depends on the frame rate or logic tick-rate. I don't see an advantage for most games (e.g. RTS) of running at a tick rate of > 20/sec. If you want to render more frames than that, you can just use interpolation (which is a good idea anyway, it frees your logic speed from your rendering).

You say "using bresenham's line algorithm", but this is for drawing pixels in lines. Is your game really entirely tile-based - can characters never occupy spaces between tiles?

Normally I'd be tempted to just set a destination for each character, and walk towards it in a straight line (turn towards it, then walk straight), then set another point. Doing this is a very simple piece of vector maths.

But that pre-supposes that your characters can actually be at any point in space.

-