Skip to main content

10.3 - Basic Searching Algorithms

Searching is one of the most common operations in game development. Whether you're finding an item in a player's inventory, locating the nearest enemy, or determining a path through a level, efficient searching algorithms are essential for creating responsive and performant games.

Introduction to Searching​

A searching algorithm is a method for finding a specific item (or items) within a collection of data. The efficiency of a searching algorithm is typically measured by:

  1. Time complexity: How long it takes to find an item
  2. Space complexity: How much memory is required during the search
  3. Preprocessing requirements: Whether the data needs to be organized in a specific way before searching

Let's explore some fundamental searching algorithms and their applications in game development.

The simplest searching algorithm is linear search (also called sequential search), which checks each element in a collection one by one until it finds the target or reaches the end.

Implementation​

public static int LinearSearch<T>(T[] array, T target) where T : IEquatable<T>
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i].Equals(target))
        {
            return i; // Return the index of the found item
        }
    }
    
    return -1; // Item not found
}

Characteristics​

  • Time Complexity: O(n) - In the worst case, we need to check all n elements
  • Space Complexity: O(1) - Uses a constant amount of extra space
  • Advantages: Simple to implement, works on unsorted data
  • Disadvantages: Inefficient for large collections
public class InventoryItem
{
    public string Id { get; }
    public string Name { get; }
    public int Quantity { get; set; }
    
    public InventoryItem(string id, string name, int quantity)
    {
        Id = id;
        Name = name;
        Quantity = quantity;
    }
    
    public override bool Equals(object obj)
    {
        if (obj is InventoryItem other)
        {
            return Id.Equals(other.Id);
        }
        return false;
    }
    
    public override int GetHashCode()
    {
        return Id.GetHashCode();
    }
}

public class Inventory
{
    private List<InventoryItem> items = new List<InventoryItem>();
    
    public bool HasItem(string itemId)
    {
        // Linear search through inventory items
        for (int i = 0; i < items.Count; i++)
        {
            if (items[i].Id == itemId)
            {
                return true;
            }
        }
        
        return false;
    }
    
    public InventoryItem GetItem(string itemId)
    {
        // Linear search to find an item by ID
        for (int i = 0; i < items.Count; i++)
        {
            if (items[i].Id == itemId)
            {
                return items[i];
            }
        }
        
        return null; // Item not found
    }
    
    public void AddItem(InventoryItem item)
    {
        items.Add(item);
    }
    
    // Other inventory methods...
}

Binary search is a much more efficient algorithm for finding items in a sorted collection. It works by repeatedly dividing the search range in half.

Implementation​

public static int BinarySearch<T>(T[] sortedArray, T target) where T : IComparable<T>
{
    int left = 0;
    int right = sortedArray.Length - 1;
    
    while (left <= right)
    {
        // Calculate middle index (avoiding potential overflow)
        int mid = left + (right - left) / 2;
        
        // Compare middle element with target
        int comparison = sortedArray[mid].CompareTo(target);
        
        // Check if target is present at mid
        if (comparison == 0)
        {
            return mid;
        }
        
        // If target is greater, ignore left half
        if (comparison < 0)
        {
            left = mid + 1;
        }
        // If target is smaller, ignore right half
        else
        {
            right = mid - 1;
        }
    }
    
    return -1; // Element not found
}

Characteristics​

  • Time Complexity: O(log n) - Much faster than linear search for large collections
  • Space Complexity: O(1) for iterative implementation, O(log n) for recursive implementation
  • Advantages: Very efficient for large sorted collections
  • Disadvantages: Requires sorted data

Let's trace through a binary search example:

Array: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Target: 60

Step 1: left = 0, right = 8, mid = 4
        array[mid] = 50, which is less than 60
        Update left = mid + 1 = 5
        
Step 2: left = 5, right = 8, mid = 6
        array[mid] = 70, which is greater than 60
        Update right = mid - 1 = 5
        
Step 3: left = 5, right = 5, mid = 5
        array[mid] = 60, which equals our target
        Return mid = 5

Game Development Example: Sorted Leaderboard​

public class LeaderboardEntry : IComparable<LeaderboardEntry>
{
    public string PlayerName { get; }
    public int Score { get; }
    
    public LeaderboardEntry(string playerName, int score)
    {
        PlayerName = playerName;
        Score = score;
    }
    
    // Sort by score in descending order
    public int CompareTo(LeaderboardEntry other)
    {
        // Note: Reversed comparison for descending order
        return other.Score.CompareTo(Score);
    }
}

