6.8 - Choosing the Right Collection

With so many collection types available in C#, choosing the right one for your specific needs can significantly impact your game's performance and code clarity. This section will help you understand the strengths and weaknesses of each collection type and provide guidance on when to use each one.

Collection Type Overview

Let's start with a quick overview of the main collection types we've covered:

Collection Type	Key Characteristics	Best For
Array	Fixed size, direct indexing, contiguous memory	When size is known and fixed, performance is critical
List<T>	Dynamic size, indexed access, ordered	General-purpose collection with flexible size
Dictionary<TKey, TValue>	Key-value pairs, fast lookups	When you need to find values by a unique key
Queue<T>	First-in, first-out (FIFO)	Processing items in order of arrival
Stack<T>	Last-in, first-out (LIFO)	Processing items in reverse order of addition
HashSet<T>	Unique elements, fast lookups	Tracking unique items, set operations

Performance Comparison

Understanding the performance characteristics of different collections is crucial for making informed decisions:

Time Complexity

Operation	Array	List<T>	Dictionary<TKey, TValue>	Queue<T>	Stack<T>	HashSet<T>
Access by Index	O(1)	O(1)	N/A	N/A	N/A	N/A
Access by Key	N/A	N/A	O(1)	N/A	N/A	N/A
Search	O(n)	O(n)	O(1)	O(n)	O(n)	O(1)
Add/Insert at End	N/A	O(1)*	O(1)*	O(1)	O(1)	O(1)*
Add/Insert at Beginning	N/A	O(n)	O(1)*	N/A	N/A	O(1)*
Add/Insert in Middle	N/A	O(n)	O(1)*	N/A	N/A	O(1)*
Remove from End	N/A	O(1)	O(1)	N/A	O(1)	O(1)
Remove from Beginning	N/A	O(n)	O(1)	O(1)	N/A	O(1)
Remove from Middle	N/A	O(n)	O(1)	N/A	N/A	O(1)

* Amortized time - occasional resizing operations may take longer

Memory Usage

Collection Type	Memory Efficiency	Notes
Array	Highest	Contiguous memory block, minimal overhead
List<T>	High	Some overhead for capacity management
Dictionary<TKey, TValue>	Medium	Overhead for hash table structure
Queue<T>	Medium	Internal circular buffer
Stack<T>	Medium	Internal array
HashSet<T>	Medium	Overhead for hash table structure

Decision Factors

When choosing a collection type, consider these key factors:

1. Access Pattern

How will you primarily access the data?

• Random access by index: Use Array or List<T>
• Access by key: Use Dictionary<TKey, TValue>
• Sequential access only: Consider Queue<T> or Stack<T>
• Checking for existence: Use HashSet<T> or Dictionary<TKey, TValue>

2. Size Dynamics

Will the collection size change?

• Fixed size: Use Array
• Growing/shrinking: Use List<T>, Dictionary<TKey, TValue>, Queue<T>, Stack<T>, or HashSet<T>

3. Element Uniqueness

Do you need to ensure elements are unique?

• Unique elements required: Use HashSet<T> or Dictionary<TKey, TValue> (keys)
• Duplicates allowed: Use Array, List<T>, Queue<T>, or Stack<T>

4. Order Requirements

Is order important?

• Insertion order matters: Use List<T>, Queue<T>, or Stack<T>
• Sorted order needed: Use SortedList<TKey, TValue>, SortedDictionary<TKey, TValue>, or SortedSet<T>
• Order not important: Use Dictionary<TKey, TValue> or HashSet<T>

5. Operation Frequency

Which operations will be performed most frequently?

• Frequent lookups: Use Dictionary<TKey, TValue> or HashSet<T>
• Frequent additions/removals at end: Use List<T>, Queue<T>, or Stack<T>
• Frequent additions/removals at beginning or middle: Consider LinkedList<T>
• Frequent iterations: Use Array or List<T>

Common Game Development Scenarios

