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.
