Efficient way to build movement schedule for large number of NPCs

My game has approximately 400-600 NPCs in the world at any given time, and among that number less than 20 are usually rendered in-game and running their complicated AI. The rest of the time they only live in my simulator, and I'm realizing that the only thing I really need to track in real time is where in the game world they reside. I already have a Room class that I can assign them to, and once assigned they'll spawn automatically when the physical geometry that Room is hooked to renders. The real challenge is figuring out the logic behind moving them from place-place.

Ideally, I would like to be able to give each NPC a Schedule class that specifies which room they need to be in at what time: instead of delineating every minute of every hour, simply give them a handful of objectives, something like "At 9am, be in <Office>, at 1pm be in <Lunch room>, at 2pm be in <Office>, at 8pm be in <Home>". However, this seems to leave a big problem: how on earth do you ensure that each NPC moves to the correct room at the correct time without manually checking all 600 schedules every tick?

 

Consider each of those schedule entries an "event", i.e., something that should happen at a specific type. Put them into one big list, sorted by time. Now you've made an event queue — on each tick, you only need to check the front of this list, and bail out as soon as you get to any event whose time has not yet come.

When you process an event, move the NPC, and then check their schedule to see what their next event (movement) should be, and insert that into the queue (keeping it sorted by time).

 

OOooh this sounds kind of fun.

I'm going to suggest something to you that was a similar suggestion to a problem I proposed a while ago, because I feel like it's fundamentally the same thing.

Create a master AI Ordered list, which contains in order of time, all of the planned orders for all meta (or simulated, whatever you call them) NPCs. Then you only have to check the entries in that list for every tick, and you'll only have to check them until the sorted time. Quick and dirty example:

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4.  
5. public class AIMasterController : MonoBehaviour { // This would be a pseudo singleton
6.  
7.     public class Command {
8.  
9.         public readonly int room;
10.         public readonly AI ai;
11.         public readonly float time;
12.  
13.         public Command (int room, string ai_name, float time) {
14.             this.room = room;
15.             this.ai = new AI(ai_name);
16.             this.time = time;
17.         }
18.  
19.     }
20.  
21.     public class AI {
22.  
23.         public static List<AI> every = new List<AI>();
24.  
25.         public readonly string name;
26.         public int room;
27.  
28.         public AI(string name) {
29.             this.name = name;
30.             this.room = 0;
31.             every.Add (this);
32.         }
33.  
34.  
35.     }
36.  
37.     static List<Command> commands;
38.  
39.     void Start() {
40.  
41.         commands = CreateCommands();
42.  
43.     }
44.  
45.     void Update() {
46.  
47.         int numberFinishedCommands = 0;
48.         for (int i = 0; i < commands.Count; i++) {
49.  
50.             //If the first command in the list hasn't happened yet, none of the other ones have either, and we're out.
51.             Command command = commands [i];
52.             if (command.time > Time.time)
53.                 break;
54.  
55.             Debug.Log (command.ai.name + " is moving to room " + command.room + " at time " + Time.time);
56.             command.ai.room = command.room;
57.             numberFinishedCommands++;
58.  
59.         }
60.  
61.         if (numberFinishedCommands > 0)
62.             commands.RemoveRange(0, numberFinishedCommands);
63.  
64.         if (commands.Count == 0)
65.             ReportAILocations();
66.  
67.     }
68.  
69.     public void ReportAILocations() {
70.  
71.         foreach(AI ai in AI.every) {
72.             Debug.Log (ai+" is in room "+ai.room);
73.         }
74.  
75.     }
76.  
77.     List<Command> CreateCommands() {
78.         List<Command> commands = new List<Command>();
79.  
80.         //Create random initial commands for 1000 ais
81.         for (var i = 0; i < 1000; i ++) {
82.  
83.             float new_time = Random.Range(1f, 60f);
84.             int new_room = Random.Range (0, 10);
85.  
86.             commands.Add (new Command(new_room, "Robot number "+i, new_time));
87.  
88.         }
89.  
90.         //Sort the list by time
91.         commands.Sort((Command c1, Command c2)  => c1.time.CompareTo(c2.time));
92.  
93.         return commands;
94.  
95.     }
96.  
97.  
98. }
99.  

Just create a new scene and put this script on the camera.

 

Oh that's a great idea, I hadn't considered using a global queue like that! Are you thinking that each AI would be in charge of curating its own commands and sending those to the AIMasterController, or would the controller be the sole source of command logic? The latter sounds like it could actually simplify things a lot- maybe just make an enum for each NPC's job (Cops and Bakers get to work earlier than Officeworkers), and give AIMasterController a template for what each job's hours look like that it could fudge by a few random minutes each day to add more variability.

