I’m working on a sandbox game that will ideally support several hundred NPCs. The entire game takes place in a single skyscraper, so every NPC is theoretically reachable with a minute or two of walking and elevator-button pounding, but there shouldn’t be any context in which more than 20-30 NPCs are at close range and potentially observable at any one time.
The way I do it right now, every NPC is always on: they always use complicated pathfinding, very intelligent AIs, and generally act in as realistic a manner as I can program them. Now, I know that optimizing early can be counterproductive and extremely time-wasting, but at the same time I know that a lot of sandbox-y games turn off nearly everything that isn’t around you, and store just enough data to convincingly pretend that NPCs you come upon have been there all along, and weren’t instantiated 15 seconds ago as you drew near.
To that end is it even worth my time working out some AI equivalent of level of detail now, or should I just leave everybody running more computationally expensive AI until I’m feature-complete and ready to start optimizing everything at once?
On a related note, is there a known best-practice to work out where AIs are supposed to be, so one can turn them off until the PC approaches the region they’re supposed to be in? Because I worked out an easy system to teleport everyone outside of view to their destination, which significantly reduces the amount of pathfinding they need to do, but it makes the building very spooky because the PC never finds natural foot traffic when he goes for a walk in the halls, as every NPC out of eyeshot have teleported directly to their office and skipped the footpaths.
optimizing all your code is harder to do than optimizing sections at a time.
I would advise doing most of it during development. Sometimes optimizing can lead to architectural changes, which if you’re doing it at the end, can be much harder to wind through your code.
Hmm okay, thanks for the clarification… not to ask the obvious, but is there a standard metric or guideline regarding when to optimize? Because I’m not getting performance drops, and from a design standpoint the easiest thing to do with my AI is to leave it unchanged, but the words “500 NPCs conducting pathfinding outside of visual range” kind of makes me twitch.
Part of the question is - when exactly are they conducting pathfinding?
One easy way to deal with performance in large amounts of processing is to break the process up and spread it out. A nice, easy example of this would be to run ai logic as a coroutine or invoked process that runs each agent in sequence, spreading out the agent calculations evenly.
Once you have something like that - it’s also fairly easy to prioritize those agents - you could do this by giving a higher priority to agents closer to the player. So agents in visual range would update their goals more frequently.
I don’t know if I’d call that kind of process an optimization even, or architecture. It’s really just another design decision: “how does the AI work?”.
If you’re doing some kind of goal update triggering system - where the agent only decides to update his goals upon some trigger condition - then the key thing to concern yourself with is making sure many of them don’t all want to update at the exact same time (resulting in frame loss as you crunch hundreds of guys at once). But this is really solved by the same as the above - dump the guys needing an update into the processing queue and spread out the load.
In terms of really hardcore optimization - it depends on the project and the needs. The more that performance and large scale processing is at the heart of a project - the more attention optimization needs. If it needs to be done early or late really depends on how central it is to successfully completing the project.
Good comments so far. I want to add that there are really two kinds of optimization: efficient design and code optimization.
Efficient design includes things like deciding to use level-of-detail, trigger systems, and implementing a processing queue like frosted suggests. Do this early on, but make it as modular as possible so you can swap out one approach for another if you need to later.
Code optimization includes things like unrolling loops. Do this last, if at all. Efficient design almost always trumps code optimization. Instead of coding faster pathfinding for 500 characters, isn’t it better to skip pathfinding altogether for 480 of them? At the very least, it’ll make you twitch less.
You could use multiple levels of detail, not just on/off, perhaps on a floor-by-floor basis. On the player’s floor, give each NPC all the processing it needs. Maybe NPCs in critical situations (such as combat or direct interaction with the player) could get more CPU time. If you run the NPC’s AI in a coroutine, between AI updates you could yield for a duration that depends on the criticality of the situation. For example, if the player is just wandering about, yield for 0.5 seconds between AI updates. But if the player is in combat, yield for 0.1 seconds. This way, NPCs in combat will get 5x as much attention.
On the floors above and below, the NPCs could use a completely different AI, perhaps teleporting to waypoints that are on the way to their goal positions over an appropriate amount of time. This way, they won’t immediately teleport all the way to the goal position.
On the remaining floors, maybe give the NPCs one move every 60 seconds or so, maybe adjusting that duration by a small random amount to help spread out the workload. Or, instead of staggering with the random time offset, you could tie this into a processing queue by setting their queue priority lower.
This is incredibly useful, thank you guys! To clarify, I’m using a utility-based AI, not unlike what the original Sims did. Each NPC has an hour-by-hour schedule that shows what his boss wants him to do, and in addition he has a set of variables for hunger, bladder fullness, stress, and so forth. It runs in a coroutine, so right now each AI evaluates its utility variables once per second, and decides whether to keep working on its current task or change states to find a sandwich, a bathroom, or another employee to be passive-aggressive at until his stress reduces.
I’m fairly sure that the decisionmaking portion is pretty fast, all it does is refer to a cached reference to the class that holds my utility variables and find the highest number. Everything else that the AI is capable of doing is contained in items- when they decide to do some work their FSM only instructs them to pathfind to their desk and message it, and it’s code living in the desk itself which runs the sittting & typing animations and slowly ticks up their stress until they go nuts and take a break.
What I’m worried about is the pathfinding code: it’s quite fast, I’m using A* Pathfinding Project and his stuff is really amazingly well-optimized. It’s configured to stop searching nodes when it reaches it’s destination, so I know nobody is evaluating nodes once they get in position, but I still have a lot of NPCs many floors down or up from the PC manually navigating to their objective when there’s nobody there to watch.
Based on everyone’s comments I’m assuming the simplest way to optimize things would be to teleport any NPC a certain distance or number of floors away from the PC directly to their location, so they skipped pathfinding entirely and only ran a very low-resource FSM to evaluate their behavior and adjust their statistics correctly. That’s easy to do, and I actually have a simple version of this written, but where I’m stumbling a bit is on how to simulate traffic: the player is intended to spend a fair amount of time running around the building and keeping track of which NPCs are where, and teleporting people around will both make the building a bit of ghost town, as most NPCs will teleport from ahead of the PC to behind him or vice-versa before he’s close enough to turn on their pathfinding.
Personally, I wouldn’t do the teleporting. I’d just do the queues. You run a maximum of one path finding execution per frame and you’re pretty much good to go. If you’re running at 60 fps, you will run through re-pathing all 500 character in under 10 seconds. The advantage here is that you have a consistent performance profile that you can work with under guaranteed parameters. I’ve seen a lot of well written games have problems due to running different modes like this - where guys end up inappropriately teleporting - better to have a single logical process to worry about than multiple wherein results fail to match up.
I agree with frosted that teleporting directly to location may cause problems, or at least confuse the player. Test it out; if you have the CPU luxury to pathfind all NPCs, keep it simple and do it. You might even implement level of detail by putting closer NPCs higher in the queue. Even if this means distant NPCs take, say, 60 seconds or more to get their paths, the player won’t notice, and you’ll free up more CPU.
If you don’t have the CPU budget even after prioritizing the queue, then consider the minimum amount of work required to produce the required effect. If the player will notice NPCs teleporting directly to their destinations, maybe you can teleport them over time to consecutive rooms on their way to their destination. This would use a very simple waypoint table that’s much less CPU-intensive than A*. It’s more code to maintain though, as frosted warns.
Side note: Coincidentally, I’m finishing up a utility-based AI system myself. The AIs also use coroutines, and the frequency of updates is dependent on distance from the player. This has worked out pretty well. Proximity-based level of detail has been a good way to keep CPU utilization really low.
My takeaway is that deciding to implement a concept of level-of-detail may be helpful, and it’s something that you should consider adding early on. But keep the implementation modular and decoupled so it’s easy to swap out one form of level-of-detail (e.g., priority queue) for another (e.g., waypoints instead of A*).
Oh hey, running pathfinding in a processing queue with level of detail is a great idea. I’m not running into problems with CPU budget right now, but I know graphics and an increasingly rich feature set are eventually going to start eating everything in sight, so I wanted to make sure that I wasn’t being incredibly dumb in how I was going about things.
This is only marginally related, but on the topic of spreading the load out, one awesome if somewhat primitive trick I’ve found works wonders is to set each AI’s tickrate equal to your desired rate plus a random number of milliseconds between, say, 0-500; when you’re dealing with hundreds of actors, that alone makes it way easier to avoid framedrop.
That’d work. It’s a little fugly, but it’d work. The queue is cleaner (and actually really easy to set up if you give it an hour!).
The real thing you want to avoid is having many things all happening at the same time. So let’s say you want to have a huge explosion that blows up a floor. When this happens you want like 100 guys to re-path. That’s the point where you’re going to lose frames. You want to look for ways to control the peaks - those are the times that count.
