9
\$\begingroup\$

This question already has an answer here:

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)
\$\endgroup\$

marked as duplicate by ClassicThunder, DMGregory Feb 28 '18 at 16:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    \$\begingroup\$ Are you using A* or some other algorithm? \$\endgroup\$ – Evorlor Feb 28 '18 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\$ – Jack Aidley Feb 28 '18 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 Feb 28 '18 at 15:55
  • \$\begingroup\$ @JackAidley I'm running on a core2duo \$\endgroup\$ – KayleMaster Mar 1 '18 at 7:26
17
\$\begingroup\$

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.

\$\endgroup\$
14
\$\begingroup\$

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.

\$\endgroup\$
  • 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 Feb 28 '18 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\$ – ratchet freak Feb 28 '18 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 Feb 28 '18 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\$ – KayleMaster Feb 28 '18 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 Mariager Feb 28 '18 at 15:05
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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 Feb 28 '18 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\$ – KayleMaster Feb 28 '18 at 13:02

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