TP:EW's Item System

§ Overview

The following summarizes several challenges and solutions for the item system in Trolley Problems: Ethical Wreckage
C#/Java style pseudocode is used in general, while some specific pointer usages will use C++ style pseudocode
- Type* ptr; means a pointer to an object of type Type
- ptr->foo() calls the function foo on the object pointed by ptr
- ptr->bar references the variable bar on the object pointed by ptr
Diagrams are used in succession, and newly added elements are marked in bold

Notes like this are for alternative designs that are either

Not used, or...

Discussed in later sections

§ Terminology and Initial Layout

§ World vs. Game vs. UI

Like most games, TP:EW has inventories that hold items
- Items fall under different types
- Different entities in the game (stations, trolleys, the player) can each hold exactly one inventory
  
  ↗
The game itself has a world, this is where mechanics happen (ex. trolleys moving around, enemies spawning)
- Item mechanics interact with the world by listening to world events and responding to them
- Item visuals and audio interact with the world either as an effect of event responses, or exist by themselves (ex. an item that spins around when it is mounted on a trolley)
- For the rest of the write-up's wording, the world is used instead of the game, since game involves both world and UI
↗

§ Basic Design Choices

The first design choice is the inventory will be directly interfacing with some UI class, since players only ever see item UI when the inventory is up
The second design choice is fixed item slot count within the inventory, and allowing item stacking within the slot
- The goal is to limit maximum number of item types per entity while not necessarily capping capcity
  - ex. 4 slots with 12 capacity is not the same as "any 12 item instances"
- Item stacking itself is good for...
  - non-linear curves
  - minimizing effect instance count by collapsing x buffs that add +y to a single effect that adds +(x * y)
Technically both are doable without slots by maintaining a map from item type to count.

Compared to the slot-less design, the slotted design has the following benefits:
- Having a dedicated slot structure makes interfacing with (slot) UI easier
- Another benefit is fixed item trigger order: TP:EW's trigger order is strictly by slot index (from top left to bottom right)
- If a item type map is used, trigger order is difficult to define, which causes issues if certain items effect is if damage X to enemy Y, then also damage X to enemy Z that must be called after other items that generate damage
There are also several issues:
- Item slots act as a (logical) middle layer between the inventory and the item instances it hold, accommodating for this layer complicates coding
  - At one point we wanted to refactor the player inventory as having unlimited slot count and capacity, but could not make it work with the slotted design unless a whole new type of inventory is coded (and made visible in UI)
- People are confused during early play-test for whether items are actually stackable or not, since nothing stops them from placing duplicates in different slots, instead of all in the same slot
The best of both worlds would be a slot-less design where only one item instance is allowed per item class in the inventory.
- Forcing the UI to not allow non-stacking placement would teach players that items are stackable
- Unlimited slot (item type) count is by default, there is little difficulty in switching between limited and unlimited
- While technically this would disallow multiple instances of the same non-stackable item type to all be active on the same owner, but after design work is done for the game we didn't actually end up with
I recommend this design for any game where the same player manages several different inventories.
↗
The next two choices are more related to TP:EW's gameplay loop
1. To prevent players from resetting cooldown by dropping and picking up an item repeatedly, cooldowns are not reset when dropped / picked back up
  - Cooldowns are also associated with a single item drop
  - ex. If you have an item of type A currently with 30s cooldown, then you pick up an item drop of type A (cooldown is reset by default), then you can immediately reuse the second item and use the original item 30s later
The alternative is to consider stacking as its own system separate from cooldown. An ItemStack uses one single cooldown counter, and on trigger the behavior of the item stack depends on the number of layers.

Another alternative is to always reset cooldown upon pickup, which games like Risk of Rain 2 uses.
1. To minimize the number of item visuals on screen, there is only one item instance per slot no matter how many stacking count there is
  - This is to both reduce in-game object count and also make item ownership obvious in mid/late game, when there are several trolleys zooming around the map, each with several items
- These two combined means a somewhat strange system must be used
  - In the following, an item instance denotes the in-world object with visuals and audio that represents 1 or more items (of the same type) in a single slot
  - An item state denotes information specific to one item stack within the slot that cannot be shared with other item stacks. This is mostly just the cooldown.
    
    ↗
    - In this case there is 1 rendered item instance on the trolley that corresponds to the occupied item slot. 4 item states are in that slot, so this P-shooter can fire 4 times in succession before needing to wait for cooldown.
  ↗