Two things occur to me:

1) How do you make the list flexible enough to handle player hijinks? If I run into a room, kick an NPC really hard in the shins, then run away, he shouldn't just go back to work when I leave- he should go to the doctor, or go home and complain to his friends, or whatever other responses I code in. I absolutely love the idea of generating a global schedule far in advance of when we need it, but it'd have to be mutable enough to let the world change in response to what the player is doing.

2) In the same vein, do you see an easy way to make commands overrideable? One of the ways I preserve the feeling of a natural world is by peppering the NPC pool with random events, things like getting a cold or skipping work to go to a party. In simulation terms this is mainly reflected by their deviating from their planned schedule and going to Bob's Watering Hole at 9am instead of Soul Crushers Office Inc, so I wouldn't want their normal schedule fighting for priority with the random event.

 

I would set it up so the AIMasterController makes all of the commands, and each individual AIInstance carries out those commands. The AIMasterController could of course, then, dictate and create those commands based on information held in the AIInstance. (Like in your example, weather it's a baker, robber, what time it is, if it's just been attacked, etcetera).

I'm imagining a couple of options and I'm not sure which I like more than the other. I'd have the Master be in charge of checking AI flags and building order queues as they change. So that if the AI encounters an event that interrupts it's idleQueue, it would set a flag and be added to a list for the master to deal with in it's update loop.

Yes! In the previous example, in the MasterAI's update loop, it would check the AI that had been attacked.
Say the ai was badly hurt in the attack. It would clear all of that AI's idle commands, and set a list of queues for it to deal with it's situation. 1) Exit building 2) Enter Cab 3) Goto Hospital, ect.

Once the situation is dealt with (Healed at Hospital), the masterAI would rebuild it's idle commands: 1) Enter Cab 2) Go home 3) Sleep

 

Ooh this is neat, I'll have to think about how I want to actually decide how the AI handles each situation, but this might be a really neat opportunity to learn how to use STRIPS planning: the AI isn't going to have that many mutable states, so it might be neat to simply teach it 20-30 command verbs and use STRIPS or a simpler automated planning algorithm to assemble a list of commands.

I'm picturing the AI Master curating one huge list with 4,000-5,000 commands reflecting every AI's every planned action throughout the day sorted by time, does that sound accurate? Because I love the idea of giving the AI the utility to clear and rebuild its command queue based on novel input, and that could even be useful for error trapping if the AI somehow gets somewhere weird and doesn't know what to do, but if one AI has, say, 10 commands spread through those 5,000 indexes, how would you cleanly find and remove his queue and re-add the new one without ruining the sort?

 

I imagine the AI could have a list of it's own commands for this:

• Master AI encounters AI that needs a new commandQueue
• Master AI checks every command in the AI's local list and destroys them or sets "ignore = true" or whatever
  
• Master AI rebuilds the ai's new command queue, adds the entries to it's own time sorted list and replaces the ai's local list.

Otherwise you'd have to check each entry in the MasterAI's list and remove them, which would be inefficient and undesirable.

 

How would you accomplish that without having to re-sort the list though? Say it's 3:30 and the AI gets a new command queue with commands at 9am, 1pm, 5pm: is there a quick way to insert them into the list based on time? I was under the impression that I would have to List.Add(newCommands) and then do another commands.Sort() to ensure that the 5pm command was nestled among all of the other 5pm commands.

 

Goodness, no, don't do that. Insert them in the proper places (via List.Insert) to begin with. You can find the correct insertion point via a binary search if you want to get fancy, though in fact, a simple sequential search would probably be good enough unless you're doing this a whole lot every frame.

Or better yet, use the SortedList class, which does all this for you!

 

Oh hey, so I just discovered a new piece of awesomeness, I had no clue that SortedList was even a thing!