public class Leaderboard
{
    private List<LeaderboardEntry> entries = new List<LeaderboardEntry>();
    private bool isSorted = true;
    
    public void AddEntry(LeaderboardEntry entry)
    {
        entries.Add(entry);
        isSorted = false; // Mark as unsorted when adding new entries
    }
    
    public void SortEntries()
    {
        if (!isSorted)
        {
            entries.Sort(); // Uses the CompareTo method
            isSorted = true;
        }
    }
    
    public int FindPlayerRank(string playerName)
    {
        SortEntries(); // Ensure the leaderboard is sorted
        
        // Binary search would be ideal here if we were searching by score
        // But since we're searching by name, we need a linear search
        for (int i = 0; i < entries.Count; i++)
        {
            if (entries[i].PlayerName == playerName)
            {
                return i + 1; // Rank is 1-based (1st place, 2nd place, etc.)
            }
        }
        
        return -1; // Player not found
    }
    
    public LeaderboardEntry GetEntryAtRank(int rank)
    {
        SortEntries(); // Ensure the leaderboard is sorted
        
        int index = rank - 1; // Convert 1-based rank to 0-based index
        if (index >= 0 && index < entries.Count)
        {
            return entries[index];
        }
        
        return null; // Invalid rank
    }
    
    // Find all entries with a score greater than or equal to a threshold
    public List<LeaderboardEntry> FindEntriesAboveScore(int scoreThreshold)
    {
        SortEntries(); // Ensure the leaderboard is sorted
        
        // Since entries are sorted by score in descending order,
        // we can use binary search to find the first entry below the threshold
        
        int left = 0;
        int right = entries.Count - 1;
        int firstBelowThreshold = entries.Count; // Default if all scores are above threshold
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            
            if (entries[mid].Score < scoreThreshold)
            {
                // This entry and all after it are below threshold
                firstBelowThreshold = mid;
                right = mid - 1;
            }
            else
            {
                // This entry is above threshold, check later entries
                left = mid + 1;
            }
        }
        
        // Return all entries before the first one below threshold
        return entries.GetRange(0, firstBelowThreshold);
    }
}

Graph Search Algorithms​

Many game scenarios involve searching through connected structures like game maps, quest dependencies, or social networks. These are typically represented as graphs, and require specialized search algorithms.

Depth-First Search (DFS)​

Depth-First Search explores as far as possible along each branch before backtracking. It's useful for maze solving, finding connected components, or checking if a path exists.

Implementation​

public class Graph
{
    private int vertices;
    private List<int>[] adjacencyList;
    
    public Graph(int vertices)
    {
        this.vertices = vertices;
        adjacencyList = new List<int>[vertices];
        
        for (int i = 0; i < vertices; i++)
        {
            adjacencyList[i] = new List<int>();
        }
    }
    
    public void AddEdge(int v, int w)
    {
        adjacencyList[v].Add(w);
    }
    
    // DFS traversal starting from a given vertex
    public void DepthFirstSearch(int startVertex)
    {
        // Mark all vertices as not visited
        bool[] visited = new bool[vertices];
        
        // Call the recursive helper function
        DFSUtil(startVertex, visited);
    }
    
    private void DFSUtil(int vertex, bool[] visited)
    {
        // Mark the current node as visited and print it
        visited[vertex] = true;
        Console.Write(vertex + " ");
        
        // Recur for all adjacent vertices
        foreach (int adjacentVertex in adjacencyList[vertex])
        {
            if (!visited[adjacentVertex])
            {
                DFSUtil(adjacentVertex, visited);
            }
        }
    }
    
    // Check if there is a path from source to destination
    public bool IsReachable(int source, int destination)
    {
        // Mark all vertices as not visited
        bool[] visited = new bool[vertices];
        
        // Call the recursive helper function
        DFSUtil(source, visited);
        
        // Return true if destination is visited
        return visited[destination];
    }
}

Breadth-First Search (BFS)​

Breadth-First Search explores all neighbors at the present depth before moving to nodes at the next depth level. It's particularly useful for finding the shortest path in unweighted graphs.

Implementation​

