RTS Target Searching Algorithm


I’m currently trying my hand at scripting the foundations for a real-time strategy game like StarCraft. At this stage, I want units to be able to tell what units are withinin range of them and which of those units is the closest. I wish for the game to be handle more than 100 units at a time.

I’ve been trying out a few methods. The most crude one would be to continuously loop through all units and then for each of them loop through the units again to find the targets in range. I found that this doesn’t scale up well. I’ve also tried using an event driven system where when a unit moves, its distance to all other units is calculated. The issue with this that I’ve run into is that I have to run the calculations as long as the unit is moving but there’s no easy way that I know of to know when a humanoid stops moving besides a loop. I’ve also considered using FindPartsInRegion which is fine for finding nearby targets but in order to narrow it down to the closest target, I’d have to loop through the results.

Can anyone think of an efficient target search algorithm that can be scaled up to handle large amount of units? Thank you!