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