A more obvious design (which several online tutorials use) is to store item states within item instances, and keep different instances separate

Intuitively this also means visuals are presented separately per instance, but there are of course ways to simplify using some sort of map-based approach

↗

§ A Central System

For ease of debugging, a central system that issues new item states upon item drop is used

Initially this central system is also responsible for updating/ticking, which just means subtracting some time per frame from the cooldown

Intuitively, when issuing an item drop some sort of type information is needed

In Unreal this is done by passing a TSublassOf<ABaseItem> value

The alternative is to have a class default object and pass its reference

class MyItem : BaseItem {
  public static MyItem Defaults = new();
  string Name;
  float DefaultCooldown = 10.0f;
}

struct ItemState {
  BaseItem Defaults;
  float CurrentCooldown;

  public ItemState(BaseItem Defaults) {
      this.Defaults = Defaults;
      Cooldown = Defaults.DefaultCooldown;
  }
}

class ItemSystem {
  Dictionary<long, ItemState> IssuedItemStates;

  public BaseItem IssueItemDrop() {
      ItemState state = new(MyItem.base);
      IssuedItemStates.Add(SomeGetIdFunction(), state);
      return state;
  }
}

There is of course a way in C# to directly pass type information, this example is just illustrating feasibility without going that route

The item system object is essentially just a pool. We decided to have one per world to allow each world to have different item options if needed

↗

In TP:EW there is no need to delete an existing item once it has been issued, but if there is such a requirement then the deletion would have to be done by the item system too

Under this pattern, the iteme system can store a unique pointer to reference each spawned item state without necessarily going through a dictionary, but it is equally valid just to store the id as a value and use ItemSystemInstance.IssuedItemStates[id] to retrieve the state
- Unique pointers are used to denote the systems's ownership of each item instance
  - Everything else that need to reference the item state simply points to the unique pointer's referenced data or nullptr if empty
  - Once a pointer is populated, it is always valid as items are never deleted
It is important to note that although unique pointers save memory use and GC complications, they do not save most of the performance as they are not cache friendly
- Consider the follwing code
```
AItemSystem : public AActor {
    TArray<TUniquePtr<ItemState>> States; // items are referenced via index
    void UpdateCooldowns(const float DeltaSeconds) {
        for (TUniquePtr<ItemState> ItemStatePtr : ItemStates)
            ItemStatePtr->DecrementCooldown(DeltaSeconds);
    }
}
```
- Even though object access look consecutive they might be jumping all over the memory and breaking cache at any place. This is completely at the mercy of your allocator.
- To solve this issue, TP:EW opted to not use centralized ownership. While it is possible to provide move functions to preserve number of item states, we just manually make sure that no item state is copied out of its owner without also removing it from the owner.
If you are implementing with C# instead of C++, now is a good time to refactor ItemState back to a struct because it is intended to be passed around by value.

The following is a cache-friendly version. It is actually not used in TP:EW and a very similar alternative is discussed in later section.
AItemSystem : public AActor {
    TArray<ItemState> States; // items are referenced via index
    void UpdateCooldowns(const float DeltaSeconds) {
        for (ItemState State : ItemStates)
            State.DecrementCooldown(DeltaSeconds);
    }
}

↗

§ Basic Item Logic

§ Custom Triggers

Intuitively, one might want items to control their own firing
ex. Imagine a turret that shoots when an enemy approaches it
- In TP:EW's system this item might have stacks, all of the stack numbers contribute to the same turret-looking object in the world
- It is this turret-looking object that actually gets triggered, perhaps by some collision check on its hitbox
- Note that there are multiple item states associated with this turret instance
  - If any of those item states has cooldown ready, then fire the item and reset that specific item state's cooldown to full
- Let's consider a simplified case without cooldown
```
class MyItem : BaseItem {
  private Capsule Trigger;
  public void BeginPlay() {
      Trigger.OnOverlapStart.Bind(Damage);
  }
  public void Damage(Object Other) {
      if (Object is Enemy) {
          (Object as Enemy).TakeDamage(1);
      }
  }
}
```
  - The trigger is custom in the sense that it is not pre-determined when inheriting from BaseItem