public void BreadthFirstSearch(int startVertex)
{
    // Mark all vertices as not visited
    bool[] visited = new bool[vertices];
    
    // Create a queue for BFS
    Queue<int> queue = new Queue<int>();
    
    // Mark the current node as visited and enqueue it
    visited[startVertex] = true;
    queue.Enqueue(startVertex);
    
    while (queue.Count > 0)
    {
        // Dequeue a vertex from queue and print it
        int vertex = queue.Dequeue();
        Console.Write(vertex + " ");
        
        // Get all adjacent vertices of the dequeued vertex
        // If an adjacent vertex has not been visited, mark it
        // visited and enqueue it
        foreach (int adjacentVertex in adjacencyList[vertex])
        {
            if (!visited[adjacentVertex])
            {
                visited[adjacentVertex] = true;
                queue.Enqueue(adjacentVertex);
            }
        }
    }
}

// Find shortest path from source to destination
public int ShortestPath(int source, int destination)
{
    // Mark all vertices as not visited
    bool[] visited = new bool[vertices];
    
    // Create a queue for BFS and a distance array
    Queue<int> queue = new Queue<int>();
    int[] distance = new int[vertices];
    
    // Initialize distances as -1 (unreachable)
    for (int i = 0; i < vertices; i++)
    {
        distance[i] = -1;
    }
    
    // Mark source as visited and set its distance to 0
    visited[source] = true;
    distance[source] = 0;
    queue.Enqueue(source);
    
    while (queue.Count > 0)
    {
        int vertex = queue.Dequeue();
        
        // If we've reached the destination, return the distance
        if (vertex == destination)
        {
            return distance[vertex];
        }
        
        foreach (int adjacentVertex in adjacencyList[vertex])
        {
            if (!visited[adjacentVertex])
            {
                visited[adjacentVertex] = true;
                distance[adjacentVertex] = distance[vertex] + 1;
                queue.Enqueue(adjacentVertex);
            }
        }
    }
    
    // If destination is not reachable
    return -1;
}

Game Development Example: Quest System​

public class Quest
{
    public string Id { get; }
    public string Title { get; }
    public bool IsCompleted { get; private set; }
    public List<string> PrerequisiteQuestIds { get; }
    
    public Quest(string id, string title, List<string> prerequisiteQuestIds)
    {
        Id = id;
        Title = title;
        IsCompleted = false;
        PrerequisiteQuestIds = prerequisiteQuestIds ?? new List<string>();
    }
    
    public void Complete()
    {
        IsCompleted = true;
    }
}

public class QuestSystem
{
    private Dictionary<string, Quest> quests = new Dictionary<string, Quest>();
    private Dictionary<string, List<string>> questDependencyGraph = new Dictionary<string, List<string>>();
    
    public void AddQuest(Quest quest)
    {
        quests[quest.Id] = quest;
        
        // Build dependency graph (which quests depend on this one)
        if (!questDependencyGraph.ContainsKey(quest.Id))
        {
            questDependencyGraph[quest.Id] = new List<string>();
        }
        
        foreach (string prereqId in quest.PrerequisiteQuestIds)
        {
            if (!questDependencyGraph.ContainsKey(prereqId))
            {
                questDependencyGraph[prereqId] = new List<string>();
            }
            
            // This quest depends on the prerequisite
            questDependencyGraph[prereqId].Add(quest.Id);
        }
    }
    
    // Get all available quests (prerequisites completed)
    public List<Quest> GetAvailableQuests()
    {
        List<Quest> availableQuests = new List<Quest>();
        
        foreach (Quest quest in quests.Values)
        {
            if (!quest.IsCompleted && ArePrerequisitesCompleted(quest))
            {
                availableQuests.Add(quest);
            }
        }
        
        return availableQuests;
    }
    
    private bool ArePrerequisitesCompleted(Quest quest)
    {
        foreach (string prereqId in quest.PrerequisiteQuestIds)
        {
            if (!quests.ContainsKey(prereqId) || !quests[prereqId].IsCompleted)
            {
                return false;
            }
        }
        
        return true;
    }
    
    // Find all quests that will become available after completing a specific quest
    public List<Quest> GetQuestsUnlockedBy(string questId)
    {
        List<Quest> unlockedQuests = new List<Quest>();
        
        if (!questDependencyGraph.ContainsKey(questId))
        {
            return unlockedQuests;
        }
        
        foreach (string dependentQuestId in questDependencyGraph[questId])
        {
            Quest dependentQuest = quests[dependentQuestId];
            
            // Check if this quest would become available
            bool wouldBeAvailable = true;
            foreach (string prereqId in dependentQuest.PrerequisiteQuestIds)
            {
                if (prereqId == questId)
                {
                    // We're simulating this quest being completed
                    continue;
                }
                
                if (!quests.ContainsKey(prereqId) || !quests[prereqId].IsCompleted)
                {
                    wouldBeAvailable = false;
                    break;
                }
            }
            
            if (wouldBeAvailable && !dependentQuest.IsCompleted)
            {
                unlockedQuests.Add(dependentQuest);
            }
        }
        
        return unlockedQuests;
    }
    
