# Pathfinding and clusters

For an assignment, I am required to implement an A* algorithm in order to find the shortest path between two object using different heuristics

1. null, this effectively becomes Dijkstra
2. Euclidean distance
3. 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 • Note that in the example, each cluster forms a convex region. That means a navigating entity can move between points within the cluster in a straight line without encountering an obstacle. Breaks between clusters are introduced where there are concavities in the navigable area (because here Euclidean distance is no longer such an effective heuristic). So you may want to consider clustering algorithms that consider the convexity of clusters, or line-of-sight visibility between nodes as a connection affinity. Feb 22, 2015 at 17:27
• Here I was referring to the convexity of the region delineated by the cluster labels. Cluster B is not a clique, because there is no edge connecting the bottom-left corner to the top-left, for example. If we clustered based on cliques alone, each triangle would be its own cluster, which is a bit excessive. Each cluster shown here is strongly connected, but so is the whole graph, so a strongly connectedness criterion alone doesn't help in determining clusters. Feb 22, 2015 at 17:39
• Just saw fryBender's edit. Given the wording of the question, describing how to cluster, I think they are expecting the student to manually tag the clusters, rather than use an algorithm to infer them from the navigation graph/mesh. You could do that as an exercise, but I think it's strictly overkill for your current needs. Feb 22, 2015 at 17:48
• @DMGregory you're right... I guess I meant "connected component"; in which case it is clustering. Feb 22, 2015 at 17:52
• Fair point. One thing to consider in your implementation - now that I can see your assignment case - is that the heuristic matters where A* can make a choice. So long corridors without branching can probably afford to be taken as a single cluster, even if they turn a corner (contrary to my convexity suggestion above). So maybe look at the branching factor too in deciding where to split clusters. :) Feb 22, 2015 at 18:01