Note that this example is extremely contrived, it only fires the weapon on the first frame the enemy enters the hitbox, and never when the enemy stays in the hitbox

In practice, none of the custom triggers in TP:EW actually needs a cooldown anyway so we just went with the sample code.

↗

§ Common Triggers

ex. Imagine an item that fires every time a trolley (which owns the item) passes a station
- The trolley receives this event, so it tells all relevant item instances to respond to it
- Each item instance queries its item states for cooldown information, similar to the custom trigger case
In general the following types of triggers are used
- Mount: triggerd on mount (unmount is just mount with stacking number 0)
- Always: triggered every frame
- DamagePrepare: damage is initiated but not yet evaluated
- DamageDealt: damage is evaluated, and whether it has killed an enemy is available to the listener
- TrolleyPassesStation: this is fired both on the trolley and the station

In TP:EW triggers response can start other triggers. This can create infinite loops if, for example, an item's effect is "dealing another damage when damage is dealt"

In general this is prevented by ordering triggers: triggers who come in front can start triggers behind them in order, but not otherwise

Consider the example case, it can also be implemented with "if a prior item adds some damage to the DamagePrepare event, then this item will modify that added damage

Since everything happens within DamagePrepare no cycles are possible

↗

§ Common Trigger Implementation

I am not very familiar with function pointers/references in either C++ or C#, so the following will use an anonymous function to wrap them
- C++ wrapper: TFunction<void(TriggerData&)> Respond = [](TriggerData&){ HandleTrigger(TriggerData); }
- C# wrapper: Action<TriggerData> Respond = (TriggerData Data) => { HandleTrigger(TriggerData); }.
  - Note that TriggerData in this case needs to be an reference type (class instead of struct) so it's passed by reference by default instead of passing by value
  - I looked online but apparently the Action<T> syntax doesn't allow using the ref keyword? Not really sure...
Adding a fixed-priority listener to a common trigger is simply adding this anonymous function to a list
- ex. Say there are 4 slots in total, slots 0 and 2 each have an item that cares about the Mount trigger, then the listener list of Mount will look like the following:
  - { MyItemA.RespondToMount, null, MyItemB.RespondToMount, null }
  - Each RespondToMount function is just the wrapped version of HandleMount(TriggerData)
This fixed order gets around the issue of using UE's event system that may or may not guarantee order.
- Evoking fixed-priority listeners take the following code
```
// @param EventType: refers to Mount, DamagePrepare, ...
void Trigger(TriggerEventType EventType, TriggerData Data) {
  ReponseQueue = ResponseQueues(EventType);
  for (int SlotIdx = 0; SlotIdx < Slots.Count; SlotIdx++) {
    var Response = ResponseQueue[SlotIdx];
    var Slot = Slots[SlotIdx];
    if (Response != null) {
      Response(ref Data);
    }
  }
}
```
Equipping and unequipping an item looks like the following:
- Player equips the item on an owner using some UI
  - Item instance is generated on the owner
    - Item instance's responses are binded to the owner's triggers
      - Mount trigger is called with updated stacking
        
        The game continues, the owner fires triggers and the instance responds to them
        
        Player unequips the item from that owner using some UI
      - Mount trigger is called with updated stacking (0 if now empty)
    - Item instance's responses are un-binded
  - Item instance is destroyed, leaving only the invisible ItemState it's associated with

↗

§ Updating Cooldowns

For most triggers there is more update action than query (checking if some state in the slot is ready)
An intuitive organization is to keep the item states sorted within the slot so that checking cooldown is simply ItemStates[0].CurrentCooldown <= 0.0f
In this scheme, when an item is triggered, the current cooldown is reset to that item's type's default cooldown
- Since the rest of the item states are not used to trigger, we can just insert the resetted state into the middle (or more likely the end) of the array so that order is preserved

Note that insertion requires shuffling previous items forward in the array to make space, this is fine if done very rarely but in late game items trigger pretty often with all the stacking and cooldown buffs

We will come back with an optimization for this issue in later section