Let's look at some common game development scenarios and the most appropriate collection types for each:

Inventory Systems

Requirements: Store items, possibly with quantities, allow lookups by ID, add/remove items.

Best Options:

• Dictionary<string, InventoryItem> for fast lookups by item ID
• List<InventoryItem> if order matters (e.g., displaying in UI)
• Dictionary<string, int> for simple item ID to quantity mapping

// Option 1: Dictionary of items with quantities
Dictionary<string, int> inventory = new Dictionary<string, int>();
inventory["HealthPotion"] = 5;
inventory["Sword"] = 1;

// Option 2: Dictionary of full item objects
Dictionary<string, InventoryItem> itemInventory = new Dictionary<string, InventoryItem>();
itemInventory.Add(healthPotion.Id, healthPotion);
itemInventory.Add(sword.Id, sword);

// Option 3: List for ordered display
List<InventoryItem> orderedInventory = new List<InventoryItem>();
orderedInventory.Add(healthPotion);
orderedInventory.Add(sword);

Enemy Spawning

Requirements: Spawn enemies in waves, manage active enemies, track spawn points.

Best Options:

• Queue<EnemyType> for enemies waiting to spawn
• List<Enemy> or HashSet<Enemy> for active enemies
• List<Transform> for spawn points

// Queue of enemies to spawn in order
Queue<EnemyType> spawnQueue = new Queue<EnemyType>();
spawnQueue.Enqueue(EnemyType.Goblin);
spawnQueue.Enqueue(EnemyType.Orc);
spawnQueue.Enqueue(EnemyType.Troll);

// List of active enemies
List<Enemy> activeEnemies = new List<Enemy>();

// Spawn points
List<Transform> spawnPoints = new List<Transform>();

// Spawn the next enemy
if (spawnQueue.Count > 0 && activeEnemies.Count < maxEnemies)
{
    EnemyType nextType = spawnQueue.Dequeue();
    Transform spawnPoint = spawnPoints[Random.Range(0, spawnPoints.Count)];
    Enemy newEnemy = SpawnEnemy(nextType, spawnPoint.position);
    activeEnemies.Add(newEnemy);
}

Pathfinding

Requirements: Track open nodes, closed nodes, reconstruct paths.

Best Options:

• HashSet<Node> for closed (visited) nodes
• Priority queue (custom or SortedList<float, Node>) for open nodes
• List<Node> or Stack<Node> for the final path

// Open set (using a custom priority queue or sorted list)
PriorityQueue<Node> openSet = new PriorityQueue<Node>();
openSet.Enqueue(startNode, 0);

// Closed set for visited nodes
HashSet<Node> closedSet = new HashSet<Node>();

// Final path
List<Node> path = new List<Node>();

// A* algorithm (simplified)
while (openSet.Count > 0)
{
    Node current = openSet.Dequeue();
    
    if (current == goalNode)
    {
        // Reconstruct path
        while (current != null)
        {
            path.Add(current);
            current = current.Parent;
        }
        path.Reverse();
        break;
    }
    
    closedSet.Add(current);
    
    foreach (Node neighbor in GetNeighbors(current))
    {
        if (closedSet.Contains(neighbor))
            continue;
            
        float newCost = current.GCost + Distance(current, neighbor);
        
        if (newCost < neighbor.GCost || !openSet.Contains(neighbor))
        {
            neighbor.GCost = newCost;
            neighbor.HCost = Distance(neighbor, goalNode);
            neighbor.Parent = current;
            
            if (!openSet.Contains(neighbor))
                openSet.Enqueue(neighbor, neighbor.FCost);
        }
    }
}

Dialog Systems

Requirements: Store dialog lines, track conversation history, manage branching.

Best Options:

• Dictionary<string, DialogNode> for dialog nodes by ID
• Queue<DialogLine> for sequential dialog
• Stack<DialogNode> for conversation history/backtracking

