# 3D: How how handle like 500 NPC

I'm currently working on a 3D game. My game have like 10 NPC's and a really small world. But if I want to have a larger world with lots of NPC's? I think it's not a good idea to update and check collision with NPC's that is far far away from the hero.

So any tip on how to handle things that are outside the hero's sight.

Two basic optimizations

1) Dividing you world into logical chunks. A chunk is a rather large portion of your game world and independent of your actual objects. It is large enough that you can make the simple assumption: You have 2 "collidable" objects, one is in chunk A, the other in chunk B. If A and B do not have a common edge or point, then the said objects cannot possibly collide, so they have a distance of 2 chunks or larger. Then you can disregard them right away. Note that if you use hexagonal chunks, you only have to check for common edges, i.e. you can use a hex-based equivalent to the "Manhattan distance".

2) Distance-based pruning. If the 2 objects in questions are in the same chunk, or in adjacent chunks, you need to refine the check. At the simplest level, imagine a sphere centered around every object that can collide with something else. The sphere is just large enough to completely surround its object, so that neither part of the object can stick out under any circumstances. Then you can conclude that if the distance between 2 objects is larger than the sum of both spheres' radius, then those 2 objects cannot have collided. To optimize this calculation, don't work with distance and sum of radii, but their squares, to avoid calculating expensive square roots.

Only when both checks indicate a possible collision, move on to the more expensive checks, which is probably hit boxes. Remember that the closer your bounding boxes resemble your actual object's geometry, the more expensive things get. You have to find a good compromise between quality and quantity of collision checks, but that depends on your game design entirely.

• If I use chunks then if player is on the edge of a portion then it would look weird right? May 10 '12 at 15:39
• @AndroidXTr3meN An object is always in exactly one chunk, never on an edge. Note that "chunks" are not visible in the game in any way, it's just a logical partitioning of your game world. May 10 '12 at 15:47
• Like some sort of spartial hashgrid mentioned above? May 10 '12 at 16:01
• @AndroidXTr3meN Yes, exactly like that. By the way, Quad-trees and Oct-trees are basically dynamic chunks. They are a bit more complicated, but have big advantages. May 10 '12 at 16:08

You should probably use a octree (see this question on StackOverflow) - don't worry about figuring out what is out of sight because would likely be more expensive than an octree.

For the collisions you'll want to do spatial hashing. What that means is that you basically subdivide the world into several small parts where it's guaranteed that things within a "chunk" of the world cannot collide with anything not in it's chunk, or possibly a chunk next to it.

What you could also do is to freeze the NPC's when you're not near their chunk. This can probably be a good solution depending on how your game works. Doing something like this assumes that you, instead of looping through all game entities in a loop, construct an "update" method for the chunks themselves. That method in turn calls the update method on the entities. This way you can easily implement this method of splitting up into chunks.

• Spatial hashing isn't that great for 3D. May 10 '12 at 11:17
• And aren't octree/quadtree spatial hashing structures? May 10 '12 at 13:44
• Technically speaking, "spatial hashing" uses fixed size buckets (like a hash table) and can't react dynamically to population densities like an octree/quadtree does. Hashing is prone to either too small buckets and wasted memory or too big and it won't solve your NPC problem. Good for static collision data, not so much for things that move and cluster/spread. May 10 '12 at 17:32
• It's because of the 3D nature of it :). Spatial hashing will allocate N buckets no matter how many of them are empty - so you are wasting quite a few more CPU/memory cycles than you would have been were you using octrees. Consider a simple 3x3 square, in a cube there is 3x3x3 cells (3 times more the memory and work). May 11 '12 at 8:21

You don't really have to apply physics and collision in NPCS, unless they're truly dynamic (Like one NPC that's on the player team, one npc that fights, etc.). Why? NPCs are already controlled by the program, so they should know where they can walk, where's the floor... So instead of:

Walk Forward;
Keep applying physics every frame to make it bound to the terrain;


You can just do once:

Walk forward at terrain level;


This can be hard if your terrain is irregular. But shouldn't be a VERY hard problem. Another solution is applying physics just when they're making some action like walking, then when you got it's final position just de-attach its body from the physics engine til it need to make another action.

• I meant more that It's to much for a computer to update 500 NPC's at the same time even if there not close to you. May 10 '12 at 15:10