0
\$\begingroup\$

Currently in my game engine when a user selects a large number of units and commands them to a target each unit finds its own path using Jump Point Search. The performance of this is generally OK. What I dislike is that over longer distances all the paths tend to converge so that the units end up competing to reach the path's nodes. Pathing Problem

My solution to this is to group the units together and create a path from the unit closest to the centre of the group. I then use steering behaviours / flocking to sensibly navigate the group along the path to the target.

The problem I am struggling with now is that the user may select many units which aren't physically grouped together. Some may be very far away from each other, others may be close but separated by walls, etc. It is not really possible to create one path for such a group. Grouping Problem

What I need is an algorithm that can create discrete physical groups from a larger set of units like in the image above. I'm at a loss as to where to start with this. I had thought of maybe using some sort of brushfire algorithm, adding units to the group as they're discovered and stopping at walls or too much empty space. I'd rather not reinvent the wheel though and would appreciate any help anyone can give me.

\$\endgroup\$
3
\$\begingroup\$

You are looking for a clustering algorithm. It is a very vast research area because it is used in statistics (Wikipedia has at least 36 articles describing algorithms).

My suggestion would be single-linkage clustering. Here is how it goes:

  • start with N clusters, each containing 1 unit
  • repeat:
    • find the two closest points that are not in the same cluster (use your in-game distance, taking walls into account)
    • if the distance between these points is small enough, merge these clusters
    • if the distance is too large, you’re done

One remark: you may see some of the above algorithms being described as “slow” or “inefficient”. While this is true for their usual purpose (i.e. when dealing with millions of statistical data points), in your case (a few dozen units) I think you’re better off with the simplest algorithm you can find.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.