Time for Action: Time and Action Management + Fast-Forward

Handling time is coupled with handling actions: The whole point of time management is handling the order of actions. I’ve done some … pre-work in the past here, so many of the concepts still apply. So:

Actions and commands

  • A EntityCommand is the basic “unit” of actions: it’s an instruction for an entity to do something, e.g. “move left in a dungeon”, “teleport there”, “Do damage to X entity”, “move north in overworld”
    • Commands happen instantly, they do not know anything about time/duration.
    • Implementation-wise, commands are stateless functors, that take a bunch of parameters and do some work. In the future, the implementation could be moved into Lua to avoid recompiles and have dynamically editable behavior
    • Commands have two functions: Execute() and OnInterrupt(). If a command that is scheduled to play gets interrupted, we call OnInterrupt instead.
  • An EntityActionConfig stores a handle to a command plus timing and interrupt information: execution/recovery durations and interrupt strength/difficulty class
    • An action happens like this:
      • Wait for execution duration (during this stage, the action can be interrupted)
      • Execute EntityCommand immediately
      • Wait for recovery duration
    • An action can interrupt another action if the interruption strength is greater than the interruption difficulty class. In this case, the execution stage of the target is cancelled and replaced with an “interrupt recovery” duration, which at the moment is half the execution duration, starting from the time of interruption.
    • EntityActionConfigs are set up in json, and are constant throughout the application.
  • An EntityActionData structure stores a handle to an EntityActionConfig plus parameters for the command to be executed.

Time system

At this point, we move onto the TimeSystem, which handles execution of actions. The TimeSystem stores a set of actions, ordered by execution time. The set data contains:

  • The entity whose turn it is
  • The time that the entity plays
  • The stage of the entity’s action (just started, execution, recovery, interrupt recovery)
  • An EntityActionData structure, storing what needs to be done with what parameters
  • A reference to the previous entry in the set, of the same entity (e.g. a “recovery” entry would store the “execute” entry)

When an AI entity plays its turn, there are two different things that can happen:

  • We don’t have an action scheduled yet, so we run AI to figure out what to do next. The AI system is responsible for filling out the EntityActionData structure (what action to execute, and which parameters). A player character, using GUI/keys would cause this structure to be filled in the same way. When we fill in the data, we schedule the execution stage which will happen after the “execute duration” if it’s not interrupted
  • We have an action scheduled, so we just execute the command and scheduled the next turn to be after the “recovery duration”. If the command fails (e.g. try to hit an entity that is now not there) we should not pay the normal recovery duration. At the moment the cost is half the recovery duration, but maybe for a failed command the cost should be zero. This is still work in progress and needs real examples (e.g. player tries to move to a wall, etc)

Fast-Forward

Fast-forward refers to coarse simulation that happens for entities that are in a different level to the player (or whatever we deem as “active” level). Fast forward will not be used for overworld entities, as the time intervals in the overworld are much larger compared to dungeons, so we won’t have performance issues simulating 1000 entities where one action takes 1 day, whereas in a dungeon a move could be several seconds.

After a lot of thought and a few test implementations, I’ve decided to keep a single list in the time system for all the game’s entities that are active. A reasonable question is “what happens to creatures in a level when a player leaves the level”? We clearly can’t afford to be simulating all levels generated ever. On the other hand, it’s not nice to just “freeze” or “reset” the level (could be fine for other games). At this point, I’ve thought (and designed the code to be supportive of) the following process: When an AI entity plays its turn and it is on an inactive level (but not the overworld), it will plan a “fast forward” action. Such actions are coarse simulation like “wander around the level”, “go pick up a fight”, “sleep”, “sentry”: these actions would take hours each. So, all the entities would always play, but the frequency of play would be drastically lower for entities in overworld or inactive dungeon levels. Maybe we can have even coarser level simulations that each lasts days or months, using the same principles.

What’s important is what happens when a level with fast-forward action-taking entities gets activated. In this case, we interrupt the entities actions and execute the OnInterrupt() command, which could place the entity randomly, run the same simulation but with a different duration (e.g. a “normal day cycle” action for 3 months that gets interrupted 1 month in, gets executed for 1 month).

Several aspects of the fast-forward system will be tested pretty soon, as the simulation will happen in the overworld and the NPC AI will be delving in dungeons. As they will enter the dungeons, the active level will be the overworld and the NPCs will be in inactive levels, therefore playing fast-forward actions like “Clear dungeon level”, “Delve to next level” and “Flee dungeon”.

Next steps

Next time will be AI revamp in addition to spawning of world events and implementing/writing some EntityCommands and EntityActionConfigs.

Towards NPC simulation

So, now that simulations now run acceptably, we need to move on from simulations to (well, simulated) reality. There’s a still big list of todos:

  • Implement turn system (I have an older implementation, so it’s not completely from scratch, maybe)
  • World occasionally generates adventure locations (dungeons)
    • Nearby cities could spread rumours about them
  • Basic city-related AI
    • City occasionally spawns quests (think town hall bulletin, paid work)
    • Factions occasionally spawn quests (guild advancement)
    • Inns occasionally spawn rumours (quests with great rewards that might or might not be true – still thinking about this)
  • Basic NPC AI
    • Actions in a city…
      • Buy rations
      • [?] Rest/heal. But maybe that will be automatic
      • Check city/faction/inn quests.
      • Meet up people at an inn and form parties
    • Actions in a dungeon…
      • Progress with an encounter
      • Flee
    • Actions in the wilderness…
      • Move towards destination (be it a city, a dungeon or an NPC/party)
        • (hmm maybe I need to consider party vs party fight simulation)
    • Actions anywhere…
      • Set destination (dungeon, city, party, etc)
    • Decision making
      • Estimate quest difficulty (expected survival. Also try to see what skills are required and compare to own skills)
      • Estimate quest importance (based on personality and goals. Rogues like gold, Paladins like righteous stuff, etc)
      • Estimate if enough rations for a quest can be purchased
  • Ability to track particular NPCs/parties (in terms of location in world map and logging)

 

