1
\$\begingroup\$

I am trying to implement HPA algorithm for finding the shortest path between two point. I came across the paper Near Optimal Path Finding Algorithm (by Botea, Müller & Schaeffer) but I am stuck at the clustering part. I have a 2 dimensional array and each index in the array is a node. Could anyone help me clustering my 2 dimensional array into clusters?

\$\endgroup\$
  • \$\begingroup\$ Clustering is a hard problem, with premade maps you can do it manually. \$\endgroup\$ – ratchet freak Apr 16 '19 at 10:33
  • \$\begingroup\$ @ratchetfreak I have a grid map already. It is a 2d array, how can i create clusters from this map. \$\endgroup\$ – Thuan Nguyen Apr 16 '19 at 10:48
  • 1
    \$\begingroup\$ What do your maps look like at the moment? Can you show us an example of the types of features you'd like to end up in the same cluster together, and what features should tend to divide clusters? \$\endgroup\$ – DMGregory Apr 23 '19 at 14:32
1
\$\begingroup\$

The easiest implementation is to divide the map into large tiles. For example, this illustration shows a 16 x 16 map clustered into 4x4 tiles:

clustered map example

While somewhat naive, this approach is very easy to implement, gives consistently sized clusters and due to the hierarchical reduction, may very well give good enough performance.

\$\endgroup\$

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.