For intentional reasons, certain units in the game I'm currently programming don't have any collision detection and response among each other.
This enables them to clutter right on top of each other. This is a wanted behavior, since there will be situations in the game when the player does want them to stack like that.
However, I want to make the process of uncluttering them easy for the player, so that they just have to press a hotkey or click some button on the screen and have the units disperse just enough so it's easy to select a group of them with the mouse (if they stand on top of each other one mouseclick selects all units).
How could I do this without running a brute force N^2 nearest neighbor search on all units?
Answer
Create a grid with enough spaces for all the units you want to "unclutter", have them each choose the nearest unclaimed grid space. Then have them move towards their respective grid space.
This will move them into something like a formation, where the player can easily select an individual unit.
That's an O(N) operation with pretty good results.
No comments:
Post a Comment