To accommodate for cooldowns, the trigger function needs to be updated

  // @param EventType: refers to Mount, DamagePrepare, ...
  void Trigger(TriggerEventType EventType, TriggerData Data) {
    ReponseQueue = ResponseQueues(EventType);
    for (int SlotIdx = 0; SlotIdx < Slots.Count; SlotIdx++) {
      var Response = ResponseQueue[SlotIdx];
      var Slot = Slots[SlotIdx];
      if (Response != null && Slot.ItemStates[0].CurrentCooldown <= 0.0f) {
        Response(ref Data);
        Slot.ItemStates[0].ResetCooldown();
        Slot.Sort();
      }
    }
  }

We assume all items require cooldown here. In the actual game there are shortcuts everywhere to skip cooldown checks when the item doesn't use cooldown at all.

§ Item Transactions

This section is more focused on UI flow and will be glossed over. The relevant point is keeping the unique pointer alive in the item system the whole time.

In TP:EW, item drops share the exact same visuals an item has when mounted, so the only thing to take care of is to not make the item functioning
- This is as simple as not binding any common triggers (and having custom triggers depend on values set through common triggers, such as stacking number)
↗
As the last section mentions, item states are technically inserted into the slot when transacted
- This actually won't really make a difference because of a later optimization, I'm bringing it up here for consistency

A note for UI is that it is good to separate checks with the actual transaction logic

This way a warning could be given to UI without actually trying to transact items, this is useful for displaying error message on hover

↗
A typical transaction logic looks like follows:

public class Slot {
  public bool CanTransact(Slot Dest, out string Err) {
    if ( SomeErrorCondition ) {
      Err = "My error description";
      return false;
    }
    // ...
  }

  public void Transact(Slot Dest) {
    if (!CanTransact(Dest, Count, out string _)) return;
    // now that transaction is verified, pull an item state out of the slot and insert it into the destination slot
  }
}

public class SlotWidget : UI {
  Slot CorrespondedSlot;
  public void OnHover() {
    if (!CorrespondedSlot.CanTransact(FindEmptySlotInOtherInventory(), out string Err)) {
      ShowError(Err);
    }
  }
  public void OnClick() {
    MySlot.Transact(FindEmptySlotInOtherInventory());
  }
}

Again this is really simplified, TP:EW actually does transactions between inventories instead of slots.

§ Compatibility

In TP:EW some items are only usable on stations while others only on trolleys
- We decided to not even allow moving items onto incompatible owners (just for inventory management)
- We also planned to allow items being incompatible with specific other items, although the feature was unused as of writing

Due to only having two possible owner types, we add two flags to the item, and use them in a validation function during transaction

class BaseItem {
  public bool CanUseOnTrolley;
  public bool CanUseOnStation;
  public TSubclassOf<BaseItem>[] IncompatibleItemTypes;

  public bool Validate(Inventory Destination) {
    if (Inventory.Owner is Trolley && !CanUseOnTrolley) return false;
    if (Inventory.Owner is Station && !CanuseOnStation) return false;
    
    if (IncompatibleItemTypes.IsEmpty()) return true;

    for (var Slot : Inventory.Slots) {
      var SlotObjectType = Slot.ItemClass;
      if (IncompatibleItemTypes.Contains(SlotObjectType)) return false;
    }

    return true;
  }
}

Having this specific list of options available turned out to work better than having each item overide the Validate function, which would end up with lots of code repetition.

§ More On Cooldown

§ Is One Cooldown Enough?

Originally we thought no, but after a semester of incorporating a separate cooldown for all 8 possible triggers, we found none of the items actually use more than one. This multi-cooldown implementation is pretty pedantic and we will just skip over it.

After correcting this overhead we're left with only two fields describing an item's cooldown
- Channel for which trigger uses the CD; when none of them do, this will just be 0
- DefaultLength for the length of the CD when reset

§ Cooldown Rates

Recall that slots keep an array of pointers to item states, sorted by cooldown
For simplicity's sake, TP:EW uses a shared cooldown multiplier per inventory owner
- When decrementing cooldown, the DeltaSeconds is multiplied to this modifier, which technically leaves room for floating point error (with repeated subtraction) but the result plays fine

Consider how this might look if we still use the central system to update cooldowns

Item states consecutive to each other in the ItemSystem might not actually fall under the same owner, so memory access could be out of order

