10.2 - Algorithmic Thinking & Problem Decomposition

Algorithmic thinking is a problem-solving approach that involves breaking down complex problems into smaller, more manageable parts. This skill is essential for game developers who frequently face intricate challenges like implementing AI behavior, optimizing game performance, or creating procedural content generation systems.

What is Algorithmic Thinking?

Algorithmic thinking is a method of reasoning that focuses on:

1. Understanding the problem clearly and completely
2. Breaking it down into smaller, solvable sub-problems
3. Identifying patterns and relationships between components
4. Creating step-by-step solutions that can be implemented in code
5. Evaluating and refining those solutions for efficiency and correctness

The Problem-Solving Process

Let's explore a structured approach to solving programming problems:

1. Understand the Problem

Before writing any code, make sure you fully understand what you're trying to solve:

• What are the inputs?
• What are the expected outputs?
• What constraints exist?
• Are there any edge cases to consider?

2. Plan Your Approach

Develop a high-level strategy:

• Break the problem into smaller sub-problems
• Determine the order in which to solve these sub-problems
• Consider multiple approaches and their trade-offs
• Choose appropriate data structures and algorithms

3. Implement Your Solution

Translate your plan into code:

• Start with a simple implementation
• Focus on correctness first, optimization later
• Use meaningful variable and function names
• Add comments to explain complex logic

4. Test and Debug

Verify your solution works:

• Test with simple examples first
• Then test edge cases and larger inputs
• Debug any issues that arise
• Refine your solution as needed

5. Optimize (if necessary)

Improve your solution's efficiency:

• Identify bottlenecks
• Consider alternative algorithms or data structures
• Make targeted optimizations
• Measure performance before and after changes

Problem Decomposition Techniques

Breaking down problems is a crucial skill. Here are some effective techniques:

Divide and Conquer

The "divide and conquer" approach involves:

1. Breaking a problem into smaller, similar sub-problems
2. Solving each sub-problem independently
3. Combining the solutions to solve the original problem

Example: Binary Search

Binary search is a classic divide-and-conquer algorithm for finding an element in a sorted array:

