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\$

1 Answer 1

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, 2016 at 4:07
  • 1
    \$\begingroup\$ @JPtheK9 Yes, that is a required part of the algorithm in order to determine the distance between entrances. \$\endgroup\$ Sep 24, 2016 at 17:25

You must log in to answer this question.

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