In fighting games, special moves like Hadoukens and Shoryukens require players to input specific sequences of motions (like quarter-circles) and button presses. To recognize these moves, the game needs to track the player's input history. However, naively storing the last few inputs isn't enough because these inputs are read frame-by-frame.
For example, let's expand upon the ramifications of a naive approach to perform the move sequence below:

• Down
• Forward
• Punch

for (_, move) in seq {
  let moveSequence = move.sequence
  let frameLeniency = move.frameLeniency
  var currentFrame = 0
  var sequenceIdx = moveSequence.count - 1
  while (currentFrame < frameLeniency) {
    if move.priority < currentMovesPrio {
        break
    }
    let readIdx = (buffer.writeIdx - currentFrame - 1) < 0 ? bufferSize - currentFrame - 1 
      : (buffer.writeIdx - currentFrame - 1) % bufferSize
    
    if (moveSequence[sequenceIdx] == buffer.buffer[readIdx]) {
        sequenceIdx -= 1
    }
    if (sequenceIdx == -1) {
        currentMove = move
        currentMovesPrio = currentMove.priority
        break
    }
    currentFrame += 1
  }
}

Fighting games need a system to dynamically draw hitboxes and hurtboxes for each move. Each move has its own animations and may include specific invulnerable areas, such as Ryu's Shoryuken. To manage this, we've linked keyframes to each animation. This allows us to enable and disable hitboxes and hurtboxes as needed, matching the behavior shown in the clip below:

The below code-snippet defines the hitboxes for a light punch:

