Pathfinding on large map

Question

I'm creating a game with a 10,000 by 10,000 map.
I would like for a user to be able to set a location and have the computer instantly find the best path.
However, since the map is 10,000 by 10,000, there are 100,000,000 nodes, and to find this path through a conventional method such as A* or Dijkstra's would require a large amount of memory and a long time.
So my question is: How can I find the best path?
The algorithm I'm considering would divide the world into 100 sections, each with 1,000,000 nodes. Each section would then be divided into 100 subsections. This would be repeated until each subsection contains 100 nodes. The algorithm would then find the best path of sections, then subsections, then sub-sub sections until it finds the best set of nodes. Would this work and is there a better way?
I'm also considering a jump-point search, but I don't know it, and it'd be a pain to learn just to find that it can't do it.

Edit: I have attempted to add A*. However, it took about 5 seconds to run, which is about 4 seconds longer than ideal.

Answer 1

Since the map is 10.000 x 10.000 the number of nodes is 100.000.000. Using a straightforward implementation of A* would be impractical and certainly wouldn't make the game scalable in mapsize.

I would recommend you to use the following solution, which is essentially what you were thinking:

HPA* (Hierarchical Path A*). This method creates different hierarchies of map. You may automate the process by saying every block of 100x100 pixels is a region. Then, for every block, we need to find the adjacent blocks and where the entries and exits for each block is. If the connection between the two blocks is more than a node then we use two nodes to represent the problem. This image explains the new graph that we're trying to build. (Black=obstacle and grey are connecting nodes between blocks).

This method provides good results as can be seen from an execution using maps from the game Baldur's Gate with every block being 10x10.

For more information read this article from Nathan Sturtevant (he is one of the most succesful path-finding researcher when it comes to games). https://skatgame.net/mburo/ps/path.pdf

For an explanation of HPA please check this lecture of Sturtevant (min 43:50 for HPA). https://www.youtube.com/watch?v=BVd5f66U4Rw

Also, if you want to see HPA* in action check this video that Sturtevant made: https://www.youtube.com/watch?v=l7YQ5_Nbifo

Answer 2

1. Make sure all the graph data is in memory
2. Use bidirectional Dijkstra - assuming you have multi-core
3. Look into using contraction hierarchies, this will greatly improve the performance.
4. Pre-calculate everything that you can such as path weights.