2
\$\begingroup\$

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.

Representation of clustering

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 Level requirement example

Improve this question
\$\endgroup\$
9
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory ♦
    Feb 22, 2015 at 17:27
  • \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory ♦
    Feb 22, 2015 at 17:39
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory ♦
    Feb 22, 2015 at 17:48
  • \$\begingroup\$ @DMGregory you're right... I guess I meant "connected component"; in which case it is clustering. \$\endgroup\$
    – mklingen
    Feb 22, 2015 at 17:52
  • 1
    \$\begingroup\$ 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. :) \$\endgroup\$
    – DMGregory ♦
    Feb 22, 2015 at 18:01

1 Answer 1

Reset to default
2
\$\begingroup\$

Clustering in Graphs

I'm not sure why your assignment has given you an open research problem (clustering in graphs) to solve. Please ask your professor if this is really required before continuing.

If you know the number of clusters, (or can guess them) I would suggest trying something like spectral clustering, or K-means clustering; using the number of edges as the affinity between clusters. You can also try min-cut-max-flow like algorithms.

Generally, the idea is to divide the graph into a number of connected components such that:

  • The connectivity within the components is maximized
  • The connectivity between components is minimized
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Thank you for your input mklingen. I haven't had the chance to speak to the professor regarding clustering, but I feel that I could get away with clustering regions manually as opposed to having it automated. >If you know the number of clusters, (or can guess them) I would have to guess 7 in total based off the level requirement. I edited the question to reflect this \$\endgroup\$
    – fryBender
    Feb 22, 2015 at 17:39
  • \$\begingroup\$ The assignment isn't asking him to do this. The assignment says "Clustering can be done automatically using graph clustering algorithms that are beyond the scope of this book". I would guess the requirement is only for manual clustering. \$\endgroup\$
    – user253751
    Feb 22, 2015 at 20:25

You must log in to answer this question.

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