Using my pathfinding more efficiently

Question

I'm making a roguelike in C# with the Roguesharp libraries, in which the map can be as large as 200x200 cells. When I have an entity requiring pathfinding, I am using Roguesharp's built in pathfinding system (which I believe uses a variation on A*, with Manhattan movement instead of orthogonal movement).

When I have an entity pathfinding every turn (to path to the player, which may constantly move) the framerate roughly halves, but the game is still playable. However, when I add in more entities the framerate drops greatly. 10 entities leaves the game running at less than 1 fps and completely unplayable.

Clearly I am doing something wrong, games like Dwarf Fortress manage to have hundreds of entities running around maps this size with little trouble. Does anyone have suggestions for how I can get better performance.

The way it currently works is: whenever the player takes his turn (attacks, moves, etc.) the game loops through every entity, does the pathfinding for that entity and moves them. Is there a more efficient way to do this when the player is moving every turn?

Answer 1

Graph-based pathfinding calculates an entire path (multiple turns' worth) and you're using only the first step, throwing away the rest, and recalculating every turn. This is wasteful. Keep following the path already computed until you think you need to recalculate it. If you're far away from the target, recalculate infrequently; if you're near it, recalculate frequently.

Also, RogueSharp's pathfinder isn't using A*; it's using Dijkstra's Algorithm underneath, which is doing a lot of unnecessary work if all you want is a path from one location to another. (On your 200x200 = 40000 tile map, it finds a path from the source to all 40000 locations, then throws away all the paths other than the one it wants.)

However, your case has a better solution.

For the special case of many entities pathfinding to the same location, Dijkstra's Algorithm works better than A*. For the special case of Dijkstra's where every step is weight 1, you can use Breadth First Search, which is even faster. Breadth First Search can be incredibly fast.

Dijkstra's and Breadth First Search find a path from one location to all other locations. You'll run pathfinding once to find a path between the player and all other locations. You'll get back a map of directions:

Then all the enemies look in that map to see which direction to move. The enemies don't have to run their own pathfinding.

I have a tutorial on this topic and some partial code in C#. Alternatively, it looks like Roguesharp includes a Dijkstra's Algorithm class so you could use that to find the paths from the player to all other locations.

Answer 2

You don't want to check for a path all at the same time for all of your entities. You could try to set a timer on each of your entities, and poll for a new path when the timer expires (instead of waiting for a move).

You can further refine this by only reducing the poll timer when the player changes positions (but this is really dependant on your specific game play).

Another thing to consider, is having a "Leader" and "Groups". The active leader of a group will poll for a path, while the remainder of that group would simply follow it's leader.