Similarly, the multiplier needs to be refreshed for each item state, which creates redundant work
↗

Instead it is much simpler for the inventory owner to update the cooldowns

↗
Note that moving away from a central item system tick leaves an issue where item states will not keep cooling down when dropped on the ground
- The fix is extremely simply: just call the item state's update function from the item drop object update/tick function, without multiplying DeltaSeconds with anything

§ Optimizing Cooldown

The sorted array method mentioned previously is conceptually simple but requires shuffling memory around (when something is triggered or removed)
- One might suggest using linked lists of other datastructures, but those are not cache friendly
A common trade-off this kind of problem is to lower expectations
1. When we say we need the cooldowns sorted, we only really need the shortest and longest cooldowns
2. Can we tolerate not having those values properly set? For how long are we fine with that discrepancy?
In practice all cooldowns are decremented per frame
- Since this operation requires operating on the cooldown value, we might as well find the minimum cooldown within the slot while doing the decrementing
- Keeping a minimum is useful as
  - The UI can render CD by how long the minimum is compared to the default total cooldown
  ↗
  - An item with cooldown partially grayed-out
  - If the minimum is less than 0, then we know one of the item states is ready
↗
- Note that we switch to use an index instead of a pointer to a pointer (i.e. pointing to the array element, which is a pointer)
  - This is because array resizing may move things around in memory (well keeping items contiguous), which would invalidate pointers issued prior to the move
We then refactored away the pointer part and just directly store item states in the owner
- As mentioned before, this improves cache friendliness
- Technically this way of writing is more error prone as item states might be created out of nowhere or fail to copy
  - We only made the refactor after item transactions are well tested
↗

These two optimizations combined results in code that looks like the following

class Slot { // <-- this is inventory slot, not item system!
  TArray<ItemState> ItemState;
  int CDShortestIdx, CDReadyIdx;

  void UpdateCooldowns(const float DeltaSeconds) {
      float ScaledDeltaSeconds = GetCooldownMultiplier() * DeltaSeconds;
      int Idx = 0;
      for (ItemState State : ItemStates) {
          const float CurrentCooldown = State.DecrementCooldown(ScaledDeltaSeconds);
          // ... update shortest idx based on CurrentCooldown ...
          Idx++;
      }
      
      if (ItemStates[CDShortestIdx].Cooldown <= 0) {
        CDReadyIdx = CDShortestIdx;
      }
  }
}

To answer the second question: the longest the indices could be incorrect is however long it takes for UpdateCooldowns to be called for the next time

While implementing this optimization, we had to drop the feature where items that were moved out of the slot (to another slot or a different inventory) are always sorted by cooldown.

ex. If 2 stacks of the same item exist in the player's bag, one has cooldown 5s, the other has 15s

The player drags one item from the slot to some trolley

The dragged item should be the 5s one to it can "get to work" quicker

In actual item design, we didn't end up with that many long-cooldown items, so whether the feature exists or not made little difference

It's not to say that popping by order is impossible to write without a pre-sorted array, just that the particular way our transaction system was implemented didn't work well with it.

Another issue with this optimization is it caps the maximum firing rate of any item instance associated with a slot. Since the CooldownReadyIdx is consumed upon use (since the ItemState it points to has its cooldown reset and is no longer ready), a second firing during the exact same frame would be ignored.

On the other hand, for the sorted array implementation one can keep checking if the first item of the array is ready. That first item is always well-maintained without needing to be populated by the next frame.

§ More On Item Firing

§ Optional Firing

Currently, firing only takes the cooldown being complete and the common trigger being activated
- This causes the issue where weapons always fire even if there are no enemies in their range, since technically those subscribe to the Always event that is triggered per frame
- For weapons with long cooldown, an enemy could enter is range right after a false firing and sneak through

To fix this issue we change the handler function so that it returns whether the item actually fired

Cooldown is only reset if the item fired


class Turret {
  public override bool OnAlways(TriggerData) {
    if (EnemyInRange()) {
      Attack(GetEneyInRange());
      return true;
    }
    else return false;
  }
}

class InventoryOwner {
  void Trigger(ItemTriggerType Type, TriggerData Data) {
    // ... skip irrelevant code ...

    const bool fired = Response(Data);
    if (fired) {
      Slot.GetCooldownReadyItemState().ResetCooldown();
      Slot.ClearCooldownReadyIdx();
    }

    // ... skip irrelevant code ...
  }
}

