How to identify if entrace to HPA* cluster is faulty?

Question

I have been working on my simple game where enemy would hunt me with A* algo. But it was a bit slow so I found this thing called HPA*. Someone who would decide to help me will probably know how it works but I shall explain how I wanted to do it until I found a limiting factor to my implementation.

First step would be to convert my map to certain sized clusers. For a 2020 map I would have 4 1010 clusers (trust me, the dimensions here are not to the scale, I just want to keep things simple while describing the problem).

For each cluser I would like to determine possible entrances. So if I was staring in the cluster where the blue circle is, I would:

1. check the edge that is shared by top left and top right cluster. Since top left cluster has that edge all blocked, then I would just return no position of entrance at all.
2. check the edge that is shared by top left and bottom left cluster. I would find that no point is blocked in top left cluster and 2 points are not blocked in bottom left cluster. These 2 points can serve as possible entrances to bottom left cluster. BUT one points is considered "faulty" and I want to know how to deal with this. I want to leave that entrance as valid, because someone might actually appear in that little hole but If my target was the red circle, I would want to dodge that "faulty" entrance.

My point is that I don't really know how to deal with HPA* generally because I have 2 solutions in my mind. First solution would be to preprocess it and create an edge between all entrances and that would serve as my graph I could execute my A* on. The second solution would be creating this abstract cluster grid, where each cluster would serve me as a node and I would firstly find my shortest path on this abstract layer before moving to another cluster. That would give me instructions like "execute A* in the topleft cluster into botleft cluster because they are connected with entrances, then execute A* in botleft cluster to botright cluster because they are connected with entrances." The problem is that if I would do that, the shortest path from botleft to botright cluster would lead me to the faulty entrance... Maybe I could floodfill the entrance and check if the floodfill hit the target. Or take all the entrances and execute A* on every of them and check if it got me where I need to be.

Answer 1

You have a set of entrances that define the connections between each map 'chunk'. These are the edges between the chunks.

You also need to keep track of the edges within each chunk (the intraedges) -- that is, all of the connections between the various entrance nodes of one given chunk. You can do this with regular A* and cache the pathfinding cost, or make it infinite if there is no path between the entrances without leaving the current map chunk.

Once you have that, there is only one more obstacle: your destination node may not be an entrance, in which case you do not know the valid intraedges for that node. One solution is to use A* to find the valid connections between your destination node and the other entrances of that chunk. Alternatively, you can run a depth first search in each map chunk to divide it into distinct disconnected 'regions' as part of your preprocessing. Then you simply compare the region ID of the destination node to the region IDs of each entrance in that chunk: different IDs means there is no path between them without leaving that chunk.

Example:

This is similar to the terrain in your question. I have added an additional set of obstacles in the upper right map chunk to demonstrate more clearly how you can mark connected regions.

This shows the entrances. Each entrance has an interedge to the adjacent entrance in the neighboring map chunk, and it also has a cache of all its intraedges to other entrances inside its own chunk.

This shows connected regions found by a depth first search. Notice the two islands in the upper right chunk that are surrounded by impassable nodes (the islands are regions '2' and '3' surrounded by the impassable region '0').

Pathfinding from the initial tile to the destination tile on the abstract layer. The entrances with white borders are the ones in the final path. Due to how we constructed the abstract representation of the map, we avoid falling into the dead-ends when we run A* on the abstract layer.

Answer 2

During your pre-process step, pick a "center" point of each cluster (some non-obstacle point near the cluster center) and initialize its cluster ID to that cluster and its distance to zero. These tiles are your initial frontier. Every other tile gets initialized to a max or infinite distance.

Next, propagate distances outward from the previous frontier to adjacent reachable tiles. When a tile's distance decreases, add it to the frontier for the next iteration, and set its cluster ID to that of the tile it was reached from. Repeat until no further tiles get a decreased distance.

Now you have a cluster ID for each tile in the map that accounts for how that tile is actually connected to its parent cluster. So both sides of a "false entrance" should get assigned to the same cluster, and won't be regarded as a cluster-to-cluster connection at all.

(Here I use colour tint to indicate assigned cluster ID and brightness to indicate path distance from cluster center. Notice that the "false entrances" no longer bridge two different clusters)