Are you thinking that the TKey would be the time each Command executes (which I've been expressing as Hour + Minute, but could easily be a single float), and TValue would be the actual Command?

 

Yep, that's the idea exactly.

 

Personally, I wouldn't have a master list thingy. I'd have a Scheduler component on each NPC that managed the NPC's schedule. Then, have each scheduled event as a component representing a scheduled command with a desired start time, end time, and priority that can be set. The component registers itself with the scheduler, which then calls the component to do its task (say, go here and do this animation for x minutes) when the time comes.

This kind of system has a number of advantages. You can use priority to handle conflicting schedules, it's flexible enough to allow you to add new scheduled events without modifying existing code, you can put together random schedules on the fly.

 

That's an interesting idea, and I think I'm gradually heading toward a hybrid between this and the large list. One of the big challenges with my structure is that most characters don't exist: the only part of a spawned NPC that persists after they despawn is their CharacterRecord, which is a data storage class which holds their name, their job, and so forth, and goes to live inside my simulator class when its character isn't active in the world.

My big logic for leaning more towards the list than individual management is efficiency, as when hundreds of NPCs are all asking for attention at once it's much easier to direct traffic and prevent spikes/lag if there is a single point for all schedule-related hijinks to go through.

Priority is a really big concern though, and it's still something that I haven't fully reconciled in my head. The way I think I'm going to structure this, there will be a "default" schedule for each NPC based on their occupation, which handles waking up, going to work, and finishing work, and then each CharacterRecord will have a list of Commands for their unique needs that get priority over their default schedule.

I'm assuming that the best place to handle the clash would be in the AIMaster function that takes a CharacterRecord as an argument and returns a list of Commands to be shuffled into the master list. If I give each Command some int priority, set 0 as default (everything can override), and give emergent commands increasing priority values based on urgency, I would be able to see which events should get precedence, but that leaves a big organizational issue: how would I actually go about identifying conflicting commands? Identical TKeys is one thing, but I'm imagining most scenarios would involve partial overlap, not complete: if 0 is midnight and 23.9 is 11:59pm, Command work with priority 0 might start at 9 and end at 18, and Command burglary with priority 1 might start at 12 and end at 1. The behavior we would want would be for the NPC to execute work until 12, switch to burglary until 1, then switch back to work, but if we're issuing commands by iterating through a master list work can't be re-considered after burglary ends, as it's already behind GameClock.Time in the schedule stack.

 

As far as efficiency goes, your large list is going to be less efficient overall than a more distributed system. Solving the problem of lag spikes is something you'll have to deal with either way. A single controller dealing with the scheduling and control of hundreds of characters is going to eat a lot of cycles at regular intervals. A more distributed approach can actually alleviate this problem, since you don't have all the processing occuring at once. There are certainly ways to prevent, say, too many characters trying to process schedules at once.

As far as dealing with overlap, with start and end times and priority, no problem. You just check each scheduled event to see if there's overlap with the scheduled event after it, and if there is, make a decision based on priority. For extra credit, you could mark events as resumable or not, so the character can know whether to say, go back to low priority cleaning after a high priority bathroom break.

 

I definitely see the logic here, but implementing it might necessitate some fairly big changes to how the simulation works: right now NPCs in the simulation don't have their own agency or any moving parts: the NPC class is just a collection of data (name, job, vital statistics) curated by the simulator, and because I'm going to be working with hundreds of them I tried to keep the class as compact as possible. Since individual NPCs aren't "awake" until they spawn and get a much more complicated AI, most of their behavior is governed by the simulator iterating through them one by one, checking flags/states, and moving parts around.

While we're on the topic though, is that a reasonably optimal way of curating lots and lots of characters? Another option would be to completely abandon the simple NPC in simulator/complex NPC rendered in-game dichotomy and simply create a permanent gameobject for each NPC, load it with behavioral scripts and so forth, and have it manage its own behavior completely independent of a central controller class, and just wait to switch its model, pathfinding, and physics on until the player is within view, but I considered and initially discarded that approach as being too resource-intensive, as I don't like the idea of doing a lot of computational work that the player will never see.

 

We may be picturing different things, but as I'm picturing it, I can't agree. A global event queue is the most efficient way to process a bunch of events spaced out in time. On each tick, you have just one place that says "Is it time for anybody to do something?" This is dramatically more efficient than having dozens, hundreds, or thousands of scripts saying "Is it time for me to do something?"

Of course when something does happen, then it makes perfect sense to pass the actual handling of that off to nice encapsulated objects with their own data. Usually, the handling will involve updating that data, and then inserting a new event into the global event queue (or sometimes, removing previous entries from that queue). Insertion into a sorted list is extremely fast; removal may or may not be, depending on how you do it. (The best is to remember the key (time) of the next event you had scheduled, so you can remove it by key.)

This is the way events are handled in any big simulation system. The alternative amounts to a polling system, where all the objects are constantly saying, "Time to do something? Nope. Time to do something? Nope." ...Very inefficient.

But again, it's entirely possible that I'm misunderstanding what you were proposing.

 

As a side note, a much less articulate form of that reasoning is what caused me to eventually side with running this as a large simulation instead of a distributed system. There are a lot of finicky things like the priority queue and getting the simulator's locations to cleanly match up with the level geometry with a minimum of manual tinkering, but unless my understanding is wrong, I'm fairly sure the central simulator buys me a heck of a lot more flexibility in the long run than distributed guys would.

 

Sorry, wasn't on here for a couplea days.

I definitely think a global event queue is necessary, but that's something that should be as de-coupled as possible from the events and characters themselves. I'd personally just have a dictionary of times and Action objects that wouldn't even be aware of anything other than calling scheduled methods at scheduled times. I wasn't really thinking in terms of the event queue when I said distributed, though.

As far as determining schedule and dealing with conflicts, that's best done in a distributed fashion, rather than having any kind of "master list". Each NPC should be able to handle their own scheduling logic, including resolving conflicts. This makes it a piece of cake for dealing with, say, pursuing the player and resuming an activity afterward. The queue doesn't make it any less distributed, it just saves some cpu cycles by dealing with time-based scheduling.

 

The decoupling is a good point, so am I correct that what you're thinking of is something like:

a) Every day at midnight (or whenever) every NPC is notified to assemble a list of every action they need to take for the next 24 hours- conflicts are resolved in this stage, and they output to the scheduler a list of actions, which they have already sanitized to ensure that no two actions conflict (e.g. priority)
b) Every timstep (which in my case will be the incrementing of the gameClock.time by one in-game minute) the scheduler checks its Dictionary<time, action> against gameClock.time and executes any actions filed under the current minute's key
c) If emergent behavior/player actions require new events to be added, the NPC whose behavior has to change is notified to strip his actions out of the dictionary, re-evaluate his action queue (and in so doing, evaluate any conflicts the new behavior has with existing behavior), then hands the scheduler a new list of actions.

