22

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.

James McDowell
  • 2,668
  • 1
  • 14
  • 27
  • Do it like with our normal street maps and build a graph out of you 10,000 x 10,000 map. I'm sure you end up with a much much smaller graph than these 100,000,000.... – CFrei May 26 '16 at 18:15
  • Are you saying to divide it into sections? If so, that's the solution I'm considering as my question states. – James McDowell May 26 '16 at 18:31
  • Maybe you dont have to split it up, just always keep your path finding in a relatively small range around your player, and updating as you move. – eldo May 26 '16 at 19:08
  • What's on the map: obstacles, height differences, different speeds of travel, ... ? – m69's been on strike for years May 26 '16 at 19:10
  • The map is a binary map: passable or impassible. – James McDowell May 26 '16 at 21:47
  • @eldo That's basically a depth first search. It's fast, but it's not always the shortest route. In fact, it's route is longer more often then not. – James McDowell May 26 '16 at 23:23
  • @James McDowell Well I've never done any path finding stuff and don't know much about them, it was just an idea. :) – eldo May 27 '16 at 17:12
  • 1
    Have you actually tried implementing A* on this map? If it is not too much of a labyrinth, the A* should never _really_ expand all those 100m nodes. I don't see why it should not work. – tobias_k Jun 10 '16 at 15:54
  • You should also have a look at algorithms like [potential fields](https://en.wikipedia.org/wiki/Motion_planning#Potential_Fields). Basically, do not think "passable" and "impassable", but assign values from 0 to 1 to field that are close to impassable areas. This way, your player will stay more "in the open" and should find a good path quicker. – tobias_k Jun 10 '16 at 15:58
  • With the heuristic limiting the number of possible next nodes to 1.5 each step, A* has a time complexity of O(1.5^n) where n is the length of the solution. Here, n can be up to about 14,000. Try plugging that in to your calculator. – James McDowell Jun 11 '16 at 11:17
  • 1
    why not use grid map A* instead of graph A* ? yes the resolution is quite big but there are guite few things that you can do to really speed things up like: scan only bounding box of area used, cast path from both ends, mask out non passable enclosed areas etc ... Also if your space is more open then you can ignore map too far from straight line path ... see [map A*](http://stackoverflow.com/a/23779490/2521214) it can be coded so it does not require list of traversed points just the map you already have in memory (although not as binary) – Spektre Jun 13 '16 at 05:57
  • I have implemented A* (Though possibly not the best implementation), but it took too long. I will look into grid map A*. – James McDowell Jun 13 '16 at 14:49
  • @JamesMcDowell I am not a JAVA coder but if your maze is in some Image may be you are accessing it wrongly... get/setpixel style access is painfully slow (1000...100000 times slower then direct access) so just to be sure check/measure if the slow down is not there first ... so you're optimizing the right thing. Also your current approach needs dynamic lists if they are not accessed/used properly they can also slow down things **a lot** in such case preallocating and preventing insertions helps. If you using recursion instead that is madness for that huge data ... from performance view point. – Spektre Jun 14 '16 at 06:19
  • 1
    You could still provide some more information. How do your maps look? How dense or sparse are obstacles? How maze-like is the map? Are there large parts of the map entirely unreachable? All those might have an influence on the best choice of algorithm. Maybe you could provide an example as an image (scaled down or just an excerpt). – tobias_k Jun 14 '16 at 13:06
  • 1
    Since this is a game, is it really necessary that the shortest path is always to be used or can it be relaxed so that the path taken may have an additional cost of 10% when compared to the shortest path? – SpaceTrucker Jun 14 '16 at 13:08

7 Answers7

15

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).

enter image description here

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.

enter image description here

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

Felipe Sulser
  • 1,185
  • 8
  • 19
1
  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.
Nick
  • 2,735
  • 1
  • 29
  • 36
0

My initial understanding of the problem statement was like follows. There are predefined terminal locations on the map. The user selects a location on the map, and the best/shortest path to the closest one of those locations must be found.

If my understanding is correct, then you can precompute the shortest paths for all locations on your map through a single application of the BFS algorithm. You can efficiently store that information using just 2 bits per node (the value associated with each node will tell in which direction you must move from that node in order to stay on the shortest path).

However, as tobias_k has commented, the problem may be defined differently - the player selects an arbitrary location on the map and the best path from the current location to that location must be found. The previously described approach can again be utilized, provided that

  1. the player doesn't move around the map too quickly and
  2. some inaccuracy can be tolerated.

Then the already described algorithm is executed to find the shortest paths from any location on the map to a small circumference centered at the player's current location. Then for a short period of time that data can be used to quickly route the quasi-shortest path toward any location on the map. When the player, while moving, gets too close to the boundary of that circle, the algorithm is preemptively executed for the player's new location.

The disadvantage of this approach is that it consumes a lot of CPU resources. The advantage is its simplicity.

Community
  • 1
  • 1
Leon
  • 31,443
  • 4
  • 72
  • 97
  • "I would like for a user to be able to set a location and have the computer instantly find the best path." The target location is chosen just before calculating the path, so "precalculating the path" does not help. Precalculate for what target? – tobias_k Jun 10 '16 at 16:05
  • I understood the problem statement like follows. There are predefined terminal locations on the map. The user selects a location on the map, and the best/shortest path to the closest one of those locations must be found. – Leon Jun 10 '16 at 16:08
  • 1
    Well, _my_ understanding is that the player selects a _target_ location anywhere on the map and the algorithm should find a path from the players current location to the target. – tobias_k Jun 10 '16 at 16:14
  • Thank you for the hint, that makes sense. Will try to address it too. – Leon Jun 10 '16 at 16:23
  • I had a similar problem once and I tried comparing each possible next node to the destination node, and whichever was most similar, do to that one. Granted, that created a whol slew of new problems, but it's something to consider! – Mr. DROP TABLE Jun 10 '16 at 16:39
  • tobias_k was correct. The start node can be any one of the 100,000,000 nodes and the end node can be any one of the 100,000,000 nodes. Your redefined solution basically says precalculate a lot of paths and navigate to the closest one. Basically create a hub system. The problem with this is that it will not be the shortest path. In fact, for it to even resemble the shortest path, it would have to have tons of precomputed paths. Additionally, you said to use a BFS search. Is this breadth first or best first? Best first is often wrong and breadth first would take way too long. – James McDowell Jun 10 '16 at 19:46
  • In my redefined solution, there are at most 2 sets of precomputed paths: one for the old position of the player, the other - for the projected future position of the player. As soon as the new set is ready, the old set is deleted. – Leon Jun 10 '16 at 20:07
0

This will be a little longer than what fits into a comment, so hence an answer.

Your setup requires clarification. 10,000x10,000 is all good, but this statement is not:

since the map is 10,000 by 10,000, there are 100,000,000 nodes

Why would there be 1 node per each unit of the coordinate system? This is not how node pathfinding works, instead the nodes are supposed to be more sparse, and by their existance describe individual (sparse) points along the path. Between the node points, the object handles movement by other means. A grid pathfinding system might, in worst case (if no obstacles at all), have 100,000,000 points, but as the Q mentions nodes, i assume this is about node pathfinding.

100,000,000 nodes

100,000,000 nodes is 381 megabytes of memory if int32 and 763 mb if float64. In addition, there are node connections. I have no idea how these would be set in your case, but each connection requires 2 integers, say of 2 bytes each. Ie. if there are as many connections as nodes, another 381 mb is needed. All in all, we end up with graph data closer to one terabyte, and i claim that for sure something is wrong then.

How to solve the issue, provided we still have a huge node graph/a huge area? I would probably simplify, by creating larger quadrants (as you mentioned). Each quadrant would however hold nodes only along the 4 edges - all nodes inside a quadrant would be replaced by straight lines. This way, one would resolve the entry/exit points for each quadrant. This would be a separate node graph, for rough calculation. Then, inside a quadrant, one would always load the inner node graph for that quadrant only at time. Ofc there would be some kind of error invloved, but hey, that's reallife, right? If this is about human behaviour, well then it is not always fully optimised.

Pre-calculation, cache, speed, small data are keywords in game coding.

Stormwind
  • 814
  • 5
  • 9
  • I don't think you would save a path as an int. It can be either usable or not usable. it can be taken or not taken, so basically it's 1 bit. 100,000,000 -> 12.5 MB, therefore it;s not that much memory. and once you travled to a path you mark it as taken. – Nicolae Natea Jun 17 '16 at 14:59
0

So even though there might be n^4 shortest paths on a square n by n map. storing all the paths doesn't necessarily require O(n^4) space. The idea is that given two different target locations on the map and their shortest path trees, than the closer those two points are on the map, the more common elements will their shortest path trees have. This is especially true when using a planar map like a grid with obstacles.

So the idea is to store only some complete shortest path trees for a small set of target locations (may even be only one target location). For the rest of the target locations only the difference of its shortest path tree to one of the previously stored shortest path trees is stored.

Then the algorithm to find the shortest path from one location to a target is to load a fully stored shortest path tree and then apply some diffs to it to get the shortest path tree of the target location. Then only the current player position needs to be found on the shortest path tree which is O(n^2) complexity.

I don't have any hard facts on how much storage space is needed for storing the shortest path trees and their diffs, but this could be in the range O(n^2 log(n^2)). Loading one and appyling the diffs might only have time complexity of O(n^2).

The shortest path tree for a target location represents all the shortest path from every location on the map to the target location.

This solution may also keep the used shortest path tree in memory and apply diffs as necessary in order to get the new shortest path tree to use. Then the complexity of getting the shortest path tree is not bound by the size of the map, but just by the size of the diffs to be applied. This scenario might really work well for games like the original Sacred or Diablo.

SpaceTrucker
  • 13,377
  • 6
  • 60
  • 99
  • Sounds like a pretty good idea, especially if you have a quick way of finding the "best" shortest path tree to use (that would probably be the one whose "root" is closest to either the starting point or destination). OTOH, there can be many more than O(n^4) shortest paths... In a square n-by-n map with no obstacles and using no diagonal moves, there are (2n choose n) different shortest paths from the top-left corner to the bottom-right (that is, sequences of moves that go only down or right). That number is approximately 4^n / sqrt(pi*n). – j_random_hacker Jun 15 '16 at 13:39
0

If your map has uniform weight (except for obstacles of course), you may have better performance with either:

  1. An algorithm that preprocesses the grid into a graph, collapsing large, empty spaces into a single node. Navigation meshes break the traversable area into convex polygons each of which can be traversed in a single step. L1 path finder groups the obstacles together, reducing them to a visibility graph calculates the path over that.

  2. An algorithm that does not expand every node. Jump-point search takes advantage of symmetry between different paths, only expanding nodes adjacent to obstacles, whereas A* would expand every node along the shortest path.

c2huc2hu
  • 2,447
  • 17
  • 26
0

A high level concept might be to find the points of the start and end - say point (0,0) and point (10000, 10000) - and make a preliminary guess for a path going from beginning to end (in this case it would run diagonally the whole way up and to the right) Then start checking to see if it can successfully get there (if there are obstacles on that path or not). If there are then programmatically choose similar paths, or alternately find where the path fails and start there and try to iterate until it works, it might not be 100% the fastest but you will get a lot better results than finding every single possible way, then deducing the shortest path from that.

Implementation

  • Method to find initial shortest path
  • Run to see if it works
    • If it fails then either try similar path or start from failure
trevren11
  • 192
  • 1
  • 4
  • 10