[Programming] NPC schedule across maps

[Nash]

Programming discussion. How do you think games like Oblivion/Fallout 3/Skyrim handle NPCs that correctly run their schedules across non-seamless maps?

And then there's also the issue of time compression. Let's say the player presses the "wait" key in a tavern. He waits untl 8 PM. Suddenly the tavern is filled with people all having a drink. So how does the game handle what happened during the time the player waited?

Another example is: an NPC is scheduled to get up at 8 AM (from his house, a separate map) and walk to the library at 10 AM (another separate map). A lazy way would be to just despawn the NPC from every other map except the library at 10 AM but that doesn't look good. A better way would be to have the NPC actually path to (walk to) the library. So what if the player isn't there to watch the NPC walk to the library? Let's say he was exploring a dungeon. Is the game simulating the NPC's walk path offscreen/internally, and when the player goes back to the map where he could visibly see the NPC walk... somehow figure out where to place the NPC in his walking state/path depending on time of day?

I hope I didn't make this post too confusing haha.

[GooberMan]

There's absolutely no need to simulate what you can't see/interact with in a reasonable timeframe in the same manner that you simulate the part of the game that you actively interact with. If an NPC has to keep to the schedule, then you just design the schedule accordingly. Taking the NPC going to the library example, you wouldn't schedule it to just magically appear at the library at 10AM. If the library exterior is loaded, the scheduler would simply spawn him at 9:55AM within 5 minutes walking distance from the library.

It does mean you need a persistent state block in memory (just like Hexen world variables for example), but that's the price you pay.

The tavern example also lends heavily in to what I just suggested - check the scheduler for who's meant to be where at 8PM, then move them all there. Simulating what happens in between isn't necessary.

[TheFortuneTeller]

GooberMan sounds like he knows what he's talking about.

[Nash]

Hmm... just had a thought. I think this would require every single NPC to have a unique allocation in a global array or something and the code has to loop through every single NPC to evaluate what they should be doing based on the time of the day and what "schedule packages" they have on them... is this the right way of thinking?

[Gez]

You could take a look at Exult's source code, since Ultima 7 does have NPC schedules.

[GooberMan]

I think this would require every single NPC to have a unique allocation in a global array or something and the code has to loop through every single NPC to evaluate what they should be doing based on the time of the day and what "schedule packages" they have on them

Loop? What is this, the dark ages? Event-based programming is far more efficient there. The 9:55AM event fires off at 9:55AM only, and puts the NPC in the right place because it's subscribed to 9:55AM on that particular map.

But yes, if you want your NPCs to be persistent, they need some kind of global data. The same data would get jammed in to save states.

[Mr. Tee]

I think this would require every single NPC to have a unique allocation in a global array or something and the code has to loop through every single NPC to evaluate what they should be doing based on the time of the day and what "schedule packages" they have on them

Loop? What is this, the dark ages? Event-based programming is far more efficient there. The 9:55AM event fires off at 9:55AM only, and puts the NPC in the right place because it's subscribed to 9:55AM on that particular map.

Question: Would this event based programming require some kind of loop anyway? There has to be a script somewhere that continuously checks the current in-game time, and verifies this against a table of NPC time-scheduled events to see if one should fire...

I haven't had to program anything in about 2 years or so, thus I might be wrong but this is my current thinking.

[GooberMan]

The code would be something like:

Code: Select all

int timeOrdinal = getTimeOfDayOrdinal();
if (!events[timeOrdinal].empty())
{
  events[timeOrdinal].trigger();
}

The only loops in there are the main update loop, and the loop that parses over each event in that trigger call. Quite far away from looping over every entity in the world to see what it should be doing. Events there can either be a brute force array (1440 elements, ergh), or optimised down with a hash map or something similar so it only cares about what times of day actually have events (the if check would need to be modified in such a case to check if the time of day exists in the map, which if you're using a hash map won't actually do a loop).

[Kinsie]

How do you think games like Oblivion/Fallout 3/Skyrim handle NPCs that correctly run their schedules across non-seamless maps?

By using an engine that actually has a concept of NPC schedules.

[Xaser]

How do you think games like Oblivion/Fallout 3/Skyrim handle NPCs that correctly run their schedules across non-seamless maps?

By using an engine that actually has a concept of NPC schedules.

This is a bit like responding to "How do I cook good spaghetti?" with "Go to an Italian restaurant."

