# How to identify entrances of a cluster in HPA*?

Recently I've become interested in understanding and implementing HPA* in a RTS game. I've found the following presentation which is really good for explaining how HPA* works: https://harablog.files.wordpress.com/2009/06/beyondastar.pdf

At slide 28 it says "identify entrance points between clusters". Slicing my map into several clusters is easy, but I can't get the idea how to identify the points between clusters. "Should I take the middle? Border points? All of them?"

I've struggled to look at some implementation in java, C# or C++ but games like 0 A.D. use a different strategy for implementing hierarchical graphs mixed with Jump-point search. Others like libgdx-ai use multi-level HPA* and can't find an implementation simple enough to understand and reproduce, specially on the matter regarding entrances and how to connect them.

Can anyone enlighten me?

Thanks

"Entrances" are simply the rectangles where both clusters have open squares on their side, right?

Computing them in pseudocode is something like this:

• Iterate along edges shared by two clusters
• For each tile, if tile is open
• Check if tile on the other side of the edge is open. If so,
• If currently tracking an entrance, add these two tiles to it.
• Otherwise, start tracking a new entrance, and add the tiles to it.
• Otherwise it's not open, so
• If currently tracking an entrance,
• Close out the entrance (stop tracking and record it)

In the example on slide 28, you can imagine they were iterating downwards along the orange middle vertical divide. They found (for those 8 tiles) that both sides of the orange divide were open. So, they marked those 8 as an entrance. Later they did as in slide 29 and computed a central transition point, which is the two opposite-side (different cluster) tiles that are closest to the center.

Then the algorithm continues on, joining those transition points, etc.