Game AI: Pathfinding, Decision Trees, and Behavior Trees

Advanced Game AI Techniques for Autonomous Agents

By Anjan Diyora (adiyora)

---

📋 Overview

This project is a comprehensive implementation of advanced Game AI techniques, demonstrating high-performance pathfinding algorithms, sophisticated agent behaviors using Behavior Trees, and machine learning-based decision-making through Decision Tree Learning. The project showcases a complete workflow from hand-crafted AI systems to machine learning-optimized solutions, achieving 45% faster decision-making while maintaining equivalent behavior.

✨ Key Features

🎯 High-Performance Pathfinding

• Dijkstra's Algorithm: Complete implementation for optimal pathfinding
• A Search Algorithm*: Enhanced with multiple heuristic functions
• Large-Scale Optimization: Handles graphs with up to 10,000 nodes and 100 million edges
• Advanced Heuristics: Manhattan distance and Haversine formula for 2D grids and geographical coordinates

🤖 Advanced Steering Behaviors

• Velocity Matching: Synchronized agent movement
• Orientation Matching: Coordinated agent rotation
• Position Matching: Precise spatial alignment
• Wander Behavior: Natural autonomous movement patterns
• Flocking Behavior: Emergent group behaviors with multiple agents

🌳 Behavior Trees

• Modular Decision-Making: Complex, stateful agent AI
• Hand-Crafted Logic: Sophisticated behavior tree implementation
• Interactive Visualization: Real-time behavior visualization using SFML

🧠 Machine Learning Integration

• Decision Tree Learning: Custom implementation from scratch in Python
• Data Generation Pipeline: Automated telemetry collection from game sessions
• Model Training: Gini impurity-based classifier training
• Performance Optimization: 45% faster decision-making compared to Behavior Trees

🛠️ Tech Stack

Technology	Purpose
C++17	Core simulation, pathfinding, and agent logic
Python 3	Decision Tree Learning algorithm
SFML 2.5	2D graphics, windowing, and visualization
Boost C++	Graph data structures and algorithms

📁 Project Structure

Game-AI-Pathfinding-Decision-Trees-and-Behavior-Trees-master/
│
├── 01_Basic_Agent_Behaviors/          # Fundamental agent behaviors
│   └── adiyora_solution/
│       ├── Task_2/                    # Basic movement behaviors
│       └── Task_3/                     # Advanced interaction patterns
│
├── 02_Steering_Behaviors/              # Autonomous steering behaviors
│   ├── task1/                          # Velocity matching
│   ├── task2/                          # Orientation & position matching
│   ├── task3_final/                    # Wander behavior (optimized)
│   └── task4/                          # Flocking behavior
│
├── 03_Pathfinding_Algorithms/          # Pathfinding implementations
│   └── adiyora_solution/
│       ├── Task2-small/                # Small graph pathfinding
│       ├── Task2-large/                # Large graph optimization
│       ├── Task3/                      # Heuristic analysis
│       └── Task4/                      # SFML visualization
│
└── 04_Behavior_Trees_and_Decision_Trees/  # AI decision-making systems
    └── Submit/
        ├── Task1/                      # Manual decision tree
        ├── Task2/                      # Behavior tree implementation
        ├── Task3/                      # Learned decision tree
        ├── Task3_data_collection_new/  # Data generation
        └── DecisionTreeLearning.py     # ML training script

🚀 Getting Started

Prerequisites

• C++ Compiler (GCC 7+ or Clang 5+)
• Python 3.6+
• CMake (optional, for some modules)
• SFML 2.5+
• Boost C++ Libraries

Installation

Linux (Ubuntu/Debian)

# Update package lists
sudo apt-get update

# Install Boost libraries
sudo apt-get install libboost-all-dev

# Install SFML
sudo apt-get install libsfml-dev

# Install Python 3
sudo apt install python3

macOS

# Using Homebrew
brew install boost sfml python3

