Hi, The world of the game I'm developping is large and very populated with agents. Therefor I have to do AI culling and only do precise pathfinding on the agents in my vicinity. At the moment any agent that is not in range is just not updated and not allowed to pathfind. The problem with this is that if you wait long enough nearly every agent on my screen walks away far enough to be AI culled and thus never returns. Another problem is that every agent is in the exact place I left him when I return which can look very unreal if a long time has passed since leaving. My question is does anyone have any good advice or articles on what to do with the agents that are AI culled to give a more real feel to the game? Greetings, Greever

Don't stop updating them entirely.

Quote: Original post by Kylotan
Don't stop updating them entirely.

The problem is I can't afford to update and pathfind every agent.
Running pathfinding on 1000+ agents would utterly destroy the framerate.
There has to be some form of AI culling to keep the framerate up.

Do not do each of the agents every frame,

Just update the ones in the vicinity, and the rest on a lesser rate

Pathfinding and actually moving are two separate deals. Agents that are not prioritized could for instance move in a straight line towards their target, ignoring colisions, something like that. Some agents might wait for a bit then teleport straight to their destination. What you're aiming for is a roughly correct end state, and you only want to pathfind when the agent is in proximity to the player.

You might look into hierarchical pathfinding. The map is divided up into small areas which are made into a coarser grained node network (similar to the tile network you already use with A*). NPCs that are outside of the full detail activation zone (not near players) move in jumps between these areas (and assumptions can be made that they wont be blocked by other NPCs). The processing for this can be run periodicly in the background to keep all your 100s/1000s NPCs moving in an abstract manner without taking up too much CPU.

Even when within the activation zone the area nodes can be used to simplify the tile-by-tile A* since paths to the next coarse area nodes center is much shorter in length ( later running pathfind again to the next coarse nodes center along the path to the final destination).

Agents don't need to be updated every frame. If you only update each AI every 0.25 or 0.5 seconds you won't really notice the difference from the player's perspective.

So the first thing you can do is timeslice: only update a hundred or so each frame.

The second thing is that no agent should _ever_ need to pathfind every frame. At most you pathfind once at the beginning of a move and not again until that move is done. Path following is separate from path finding.

The efficiency of path following is really a physics problem, not an AI problem since your locomotion should be seperate from your path finding: i.e. path finder finds a path locomotion system knows how to follow it.

But primarily this is an optimization problem: what is your desired framerate? let's say 30FPS. This gives you 33 milliseconds to update your entire frame (graphics, physics, user input, networking... everything.

What is the budget for your AI? Let's say 30% of your frame time. This gives you ~10 miliseconds for your AI. Now the next steps are:

1) profile your code and see what the average update time for a single unit is. Divide 10 by that number and you get the number of units you can update in a single frame and maintain framerate. (from there you can calculate how long it will be between updates for a unit; figure out if this is acceptible)

2) That number is going to be horrible because your code is probably very un-optimized. So the next step is profile your code and see where all the time is being spent.

3) now that you know where all the time is being spent for AI updating, change your algorithm to make it faster (make something that's O(n^2) into O(nlogn) or O(n) -> re-profile -> try changing algorithms again -> re-profile -> now start optimizing individual functions.

At some point you then have to start making decisions between fidelity and speed. If you can't cut fidelity but you can't make your code faster you have to cut the total number of units or raise your min-spec.

Certainly you can make things further away update less often. But they still need to update.

-me

Update them probabilistically. Create a probability function that takes the distance (or preferably squared distance) from the player, and will decide if the agent should be updated or not. You can factor in number of agents near the player, idle CPU time, etc.