2
\$\begingroup\$

so I have been working on implementing a form of HPA* but i'm really struggling to decide what to do next.

https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf <- here is the article.

There is pseudo-code but the notation is very hard for me to understand, but I struggle to read due to learning difficulties (visual snow / ADD) and I find the paper very difficult to understand, so I appreciate anyone willing to explain/ break it down to me in simpler language.

I have implemented my grid and seperated it into squares. Example diagram - here is my guess, I haven't implemented exits and entrances yet, green terrain is normal, white terrain are roads which travellers will travel across quicker, brown is mountains inpassable unless meets a special condition, and there are boats but they will use a different algorithm, since im only implementing HPA* for ground units in the game ,and JPS for sea units as the sea grid is uniform without costs.

Lets say for sake of argument each pixel on that image is its own individual grid space.

enter image description here

Question 1. Do I have to resize the squares if water/mountains is involved- lets assume the water/mountains is a wall for the sake of the argument. (If so whats a good method?)

Question 2. Is there a general algorithm that can be used, I know the A* algorithm, but how do entrances and exits link to eachother ? (thinking quad tree)

Question 3. How do I reconstruct the squares dynamically if the map could change or be dynamic.

Question 4. how does one traverse across the map from higher representation to lower representation.

Assumptions, I'm assuming first we path-find across the squares as a whole, then work out individually the route inside it from one end to another yes?

Also if you know the location of a good HPA* library that would be also be nice.

\$\endgroup\$
  • 1
    \$\begingroup\$ As I commented a few months back, I don't think per-pixel pathfinding is your best bet here. It makes your graph gigantic, forcing you to use more complex pathfinding algorithms. It still looks to me like a navigation mesh would let you represent your pathfinding problem much more simply, and would likely bring down the graph size small enough that you can use regular A* without needing extra hierarchical considerations. Remember too that we can answer one question per post, so see if you can boil down your 4 questions into the one thing you need to know first. You can always make another post \$\endgroup\$ – DMGregory Nov 30 '17 at 13:08
  • \$\begingroup\$ @DMGregory its not feasible to go back and replace all the groundwork, this would completely break how my units move, and my influence map, it was designed this way so that it links in, also strictly speaking its not per pixel, the map is divided into 170x80 resolution for the initial detail, which is not per pixel but as high as i have to go for coordinates not to be ridiculously far away from eachother. \$\endgroup\$ – RNewell122 Nov 30 '17 at 13:46
1
+50
\$\begingroup\$

This paper is actually set up pretty oddly, most CS papers I see are, well, more succinct and to the point? This one kind of rambles doesn't properly label headers and doesn't go into what it is actually doing until section 3 and the appendix. You'll need to learn how to read these papers if you want to use these algorithms, so if you have problems with the appendix interpretation, I'm afraid you have a deeper level of misunderstanding somewhere that we can't help with unless you give more specific information on the holdup. But I can give you an overview of what the algorithm is.

This tackles the problem of "equal weighted un-directed graph with small constant maximum edge vertices per node (4 for rectangular grids) with predictable connection order" if you are looking for some keywords to look up for other methods.

Basically, the whole idea is:

  • subdivide rectangular grid into sub grids.
  • for each subgrid pre-compute paths to the borders
  • create 2 border symetrical border "node" for each unobstructed border of equal length for adjacent subgrids.
  • created edge between nodes on adjacent blocks if they were symmetric.
  • created edge between nodes on the same block if there exists a connection.
  • abstract grid now created.
  • perform all pathfinding calculations using this as a heuristic and recalculate fastest path from your position to next position

On new path, the paper recommends using straight line approach to find smoothed paths, additionally A* is used on the higher level graph.

Even higher levels of abstraction can be obtained for graphs via using combining the clusters seen at the previous levels, and essentially going through these steps again, but using your subgrids/clusters as the new basic block unit, and using the connections we previously created on them instead of cardinal direction connections.

This paper seems to ignore the existence of search algorithms that are APSP (all points shortest path) with which you would find the entire set of path for all nodes in a graph. If you try to use A* for this you will have a very slow algorithm. The most basic algorithm taught in school, Floyed Warshalls, will mislead you into thinking that is the best one to use for this problem, however its runtime complexity is O(V^3) and trust me, I've personally tried to use this on uniform grids only to find that it will literally take days to months to compute any significantly sized grid (1024x1024? forget about it). For grids, you can just use breadth first search with O(EV) runtime complexity, and if you subdivide your grids into small enough chunks, your complexity (for example for 8x8 subdivisions) will be quite small, O(N*C), where N is the number of blocks you have, and C ends up being number of verticies (V) * number of edges(E) but since it never changes it is constant.

You can additionally reduce the cost even further by only computing the paths from edge to edge, reducing both computational and space cost significantly (and with smaller subgrids this is probably preferred).

It might look like we did some magic to make the complexity go down, but keep in mind that we eat that cost at run-time since we still have to do some path finding.

Just know that each of your precomputed results for each subgrid will have a space complexity of O(N^2), so if you divide each into blocks of 8x8 = 64 cells, you'll have 4096 entries in some table telling you how to move to each thing in the fastest way for each of the N subgrid blocks. You can use this on the higher level abstracted grids as well for faster results.

Question 1. Do I have to resize the squares if water/mountains is involved- lets assume the water/mountains is a wall for the sake of the argument. (If so whats a good method?)

Nope, they are walls, as long as they don't change edge traversal cost your all good, the algorithm applies the same

Question 2. Is there a general algorithm that can be used, I know the A* algorithm, but how do entrances and exits link to eachother ? (thinking quad tree)

Not sure exactly what you are getting at, really all you need to know is if you can move from one edge to another, in this algorithm, edges are unobstructed symetric lines of grid points of the same length from adjacent blocks. All you need to do here is just run A* on each edge point within a block, and if a path is found with in one of the cells a long that edge to the other edge you are good, and you don't have to look at the rest of the cells with in an edge since they are all connected (if you can get to one block you can get to them all)

Question 3. How do I reconstruct the squares dynamically if the map could change or be dynamic.

You would have to re-run the algorithm to construct the sub-grid/block edges for that specific block, remove any previous connections, and find the adjacent edges again. Additionally rerun the algorithm to create the abstract graph on top of the blocks/subgrids/clusters if you had higher levels of graphs.

Question 4. how does one traverse across the map from higher representation to lower representation.

Run A* on the top level representation, this essentially becomes your heuristic where you can then run more localized versions of A* in the subgrids you created earlier in the lower levels, knowing that a path now absolutely has to pass through that subgrid.

\$\endgroup\$

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.