The turn/time system will be the first in the list, as actions and AI all utilize the concept of time

NPC Party Dungeon Delving and Wilderness Encounter Simulation

As a reasonable follow-up to single NPC dungeon delving simulation, now we test parties of adventurers.

Strength in Unity, Complementary

Parties are stronger than individual NPC, but without being overpowered. The increase in power is not linear: 5 heroes working together are not 5x more effective than a single hero, but general survival rate is greatly improved. So, here are a few similarities/differences between a single NPC and a party, with regards to mechanics in the coarse simulation layer that I’m currently developing:

  • Healing is applied to all members equally
  • Damage is reduced based on the number (N) of party members by: \frac{N-1}{2N}
    • N=1: 0%, N=2: 25%, N=3: 33%, etc.
  • XP are divided among party members
  • For skill checks: use the max value among members
  • For skill category checks: for each member calculate the average of the category’s skills, and use the max among members

With these in mind, it’s clear that it’s beneficial to have parties with complementary skills.

Single-Delve Tests Revisited

Here are a few examples that show survival rate in a few party size configurations (1,2,6) when we put a party (of any level) against a dungeon of a similar level.

Lifetime-Delve Tests Revisited

Here are a few examples that show survival rate when we put a lvl 1 party against a series of dungeons of a similar level to the party (dungeons progressively get stronger as party levels up). CR mod is difference of character level to dungeon level, so a crmod of -5 means a level 25 party will tackle a level 20 dungeon.

 

Wilderness Encounters

Adventurers start their adventures typically at cities. They travel, and travel, following well-established routes as much as possible and crossing through other cities, until finally they enter full-on wilderness to get to a dungeon to clear. So, with some quick and not-too-inaccurate math we can figure out that if X is the total distance to the dungeon and Y is the average city-to-city distance, then the distance off roads will be \text{min}(Y/2,X). The split to off-road and on-route is important, as threat on route is significantly smaller.

The tests assume a +-20% in challenge rating compare to the character level, and they utilize the dungeon delving simulation code from the previous post, but with 1-3 encounters only.

These examples show the benefits of being in a party, and they also demonstrate that survival chances drop with larger distances (but the drop decays sharply), and they also drop with higher character levels, as more dangerous encounters get spawned.

Side-effect plot viewer

The generated graphs use several parameter sets, e.g. party size, retreat threshold, etc. It becomes difficult to navigate through the graphs when you want to flip between two arbitrary parameter values. So, instead of researching it further, I wrote a dead simple script that allows “interactive” graph rendering in the cheatiest way: it parses special parameter-encoding filenames, e.g. “wildernesssurvival_retreat2_party5.png”, and listens to keypresses. When e.g. ‘r’ is pressed, I load the file ‘wildernesssurvival_retreat3_party5.png’, while now if ‘p’ is pressed, I load ‘wildernesssurvival_retreat3_party6.png’. This is actually a lifesaver! And works with all graphs. Here’s the code in all its glory:

 

import glob
import sys
import os
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg

def run(img_format, params):

    param_ranges = [] # for each param, a list of values
    param_cur_indices = []
    ax = None
    fig = None

    def press(event):
        sys.stdout.flush()
        for k in range(len(params)):
            if event.key.lower() == params[k]:
                off = 1 if event.key == params[k] else len(param_ranges[k])-1
                param_cur_indices[k] = (param_cur_indices[k]+off) % len(param_ranges[k])
                param_cur_values = [ param_ranges[i][param_cur_indices[i]] for i in range(len(params))]
                img=mpimg.imread( img_format.format(*param_cur_values))
                ax.imshow(img)
                fig.canvas.draw()

    all_files = glob.glob(img_format.replace("{}","*"))
    img_format_const_parts = img_format.split('{}')
    for i in range(len(params)):
        """
            To extract number for i-th param, locate the end of the string before and the start of the string after
        """
        values = []
        for j in range(len(all_files)):
            fname = all_files[j].replace('\\','/')
            idx_start = fname.find(img_format_const_parts[i]) + len(img_format_const_parts[i])
            idx_end = fname.find(img_format_const_parts[i+1])
            values.append( int(fname[idx_start:idx_end]))
        values = sorted(list(set(values)))
        param_ranges.append(values)
        
    param_cur_indices = [0] * len(params)
    param_cur_values = [ param_ranges[i][param_cur_indices[i]] for i in range(len(params))]

    plt.close('all')
    plt.ioff()
    img=mpimg.imread( img_format.format(*param_cur_values))

    fig, ax = plt.subplots()
    plt.axis('off')
    fig.canvas.mpl_connect('key_press_event', press)
    ax.imshow(img)
    plt.show(block=True)


if __name__ == '__main__':
    #img_format = 'C:/Users/Babis/Documents/repos/aot/build/apps/aot_v0/imgadvlocreslvl_crmod{}_enc{}_retreat{}.png'
    #params = ['c','e','r']

    #img_format = 'C:/Users/Babis/Documents/repos/aot/build/apps/aot_v0/advlocres_crmod{}_enc{}_retreat{}_party{}.png'
    #params = ['c','e','r','p']

    img_format = 'C:/Users/Babis/Documents/repos/aot/build/apps/aot_v0/wildernesssurvival_retreat{}_party{}.png'
    params = ['r','p']
    run(img_format, params)