I’m just getting started in UE4, so I apologize if this is a pretty obvious question, but my game has a large number of NPCs (numbering in the low hundreds) who need to do three things, even when the NPC isn’t around: 1) move around the map based on conditions I set in the AI, 2) Find interactable objects in the level (when the AI says they should go to work, they actually accomplish this by locating the computer/counter/cash register at their job and pathing to it), 3) Remain aware of what other NPCs are nearby.
It seems like the simplest way to do this would be to simply give the AI a “smart” AI for when the player can see them, and a “dumb” AI that is much more optimal and ticks much less frequently when the player isn’t nearby, or even used a centralized queue to manage when an AI ticks and prevent bottlenecks. However, this all hinges on how UE4 likes to optimize levels, and although I’m prototyping the whole game inside one building I’m eventually looking at simulating an entire city, which almost certainly means hyper-aggressive level streaming, which in turn means that 90% of the world geometry won’t exist for NPCs to query and pathfind through.
Is there an obvious solution to this issue, or am I looking at building a pretty complicated simulation to completely divorce NPC movement from level geometry?
There’s actually a pretty smart solution to this problem in a paper by Sunshine-Hill, who was one of Prof Norm Badlers PhD students and now works at Havok I believe. The paper is called “Perceptually realistic behavior through Alibi generation”.
The basic idea is that you simulate a whole bunch of agents in a full simulation mode. You gather statistics for what they do during the simulation. Then when you need them (i.e. you are close enough that they are needed) you spawn new agents and give them the statistical model of what they were doing. Think of it as generating a playbook and then playing from the playbook when you need the agent to be seen. The key is that they are “plausible” because they have that history encoded in the playbook.
I also like what terms the “simulation bubble”, its normally referred to as level of detail (or in this case behavioral level of detail) or LOD for short. I prefer the bubble term though
This pretty much gives you a good solution to the thing you are asking about (I believe).
This article is great, the math is way above my head but I’m pretty sure it solves 80% of the problem I’m having. I’m going for a really detailed open world feel (If you figure out that NPC Bob eats donuts every day, you can successfully enrage him by sneaking into his workplace and house and stealing every donut in sight), but that needs to involve an awful lot of cheating to keep from wasting computational resources on things the player can’t see. The idea about doing everything by probability is brilliant though- I could probably simplify this into math that even I can understand by just storing each NPC’s daily “schedule” as a flat percent chance of location by category: Ned the Diligent has an 85% chance of being at work from 8-5 and in bed from 10-7, while George the Disorganized only has a 60% chance of being at work at any given time. Whenever I path into a location (office buildings, seedy hotels) the engine could generate a list of occupants based on who has a high chance of being there.
The only challenge with this is consistency: the game involves an awful lot of the player following up on the alibis of specific NPCs and rewards them for discovering discrepancies (if Ned’s profile says he’s almost always at work, and you rarely find him there when you check up on him, that should suggest that you should investigate him further), so I’ll have to massage the numbers a lot to make sure this works. The only other problem I could see with this approach is getting everybody to move around correctly: if I know that Ned is going to walk from his office to the bus stop at 5:15pm, I should be able to run into him by standing on the sidewalk connecting the two locations, and with my variation on this idea there’s a nontrivial chance that he’ll just never appear, and I don’t want the player to notice that people are teleporting around.
You could get around that issue by having each agent have a probability for spawning into the sector your player is in based on their previous occupancy of that area. So if they use a route a lot, then statistically they will almost always be spawned in that area. Have a relatively sparse grid of spawns per agent subtype (so do it for specific types of agents and/or “specials” to save memory). The point about 's idea is that you know it is plausible because it encodes the history of activity in the alibi generated.
I guess it depends on how much memory you want to throw at it. You could store a localized grid per agent if you really wanted to (basically a “heat map” for the probability of spawning the agent for that grid cell).
Hmm, scalability is of semi-moderate concern, ideally I want this to work with 500 agents or 5,000, so I’ll see how far I can get with literally adopting 's method- if I’m lucky, history of activity should be more than enough- thank you again for the cite, this is proving to be really fun reading.
Oh, this is more of a minor technical quip, but does UE4 have anything already in the API that could be used for breaking levels into targets and portals programmatically, or would I be looking at having our level designer manually place them in the final level design?
Hey! here. Glad to hear you’re interested in my alibi generation stuff. The most approachable and up-to-date version of it is in an article in Game AI Pro. Shoot me an email if you have any questions, or if you’d like a draft of the Game AI Pro article.
I’m still drinking my coffee so I’m having problems wrapping my head around the paper, but the idea of LOD for AI is fascinating. , how would this work for large open spaces where the PC has an overview of the crowd? (Get them down from that viewpoint PDQ, I guess).
When you are looking from higher up, its probably not very noticeable what every single crowd member is doing, so long as the crowd is doing something “crowd like” then you should be fine. Its at the ground level where the plausibility becomes the most important. Bens solution provides a really efficient method of generating decent ground level character behavior on the fly, but because its based on simulated stats, you could adapt the same approach at any level of detail. So store the stats for a higher level viewpoint from the simulation (i.e. where the the agents go, what do they look at etc), as a set of probabilities, then make your agents follow the behavior with that same probability and it should be plausible from any viewpoint.
Crowd simulation is a pretty big research area. The guy who runs the lab went to, a guy called Prof Norman Badler has a whole bunch of papers on crowd simulation, along with his colleague Nuria? Pelechaud, so check out their work as well for more info. There are a few other labs working on crowd simulation, but I guess I’ve got a soft spot for Norm’s work because he seems to care a bit about games simulation qualities as well (i.e. he cares about animation and social dynamics and the like).
Good question! You run into this situation in games like GTA. Go up in a helicopter at night and look down, and you’ll see hundreds of little headlights streaming around, doing their thing. If you’re trying to do things perfectly this is a real problem, because pretty soon all of those anonymous cars are gonna need alibis.
In that situation, quantity is more important than quality. As a player, you’re not paying critical attention to all of those little dots simultaneously. This was where my later work on the “LOD Trader” came in… basically, the game realizing that it doesn’t have the computational resources to simulate all the characters simultaneously, so it drops the unimportant ones down in quality. The alibi stuff connects up with that, because generating and maintaining an alibi is more expensive than random wandering. (There was a different chapter in Game AI Pro on that. Alternatively, check out my thesis, which goes into both that and alibi generation [and some other stuff too]:
I was thinking of something like a shopping mall, where the people are just one flight of stairs away, and I should still be able to hear them talking. I guess I would have to obfuscate the view on the stairs for a few seconds, and start everything up properly while the NPCs are hidden from view.
The idea of “AI pop-up” fills me with dread. (A bit like that scene in Westworld, when they all shut down for the night. Or maybe Dark City?) That would reallly break the immersion.
