Finding the closest gameobject of another gameobject

[Bug_Slayer]

Hi I have a problem.
Suppose there are 100 units on one side and another 100 units on the other side of a field, how can I calculate the closest enemy for each of them without lowering the fps too much? I tried to follow some youtube tutorials on them but havent found one that is good. So I tried to use kd-trees and knearest algorithm, but I don’t know if that’s the right way to do it.
pls I need some advice on this

[Kurt-Dekker]

Generally speaking, your choices lie in three areas:

• do less work (consider fewer entities)

• do the work less often (does it need to be updated each frame or can it be calculated one unit per frame so you get updated once per 100 frames??)

• come up with a different approach to achieve the same ends

Because the answers to the above are closely tied to your game’s needs, it’s kinda hard to answer specifically.

But remember, DO NOT OPTIMIZE CODE RANDOMLY… always start by using the profiler:

Window → Analysis → Profiler

Is it still worth optimizing square roots in 2021+?

It depends on the target architecture and runtime library of course, as all computer code runs on the actual CPU where your game is running, not some “theoretical magical global CPU of today” construct. But in 2021 a floating point unit (FPU) is pretty standard on most targets. All that said, don’t do needless work, especially on mobile, as that just burns down battery life. If you suspect you have a performance bottleneck, DO NOT START MAKING OPTIMIZATION CHANGES!! Instead, start with the …

Optimizing UnityEngine.UI setups:

How to efficiently copy transform data into an array

Just so you know, the entire UnityEngine.UI system is available in source control from the package manager (and from github) and you can look at it and probably see there isn't going to be a lot of fat. If there are some particular specific widgets you use in there that are too slow because of the use-generalization assumptions made, you might be able to get some benefit by tweaking them, but since so much of mobile performance bumps against pixel fill bounds, it's unlikely to g…

[Bug_Slayer]

@Kurt-Dekker

Generally speaking, your choices lie in three areas:

• do less work (consider fewer entities)

• do the work less often (does it need to be updated each frame or can it be calculated one unit per frame so you get updated once per 100 frames??)

• come up with a different approach to achieve the same ends

Because the answers to the above are closely tied to your game’s needs, it’s kinda hard to answer specifically.

But remember, DO NOT OPTIMIZE CODE RANDOMLY… always start by using the profiler:

Window → Analysis → Profiler

https://discussions.unity.com/t/841163/2

Optimizing UnityEngine.UI setups:

https://discussions.unity.com/t/846847/2

Hi thanks for your answer,
but that was not what I was looking for,
ofcourse I know that by doing less work or doing it less often works, but that just ignores the problem and doenst solve it.

So coming up with a different approach is better to do and I don’t know how I should do it, so I asked it.

But why did u send links of UI elements and square roots? My question is about finding the closest object. That is like giving a vegetarian meat.

[Joe-Censored]

Take all unit positions, send them to your own separate thread. Calculate the closest target for each on this separate thread, and since on this separate thread it doesn’t affect FPS of the main thread you’re generally free to do it with whatever optimal or unoptimal algorithm you wish. When done, send the chosen targets back to the main thread. Should be hardly any FPS drop, since you’re just copying or setting Vector3’s primarily on the main thread for this kind of thing. This would be my first thing I’d try at least (while only spending 2 minutes thinking about it, so there’s probably even better ways ).

[Kurt-Dekker]

@Bug_Slayer

but that just ignores the problem and doenst solve it.

You only told us a tiny fraction of the problem (“100 units on each side”) so I’m only able to give you a tiny fraction of the answer, and I attempted to guide you to a better solution but it seems to have eluded your notice.

Let me offer you these questions that I think you should consider.

• do these units need this data every frame? (eg, can you do the work less often?)

• how mobile are these units? (eg can caching help? if they’re all fixed turrets, of course it can!)

• are they all equivalently mobile? (eg can caching help in certain cases, are some of them fixed?)

@Bug_Slayer

So coming up with a different approach is better to do and I don’t know how I should do it, so I asked it.

NOBODY here can give you an actual response for “100 units on each side” optimization until you answer a whole awful lot more questions. If you don’t understand that you’re going to have a hard time reasoning about a solution.

Put another way, you have already discovered that an O(n^2) solution is not suitable. That’s a given. That’s why you’re posting here. I’m trying to guide you to deciding if an O(n^2) problem is really what you have, or if it is far less of a critical problem than that.