// Dialog database
Dictionary<string, DialogNode> dialogNodes = new Dictionary<string, DialogNode>();
dialogNodes.Add("greeting", new DialogNode("Hello there!"));
dialogNodes.Add("quest", new DialogNode("I need your help with something."));

// Current conversation path
Stack<DialogNode> conversationHistory = new Stack<DialogNode>();

// Display the current dialog and track history
void ShowDialog(string nodeId)
{
    if (dialogNodes.TryGetValue(nodeId, out DialogNode node))
    {
        DisplayText(node.Text);
        conversationHistory.Push(node);
    }
}

// Go back to previous dialog
void GoBack()
{
    if (conversationHistory.Count > 1)
    {
        conversationHistory.Pop(); // Remove current
        DialogNode previous = conversationHistory.Peek();
        DisplayText(previous.Text);
    }
}

Collision Detection

Requirements: Track colliding objects, check for collisions efficiently.

Best Options:

• HashSet<GameObject> for objects in collision
• Spatial partitioning with Dictionary<Vector2Int, List<Collider>> for broad phase
• HashSet<CollisionPair> for active collisions

// Spatial hash grid for broad-phase collision detection
Dictionary<Vector2Int, List<Collider>> spatialGrid = new Dictionary<Vector2Int, List<Collider>>();

// Active collisions
HashSet<CollisionPair> activeCollisions = new HashSet<CollisionPair>();

// Update spatial grid
foreach (Collider collider in allColliders)
{
    Vector2Int cell = GetCell(collider.transform.position);
    
    if (!spatialGrid.TryGetValue(cell, out List<Collider> cellColliders))
    {
        cellColliders = new List<Collider>();
        spatialGrid[cell] = cellColliders;
    }
    
    cellColliders.Add(collider);
}

// Check for collisions
HashSet<CollisionPair> newCollisions = new HashSet<CollisionPair>();

foreach (var cellColliders in spatialGrid.Values)
{
    for (int i = 0; i < cellColliders.Count; i++)
    {
        for (int j = i + 1; j < cellColliders.Count; j++)
        {
            Collider a = cellColliders[i];
            Collider b = cellColliders[j];
            
            if (CheckCollision(a, b))
            {
                CollisionPair pair = new CollisionPair(a, b);
                newCollisions.Add(pair);
                
                if (!activeCollisions.Contains(pair))
                {
                    // New collision
                    OnCollisionEnter(a, b);
                }
            }
        }
    }
}

// Find ended collisions
foreach (CollisionPair pair in activeCollisions)
{
    if (!newCollisions.Contains(pair))
    {
        // Collision ended
        OnCollisionExit(pair.A, pair.B);
    }
}

activeCollisions = newCollisions;

Turn-Based Game Logic

Requirements: Manage turn order, track action history, implement undo functionality.

Best Options:

• Queue<Player> for turn order
• Stack<GameAction> for action history and undo
• Dictionary<Player, List<GameAction>> for player-specific actions

// Turn order
Queue<Player> turnOrder = new Queue<Player>();
foreach (Player player in players)
{
    turnOrder.Enqueue(player);
}

// Action history for undo
Stack<GameAction> actionHistory = new Stack<GameAction>();

// Execute a turn
void ExecuteTurn()
{
    Player currentPlayer = turnOrder.Dequeue();
    
    // Let the player take their action
    GameAction action = currentPlayer.ChooseAction();
    
    // Execute the action
    action.Execute();
    
    // Record for undo
    actionHistory.Push(action);
    
    // Add player back to the end of the queue
    turnOrder.Enqueue(currentPlayer);
}

// Undo the last action
void Undo()
{
    if (actionHistory.Count > 0)
    {
        GameAction lastAction = actionHistory.Pop();
        lastAction.Undo();
    }
}

Performance Optimization Tips

Here are some tips for optimizing collection performance in your games:

1. Preallocate Capacity

For collections that resize dynamically, preallocate capacity when you know approximately how many elements you'll need:

// Instead of this
List<Enemy> enemies = new List<Enemy>();

