How can I optimise collision checks for a large number of AI units?

Let's say I got 100 Orcs in my 3D world and they all aim to kill each other.

That means for every 1 Orc I have to check for collision with the 99 others. That will give me 99^2 which is about 10,000! That many collision checks every update (24-60 times a second) only for the AI will probably use my whole GPU + CPU.

How can I handle such a large number of AI?

How is this is done in games with large numbers of NPCs (e.g. Skyrim, Fallout, Red Dead Dedemption...).

• Do a search for "space partitioning". There have already been quite a few questions on the subject. May 22 '12 at 7:13
• Collision detection is not the job of AI. It's the job of collision detection. May 22 '12 at 7:19
• YE sure but the NPC need to have some sort of collision so they can kill eachother May 22 '12 at 7:20
• "... will probably use my whole GPU+CPU" Have you tried? Computers are unexpectedly fast sometimes.
– Anko
May 22 '12 at 9:06
• well not maby not only but combinded with lots of rendering and other calculations my computer starts shaking May 22 '12 at 12:03

Actually, if you have N orcs, you have to check only (1+N)*(N/2) times (a smart dude named Gauss found this out). In your case, that is 5050. If orc A collides with orc B, that means that orc B collides with orc A. So for the fist orc you have to check 99 times, for the second 98 times, and so on. If you use space partitioning as the suggested in the comments, and check only orcs that are close to each other the number of checks is not so big.

p.s. collision checking should not be performed by the AI. The AI should act based on the result of collision checking

• who should do collision check then? May 22 '12 at 12:04
• A separate component. Beside the AI, there are other parts of the game that usually need to know about collisions. (If you use an existing game engine, there's a good chance it already has some form of collision detection, scene graph and spatial partitioning.) May 22 '12 at 12:31
• Well I use the MVC. one class fro rendering one for updating and one for input. So yes my udpater updates the collison but I will look up spartial partition or what that is! May 22 '12 at 12:58
• MVC is one of the worst possible ways to architect a game engine. I've seen plenty of people (mostly experienced Web devs) try to use for games. It can certainly be done, but the second you run into "well I use MVC so I can't easily do things correctly" you should realize that MVC is a bad idea for games and throw it out. May 23 '12 at 19:28
• a smart dude named Gauss found this out , and probably when he was 8. Dec 15 '14 at 2:48

Use spatial partition to reduce collision to O(n logn), not O(n^2). Also, a modern CPU can easily push 10k checks 60 times a second. I had an N-body simulation which could push about 2m checks at 30fps. And the GPU does not give a monkey's thrown faeces about your AI.

• "does not give a monkey's thrown faeces" nice ^^ well any modern CPU. how do define modern? 1 year, 2? 3? 8? May 22 '12 at 12:09
• lol the O(n log n), this is a complete assumption. A good partitionning scheme will give you O(k.n). k being the average number of entities close to any given single entity. Dec 15 '14 at 2:50