Enemy detection system

What is the most efficient way to check if enemy is in range.

Lets use the game starcraft for example, each player can have up to 200 units, in a FFA(free for all), you can have up to like 8 players, so there will be up to a max 1600 units in the game, each unit will have to cycle through all enemies(1400 other units) to see if they are in range, thats like 1600x1400(2.24M) to loop. if detection script is in update, then you will need to perform 134millions of checking per second.

I wonder if thats a good idea to do that, or are there a better way to reduce load while maintain the performance ?

 

No. It does not work like that.

RTS games use some spatial mapping, to find near units.
For example quad tree. This way, you reduce searching algorithm greatly.

 

No. This is an incredibly naive approach and it would only be used if programmer is unfamiliar with any sort of spatial optimization technique. No game does it this way.

What ACTUALLY would happen is that each unit would use "overlap sphere" or something similar, and physics system will use sweep and prune, octrees, bsps or any other technique which will reduce number of queries at least to logarithmic complexity.

If you're implementing queries yourself (for some reason), then something basic like octree will greatly speed up the process.

Basically, you can have a million enemy units on the map and use something like 16 queries per your unit to identify who is within range.
https://en.wikipedia.org/wiki/Octree

 

thanks for the basic info, im no game programmer, just ordinary application programmer, is trying to learn how game works, it may sounds obvious for you, its definitely new for me.

 

Look up the keywords I provided - octree, bsp, sweep and prune. Well, you could also try kdtree, sphere tree, obb tree and do on.

Those algorithms can be thought as being a spatial equivalent of binary search, lower/upper bound and so on. There are, of course even more exotic stuff like Morton codes (used for scene voxelization on gpu) but even basic octree /kdtree will provide you performance boost you want.

I'm my experience, using algorithms like sweep and prune, it is possible to implement a particle billiard (bouncy balls colliding with each other, but no rotational component) for 20000 particles. On a single core. On a 10 years old cpu.

 

As neginfinity says, these are extremely battle tested algorithms, usually going back a fair few decades in some cases. As a general piece of advice, I do recommend looking into bsp trees first since they're relatively simple structures to grasp as a beginner and make it a lot easier to grasp other tree types. Wikipedia offers some very simple explanations of sweep and prune and bounding boxes that will help you get on your way.

In some ways they're a little too simple, but they give you just enough info starting out that the topics won't get too overwhelming as you start digging into them. Consider them a primer and nothing more, basically.

 

You might be able to get away with only minimal spatial optimizations if you use a system like DOTS. Below is one of the more recent demos where the presenter used the naive approach for a number of units roughly similar to what is stated in the original post.

Spoiler: Unite Copenhagen - Converting Your Game To DOTS

 

The problematic part of bsp is selecting the splitting plane. Octree does not have such issue.

 

That's neat as a demonstration of how to use the system, but I'd not recommend it as an approach in a real project.

That's not to say I'd never do something like that, but I'd be aware that it's a quick-n-dirty approach and treat it as such.

 

Right. That's why I mentioned "minimal spatial optimizations". My idea is that you apply a global optimization (DOTS) to reduce the number and complexity of specific optimizations (spatial optimizations in this case).

 

<3

Thousands of enemies, noooo?! Millions make for an enjoyable game.

 

You'd have to cheat a lot for millions of active agents. Basically, in thsi scenario size of data sturctures you're using starts to matter a lot,

 

thats another thing i want to know, having millions of agents, does it mean you will have a millions of update calls ? isnt that a hell of a slowdown ?

 

Yes, if you continued using GameObjects with MonoBehaviours for each entity in the game you would have problems which is why you won't use this approach for games where you expect large numbers of them. Instead of that you would have one GameObject controlling multiple entities or all of them depending on the way the game plays.

 

do u mean using gameobject without update, or not using gameobject at all for those that has too many instances ?

 

The second one. Unity provides ways of drawing meshes without having to use gameobjects.

https://docs.unity3d.com/ScriptReference/Graphics.DrawMeshInstanced.html

With it you can achieve things like at the link below where someone shows off 100,000 animated characters.

https://forum.unity.com/threads/graphics-drawmeshinstanced.537927/#post-3550738
https://forum.unity.com/threads/graphics-drawmeshinstanced.537927/#post-3554726

 

Great info, thats indeed really good to know. Thanks, and happy new year.