I think this is pretty pleasingly simple, but assuming I'm not completely mis-interpreting what you gentlemen have suggested, I have two quick questions:

1) How does filing multiple TValues under the same TKey work? Do I need to do something like making each entry a single <Time,List<Action> actionList>, or can I just file multiple single actions under the same key and expect that InvokeAction(actionDictionary[gameclock.Time]) will notify every Action filed with the current time as its key?

2) If I'm trying to keep this as decoupled as possible, what's the cleanest way to handle passing actions back to NPCs at the right time? Something like this?

Code (csharp):

1. class NPC{
2.  
3. Action currentAction;
4.  
5. void updateAction(Action passedValue){
6. currentAction = passedValue;
7. }
8. }
9.  
10. class Action{
11. NPC myOwner;
12.  
13. InvokeAction(){
14. myOwner.updateAction(this)
15. }
16. }
17.  

Assuming the action itself is what notifies the NPC, that actually introduces a slightly clunky but simple way to manage priorities: give each Action some int priority, and when an action invokes itself it checks if the player currently has an action, and if they don't it will only apply if its priority is higher than the current action, otherwise it either self-terminates or just sits inert in the queue. Leaving it inert would handle cases where a low priority action occurs from 4:30-5:30, a high-priority one occurs 4-5, and we want the NPC to do his high-priority action until 5, then shift to the low-priority one.

I'm a bit fuzzy on the logic of making overlapping actions work... what if, assuming every action has a start and an end time, if an action is completed and no new action exists to take its place the NPC checks the end time of its last action (before the current one), and returns to it if that action's end time is still > gameClock.Time? It's kind of clunky, but I think it could work- fringe cases (like one task ending at 4:55 and a new one starting at 5:00) could be handled by defaulting to a very low-priority action like Wander that could be overridden by anything else in the queue.

 

I'll pop by tomorrow with a functional example of how I'd do it. You have the basic gist, but some of the finer details will be better shown in code. Plus, it's code I need to do anyway for my own projects.

 

Sorry, forgot the weekend was coming, but threw it together today. Attached is a sample project. The code is documented, but mostly I rely on self-commenting code, so let me know if there's anything in particular you have questions about. It goes without saying that this code hasn't been bug tested in any real way.

It was a little different in implementation from the way I was thinking. For example, I used a List instead of a Dictionary, but mostly it works as I was trying to state.

The NPCs are represented as cubes. There are 400 of them in the scene, each with two alternating events that move them from place to place, switching out every 20 seconds. The second event is actually triggered while the first one is still being acted out, and is placed in the queue. 400 actual NPCs would actually be triggering new events far less than every 20 seconds, so this is even more of a stress test than it might seem.

Enjoy!

 

Just a thought, it'd take much more time to create, but would theoretically be less stress:

You could concatenate the times and locations into two 400 length int lists that represent the schedules of each NPC.
Check only the integer values of those arrays, and set up a complex system of delegates to handle the permutations.

Then it would only be checking two values before executing the appropriate "events."

Haven't had a chance to check out the code, just thought it was an interesting problem.