CharacterMove(sequence: [ButtonType.LP], stateChages: CharacterState.Attacking, priority: 1, frameLeniency: 2, attackKeyFrames: [
            AttackKeyFrame(keyTime: 0.1, name: "Hand_R", boxType: BoxType.Hitbox, boxModifier: BoxModifier.Active),
            AttackKeyFrame(keyTime: 0.2, name: "", boxType: BoxType.Hitbox, boxModifier: BoxModifier.Inactive, setAll: true),
            AttackKeyFrame(keyTime: 0.3, name: "Hand_R", boxType: BoxType.Hitbox, boxModifier: BoxModifier.Active),
            AttackKeyFrame(keyTime: 0.4, name: "", boxType: BoxType.Hitbox, boxModifier: BoxModifier.Inactive, setAll: true),
            AttackKeyFrame(keyTime: 0.5, name: "Hand_R", boxType: BoxType.Hitbox, boxModifier: BoxModifier.Active),
            AttackKeyFrame(keyTime: 0.6, name: "", boxType: BoxType.Hitbox, boxModifier: BoxModifier.Inactive, setAll: true)

This system also enables us to balance moves based on their "start-up," "active," and "recovery" times. It allows us to fine-tune each move for better game balance, as shown below:

Collision detection is handled using bitmasks along with SceneKit's physics system. This setup identifies which hitboxes/hurtboxes have collided and determines whether an attack should be triggered. They are defined programmatically like so:

// Hitboxes and Hurtboxes bitmasks.
let p1HitBox = 1 << 0  // Binary: 00000001
let p2HitBox = 1 << 1  // Binary: 00000010
let p1HurtBox = 1 << 2 // Binary: 00000100
let p2HurtBox = 1 << 3 // Binary: 00001000

This allows us to implement hit detection with the following table:

In Gouken, we model each character as a Finite State Machine (FSM). This simplifies game logic by limiting the actions a character can take based on their current state, rather than using complex nested if-else checks to account for every possible scenario.

For example, when a character is jumping, we only need to check if the player gets hit or completes the jump, instead of considering every possible situation. Below is a State Transition Diagram and Table for Gouken's character FSM:

For the attacking, staggered, and blocking states, we can loop the animation of the resulting state-transition depending on the input. For example, a character walking forwards being hit by a low or a heavy will get staggered, however, a heavy will stagger them for longer as depicted below:

This is crucial for fighting games like Gouken because it enables the creation of a combo system by varying the stagger times that different moves apply. Moreover, we can tune how long it takes a blocked attack to fully recover vs a whiffed attack, which opens up design space for balancing purposes. Unfortunately, we ran out of time in the course to fully design functional combo routes. Developing these would require creating animations, fine-tuning them, and expanding the move list. With more time-to-develop, this would be a top priority.

Regarding flow-of-control, SceneKit provides a rendering/physics loop where you can hook your code changes in using callbacks. Below is a complete diagram of SceneKit's update loop:

In the above diagram, blocks prepended with "renderer:" are functions we can implement that will be called at that specific time in the game loop. This allows us to implement per-frame game logic to be executed after or before specific events. For example, one can implement renderer:didSimulatePhysicsAtTime: to handle collision events right after physics has finished being simulated.

In Gouken, we implement both the renderer:updateAtTime: and renderer:didSimulatePhysicsAtTime: functions. The former houses all of our core game logic, handling character state transitions, win cons, netcode, etc. whereas the latter appends collision events to a queue to be processed in future game loop ticks by the renderer:updateAtTime: function.

Moreover, we opted to implement an Entity Component System to better handle the addition of new code. Because of this, a programmer need only create an entity or new component, and it will be called in the rendering loop automatically. as can be seen by the following code-snippet:

entityManager.entities.forEach { entity in
  entity.update(deltaTime: deltaTime)
}

Two conditions are necessary for a fighting game to have functioning multiplayer: as fast-as-possible latency between players and deterministic gameplay. In order to service the former, a peer-to-peer approach is required (as an additional hop between the clients and a server would be too slow) and a deterministic approach is required so that both players can send eachother merely inputs and handle state transitions accordingly on their own machines. We will expand on both aspects in the below sections.

Peer-to-Peer via iOS' Multi-Peer Framework

iOS's Multi-Peer Connectivity framework enables seamless communication between nearby devices without requiring an internet connection. Utilizing both Bluetooth and Wi-Fi, it supports peer-to-peer connectivity for real-time multiplayer experiences. Two devices, on the same wireless network or within Bluetooth range, can join eachother for a match of Gouken.




As of now, only two users on the same network/within bluetooth range can play together. This is due to the need of a session key to be exchanged between both clients, of which only one is hard-coded at the moment. Given more time, we would implement a server browser and lobby system to match-make users.

Deterministic Game State

Thanks to the "Characters as State Machines" and "Input Buffer" implementations, a Gouken match can be completely reconstructed with just it's input history provided. This means that Gouken's game state is deterministic - i.e. 100% reproducible. The below figure gives a visual example of what a non-deterministic fighting game would play like:



A deterministic fighting game makes netcode much easier to reason with! It allows us to send packets between clients containing only the inputs of each player, plus maybe some metadata to detect disconnections. Each player's machines then inserts the incoming inputs into their respective input buffers and updates the game state accordingly - advancing to the next frame.

Netcode Steps Going Forward

The illumination at a point is inversely proportional to the square of the distance of the point from the light source and directly proportional to the intensity of the light source. The unit for measuring illumination, candelas per square metre (cd/m²), is called luminance.

In other words, let L be the luminance emitted by a given light source, then the luminance of the player, P, is given by:

$$P=\frac{L}{2\pi r^2}$$
Where r is the distance from the player to the light source. This is how ShadowDancer calculates the illumination of the player. Every light source has a collider which runs a script to update the luminance value of the player with the above formula. It is then clamped to a value between 0.0 and 1.0 and is factored into a scalar multiplication of all enemy FOVs. When light sources overlap, ShadowDancer sums the illumination from all sources before clamping. The below figure gives a more visual depiction of how illumination is calculated in ShadowDancer:



Moreover, the light calculation is dynamic - i.e. a light source can be destroyed and it will no longer factor into determining the player's luminance. See below:

ShadowDancer detects how much noise the player is making and notifies nearby enemies to investigate. This is implemented by having the enemy AI's update loop check how much noise the player is making and whether or not it is in audible range.

if (IsPlayerInAudableRange() || IsThrownObjectInAudableRange()) {
  if ((soundIntensity >= mediumSoundThreshold) && (soundIntensity < loudSoundThreshold)) {
    LookAroundForPlayer(positionToChase);
  }
  else if (soundIntensity >= loudSoundThreshold) {
    ChaseThePlayer(positionToChase);
  }
}

Initial Hurdles

ShadowDancer has enemies that patrol an area, detect the player through visuals/noise, and chase and attack the player. To codify these three capabilities, ShadowDancer's A.I. has three "alertness" states that determine their behaviour:

• Patrolling


• Searching


• Chasing

Patrolling

Searching

Chasing

#ifndef __THREAD_FIXED_POINT_H
#define __THREAD_FIXED_POINT_H
                
typedef int fixed_point;
                
#define FRACTION 15
#define CONVERT_TO_FIXED_POINT(x) ((fixed_point)(x << FRACTION))
#define CONVERT_TO_INT_TOWARD_ZERO(x) (x >> FRACTION)
#define CONVERT_TO_INT_NEAREST(x) (x >= 0 ? ((x + (1 << (FRACTION - 1))) >> FRACTION) 
  : ((x - (1 << (FRACTION - 1))) >> FRACTION))
#define ADD_FIXED_POINT(x,y) (x + y)
#define ADD_INTEGER(x,n) (x + (n << FRACTION))
#define SUB_FIXED_POINT(x,y) (x - y)
#define SUB_INTEGER(x,n) (x - (n << FRACTION))
#define MULTIPLY_FIXED_POINT(x,y) (x * y)
#define MULTIPLY_INTEGER(x,n) ((fixed_point)(((int64_t) x) * n >> FRACTION))
#define DIVIDE_FIXED_POINT(x,y) (x / y)
#define DIVIDE_INTEGER(x,n) ((fixed_point)((((int64_t) x) << FRACTION) / n))

#endif /* thread/fixed_point.h */

struct list_elem sleep_element;  
struct list held_lock;             
struct lock *curr_lock;       
int our_priority;                   
int nice;     
int64_t remaining_time;                      
fixed_point recent_cpu;

MLFQS Formulas

void update_thread (struct thread *t)
{
  enum intr_level old_level = intr_disable ();
  int our_priority = t->our_priority;
  if (list_empty (&t->held_lock))
  {
    t->priority = our_priority;
  }
  else
  {
      int priority = list_entry (list_max (&t->held_lock, compare_locks, NULL), struct lock, elem)->max_p;
      t->priority = our_priority > priority ? our_priority : priority;
  } 
  intr_set_level (old_level);
}

void thread_update_recent_cpu(struct thread *t, void *aux UNUSED)
{ 
  t->recent_cpu = ADD_INTEGER (DIVIDE_INTEGER (MULTIPLY_INTEGER (MULTIPLY_FIXED_POINT 
            (load_avg, 2), t->recent_cpu),
            ADD_INTEGER (MULTIPLY_FIXED_POINT (load_avg, 2), 1)), t->nice);
  thread_update_priority_mlfqs (t);
}

void thread_update_priority_mlfqs(struct thread *t)
{
  int new_priority = (int) CONVERT_TO_INT_NEAREST 
      (SUB_FIXED_POINT 
      (CONVERT_TO_FIXED_POINT ((PRI_MAX - ((t->nice) * 2))), 
    DIVIDE_FIXED_POINT (t->recent_cpu, 4)));
  if (new_priority > PRI_MAX)
    new_priority = PRI_MAX;
  else if (new_priority < PRI_MIN)
    new_priority = PRI_MIN;
  t->priority = new_priority;
}

PintOS came with two major synchronization primitives - semaphores and locks, which did not account for priority (as the initial scheduler was priority-less). The modifications we made were minor but significant:

Sema V

Lock Acquire

Lock Release

Conditional Variable Wait