    // Check if there's a path from one quest to another in the dependency graph
    // (i.e., if completing one quest eventually leads to another becoming available)
    public bool DoesQuestLeadTo(string startQuestId, string targetQuestId)
    {
        if (!quests.ContainsKey(startQuestId) || !quests.ContainsKey(targetQuestId))
        {
            return false;
        }
        
        // Use BFS to find a path
        HashSet<string> visited = new HashSet<string>();
        Queue<string> queue = new Queue<string>();
        
        visited.Add(startQuestId);
        queue.Enqueue(startQuestId);
        
        while (queue.Count > 0)
        {
            string currentQuestId = queue.Dequeue();
            
            if (currentQuestId == targetQuestId)
            {
                return true;
            }
            
            if (questDependencyGraph.ContainsKey(currentQuestId))
            {
                foreach (string nextQuestId in questDependencyGraph[currentQuestId])
                {
                    if (!visited.Contains(nextQuestId))
                    {
                        visited.Add(nextQuestId);
                        queue.Enqueue(nextQuestId);
                    }
                }
            }
        }
        
        return false;
    }
}

Spatial Searching​

Games often need to find objects in 2D or 3D space efficiently. Linear search through all game objects would be too slow for large worlds.

Spatial Partitioning​

Spatial partitioning divides the game world into regions to limit the search space. Common techniques include:

  1. Grid-based partitioning: Divides the world into a uniform grid
  2. Quadtrees/Octrees: Recursively subdivides space into quadrants/octants
  3. Binary Space Partitioning (BSP): Recursively divides space using planes

Here's a simple grid-based spatial partitioning example:

public class SpatialGrid
{
    private List<GameObject>[,] grid;
    private float cellSize;
    private int width, height;
    
    public SpatialGrid(float worldWidth, float worldHeight, float cellSize)
    {
        this.cellSize = cellSize;
        
        // Calculate grid dimensions
        width = (int)Math.Ceiling(worldWidth / cellSize);
        height = (int)Math.Ceiling(worldHeight / cellSize);
        
        // Initialize grid
        grid = new List<GameObject>[width, height];
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                grid[x, y] = new List<GameObject>();
            }
        }
    }
    
    // Convert world position to grid cell
    private (int, int) WorldToCell(Vector2 position)
    {
        int x = (int)(position.X / cellSize);
        int y = (int)(position.Y / cellSize);
        
        // Clamp to grid boundaries
        x = Math.Clamp(x, 0, width - 1);
        y = Math.Clamp(y, 0, height - 1);
        
        return (x, y);
    }
    
    // Add object to the grid
    public void AddObject(GameObject obj)
    {
        (int cellX, int cellY) = WorldToCell(obj.Position);
        grid[cellX, cellY].Add(obj);
    }
    
    // Remove object from the grid
    public void RemoveObject(GameObject obj)
    {
        (int cellX, int cellY) = WorldToCell(obj.Position);
        grid[cellX, cellY].Remove(obj);
    }
    
    // Update object position in the grid
    public void UpdateObjectPosition(GameObject obj, Vector2 oldPosition)
    {
        (int oldCellX, int oldCellY) = WorldToCell(oldPosition);
        (int newCellX, int newCellY) = WorldToCell(obj.Position);
        
        // If the object moved to a different cell
        if (oldCellX != newCellX || oldCellY != newCellY)
        {
            grid[oldCellX, oldCellY].Remove(obj);
            grid[newCellX, newCellY].Add(obj);
        }
    }
    
    // Find all objects in a radius around a position
    public List<GameObject> FindObjectsInRadius(Vector2 position, float radius)
    {
        List<GameObject> result = new List<GameObject>();
        
        // Calculate the cell range to check
        int minCellX = (int)Math.Max(0, (position.X - radius) / cellSize);
        int maxCellX = (int)Math.Min(width - 1, (position.X + radius) / cellSize);
        int minCellY = (int)Math.Max(0, (position.Y - radius) / cellSize);
        int maxCellY = (int)Math.Min(height - 1, (position.Y + radius) / cellSize);
        
        // Check each cell in the range
        for (int x = minCellX; x <= maxCellX; x++)
        {
            for (int y = minCellY; y <= maxCellY; y++)
            {
                foreach (GameObject obj in grid[x, y])
                {
                    // Calculate actual distance
                    float distance = Vector2.Distance(position, obj.Position);
                    if (distance <= radius)
                    {
                        result.Add(obj);
                    }
                }
            }
        }
        
        return result;
    }
    
    // Find the nearest object to a position
    public GameObject FindNearestObject(Vector2 position, float maxDistance = float.MaxValue)
    {
        GameObject nearest = null;
        float nearestDistance = maxDistance;
        
        // Start with the cell containing the position
        (int centerX, int centerY) = WorldToCell(position);
        
        // Search in expanding "rings" of cells
        int ringSize = 0;
        bool foundInLastRing = true;
        
        while (foundInLastRing && ringSize * cellSize <= nearestDistance)
        {
            foundInLastRing = false;
            
            // Check all cells in the current ring
            for (int x = centerX - ringSize; x <= centerX + ringSize; x++)
            {
                for (int y = centerY - ringSize; y <= centerY + ringSize; y++)
                {
                    // Skip cells that aren't on the perimeter of the ring
                    // (except for the first ring, which is just the center cell)
                    if (ringSize > 0 && 
                        x > centerX - ringSize && x < centerX + ringSize && 
                        y > centerY - ringSize && y < centerY + ringSize)
                    {
                        continue;
                    }
                    
                    // Skip cells outside the grid
                    if (x < 0 || x >= width || y < 0 || y >= height)
                    {
                        continue;
                    }
                    
                    // Check objects in this cell
                    foreach (GameObject obj in grid[x, y])
                    {
                        float distance = Vector2.Distance(position, obj.Position);
                        if (distance < nearestDistance)
                        {
                            nearest = obj;
                            nearestDistance = distance;
                            foundInLastRing = true;
                        }
                    }
                }
            }
            
            ringSize++;
        }
        
        return nearest;
    }
}

