For an assignment, I am required to implement an A* algorithm in order to find the shortest path between two object using different heuristics
- null, this effectively becomes Dijkstra
- Euclidean distance
- Clustering
So I have successfully implemented the A* algorithm and the first two heuristics and they work wonderfully. However the third heuristic I am having trouble with. According to the text
The cluster heuristicworks by grouping nodes together in clusters. The nodes in a cluster represent some region of the level that is highly interconnected. Clustering can be done automatically using graph clustering algorithms that are beyond the scope of this book
When the heuristic is called in the game, if the start and goal nodes are in the same cluster, then Euclidean distance (or some other fallback) is used to provide a result. Otherwise, the estimate is looked up in the table.
I'm not one to give up on a challenge so I would like to implement some automatic clustering technique. I am lazy and I really don't feel like manually clustering nodes, I want it to be automated. So I have been doing research on clustering and I've come across this technique: Markov Cluster Algorithm(MCL)
Are there any good methods besides the one presented? I have searched the IEEE database for clustering techniques but I am not entirely sure if those are valid for the scope of my assignment. I'm not looking for any code but I would surely appreciate any guidance on the matter.
Edit: I should clarify what is required in the assignment for clustering.
For the Cluster heuristic consider the nodes in each room to contain a cluster, and each corridor to contain a cluster. Using Dijkstra’s algorithm, between each pair of clusters compute the shortest distance between any two nodes (one from each cluster). Use these results between pairs of clusters to create a lookup table.
Furthermore this is the requirements for the level. Each convex polygon represents an obstacle. If I had to guess, there are 7 clusters in total