Windows

• Install vcpkg or use pre-built libraries
• Install Boost and SFML through vcpkg or download pre-compiled binaries
• Install Python 3 from python.org

🎮 Usage

Running C++ Modules

Each module can be built and run independently:

# Navigate to the desired module
cd 02_Steering_Behaviors/task1

# Clean previous builds (optional)
rm -rf main main.o

# Compile
make

# Run
./main

Training Decision Tree Model

1. Generate Training Data:

   cd 04_Behavior_Trees_and_Decision_Trees/Submit/Task3_data_collection_new
   make
   ./main
   # This generates data.csv with agent telemetry

2. Train the Model:

   cd 04_Behavior_Trees_and_Decision_Trees/Submit
   python3 DecisionTreeLearning.py

3. Implement Learned Tree:

   • Copy the output tree structure from the Python script
   • Implement it in Task3/main.cpp
   • Build and run to see optimized AI behavior

📊 Performance Metrics

Metric	Behavior Tree	Learned Decision Tree	Improvement
Decision Time	Baseline	45% faster	⚡ 45%
Behavior Accuracy	100%	100%	✅ Equivalent
Code Complexity	High	Low	📉 Reduced

🎨 Visualizations

The project includes interactive visualizations for:

• Pathfinding Algorithms: Real-time path computation and visualization
• Steering Behaviors: Agent movement patterns and flocking
• Behavior Trees: Decision-making process visualization
• Decision Trees: Learned tree structure representation

Screenshots and visual outputs are available in each module's screenshots/ directory.

🔬 Technical Highlights

Pathfinding Algorithms

• Dijkstra's Algorithm: Guaranteed shortest path finding
• A Search*: Optimal pathfinding with heuristic guidance
• Heuristic Functions:
  • Manhattan distance for grid-based navigation
  • Haversine formula for geographical coordinates
• Large-Scale Optimization: Efficient handling of massive graphs

Steering Behaviors

• Kinematic Steering: Direct velocity and rotation control
• Dynamic Steering: Acceleration-based movement with realistic physics
• Flocking: Emergent behaviors through local rules (separation, alignment, cohesion)

Behavior Trees

• Composite Nodes: Sequences, selectors, and decorators
• Leaf Nodes: Actions and conditions
• State Management: Persistent blackboard for agent memory
• Modularity: Reusable behavior components

Machine Learning

• Decision Tree Learning: Custom implementation using Gini impurity
• Feature Engineering: Environment state and agent context
• Data Collection: Automated telemetry from game sessions
• Model Translation: From Python to optimized C++ implementation

📚 Module Descriptions

Module 1: Basic Agent Behaviors

Fundamental agent movement and interaction patterns. Demonstrates core concepts of agent-based systems.

Module 2: Steering Behaviors

Advanced autonomous steering behaviors including velocity matching, orientation control, wander patterns, and emergent flocking behaviors.

Module 3: Pathfinding Algorithms

High-performance pathfinding implementations with support for both small and large-scale graphs, including visual demonstrations.

Module 4: Behavior Trees and Decision Trees

Complete AI decision-making system showcasing:

• Hand-crafted Behavior Trees for complex agent logic
• Machine learning pipeline for data collection and model training
• Optimized Decision Tree implementation achieving 45% performance improvement

🤝 Contributing

This is a portfolio project demonstrating advanced Game AI techniques. For questions or discussions, please refer to the implementation details in each module's README.

📝 License

This project is for educational and portfolio purposes.

👤 Author

Anjan Diyora (adiyora)

• Portfolio project demonstrating Game AI expertise
• Implementation of pathfinding, steering behaviors, and machine learning for game AI

🙏 Acknowledgments

• SFML community for excellent graphics library
• Boost C++ Libraries for graph data structures
• Game AI research community for algorithms and techniques

---

Built with ❤️ for Game AI Development

⭐ Star this repo if you find it helpful!