// Simple GameObject class for this example
public class GameObject
{
    public string Id { get; }
    public Vector2 Position { get; set; }
    
    public GameObject(string id, Vector2 position)
    {
        Id = id;
        Position = position;
    }
}

// Simple Vector2 struct 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 float Distance(Vector2 a, Vector2 b)
    {
        float dx = a.X - b.X;
        float dy = a.Y - b.Y;
        return (float)Math.Sqrt(dx * dx + dy * dy);
    }
}
Unity Relevance

Unity provides several built-in spatial searching mechanisms:

  1. Physics.OverlapSphere/Physics2D.OverlapCircle: Find all colliders within a radius
  2. Physics.Raycast/Physics2D.Raycast: Find objects along a ray
  3. Physics.SphereCast/Physics2D.CircleCast: Cast a sphere/circle along a ray

For custom spatial partitioning, Unity's Job System and Burst Compiler can significantly accelerate spatial searches in large worlds.

// Example of using Unity's built-in spatial search
void FindNearbyEnemies()
{
    // Find all colliders within 10 units of the player
    Collider[] hitColliders = Physics.OverlapSphere(transform.position, 10f);
    
    foreach (Collider collider in hitColliders)
    {
        if (collider.CompareTag("Enemy"))
        {
            // Found an enemy within range
            Debug.Log($"Found enemy: {collider.gameObject.name}");
        }
    }
}

Choosing the Right Search Algorithm​

The best search algorithm depends on your specific requirements:

AlgorithmWhen to Use
Linear SearchSmall collections, unsorted data, one-time searches
Binary SearchLarge sorted collections, frequent searches
Depth-First SearchMaze solving, path finding, exploring all possibilities
Breadth-First SearchFinding shortest paths, level-order traversal
Spatial PartitioningFinding objects in 2D/3D space, collision detection

Consider these factors when choosing:

  1. Data structure: Is your data in an array, list, tree, or graph?
  2. Data ordering: Is your data sorted or can it be sorted?
  3. Search frequency: How often will you search the data?
  4. Collection size: How many items are you searching through?
  5. Memory constraints: How much extra memory can you use?

Conclusion​

Searching algorithms are fundamental tools in a game developer's toolkit. By understanding and implementing these algorithms, you can efficiently find items in inventories, locate nearby enemies, determine optimal paths, and solve many other game development challenges.

In the next section, we'll explore basic sorting algorithms, which are often used in conjunction with searching algorithms to organize data for more efficient access.