The Big Complicated Chronicles Actions System

Chronicles IV: Ebonheim attempts to mix the “instant-turn-based” combat of a classic roguelike (what do we call that? a dungeon crawler? a Nethack-like?) with more complex targeted abilities like a traditional grid-based tactics RPG such as Disgaea and also have perfect-ish deterministic turn information like Into the Breach.

Defining the Problems

Into the Breach's Prediction Model

ItB is really smart and innovative because it doesn't only show what the AI units intend to do on their turn, it also shows the consequences of the player's decision prior to committing to it. This would normally be a really complex thing to get right but not for ItB because the prediction problem is heavily simplified by a very key design decision: the board can't change between decision and execution.

Since all enemy units act together on their turn stage, they can never interrupt a player's plan. The player can decide what a unit will do, calculate it's outcome by only simulating one action (based on the current board which is guaranteed to be accurate), and then instantly execute it, modifying the board.

There's no turn-order in the classic sense that requires a player decision to be delayed and executed at a later point when the board may have been modified by other units acting first.

Chronicles' Design Constraints

Chronicles wants to have this nice feature of showing the intended decisions of AI as well as the consequences of player decision prior to committing. However, there are several design constraints for the game that make this a lot harder to predict and message:

I also wrote out a long list of abilities I already intend to implement. Some of those are a surprise but many of the basics are:

Finally, let's also throw in some architecture design constraints that will make the final system scalable into the future:

The Solution

Breaking it Down

To try and build a unified theory of Actions that satisfied all constraints it was helpful to start by separating concerns; first by user. Who are the consumers of this system? 1. The Developer: Writes C++ and adds new features to the system like pushes and branching and looping. Cares most about the ease of adding and tweaking types of actions with minimum boiler-plate. Doesn't want to ever have to touch the prediction code ever again. 2. The Content Creator: Uses the in-engine editor to define arbitrary actions for use in all the different abilities. Likes having tons of knobs and clickers to tweak everything and make unique abilities. Expects everything to have tactile UI and doesn't want to write scripts. 3. The Game Renderer: Needs to be able to inspect a given action against an immutable game state and then draw both decision-time and execution-time UI and messaging. Really doesn't want to have to care about the underlying assets, enjoys being real stupid and just simulating component parts to draw. 4. The Game Logic Step: Needs to be able to modify itself based on the actions. Also doesn't want to care about the underlying asset, just wants to loop through the actions and call Do(). Likes long walks on the beach and trivial copyability.

I realized that satisfying the Content Creator's stories is a fairly isolated set of problems. Most of what makes their life easiest doesn't need to touch the other users. What they need is Game Assets that serialize and deserialize, have UI, and are able to be referenced in immediate-mode from the asset directory. So this is where I split the problem into two distinct parts: Actions and ActionTokens.

Actions

An Action is a pure-virtual interface (C-style vtable in my implementation but still). Because this is a Game Asset, these are completely const and immutable during gameplay. This interface has the functions create(), destroy(), serialize(), deserialize(), and, most importantly, doUI() and compile().

doUI() uses ImGui's immediate-mode idiom for rendering out a complete frame of UI for modifying the content of that Action. A lot of my UI is also driven by code-generated reflection so it's extremely easy to throw together some rapid UI for modifying a new type of action.

compile() spits out a set of ActionTokens, which are consumed by the other users.

What makes the Action Interface really slick is that you can make an Action that is, itself, a list of Actions. The ActionList implementation just holds onto a list of child Actions and calls the virtual functions on each of its children. This makes all Actions reusable, modular, and embeddable!

Right now there are 3 action implementations: DeclareTarget, MoveAttack, and ActionList. In the future, ActionList can be expanded to have options for looping and conditional branching, and of course new Actions are easy to add like pushes, teleports, or AoE damage.

With the Game Asset side of the problem completely fleshed out and implemented, the content-creator is happy and the Developer is happy because all the UI code and boiler plate for ser/deser is contained in a separate module that never touches game state.

ActionTokens

static void _actionList_Compile(Action const* self, ActionTokenSet &tokens) {
   auto data = (ActionDataActionList*)self->data;

   auto tok = tokens.tokenGen.alloc();
   tokens.tokenType[tok] = ActionTokenType_BeginScope;
   tokens.tokens.push_back(tok);

   for (auto&& a : data->actions) {
      actionCompile(a, tokens);
   }

   tok = tokens.tokenGen.alloc();
   tokens.tokenType[tok] = ActionTokenType_EndScope;
   tokens.tokens.push_back(tok);
}

For how we ended up at ActionTokens, let's talk a little bit about what a program is versus what a programming language is. When you write a program in C, you have all sorts of bog-standard utilities like looping, conditions, scoped variable declarations, stacks, heaps, memory referencing, etc. You can think of a program as a series of expressions. Every expression has different behavior and different sets of inputs but ultimately the written pre-compiled program is one big expression that contains expressions that contain expressions all the way down.

When you compile, these expressions are translated. Loops and Branches become GOTOs/JUMPs, memory value referencing turns into a whole ton of MOVEs and PUSHes, and you end up with a machine-readable completely linear list of instructions. Your PC doesn't need to know anything about C, as long as the instruction set is compatible with the CPU.

You might be catching on that this is a great metaphor for Actions! If Actions are the expressions of a program, ActionTokens are the instructions! Before our Actions-as-defined-by-our-Game-Assets can be used by the other two users, Step and Render, we have to compile it to a linear list of instructions.

Data-Flow