// Do this
List<Enemy> enemies = new List<Enemy>(100); // Preallocate for 100 enemies

// Same for other collections
Dictionary<int, GameObject> objectsById = new Dictionary<int, GameObject>(100);
HashSet<GameObject> activeObjects = new HashSet<GameObject>(100);

2. Reuse Collections

Instead of creating new collections frequently, reuse existing ones:

// Bad: Creates garbage each frame
void Update()
{
    List<Enemy> nearbyEnemies = FindNearbyEnemies();
    ProcessEnemies(nearbyEnemies);
}

// Better: Reuse the same list
private List<Enemy> nearbyEnemies = new List<Enemy>();

void Update()
{
    nearbyEnemies.Clear(); // Clear instead of creating new
    FindNearbyEnemies(nearbyEnemies); // Fill the existing list
    ProcessEnemies(nearbyEnemies);
}

3. Choose the Right Iteration Method

Different iteration methods have different performance characteristics:

List<int> numbers = new List<int>(1000);
// Fill the list...

// Option 1: foreach - clean but slightly less efficient for value types
foreach (int number in numbers)
{
    // Process number
}

// Option 2: for with indexer - most efficient for List<T>
for (int i = 0; i < numbers.Count; i++)
{
    int number = numbers[i];
    // Process number
}

// Option 3: LINQ - clean but less efficient
numbers.ForEach(number => {
    // Process number
});

4. Avoid Unnecessary Boxing/Unboxing

Use generic collections to avoid boxing/unboxing value types:

// Bad: Causes boxing/unboxing for value types
ArrayList legacyList = new ArrayList();
legacyList.Add(42); // Boxes int to object
int number = (int)legacyList[0]; // Unboxes object to int

// Good: No boxing/unboxing
List<int> genericList = new List<int>();
genericList.Add(42); // No boxing
int number = genericList[0]; // No unboxing

5. Use Specialized Collections for Specific Needs

Consider specialized collections for specific performance needs:

// For read-only collections (prevents accidental modifications)
IReadOnlyList<Item> items = inventory.GetItems();

// For thread-safe collections
ConcurrentQueue<NetworkMessage> messageQueue = new ConcurrentQueue<NetworkMessage>();

// For collections that maintain sorted order
SortedDictionary<float, GameObject> sortedByDistance = new SortedDictionary<float, GameObject>();

Collection Selection Flowchart

Here's a simplified flowchart to help you choose the right collection:

1. Do you need to access elements by a key?

   • Yes → Use Dictionary<TKey, TValue>
   • No → Continue

2. Do you need to ensure elements are unique?

   • Yes → Use HashSet<T>
   • No → Continue

3. Do you need to process elements in a specific order?

   • FIFO (first in, first out) → Use Queue<T>
   • LIFO (last in, first out) → Use Stack<T>
   • No specific order → Continue

4. Will the collection size change?

   • No → Use Array
   • Yes → Continue

5. Do you need indexed access?

   • Yes → Use List<T>
   • No → Reconsider your requirements

Practical Example: Game Object Management System

Let's put it all together with a practical example of a game object management system that uses different collection types for different purposes:

public class GameObjectManager : MonoBehaviour
{
    // Fast lookup by ID
    private Dictionary<int, GameObject> objectsById = new Dictionary<int, GameObject>();
    
    // Fast lookup by type
    private Dictionary<GameObjectType, HashSet<GameObject>> objectsByType = new Dictionary<GameObjectType, HashSet<GameObject>>();
    
    // Spatial partitioning for collision detection
    private Dictionary<Vector2Int, List<GameObject>> spatialGrid = new Dictionary<Vector2Int, List<GameObject>>();
    
    // Objects waiting to be spawned
    private Queue<GameObjectSpawnInfo> spawnQueue = new Queue<GameObjectSpawnInfo>();
    
    // Objects waiting to be destroyed
    private List<GameObject> destroyList = new List<GameObject>();
    
