Automatic generation of enemies in a survival computer game

Michal Baránek

Supervisor: Alexander Šimko

Introduction

The Evolution of Game AI

AI has been crucial since the earliest arcade systems. As games became larger and more dynamic, developers faced a new challenge.
The systems needed to be predictable, efficient, and understandable.

Behavior Trees

Behavior Trees (BTs) emerged as the dominant framework for scalable decision-making.

What Are Behavior Trees?

A hierarchical model representing AI logic as a directed tree of nodes, determining how an agent chooses actions.


  • Hierarchical Structure Decisions flow Parent to Child, ensuring readability.
  • Control Flow Composites (Selectors, Sequences) dictate execution flow.
  • Leaf Nodes Tasks trigger actual gameplay actions.
  • Deterministic Consistent behavior given the same world state.

Advantages of Behavior Trees

  • Modularity Extend or reorganize logic without rewriting entire systems.
  • Reusability Subtrees can be shared across different NPC types.
  • Debuggability Visual editors (like Unreal's) allow step-by-step inspection.
  • Scalability Handles both simple and complex logic efficiently.

Genetic Programming (GP)

An evolutionary computation technique that evolves computer programs, typically represented as tree structures.

  • Tree Representation: GP and BT's are inherently hierarchical.
  • Subtree Crossover: Swapping branches works naturally in both.
  • Mutation: Inserting/removing nodes mirrors code mutation.

The Problem

The manual design of BTs for autonomous agents creates these complications:

  • Time Consuming Manual authoring is iterative and slow. Tweak → Compile → Test loop is inefficient.
  • Designer Bias We only build logic we can predict. This limits exploration of novel strategies.
  • Scalability As complexity grows, maintaining massive BTs becomes unmanageable.
  • Need: Automated Exploration

Framework

  • Direct Evolution Works directly with real UBehaviorTree node structures.
  • No Symbolic DNA Evolution happens on concrete memory objects, not a string abstraction.
  • Offline Tool An AI training tool for developers, not a runtime learner for shipped games.

System Architecture

  • Simulation Manager The "God Object" controlling the full evolutionary loop.
  • Dynamic Constructor Creates and modifies UBehaviorTree nodes in memory.
  • AI Controller Wrapper Executes the generated BTs on agents.
  • Fitness Tracker Monitors metrics (Survival, Damage, Navigation).

Simulation Environment

Benchmark Mode

Uses -benchmark launch option.

Ensures Deterministic, Maximum-FPS simulation speed.

  • Controlled Arena Predictable testing environment.
  • Population Supports Single-Agent evaluation setups.

Fitness Metrics

  • Survival Time Duration alive in hostile environment.
  • Damage Dealt Aggression towards player/objectives.
  • Time to kill Duration to kill player.

And many more planned.

Genetic Algorithm Workflow

1. Selection

2. Crossover

3. Mutation

Mutation (Tree Editing)

  • Replace Type Change Sequence to Select
  • Insert Task Add new leaf
  • Prune Remove branch
  • Swap Order Reorder execution

Challenges

  • Reachability Preventing logic bottlenecks where a single dominant branch blocks the execution of others.
  • Complexity Large trees degrade comprehensibility and evolution speed.
  • Fitness Shaping "You get what you measure" (e.g. passive survival vs active combat).

Current Implementation Status

Key milestones achieved in the prototype.

  • Modularisation Decoupled core evolutionary logic from game-specific mechanics.
  • Persistence & Visualization Load/Save BTs with auto-generated visual graphs for inspection.
  • Deterministic Speedup Faster than real-world simulation.
  • Use of Headless Mode Supports command-line execution for faster training cycles.
  • Simulation Loop Mutation, simulation, evaluation.
  • Fitness Evaluation Multi-part scoring system.
  • Custom Log Output Structured data export for easier debugging.

Genetic Evolution Pipeline

Function OnLevelReload(World):
    TargetWorld = World 
    ActiveAgent = null 
    PreparePlayer() 
    RunEvolutionStep() 

Function RunEvolutionStep():
    CandidateTree = NewTree(BestTree) // Hill Climbing Logic
    Mutate(CandidateTree)
    
    // Spawn & Possess
    SpawnPos = GetSpawnLocation() 
    Enemy = SpawnActor(EnemyClass, SpawnPos)
    Controller = SpawnActor(AIClass, SpawnPos) 
    Controller.Possess(Enemy) 

    // Assign Tree & Track
    BehaviourTree = TreeWrapper.AssignTree(CandidateTree)
    Controller.AssignTree(BehaviourTree, BlackboardData)
    ActiveAgent = {Enemy, TreeWrapper, Controller}
    StartSimulation(30.0) 

Function StartSimulation(Timeout):
    UnpauseGame()
    Wait(2.0) // Physics warmup
    ActiveAgent.Controller.RunAssignedTree()
    ActiveAgent.FitnessTracker.BeginTracking()
    SetTimer(StopSimulation, Timeout)

Function StopSimulation():
    PauseGame()
    Fitness = ActiveAgent.FitnessTracker.CalculateFitness()

    // Restart
    GenerationCount++
    OpenLevel(CurrentLevelName)

Results Preview

Quantifying speedup & visualizing intelligence.

Simulation Speedup

Benchmark Mode

By decoupling game logic from rendering framerate, we achieve massive time acceleration.

30 seconds of gameplay ≈ 1 second of compute. 


[23.40.33:467]LogGeneticGeneration: Warmup Complete. 
[23.40.34:477]LogGeneticGeneration: TIMEOUT! Simulation time limit reached.

Log snippet showing a full 30 second timeout simulating in 1 second.

Generation 0: The Baseline


[LogGeneticGeneration] --- STARTING WORKFLOW ---
[LogTemp] LoadBehaviorTree: Loaded BT_EnemyUnleashed

// INITIAL STRUCTURE
[LogTemp] Display: L-- Sequence
[LogTemp] Display:      |-- CheckAreaForPlayer
[LogTemp] Display:      |-- MoveToPlayer
[LogTemp] Display:      L-- Attack

[LogGeneticGeneration] [Step 1] Loaded Original.
[LogTemp] Found 3 valid Task classes for mutation.

Status

Hand-authored logic. Standard patrol behavior.

Structure: Check → Move → Attack

Generation 1: Mutation


// MUTATION EVENT: INSERTION
[LogTemp] MutateTree: Inserted BTTask_Attack_C_1

[LogGeneticGeneration] [Step 2] Mutated (In-Memory)
[LogGeneticGeneration] [Step 3] Saved Gen1.uasset

// NEW STRUCTURE
[LogTemp] Display: L-- Sequence
[LogTemp] Display:      |-- CheckAreaForPlayer
[LogTemp] Display:      |-- MoveToPlayer
[LogTemp] Display:      |-- Attack
[LogTemp] Display:      L-- Attack

Change: Added second Attack node.

Generation 2: Refinement


// MUTATION EVENT: REPLACEMENT
[LogTemp] MutateTree: Replaced CheckArea with MoveTo

[LogGeneticGeneration] [Step 5] Mutated (In-Memory)
[LogGeneticGeneration] [Step 6] Saved Gen2.uasset

// FINAL STRUCTURE
[LogTemp] Display: L-- Sequence
[LogTemp] Display:      |-- MoveToPlayer
[LogTemp] Display:      |-- MoveToPlayer
[LogTemp] Display:      |-- Attack
[LogTemp] Display:      L-- Attack

Change: Replaced CheckAreaForPlayer initial logic.

Insights from Literature

Foundational research validating the BGEN approach.

Constructing Complex NPC Behavior via Multi-Objective Neuroevolution

Schrum & Miikkulainen (2008)

  • Multi-Objective Evolution Uses Pareto Fronts to balance objective rewards. Bots excelling at one task but failing others are overtaken by universal bots.
  • Emergent Strategy Evolving produced roles and complex strategies: Baiting, Retreating, Flanking, and Coordinated Attacks.
  • Group Fitness Averaging group fitness ranked cooperative teams higher than individualistic bots.
The Loop

1. Start with simple player behavior.
2. Identify promising bot individuals.
3. Increase player complexity.
4. Further evolve bots against new challenge.

Procedural Enemy Generation through Parallel Evolutionary Algorithm

Pereira et al. (2021)

  • Goal [cite_start]Automatically generate diverse, balanced enemies matching a required difficulty[cite: 5431, 5456].
  • Attribute Adjustment [cite_start]Evolution adjusts stats (Health, Damage, Speed) rather than logic[cite: 5398].
  • Parallel Evolutionary Algorithm [cite_start]Uses Behavior Trees evolved in parallel to ensure performance[cite: 5437, 5438].
Fitness Calculation From Stats
$$ f_w = damage \times weapon $$
$$ f_m = movement\_speed \times movement $$
$$ f = health + active + \frac{1}{rest} + f_W + f_p + f_m $$

AI in Computer Games: Generating Interesting Interactive Opponents by the use of Evolutionary Computation

Georgios N. Yannakakis

1. Challenge ($T$)

Too many or too few steps to kill the player is not optimal.

$$ T = (1 - \frac{E\{t_k\}}{max\{t_k\}})^{p_1} $$

2. Behavior ($S$)

Higher standard deviation of steps taken to kill = more interesting.

$$ S = (\frac{\sigma_{t_k}}{\sigma_{max}})^{p_2} $$

3. Spatial ($H_n$)

Entropy of predator visits across regions (cells) of the world.

$$ H_n = [\frac{-1}{\log V_n} \sum \frac{v_{in}}{V_n} \log ...]^{p_3} $$

Future Work

  • Mutation penalties Penalize BTs with large trees
  • Multi-Objective Fitness Pareto optimization for complex traits.
  • Group Fitness Averaging fitness of multiple agents to promote teamwork
  • Distributed Evaluation Parallel simulation across cores.

Thank you