[Nash]

Eh, it's all good, I have a pretty solid idea on how to go about it already... just need to get my ass to coding it...

[carlcyber]

As GooberMan's suggest, this can be something like...

Code: Select all

Script "EventLoop" (void)
{
    switch (date)
    {
    case 20130318:
        switch (time)
        {
        case 0800:
            JackSowsBeans();
            break;
        case 1500:
            ZackStealsBeans();
            break;
        ...
        }
    case 20130319:
        switch (time)
        {
        case 0800:
            JackSowsBeansAgain();
            break;
        ...
        }
    ...
    }
    Delay(1);
    restart;
}

By this code, you don't have to worry about the complexity growing with the number of NPCs.

[GooberMan]

That's not really at all what I suggested. In fact, that's the brute force way of doing it.

Code: Select all

#define SECONDS_IN_DAY 1440
#define TICS_PER_MINUTE 140
#define MAX_EVENTS 16

str eventCallbacks[SECONDS_IN_DAY][MAX_EVENTS];
int eventCount[SECONDS_IN_DAY];

int timeOfDay = 0;
int currentTics = 0;

function void TriggerEvent(int ordinal)
{
  for(int eventNum = 0; eventNum < eventCount[ordinal]; ++eventNum)
  {
    ACS_NamedExecute(eventCallbacks[ordinal][eventNum], 0, ordinal);
  }
}

function void SubscribeEvent(str scriptName, int ordinal)
{
  if (eventCount[ordinal] < MAX_EVENTS)
  {
    eventCallbacks[ordinal][eventCount[ordinal]] = scriptName;
    ++eventCount[ordinal];
  }
}

function void UnsubscribeEvent(str scriptName, int ordinal)
{
  for (int eventNum = 0; eventNum < eventCount[ordinal]; ++eventNum)
  {
    if (eventCallbacks[ordinal][eventNum] == scriptName)
    {
      --eventCount[ordinal];
      eventCallbacks[ordinal] = eventCallbacks[eventCount[ordinal]];
      return;
    }
  }
}

function int GenerateTimeOrdinal(int hour, int minute)
{
  return hour * 60 + minute;
}

function int GetCurrentTimeOrdinal(void)
{
  return timeOfDay;
}

function void UpdateTime(void)
{
  if (++currentTics >= TICS_PER_MINUTE)
  {
    currentTics = 0;
    if (++timeOfDay >= SECONDS_IN_DAY)
    {
      timeOfDay = 0;
    }
    
    TriggerEvent(timeOfDay);  
  }
}

bool beansSowed = false;

script "JackSowsBeans" (int ordinal)
{
  if (!beansSowed)
    beansSowed = true;
}

script "ZackStealsBeans" (int ordinal)
{
  if (beansSowed)
  {
    beansSowed = false;
    UnsubscribeEvent("ZackStealsBeans", ordinal);
  }
}

function void InitLevel (void)
{
  SubscribeEvent("JackSowsBeans", GenerateTimeOrdinal(8, 0));
  SubscribeEvent("ZackStealsBeans", GenerateTimeOrdinal(15, 0)))
}

script "LevelState" open
{
  InitLevel();
  
  while (true)
  {
    UpdateTime();
    // Do other level stuff
    Delay(1);
  }
}

I haven't compiled that in ACS, so it may need some bug fixing. (EDIT: In fact, there's a bug in unsubscribing while you're in the middle of a triggered event - see if you can spot it). But that's exactly what I'm getting at: a generic system that doesn't require complex loops or switch statements. You subscribe to a time of day, unsubscribe if you're done, and everything just magically works. Being event based, there is no complex additional logic required at any point in time, thus generating far more efficient code than brute force loops and switch statements can provide.

Notice I've left a date out of it. There's two questions to ask there: Are dates really necessary? If so, is it worth expanding your event array there to handle seven days a week, or would you find it easier to put an end of day event in that reschedules an NPC according to the next day?

[Kinsie]

How do you think games like Oblivion/Fallout 3/Skyrim handle NPCs that correctly run their schedules across non-seamless maps?

By using an engine that actually has a concept of NPC schedules.

This is a bit like responding to "How do I cook good spaghetti?" with "Go to an Italian restaurant."

Kind of a good analogy considering I'm so bad at cooking I burn cereal.