    // Recently spawned objects (for undo)
    private Stack<GameObject> recentlySpawned = new Stack<GameObject>();
    
    // Cell size for spatial partitioning
    private float cellSize = 10f;
    
    void Awake()
    {
        // Initialize collections
        foreach (GameObjectType type in Enum.GetValues(typeof(GameObjectType)))
        {
            objectsByType[type] = new HashSet<GameObject>();
        }
    }
    
    void Update()
    {
        // Process spawn queue
        ProcessSpawnQueue();
        
        // Update spatial grid
        UpdateSpatialGrid();
        
        // Process destroy list
        ProcessDestroyList();
    }
    
    // Register a game object with the manager
    public void RegisterObject(GameObject obj, int id, GameObjectType type)
    {
        // Add to ID lookup
        objectsById[id] = obj;
        
        // Add to type lookup
        objectsByType[type].Add(obj);
        
        // Track for undo
        recentlySpawned.Push(obj);
        
        Debug.Log($"Registered object {id} of type {type}");
    }
    
    // Unregister a game object
    public void UnregisterObject(GameObject obj, int id, GameObjectType type)
    {
        // Remove from lookups
        objectsById.Remove(id);
        objectsByType[type].Remove(obj);
        
        // Add to destroy list
        destroyList.Add(obj);
        
        Debug.Log($"Unregistered object {id} of type {type}");
    }
    
    // Queue an object for spawning
    public void QueueForSpawn(GameObjectSpawnInfo spawnInfo)
    {
        spawnQueue.Enqueue(spawnInfo);
    }
    
    // Get objects by type
    public HashSet<GameObject> GetObjectsByType(GameObjectType type)
    {
        if (objectsByType.TryGetValue(type, out HashSet<GameObject> objects))
        {
            // Return a copy to prevent external modification
            return new HashSet<GameObject>(objects);
        }
        
        return new HashSet<GameObject>();
    }
    
    // Get an object by ID
    public GameObject GetObjectById(int id)
    {
        if (objectsById.TryGetValue(id, out GameObject obj))
        {
            return obj;
        }
        
        return null;
    }
    
    // Get objects near a position
    public List<GameObject> GetObjectsNearPosition(Vector3 position, float radius)
    {
        List<GameObject> nearbyObjects = new List<GameObject>();
        
        // Calculate the cells that could contain objects within the radius
        int minX = Mathf.FloorToInt((position.x - radius) / cellSize);
        int maxX = Mathf.FloorToInt((position.x + radius) / cellSize);
        int minY = Mathf.FloorToInt((position.z - radius) / cellSize);
        int maxY = Mathf.FloorToInt((position.z + radius) / cellSize);
        
        // Check each cell
        HashSet<GameObject> checkedObjects = new HashSet<GameObject>(); // Avoid duplicates
        
        for (int x = minX; x <= maxX; x++)
        {
            for (int y = minY; y <= maxY; y++)
            {
                Vector2Int cell = new Vector2Int(x, y);
                
                if (spatialGrid.TryGetValue(cell, out List<GameObject> cellObjects))
                {
                    foreach (GameObject obj in cellObjects)
                    {
                        // Skip if already checked
                        if (checkedObjects.Contains(obj))
                            continue;
                            
                        checkedObjects.Add(obj);
                        
                        // Check actual distance
                        float distance = Vector3.Distance(position, obj.transform.position);
                        if (distance <= radius)
                        {
                            nearbyObjects.Add(obj);
                        }
                    }
                }
            }
        }
        
        return nearbyObjects;
    }
    
    // Undo the most recent spawn
    public bool UndoLastSpawn()
    {
        if (recentlySpawned.Count > 0)
        {
            GameObject obj = recentlySpawned.Pop();
            
            // Get the object's ID and type
            GameObjectData data = obj.GetComponent<GameObjectData>();
            if (data != null)
            {
                UnregisterObject(obj, data.Id, data.Type);
                return true;
            }
        }
        
        return false;
    }
    
