I have a 2048x2048 map and if I path-find to an unreachable location, it makes the pathfinder go through every node on the map which freezes the thread for 4 seconds.

How can I reduce that time?

  • I'm using JPS
  • It's a dynamic map (it changes at runtime)
  • 1
    \$\begingroup\$ Are you using A* or some other algorithm? \$\endgroup\$
    – Evorlor
    Commented Feb 28, 2018 at 13:49
  • \$\begingroup\$ Regardless of other matters, a 4 second freeze suggests there are severe problems with the efficiency of your path finding code unless you're running on some highly legacy system. What language/hardware are you using? \$\endgroup\$ Commented Feb 28, 2018 at 14:11
  • \$\begingroup\$ When you say the map changes at runtime, can passages can be both added & removed while the game is running? \$\endgroup\$
    – Pikalek
    Commented Feb 28, 2018 at 15:55
  • \$\begingroup\$ @JackAidley I'm running on a core2duo \$\endgroup\$ Commented Mar 1, 2018 at 7:26

3 Answers 3


Using a bidirectional path finder usually solves this issue if the area the player is stuck in is small. They basically advance from the player's position and the destination at the same time and when they meet, the algorithm ends. If one of them gets stuck, then you can stop both.


You should make a sort of connectivity map - by flood-filling all unconnected walkable areas and marking each one with a different tag, once at game start (and every time when terrain changes). Then, before even trying to make a path, check if source and destination locations belong to areas with the same tag, if not - path obviously can not be made.

Additionally, you could discard all isolated unreachable areas from pathfinding at all.

  • 2
    \$\begingroup\$ That's a nice Idea, but it has the restriction of only working on static maps, which fortunately most are. However, if your game has doors, the flood fill would need to be recomputed, and may end up costing more than the original algorithm. \$\endgroup\$
    – Ian Young
    Commented Feb 28, 2018 at 11:35
  • 3
    \$\begingroup\$ @IanYoung Or create a graph where each room is a node and each door is an edge, then when path finding first search in the room graph with edge values based on open/closed doors and then search the grid. This assumes that doors are known when doing the floodfill \$\endgroup\$ Commented Feb 28, 2018 at 11:40
  • 2
    \$\begingroup\$ @ratchetfreak Yes, this has been done before using "portals". Regions which are normally unpathable have portals connecting them (other floors/rooms). The main path finding algorithm sets the destination cell to the portal instead of the region. \$\endgroup\$
    – Ian Young
    Commented Feb 28, 2018 at 11:44
  • \$\begingroup\$ Good idea, I'm not sure if it's feasible with a dynamic map. The cons may outnumber the pros. \$\endgroup\$ Commented Feb 28, 2018 at 13:00
  • \$\begingroup\$ Here's how I did something along this idea: i.imgur.com/K2u5Okx.png Updating it was very fast. Allowed me to do a two pass pathfinding, a broad phase and a narrow phase. Broad would just check if there's a connection between the sectors, narrow phase would avoid local obstacles. \$\endgroup\$
    – William
    Commented Feb 28, 2018 at 15:05

Add a "maximum number of iterated nodes" parameter to your pathfinding algorithm. When the limit is reached, simply give up and claim that there is no path.

  • \$\begingroup\$ This would work, but it should be part of the original A* algorithm anyway, as one of it's possible cases. We can also say that if the closed list is ever empty after being started, then the path cannot be found, as all possible moves have been eliminated. \$\endgroup\$
    – Ian Young
    Commented Feb 28, 2018 at 11:39
  • \$\begingroup\$ I've added this limit and that's actually how I reduced my freeze time to 4 seconds as opposed to 10+ seconds. Any more and the paths will be very short. \$\endgroup\$ Commented Feb 28, 2018 at 13:02

Not the answer you're looking for? Browse other questions tagged .