2
\$\begingroup\$

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...).

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

2 Answers 2

Reset to default
9
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ who should do collision check then? \$\endgroup\$
    – AndroidXTr3meN
    Commented May 22, 2012 at 12:04
  • \$\begingroup\$ 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.) \$\endgroup\$
    – loodakrawa
    Commented May 22, 2012 at 12:31
  • \$\begingroup\$ 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! \$\endgroup\$
    – AndroidXTr3meN
    Commented May 22, 2012 at 12:58
  • \$\begingroup\$ 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. \$\endgroup\$
    – Sean Middleditch
    Commented May 23, 2012 at 19:28
  • \$\begingroup\$ a smart dude named Gauss found this out , and probably when he was 8. \$\endgroup\$
    – v.oddou
    Commented Dec 15, 2014 at 2:48
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ "does not give a monkey's thrown faeces" nice ^^ well any modern CPU. how do define modern? 1 year, 2? 3? 8? \$\endgroup\$
    – AndroidXTr3meN
    Commented May 22, 2012 at 12:09
  • \$\begingroup\$ 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. \$\endgroup\$
    – v.oddou
    Commented Dec 15, 2014 at 2:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .