3D: How how handle like 500 NPC

Question

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.

Answer 1

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.

Answer 2

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.

This article explains how to use a quadtree (2D analogue of a octree) which should help demonstrate the concept. You might also find this page useful.

Answer 3

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.

Answer 4

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.