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?
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:
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.