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?

  • \$\begingroup\$ Clustering is a hard problem, with premade maps you can do it manually. \$\endgroup\$ Apr 16, 2019 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\$ Apr 16, 2019 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, 2019 at 14:32

1 Answer 1


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.


You must log in to answer this question.

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