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][1]][1]

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][2]][2]

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. [1]: https://i.sstatic.net/FdrcP.png [2]: https://i.sstatic.net/bDMgm.png

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.