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:
- An algorithm to quickly compute a lot of simple routes.
- 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.