public static int BinarySearch(int[] sortedArray, int target)
{
    int left = 0;
    int right = sortedArray.Length - 1;
    
    while (left <= right)
    {
        // Calculate middle index (avoiding overflow)
        int mid = left + (right - left) / 2;
        
        // Check if target is at the middle
        if (sortedArray[mid] == target)
        {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (sortedArray[mid] < target)
        {
            left = mid + 1;
        }
        // If target is smaller, ignore right half
        else
        {
            right = mid - 1;
        }
    }
    
    // Target not found
    return -1;
}

Stepwise Refinement

Stepwise refinement involves starting with a high-level description and progressively adding more detail:

1. Begin with a general outline of the solution
2. Refine each step into more detailed sub-steps
3. Continue until each step is simple enough to implement directly

Example: Character Movement System

Let's design a basic character movement system using stepwise refinement:

Level 1 (High-level):

1. Get player input
2. Calculate movement direction and speed
3. Apply movement to character
4. Handle collisions

Level 2 (More detailed):

1. Get player input
   1.1. Read horizontal input (left/right)
   1.2. Read vertical input (up/down)
   1.3. Normalize input vector if necessary

2. Calculate movement direction and speed
   2.1. Convert input to movement vector
   2.2. Apply movement speed
   2.3. Apply any modifiers (sprint, slow, etc.)

3. Apply movement to character
   3.1. Update position based on movement vector
   3.2. Update character orientation

4. Handle collisions
   4.1. Check for collisions with environment
   4.2. Resolve collisions by adjusting position

Level 3 (Implementation detail):

public class PlayerController
{
    public float moveSpeed = 5f;
    public float sprintMultiplier = 1.5f;
    
    private Vector2 position;
    private bool isSprinting;
    
    public void Update(float deltaTime)
    {
        // 1. Get player input
        float horizontalInput = GetHorizontalInput(); // -1 to 1
        float verticalInput = GetVerticalInput();     // -1 to 1
        
        // Normalize input if magnitude > 1 to prevent diagonal speed boost
        Vector2 inputVector = new Vector2(horizontalInput, verticalInput);
        if (inputVector.Magnitude() > 1f)
        {
            inputVector = inputVector.Normalize();
        }
        
        // Check sprint input
        isSprinting = IsSprintKeyPressed();
        
        // 2. Calculate movement direction and speed
        float currentSpeed = moveSpeed;
        if (isSprinting)
        {
            currentSpeed *= sprintMultiplier;
        }
        
        Vector2 movementVector = inputVector * currentSpeed * deltaTime;
        
        // 3. Apply movement to character
        Vector2 newPosition = position + movementVector;
        
        // 4. Handle collisions
        if (!WouldCollide(newPosition))
        {
            position = newPosition;
        }
        else
        {
            // Try to slide along walls (simplified)
            Vector2 horizontalMove = new Vector2(movementVector.X, 0);
            if (!WouldCollide(position + horizontalMove))
            {
                position += horizontalMove;
            }
            
            Vector2 verticalMove = new Vector2(0, movementVector.Y);
            if (!WouldCollide(position + verticalMove))
            {
                position += verticalMove;
            }
        }
        
        // Update character orientation
        UpdateOrientation(inputVector);
    }
    
    // Implementation of helper methods would go here
    private float GetHorizontalInput() { /* ... */ return 0; }
    private float GetVerticalInput() { /* ... */ return 0; }
    private bool IsSprintKeyPressed() { /* ... */ return false; }
    private bool WouldCollide(Vector2 position) { /* ... */ return false; }
    private void UpdateOrientation(Vector2 direction) { /* ... */ }
}

// Simple Vector2 implementation for this example
public struct Vector2
{
    public float X { get; }
    public float Y { get; }
    
    public Vector2(float x, float y)
    {
        X = x;
        Y = y;
    }
    
    public static Vector2 operator +(Vector2 a, Vector2 b)
    {
        return new Vector2(a.X + b.X, a.Y + b.Y);
    }
    
    public static Vector2 operator *(Vector2 v, float scalar)
    {
        return new Vector2(v.X * scalar, v.Y * scalar);
    }
    
    public float Magnitude()
    {
        return (float)Math.Sqrt(X * X + Y * Y);
    }
    
    public Vector2 Normalize()
    {
        float mag = Magnitude();
        if (mag > 0)
        {
            return new Vector2(X / mag, Y / mag);
        }
        return this;
    }
}

Abstraction

Abstraction involves hiding complex implementation details behind simpler interfaces:

1. Identify the essential aspects of the problem
2. Create interfaces or abstractions that encapsulate complexity
3. Work with these abstractions rather than low-level details

Example: Inventory System

Let's design a simple inventory system using abstraction:

// Abstract base class for all items
public abstract class Item
{
    public string Name { get; protected set; }
    public string Description { get; protected set; }
    public int Value { get; protected set; }
    public float Weight { get; protected set; }
    
    public abstract void Use(Player player);
}

// Concrete implementation for a health potion
public class HealthPotion : Item
{
    public int HealAmount { get; private set; }
    
    public HealthPotion(int healAmount)
    {
        Name = "Health Potion";
        Description = $"Restores {healAmount} health points.";
        Value = healAmount * 10;
        Weight = 0.5f;
        HealAmount = healAmount;
    }
    
    public override void Use(Player player)
    {
        player.Heal(HealAmount);
        Console.WriteLine($"{player.Name} used {Name} and restored {HealAmount} health!");
    }
}

// Inventory class that manages items
public class Inventory
{
    private List<Item> items;
    private float maxWeight;
    
    public Inventory(float maxWeight)
    {
        items = new List<Item>();
        this.maxWeight = maxWeight;
    }
    
    public bool AddItem(Item item)
    {
        if (GetTotalWeight() + item.Weight <= maxWeight)
        {
            items.Add(item);
            return true;
        }
        return false;
    }
    
    public bool RemoveItem(Item item)
    {
        return items.Remove(item);
    }
    
    public float GetTotalWeight()
    {
        float total = 0;
        foreach (Item item in items)
        {
            total += item.Weight;
        }
        return total;
    }
    
    public void ListItems()
    {
        Console.WriteLine("Inventory Contents:");
        if (items.Count == 0)
        {
            Console.WriteLine("  Empty");
            return;
        }
        
        foreach (Item item in items)
        {
            Console.WriteLine($"  {item.Name} - {item.Description} (Value: {item.Value}, Weight: {item.Weight})");
        }
        
        Console.WriteLine($"Total Weight: {GetTotalWeight()}/{maxWeight}");
    }
}

// Simple Player class for this example
public class Player
{
    public string Name { get; private set; }
    public int Health { get; private set; }
    public int MaxHealth { get; private set; }
    public Inventory Inventory { get; private set; }
    
    public Player(string name, int maxHealth)
    {
        Name = name;
        MaxHealth = maxHealth;
        Health = maxHealth;
        Inventory = new Inventory(50f); // Player can carry 50 weight units
    }
    
    public void Heal(int amount)
    {
        Health = Math.Min(Health + amount, MaxHealth);
    }
}

Game Development Example: Wave Spawner

Let's apply algorithmic thinking to design a wave-based enemy spawner for a tower defense game:

Problem: Create a system that spawns increasingly difficult waves of enemies over time.

Step 1: Understand the Problem

• Inputs: Wave number, available enemy types, spawn points
• Outputs: Sequence of enemy spawns with timing
• Constraints: Balanced difficulty progression, performance considerations

Step 2: Break Down the Problem

1. Define wave difficulty progression
2. Determine enemy composition for each wave
3. Handle the spawning logic and timing
4. Track wave state (active, completed)

Step 3: Design the Solution

public class WaveSpawner
{
    // Enemy types with their difficulty ratings
    private Dictionary<EnemyType, int> enemyDifficultyRatings;
    
    // Spawn points
    private List<Vector2> spawnPoints;
    
    // Wave configuration
    private int currentWave = 0;
    private bool waveActive = false;
    private int baseDifficulty = 10;
    private float difficultyMultiplier = 1.5f;
    private float timeBetweenWaves = 30f;
    private float timeBetweenSpawns = 1.5f;
    
    // Tracking
    private List<Enemy> activeEnemies = new List<Enemy>();
    private float waveTimer;
    private float spawnTimer;
    
    public WaveSpawner(List<Vector2> spawnPoints)
    {
        this.spawnPoints = spawnPoints;
        
        // Initialize enemy difficulty ratings
        enemyDifficultyRatings = new Dictionary<EnemyType, int>
        {
            { EnemyType.Basic, 1 },
            { EnemyType.Fast, 2 },
            { EnemyType.Armored, 3 },
            { EnemyType.Boss, 10 }
        };
        
        waveTimer = timeBetweenWaves;
    }
    
    public void Update(float deltaTime)
    {
        // Update timers
        if (!waveActive)
        {
            waveTimer -= deltaTime;
            if (waveTimer <= 0)
            {
                StartNextWave();
            }
        }
        else
        {
            // Handle enemy spawning during active wave
            spawnTimer -= deltaTime;
            if (spawnTimer <= 0 && HasRemainingEnemiesInWave())
            {
                SpawnNextEnemy();
                spawnTimer = timeBetweenSpawns;
            }
            
            // Check if wave is complete
            if (!HasRemainingEnemiesInWave() && activeEnemies.Count == 0)
            {
                EndWave();
            }
        }
        
        // Clean up destroyed enemies
        activeEnemies.RemoveAll(e => !e.IsAlive);
    }
    
    private void StartNextWave()
    {
        currentWave++;
        waveActive = true;
        
        // Calculate wave difficulty
        int waveDifficulty = (int)(baseDifficulty * Math.Pow(difficultyMultiplier, currentWave - 1));
        
        // Generate enemy composition based on difficulty
        GenerateWaveComposition(waveDifficulty);
        
        spawnTimer = 0; // Spawn first enemy immediately
        
        Console.WriteLine($"Wave {currentWave} started! Difficulty: {waveDifficulty}");
    }
    
    private void EndWave()
    {
        waveActive = false;
        waveTimer = timeBetweenWaves;
        Console.WriteLine($"Wave {currentWave} completed! Next wave in {timeBetweenWaves} seconds.");
    }
    
    private Queue<EnemyType> waveEnemies = new Queue<EnemyType>();
    
    private void GenerateWaveComposition(int waveDifficulty)
    {
        waveEnemies.Clear();
        int remainingDifficulty = waveDifficulty;
        
        // Always include at least some basic enemies
        int minimumBasicEnemies = Math.Max(3, currentWave / 2);
        for (int i = 0; i < minimumBasicEnemies; i++)
        {
            waveEnemies.Enqueue(EnemyType.Basic);
            remainingDifficulty -= enemyDifficultyRatings[EnemyType.Basic];
        }
        
        // Add boss enemy every 5 waves
        if (currentWave % 5 == 0 && currentWave > 0)
        {
            waveEnemies.Enqueue(EnemyType.Boss);
            remainingDifficulty -= enemyDifficultyRatings[EnemyType.Boss];
        }
        
        // Fill remaining difficulty with a mix of enemies
        Random random = new Random();
        List<EnemyType> availableTypes = new List<EnemyType>();
        
        // Unlock enemy types based on wave number
        if (currentWave >= 1) availableTypes.Add(EnemyType.Basic);
        if (currentWave >= 3) availableTypes.Add(EnemyType.Fast);
        if (currentWave >= 5) availableTypes.Add(EnemyType.Armored);
        
        while (remainingDifficulty > 0 && availableTypes.Count > 0)
        {
            // Filter to enemy types we can afford
            List<EnemyType> affordableTypes = availableTypes
                .Where(t => enemyDifficultyRatings[t] <= remainingDifficulty)
                .ToList();
            
            if (affordableTypes.Count == 0) break;
            
            // Select random enemy type
            EnemyType selectedType = affordableTypes[random.Next(affordableTypes.Count)];
            waveEnemies.Enqueue(selectedType);
            remainingDifficulty -= enemyDifficultyRatings[selectedType];
        }
        
        Console.WriteLine($"Generated wave with {waveEnemies.Count} enemies");
    }
    
    private bool HasRemainingEnemiesInWave()
    {
        return waveEnemies.Count > 0;
    }
    
    private void SpawnNextEnemy()
    {
        if (!HasRemainingEnemiesInWave()) return;
        
        EnemyType enemyType = waveEnemies.Dequeue();
        
        // Select random spawn point
        Random random = new Random();
        Vector2 spawnPosition = spawnPoints[random.Next(spawnPoints.Count)];
        
        // Create enemy
        Enemy enemy = CreateEnemy(enemyType, spawnPosition);
        activeEnemies.Add(enemy);
        
        Console.WriteLine($"Spawned {enemyType} enemy at position {spawnPosition.X}, {spawnPosition.Y}");
    }
    
    private Enemy CreateEnemy(EnemyType type, Vector2 position)
    {
        // In a real game, this would instantiate the actual enemy GameObject
        switch (type)
        {
            case EnemyType.Fast:
                return new FastEnemy(position);
            case EnemyType.Armored:
                return new ArmoredEnemy(position);
            case EnemyType.Boss:
                return new BossEnemy(position);
            case EnemyType.Basic:
            default:
                return new BasicEnemy(position);
        }
    }
}

// Enum for enemy types
public enum EnemyType
{
    Basic,
    Fast,
    Armored,
    Boss
}

// Base Enemy class
public abstract class Enemy
{
    public Vector2 Position { get; protected set; }
    public bool IsAlive { get; protected set; } = true;
    
    public Enemy(Vector2 position)
    {
        Position = position;
    }
    
    public abstract void Update(float deltaTime);
}

// Enemy implementations
public class BasicEnemy : Enemy
{
    public BasicEnemy(Vector2 position) : base(position) { }
    
    public override void Update(float deltaTime)
    {
        // Basic enemy movement and behavior
    }
}

public class FastEnemy : Enemy
{
    public FastEnemy(Vector2 position) : base(position) { }
    
    public override void Update(float deltaTime)
    {
        // Fast enemy movement and behavior
    }
}

public class ArmoredEnemy : Enemy
{
    public ArmoredEnemy(Vector2 position) : base(position) { }
    
    public override void Update(float deltaTime)
    {
        // Armored enemy movement and behavior
    }
}

public class BossEnemy : Enemy
{
    public BossEnemy(Vector2 position) : base(position) { }
    
    public override void Update(float deltaTime)
    {
        // Boss enemy movement and behavior
    }
}

This example demonstrates several algorithmic thinking principles:

1. Problem decomposition: Breaking the wave spawner into distinct components (wave generation, enemy spawning, wave management)
2. Abstraction: Using classes and inheritance to manage different enemy types
3. Stepwise refinement: Starting with high-level wave management and refining to specific enemy spawning details

Developing Your Algorithmic Thinking Skills

Improving your algorithmic thinking takes practice. Here are some strategies:

1. Solve programming puzzles: Platforms like LeetCode, HackerRank, and CodeWars offer algorithmic challenges
2. Analyze existing algorithms: Study how common algorithms work and why they're designed that way
3. Implement from scratch: Try implementing standard algorithms without looking at reference code
4. Review and refactor: Regularly review your code and look for ways to improve it
5. Learn from others: Study open-source code and see how experienced developers solve problems

Unity Relevance

In Unity development, algorithmic thinking is particularly valuable for:

1. Game mechanics: Designing systems like combat, inventory, or crafting
2. AI behavior: Creating intelligent and responsive NPCs
3. Procedural generation: Generating levels, terrain, or content
4. Optimization: Improving performance in resource-intensive games
5. Editor tools: Creating custom tools to streamline your workflow

Unity's component-based architecture encourages breaking down problems into manageable pieces, which aligns perfectly with algorithmic thinking principles.

Conclusion

Algorithmic thinking and problem decomposition are foundational skills for any programmer, but they're especially crucial for game developers who often face complex, interconnected systems. By breaking down problems, identifying patterns, and building solutions step by step, you can tackle even the most challenging game development tasks.

In the next section, we'll explore basic searching algorithms, which are essential tools for finding information in your game's data structures.