@Bug_Slayer

That is like giving a vegetarian meat.

That is all part of my standard “don’t optimize crap you don’t need to optimize” but I guess that was lost on you as well.

[Joe-Censored]

@Bug_Slayer

Hi thanks for your answer,
but that was not what I was looking for,
ofcourse I know that by doing less work or doing it less often works, but that just ignores the problem and doenst solve it.

So coming up with a different approach is better to do and I don’t know how I should do it, so I asked it.

But why did u send links of UI elements and square roots? My question is about finding the closest object. That is like giving a vegetarian meat.

@Kurt-Dekker was sending you links related to optimization. Really the best way to optimize is to try several different ways of doing the same thing, and test the results. Unity’s Profiler tool is usually the go to tool to use when testing results. Optimizing square roots or optimizing a target finding algorithm is really no different as far as the overall steps. Try a few different ways, test and see what the Profiler says for each, and go with the one which meets your needs for performance and maintainability of the code.

[Bug_Slayer]

Thanks for your answers and time

@Kurt-Dekker

You only told us a tiny fraction of the problem (“100 units on each side”) so I’m only able to give you a tiny fraction of the answer, and I attempted to guide you to a better solution but it seems to have eluded your notice.

You have a point there, I am sorry, they can move and can fight if they are close to their target

@Kurt-Dekker

• do these units need this data every frame? (eg, can you do the work less often?)

Maybe every 2 frames, whatever you like, but if their closest enemy dies or it goes away and another unit is closer, it should change to the closer one.

@Kurt-Dekker

Put another way, you have already discovered that an O(n^2) solution is not suitable. That’s a given. That’s why you’re posting here. I’m trying to guide you to deciding if an O(n^2) problem is really what you have, or if it is far less of a critical problem than that.

I don’t know what u mean by that, but a unit should go to the closest unit to fight, and my problem is that I want a fast way to get the closest one

[dgreenheck]

I’m with Kurt-Dekker: premature optimization is the death of all projects. Is your current implementation too slow? You mentioned kd-trees and k-nearest but didn’t mention anything about how they performed. If they work then use them and move onto the next part of your game.

---- The rest of this is assuming that those approaches didn’t work -------

Rather than finding the closest for each enemy (which is an expensive operation), are there different approaches that would give the same visual result you are looking for?

• Have each unit cast a ray in the direction they are looking. If you’re dealing with soldiers, this is probably a bit more realistic anyway because we aren’t that good at measuring distance.
• Are units arranged in a known, ordered formation when they start? You can precompute the closest ahead of time and then during combat as units die, find a new target using gridded binary search.

You’ll also need to answer other questions

• Should target update to pick the closest constantly? Or once locked onto a target, stick with that target until it dies or the target dies?
• If a unit is being attacked, does it re-target to the attacker or stay on its own target?
• Can a unit be attacked by more than once? Or is it one to one combat? If one to one combat, look into using hash sets to store which enemies are engaged to avoid searching over all.

Another thing to keep in mind, I worked on a project like this 10 years ago and all of the units tended to move into one big blob in the center. It wasn’t very interesting to look at. Adding some randomization to the targeting should help.

[_geo1]

@dgreenheck

I worked on a project like this 10 years ago and all of the units tended to move into one big blob in the center.

I love how such simple simulations tend to emulate real world behaviours like “surface tension”. Everyone want’s to minimize distance and find a partner, kinda similar to what atoms do. Sorry for the sidetrack, just thought it’s funny

As for the question at hand, does every agent really need to find the exact closest target or is any target reasonably nearby acceptable? If any nearby target is okay then an algorithm which just searches for any nearby target group would suffice (my variation of what kurt said with “do less work” in his first post).

[exiguous]

I guess a unit has a certain range? Then I would just iterate all enemies and put all of them WITHIN RANGE into a list/array. Then you just have to search this list (with enemies updated positions) each time you need a new target. And you repopulate the list when the unit itself has moved a certain distance or when the list of viable targets is empty (either because all are dead (could be killed by other units too) or moved out of range). This way you only check when necessary in a much smaller data collection. The targetlist/-array works as a preselection so you don’t always check against all possible targets but you keep those close enough “in mind”. If there is no target in range you need to move towards the closest one. I think this method allows to reduce the load quite a bit. But you can’t just remove targets when they are dead but you must “flag” them as dead as they list owners must remove them from their list in that case themselfes.