One problem I ran into immediately is that while we have a token for declaring a target-request with a specific ID, it's actually really tricky to determine what targets are available at different points in the execution. Similarly it is difficult to get the decisions for each request stored in an appropriate place so that the tokens that reference the decisions are able to resolve their targets. Here's an overly-complicated situation you could run into with embeddable Action Lists:

Begin Scope
   Declare Target "T1"
   Declare Target "T2" relative to "T1"
   Move/Attack "T2"
   Begin Scope
      Declare Target "T1"
      Move/Attack "T2"
      Declare Target "T3"
   End Scope
   Move/Attack "T3"
End Scope

While looping over our tokens prompting the user for decisions on all of the target requests, you need these name-resolutions to work the way they would with scoped variables in a normal programming language!

And so in addition to the const, immutable TokenSet we got from the compiled Action, we now also need a very mutable TokenMemory for keeping track of all of this! With TokenMemory we can iterate through our token set and define memory addresses to all of these target references so we don't need to worry about scoped name resolution anymore.

Begin Scope
   Declare Target "T1" -> 0x00: New Target
   Declare Target "T2" relative to "T1" -> 0x01: New Target referencing 0x00
   Move/Attack "T2" -> referencing 0x01 relative to 0x00
   Begin Scope
      Declare Target "T1" -> 0x02: New Target
      Move/Attack "T2" -> referencing 0x01 relative to 0x00
      Declare Target "T3" -> 0x03: New Target
   End Scope
   Move/Attack "T3" -> Error, unresolved name in scope
End Scope

With the links made between all the tokens in the memory object, we can get decisions from the player or AI, and assign them to the appropriate place to be referenced by the other tokens.

Consuming a TokenSet

Now we have everything we need for our token set to actually affect things, how do we actually use them? If we think back to our list of design constraints, a TokenSet is only the things performed by a single actor. That actor might be going 3rd in a turn-ordered list of 7 actors. That actor might be the player-character which means all the other actors have already decided what they will do. Therefore, your target-highlighting needs to convey to you the consequences of that particular target decision at the point in the turn order that the player acts. How do we do that?

This brings us all the way back to functional programming, inline state modification, immutability, and, chiefly of all, trivially-copyable Game State.

When I first started trying to tackle this system months ago I very naively attempted to make little snapshots of the board state that I could pass around to different places to make decisions relative to the expected board. This runs into a lot of issues as you start to scale up in complexity and the amount that you need to be correct and in-sync in these little snapshot objects starts to grow into a medusa.

So hey, what if you just copied your literal entire game state and then applied every token to it in-order until you reach your targeted simulation point.

And that's exactly what we do:

void _renderActorDecisionsUnderActors(EGATexture& target, GameState const& g) {
   auto gPrev = g; // copy game state to preview game state
 
   // loop over all turn members in turn-order
   for (auto actor : g.turn.members) {
      // at this point actor should have the full list compiled AND memory should be filled with decisions (except for the player)
      auto &actorState = *g.turn.actors.find(actor);
 
      size_t idx = 0;
      auto &set = actorState.tokens;
      auto &mem = actorState.tokenMemory;
 
      while (idx < set.tokens.size()) {
         // if we reach the player in the turn-order and they're still deciding this frame, skip them
         if (actor == gPrev.player_controlled && turnMemberTokensNeedDecisions(g, actor) && idx == actorState.tokenIndex) {
            // we're at the player's current decision node, break
            break; // go on to next actor
         }
         // render the token messaging (show arrows, highlight squares, show damage)
         _renderActionTokenUnder(target, gPrev, actor, set.tokens[idx], set, mem);
 
         // apply the token to the PREVIEW game state
         gameStateApplyActionTokenForPreview(gPrev, actor, set.tokens[idx], set, mem);
         ++idx;
      }
   }
}

We can do this every frame for our Render user who never needs to modify the actual source GameState!

This method of simulation is so intensely simple and intuitive and it solves all simulation problems. Need to cancel target request 2-of-3 after noticing that request 1-of-3 was too short? re-simulate. Need to use an ability that has Turn Priority and makes the player suddenly go first? re-simulate.

In the end, both the Render user and the Logic-Step user are the same! They're just interpreters of the compiled token set. That's really all there is to it!

Out of everything we've gone through and decided up to this point, the beauty is that the turn prediction engine is actually the simplest and smallest section of code out of them all.

Closing Thoughts

Why didn't you use LUA for your action scripts?

I want to use LUA! For... some things. The truth is that scripts are data is logic is data. I could pretty easily replace the Game Asset Action with a LUA script and let people go crazy with loops and branching and everything. But then I lose all this cool UI! ImGui lets me do scripting without actually writing scripts and that is COOL.

Preview vs Execution

Because we're making a roguelike and perfect knowledge would ruin the fun, we have two different execution functions for the different ActionTokens. ApplyForPreview will do things that may modify the board state but provide imperfect information. ApplyForExecution is when we actually perform all the actions and loop through all actors and modify the base game state with all the results. The difference between these two is going to be a bit of a grey area and will require a lot of iteration! All I know is sometimes you need to see an ogre and for it to say “Doing ???? to you.” and for you to need to change your pants.

A Very Small Example

After I got the system working last night, I rigged up a version of the move attack that asks for you to decide on three consecutive target-requests, each one relative to the previous. The Move-Attack at the end would then act upon the final selected tile. The following gifs were made with zero code changes only modifying the Action assets:

You made it all the way to the end!

:eggbug: Good Job!

#gamedev #chron4 #longpost

| 🌐 | 🙋‍ | @britown@blog.brianna.town