ft_ality

A functional programming project that implements a finite-state automaton to recognize fighting game combos and moves, inspired by Mortal Kombat's training mode.

📖 Table of Contents

• Overview
• Objectives
• Features
• Requirements
• Installation
• Usage
• Grammar File Format
• Project Structure
• Implementation Details
• Examples

🎮 Overview

ft_ality is a training mode simulator for fighting games that uses finite-state automata to recognize move combinations. The project demonstrates key concepts in formal language theory and compiler design:

• Finite-State Automata (FSA): The core recognition engine
• Regular Languages: Moves are regular languages that can be recognized by FSA
• Tokenization: Breaking down input sequences into recognizable tokens
• Real-time Input Processing: Interactive keyboard/gamepad input handling

Think of it as a sophisticated pattern matcher where combos are "words" made up of button presses as "symbols", and the automaton recognizes valid sequences.

🎯 Objectives

This project teaches fundamental concepts in:

• Formal Grammars and the Chomsky Hierarchy
• Regular Languages (Type 3 languages)
• Finite-State Machines and automaton theory
• Functional Programming principles and best practices
• Syntactic Analysis (parsing) foundations

✨ Features

Mandatory Features

• Dynamic Automaton Building: Constructs a finite-state automaton from grammar files at runtime
• Real-time Input Recognition: Processes keyboard input and recognizes valid move combinations
• Automatic Key Mapping: Generates key bindings from grammar definitions
• Multiple Move Recognition: Detects when multiple moves share the same input sequence
• Grammar File Support: Flexible grammar file format for defining moves and key mappings

Bonus Features

• Graphical Interface: SDL2-based visual display with automaton visualization
• Code Optimization: Tail-recursive functions and efficient memory management
• Functional Programming: Pure functional design with minimal mutations
• Debug Mode: Step-by-step automaton state visualization
• Gamepad Support: Optional joystick/arcade stick input handling

📋 Requirements

System Requirements

• GHC (Glasgow Haskell Compiler) 8.0 or higher
• SDL2 libraries (for graphical interface)
• SDL2_ttf (for text rendering)

🚀 Installation

1. Install System Dependencies

On Ubuntu/Debian:

./haskell_install.sh

This script will:

• Install GHCUP in path: .ghcup/
• Make ghcup install the recommanded version of ghc in .ghcup/

2. Install SDL2 Libraries

To install SDL2 locally, use the provided installation script:

bash sdl2-install.sh

This script will:

• Install the latest Cabal
• Download and compile SDL2 from source
• Install SDL2_ttf
• Configure library paths
• Install Haskell SDL2 bindings

3. Build the Project

make

This compiles the project with optimizations enabled and creates the ft_ality executable.

Other Make Targets

make clean      # Remove build artifacts
make fclean     # Remove build artifacts and binary
make re         # Clean rebuild

💻 Usage

Basic Usage

./ft_ality <grammar_file>

Example

./ft_ality grammars/mk1.gmr

Command-line Options

./ft_ality -h          # Show help message
./ft_ality --help      # Show help message

Interactive Mode

Once running, the program will:

1. Display the key mappings generated from the grammar
2. Open a graphical window (SDL2)
3. Wait for keyboard/gamepad input
4. Recognize and display matching moves in real-time

Press keys according to the displayed mapping, and when a valid combo is executed, the move name will be displayed!

📝 Grammar File Format

Grammar files define both key mappings and move rules using a simple text format.

Structure

[keymap]
<token> = <key>
...
[/keymap]

[grammar]
<sequence> -> <move_name>
...
[/grammar]

Example

[keymap]
U = w
D = s
F = d
B = a
FP = j
FK = k
BK = l
BP = i
[/keymap]

[grammar]
D, B, [FP] -> Hadouken (Ryu)
D, F, [FP] -> Shoryuken (Ryu)
B, D, B, [FK] -> Tatsumaki (Ryu)
[/grammar]

Key Mapping Section

• Format: <TOKEN> = <keyboard_key>
• Defines the mapping between abstract tokens and physical keyboard keys
• <TOKEN> can be any string (commonly: U, D, F, B for Up, Down, Forward, Back)
• <keyboard_key> are single characters representing keyboard keys

Grammar Section

• Format: <token1>, <token2>, ... -> <move_name>
• Defines move sequences using the tokens from the keymap
• Tokens in brackets [TOKEN] represent actual button presses
• Tokens without brackets (U, D, F, B) represent directional inputs
• Move names can include character names in parentheses

📁 Project Structure

ft_ality/
├── ft_ality.hs          # Main entry point
├── Makefile             # Build configuration
├── sdl2-install.sh      # SDL2 installation script
├── haskell_install.sh   # Haskell installation script
├── grammars/            # Grammar files
│   └── mk1.gmr          # Mortal Kombat 1 moves
└── srcs/                # Source modules
    ├── Automaton/
    │   └── Build.hs     # Automaton construction
    │   └── Run.hs       # Automaton runner
    │   └── Types.hs     # Automaton types definitions
    ├── Debug/
    │   └── Debug.hs     # Debug informations
    ├── Parser/
    │   └── Grammar.hs   # Grammar file parsing
    ├── Input/
    │   └── Keyboard.hs  # Input handling
    ├── UI/
    │   ├── Console.hs   # Console output
    │   └── Graphical.hs # SDL2 graphical interface
    ├── Utils/
    │   ├── Types.hs     # Type definitions
    │   └── Helpers.hs   # Utility functions
    └── ...

🔧 Implementation Details

Finite-State Automaton

The automaton is formally defined as a tuple: A = ⟨Q, Σ, Q₀, F, δ⟩

• Σ (Sigma): The input alphabet (button presses)
• Q: Set of states
• Q₀: Initial/starting state
• F: Set of accepting/recognition states
• δ (Delta): Transition function Q × Σ → Q

How It Works

1. Grammar Parsing: Reads the grammar file and extracts move definitions
2. Automaton Construction: Builds a finite-state machine where:
   • Each move creates a path through states
   • Shared prefixes reuse states (efficient)
   • Terminal states are marked as accepting states with associated move names
3. Input Processing:
   • Reads keyboard input in real-time
   • Follows transitions based on input symbols
   • When an accepting state is reached, the move is recognized
4. Output: Displays recognized moves through the graphical interface

Functional Programming Principles

This project follows functional programming best practices:

• Pure Functions: No side effects except in IO monad
• Immutability: Avoids mutable state (ref, mutable records, arrays)
• Tail Recursion: Recursive functions are tail-call optimized
• Type Safety: Leverages Haskell's strong type system
• Modular Design: Well-organized modules with clear interfaces
• Error Handling: Uses Maybe and Either types instead of exceptions (only one for IO exception at start)

📚 Examples

Example Output

Key mappings:
w -> Up
s -> Down
a -> Back
d -> Forward
j -> [FP]
k -> [FK]
l -> [BK]
i -> [BP]
----------------------

When you press s, a, j in sequence:

[FP]
Hadouken (Ryu) !!

Multiple Move Recognition

Some combos share prefixes and can recognize multiple moves:

[BP]
Claw Slam (Freddy Krueger) !!
Knockdown (Sonya) !!
Fist of Death (Liu-Kang) !!

---

"FINISH HIM!" - Mortal Kombat