    // Process the spawn queue
    private void ProcessSpawnQueue()
    {
        int spawnCount = Mathf.Min(spawnQueue.Count, 10); // Process up to 10 per frame
        
        for (int i = 0; i < spawnCount; i++)
        {
            if (spawnQueue.Count > 0)
            {
                GameObjectSpawnInfo spawnInfo = spawnQueue.Dequeue();
                GameObject obj = Instantiate(spawnInfo.Prefab, spawnInfo.Position, spawnInfo.Rotation);
                
                // Set up the object data
                GameObjectData data = obj.AddComponent<GameObjectData>();
                data.Id = spawnInfo.Id;
                data.Type = spawnInfo.Type;
                
                // Register the object
                RegisterObject(obj, spawnInfo.Id, spawnInfo.Type);
            }
        }
    }
    
    // Update the spatial grid
    private void UpdateSpatialGrid()
    {
        // Clear the grid
        spatialGrid.Clear();
        
        // Add all objects to the grid
        foreach (GameObject obj in objectsById.Values)
        {
            if (obj != null)
            {
                Vector2Int cell = GetCell(obj.transform.position);
                
                if (!spatialGrid.TryGetValue(cell, out List<GameObject> cellObjects))
                {
                    cellObjects = new List<GameObject>();
                    spatialGrid[cell] = cellObjects;
                }
                
                cellObjects.Add(obj);
            }
        }
    }
    
    // Process the destroy list
    private void ProcessDestroyList()
    {
        foreach (GameObject obj in destroyList)
        {
            if (obj != null)
            {
                Destroy(obj);
            }
        }
        
        destroyList.Clear();
    }
    
    // Get the grid cell for a position
    private Vector2Int GetCell(Vector3 position)
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int y = Mathf.FloorToInt(position.z / cellSize);
        return new Vector2Int(x, y);
    }
}

// Helper classes
public enum GameObjectType
{
    Player,
    Enemy,
    Projectile,
    Pickup,
    Obstacle
}

public class GameObjectData : MonoBehaviour
{
    public int Id;
    public GameObjectType Type;
}

public class GameObjectSpawnInfo
{
    public GameObject Prefab;
    public Vector3 Position;
    public Quaternion Rotation;
    public int Id;
    public GameObjectType Type;
    
    public GameObjectSpawnInfo(GameObject prefab, Vector3 position, Quaternion rotation, int id, GameObjectType type)
    {
        Prefab = prefab;
        Position = position;
        Rotation = rotation;
        Id = id;
        Type = type;
    }
}

This example demonstrates how different collection types can work together in a comprehensive system:

1. Dictionary<int, GameObject> provides fast lookups by ID
2. Dictionary<GameObjectType, HashSet<GameObject>> groups objects by type with fast lookups
3. Dictionary<Vector2Int, List<GameObject>> implements spatial partitioning for efficient proximity queries
4. Queue<GameObjectSpawnInfo> manages objects waiting to be spawned
5. List<GameObject> tracks objects to be destroyed
6. Stack<GameObject> enables undo functionality for recent spawns
7. HashSet<GameObject> prevents duplicate processing in proximity queries

Conclusion

Choosing the right collection type is an important decision that can significantly impact your game's performance and code clarity. By understanding the strengths and weaknesses of each collection type, you can make informed decisions that lead to more efficient and maintainable code.

Key takeaways:

• Arrays are best for fixed-size collections with direct indexing
• Lists are versatile for ordered, dynamic collections
• Dictionaries excel at key-based lookups
• Queues are ideal for first-in, first-out processing
• Stacks are perfect for last-in, first-out processing
• HashSets are optimized for storing unique elements with fast lookups

Remember that there's no one-size-fits-all solution. Often, the best approach is to use multiple collection types together, each handling the aspect of your data management that it's best suited for.

In the next section, we'll put our knowledge of collections to use in a practical exercise: building an inventory system.