2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ It sounds as though you're doing all the pathfinding between frames? You need to either spread this work across frames or possibly consider moving some of this work to another thread so your game can still render while processing paths \$\endgroup\$ – zcabjro Jun 22 '16 at 8:06
  • \$\begingroup\$ I'll certainly look at moving the pathfinding over to another thread, this is something I haven't tried in C# before (only assembly). \$\endgroup\$ – Omegastick Jun 22 '16 at 16:22
3
\$\begingroup\$

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:

Breadth First Search output

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.

\$\endgroup\$
  • \$\begingroup\$ That tutorial was fantastic. Roguesharp has Dijkstra's algorithm packaged with the library, but only a shortest path method is actually integrated into the rest of the package. I will write my own code that integrates with the game as I currently have it. Thanks a bunch. \$\endgroup\$ – Omegastick Jun 22 '16 at 20:27
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I have set a timer for each of the entities pathing, if the timer is up when the entities turn comes then the entity paths and moves as well. The timer gets longer the further the entity is from the player, so entities further away from the player aren't constantly pathing every turn. However, while on a map with 10 entities, the game has only a small amount of delay while the entities are far away. But once one or two entities get closer (onscreen) the game slows right back to a crawl. Any other advice? Should I try writing my own pathfinding code and see if it is more efficient? \$\endgroup\$ – Omegastick Jun 22 '16 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.