↗

§ Slot States And The Mount Bug(s)

In the aforementioned design, there is no barrier between an in-world event and firing (the former guarantees the latter)
- If the player stop a trolley and inspects its elements, the weapons on the trolley can still fire
- Since TP:EW tries to not be a tower defense (most "towers" that actually deal damage must move), allowing players to pause trolleys and keep them firing would allow them to break the rule
To solve this issue, inventories require a state
- TP:EW actually implements this as a separate state per slot, as initially the item transaction rules allow moving an incompatible item into a slot (and then it will disable that slot)
Enabling and disabling is implemented as a set of "reasons" to disable, this allows for multiple reasons to co-exist
When the state of a slot enables, the slot registers all common triggers (except for Mount which is always registered after the item instance spawns)
- The reverse happens for disabling
- Mount it is guaranteed to only trigger during editing (when the trolley/station is guaranteed to be disabled)
One could record all Mount calls and trigger them one after the other immediately after editing stops, but this would greatly complicate code.

§ Remaining Issues

This section is more about the conflict between different systems than the actual design of the item system itself, so you may want to skip to the end.

§ Pre-emption

In summary, all the current cooldown system does is to let items know when it could be triggered
A missing feature is to allow items to expect to be triggered some time before it actually does
- This is sometimes useful where the vfx/sfx for triggering needs to be played ahead of time (ex. a laser beam charging up and then firing)

A fix for this issue would be to allow item instances to access their parent slot's cooldown reading

ex. If there are enemies in range and cooldown is 1.0s, then a turret would expect itself to trigger in 1.0s.

(There is of course no way to completely predict the game, since there are always different behavior from the player and AI)

§ The Flower

In TP:EW trolleys move along raiway tracks, and tracks are responsible for "propelling" the trolley each frame
- Every frame there is a "delta" that the trolley needs to consume (speed times delta seconds), and the Propel function will keep doing the following things until the delta is used up
  - If the track is the end of the line, then it bounes the trolley back and call "trolley passes station"
  - If there is a different track after this one, then transfer the trolley on to that track and also call "trolley passes station" since the station is passed during the process
- Simplified exerpt from the Track class
```
  // bounce back and start from the end
  if (NextTrack == this) {
    Dst->TrolleyPassBy(Trolley);
    // omitting logic for reversing the trolley
    Propel(Trolley, Delta);
  }
  // transfer trolley to next track
  else {
    RemoveTrolley(Trolley);
    Trolley->SetParentTrack(NextTrack);
    NextTrack->Propel(Trolley, Delta);
  }
```
Why is this relevant? In TP:EW there is an item called "The Surfer's Flower" that massively improves a trolley's speed, but at the cost of transfering it to random lines once the current line is fully traversed by that trolley

↗
- This is first implemented in the TrolleyPassesStation event and does some track-transferring logic
The conflict between the track logic and the item logic illustrates an issue with the common-trigger design
- When the Flower transfers the trolley away, there is often still remaining delta left in the frame (the only other case is where the delta is exactly used up when the trolley hits the station that triggers the Flower)
- Because there is delta left, the Propel function does not terminate after calling TrolleyPassesStation
- However, because the Flower transferred the trolley away, the Propel function of the original track will come into conflict with that of the new track
Sometimes conflicts like this is difficult to discover when you have forgotten how the trigger-side logic works
- The item logic could be flawless on its own, but there is no way to solve the issue unless some kind of hard-coded checks are added on the trigger side as well

§ Lessons

Make your code refactor-friendly
- Use specific function naming to denote stages required for a feature
- The most refactor-friendly code will not have existing interface functions removed/replaced
  - Rather, only helper-functions used by those interface functions might be replaced
  - The most an interface function would need to change is its internal code
Know / figure out what your game needs as early as possible
- TP:EW had most of its item system done before the design work started coming in, so a lot of work is wasted on anticipation
  - ex. Multiple cooldowns, redundant triggers
- Pick the right optimizations
Make trade-offs after the system is stable, refactor as much as you need
- The most intuitive way of writing things (using ownership idioms and centralized "manager" objects)

::

Software-design

::