Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite

Let's say I got 100 Orcs in my 3D world. They all have the goal to kill each other.

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

Any tip on handling AI?

Maybe someone know how they do in huge games like Skyrim, fallout, Red dead redemption...so on which has huge openworld with lots of NPC.

share|improve this question
3  
Do a search for "space partitioning". There have already been quite a few questions on the subject. – Sam Hocevar May 22 '12 at 7:13
5  
Collision detection is not the job of AI. It's the job of collision detection. – Nicol Bolas May 22 '12 at 7:19
YE sure but the NPC need to have some sort of collision so they can kill eachother – AndroidXTr3meN May 22 '12 at 7:20
1  
"... 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 – AndroidXTr3meN May 22 '12 at 12:03
show 2 more comments

2 Answers

up vote 8 down vote accepted

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

share|improve this answer
who should do collision check then? – AndroidXTr3meN 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.) – loodakrawa 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! – AndroidXTr3meN 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. – Sean Middleditch May 23 '12 at 19:28
up vote 1 down vote

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.

share|improve this answer
"does not give a monkey's thrown faeces" nice ^^ well any modern CPU. how do define modern? 1 year, 2? 3? 8? – AndroidXTr3meN May 22 '12 at 12:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.