0
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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

Does this answer your question?

\$\endgroup\$
2
  • \$\begingroup\$ I will try to implement your approach, feels easy enough for my problem. Then once I grasp the idea I can evolve into multilevels and so on. Thank you Chris. Btw, do you know any place where I can see a real HPA* implementation? \$\endgroup\$ Commented Jan 28, 2016 at 22:42
  • \$\begingroup\$ Nothing off the top of my head, sorry. Good luck, and let me know how it goes. :) \$\endgroup\$ Commented Jan 29, 2016 at 0:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .