Combo DFA Project

Overview

For a class final project, another student and I teamed up to make a fighting game combo system using Deterministic Finite Automata. The system detects when a series of inputs is executed quickly in order, but does so more efficiently and with more customization than other methods.

On top of this, we created a level generation system that places level chunks together in a way that ensures the pattern will never repeat! This is due to the wonderful (and confusing) properties of the Thue-More sequence, which we used in combination with another DFA to make cool random levels.

ROLES:

Co-programmer on DFA combo system. Independently responsible for Thue-Morse level generation, player movement, and general polish

DURATION:

2 Weeks

ENGINE:

Unity

PLATFORMS:

Windows

My Contributions

Used pair-programming to co-develop the DFA generation and combo system
- I led these pair-programming sessions, sketching out my ideas and programming for a majority of the time

Developed the script for level generation using the Thue-Morse sequence, stringing together different level chunks in a way that ensures the pattern of chunks will never repeat

Hooked together successful combo execution with unique animations

Added a small menu to remind players of the possible combos

Presented our project at the 2023 Spring MSCS Department Conference along with 3 other excellent student projects from other classes

DFAs: What is it?

A Deterministic Finite Automata is a state machine that accepts an input, usually a series of characters or numbers, and follows the transitions between states to arrive at a final state, the output.

A DFA representing all binary numbers divisible by 3

How did we represent that programatically?

We used a 2d array of integers with each element of the outer array representing a different state in the DFA. Index 0 was our reset state, where no combo string is being tracked.

Each inner array holds 6 integers, 1 for each of the possible inputs a player could perform. When the player executes a new input, the system will grab the number of the next state to go to, found by grabbing the outer array element at the current state number and the inner array element specified for that input.

Here's an example. Say we're at index 0, our reset state. The player presses the Punch button. To find the next state:

The system goes to the outer array element 0, as that's our current state
The system grabs the 1st element of the inner array, as that's the element for punch

Detecting Combos

With our system, we had a problem. How can we detect when a combo is reached?

Our solution was to have another common state, this one called the goal state! We gave it the index -1, and whenever the system was told to travel to the goal state we did a couple things:

As we traversed the graph, we added each new input to a string. When the system tried to travel to the goal state, we looked up the input string in a dictionary where each combo string was the key to the combo we were trying to execute.
- An example might be "pklr" : "Hadouken"
We then traveled to state 0, resetting the input string and getting ready to detect another combo

To the left are a couple graphs depicting this process. It should be noted that if at any point the player executes an input that could not lead to a combo, the next index will be the reset state (index 0).

Pros and Cons of this system

Pros

Very Quick - By using an array lookup, we can travel through the DFA very quickly
Highly Customizable - Because we generate the DFA array at runtime, you can easily change the combo to be (almost) any series of inputs. You can also easily change the move that gets executed after the combo, letting you turn the "uudl" combo from a whirlwind kick to a uppercut punch easily.

Cons

Can't Handle Combo Substrings - If we have a combo for "pkp" and a combo for "pkpk", then the second combo can never be reached as the first will lead to the success state (-1).
Not Forgiving of Mistakes - Lets say a player is trying to execute a 4 input combo but messes up at the second input, returning to the reset state. The next 2 inputs could lead to a new state, confusing a player that might be executing the next combo under the assumption that they're at the reset state.

Take a look!

Here I'm imputing different combos and showing the results. You can see the system detects when I do a combo properly, and resets when I fail (which I do at the very start)

What about that Thue-Morse Stuff?

The Thue-Morse Sequence...

is a sequence of 1s and 0s that can never repeat. It has a ton of cool mathematical implications, like being the fairest order for picking players in team sports.

We used it to select which level chunk to load next. Each 1 or 0 gives us the transition from the current level chunk to the next. For example, using the example below we can see that getting a 0 in the sequence while at state "Out 2" will have us travel to "Out 3".

Fun Fact:

The Thue-Morse Sequence can be calculated by counting up in binary and taking the number of 1s mod 2.

Take a look!

Due to the extremely small number of level chunks we're using there's a ton of repetition, but it was definitely a cool thing to implement and I'm glad we did!