3
\$\begingroup\$

Aigamedev.com provides this visualization of HPA*:

aigamedev visualization

All the nodes within the same chunk connect to each other. What if there was an obstruction between nodes in the same chunk? For example:

obustruction in center bottom left chunk

What would the resulting visualization look like with an obstruction in the center bottom left chunk? How would this be detected?

\$\endgroup\$
2
\$\begingroup\$

Partitioning the chunk into two might result in additional entrances (nodes) in the graph, but otherwise there is nothing special that happens. Your statement "all the nodes within the same chunk [must] connect to each other" is false.

In your example the resulting entrances are the same (only a few edges are removed from the graph), but in the paper the authors give an example where a partition causes the sides of one chunk to be split into multiple entrances.

Multiple entrances

\$\endgroup\$
2
  • \$\begingroup\$ To detect these obstructions and prevent the connection from being generated, do I need to pathfind within the cluster between all the entrances? \$\endgroup\$ – JPtheK9 Sep 24 '16 at 4:07
  • 1
    \$\begingroup\$ @JPtheK9 Yes, that is a required part of the algorithm in order to determine the distance between entrances. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Sep 24 '16 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.