Skip to main content

6.7 - HashSet<T>

A HashSet<T> is a collection that stores unique elements in no particular order, providing very fast operations for adding, removing, and checking if an element exists. It's based on the mathematical concept of a set, where each element can appear only once.

Why Use HashSet<T>?​

HashSets excel in scenarios where you need to:

  1. Store unique elements: Ensuring no duplicates exist in a collection.
  2. Perform fast lookups: Quickly checking if an element exists.
  3. Track visited states: Keeping track of items you've already processed.
  4. Implement set operations: Performing union, intersection, and difference operations.

Common game development uses include:

  • Tracking visited locations or states
  • Eliminating duplicate items
  • Implementing collision detection optimizations
  • Managing unique identifiers
  • Implementing fast object pools
  • Checking for overlapping properties

Creating and Initializing HashSets​

Here's how to create and initialize a HashSet<T>:

Basic Creation​

// Create an empty HashSet of integers
HashSet<int> uniqueIds = new HashSet<int>();

// Create an empty HashSet of strings
HashSet<string> uniqueNames = new HashSet<string>();

// Create a HashSet with an initial capacity
HashSet<GameObject> uniqueObjects = new HashSet<GameObject>(100);

Initializing with Elements​

// Initialize from an array
int[] numbers = { 1, 2, 3, 4, 5, 3, 2 }; // Note the duplicates
HashSet<int> uniqueNumbers = new HashSet<int>(numbers);
// uniqueNumbers contains { 1, 2, 3, 4, 5 } (duplicates removed)

// Initialize from a list
List<string> names = new List<string> { "Alice", "Bob", "Charlie", "Alice" };
HashSet<string> uniqueNames = new HashSet<string>(names);
// uniqueNames contains { "Alice", "Bob", "Charlie" } (duplicates removed)

// Initialize with collection initializer syntax
HashSet<char> vowels = new HashSet<char> { 'a', 'e', 'i', 'o', 'u' };

HashSet Operations​

HashSet<T> provides several operations for adding, removing, and checking elements:

Adding Elements​

HashSet<string> visitedLocations = new HashSet<string>();

// Add elements (returns true if added, false if already exists)
bool added1 = visitedLocations.Add("Forest"); // true
bool added2 = visitedLocations.Add("Cave");   // true
bool added3 = visitedLocations.Add("Forest"); // false (already exists)

Console.WriteLine($"Unique locations: {visitedLocations.Count}"); // 2

Removing Elements​

HashSet<string> inventory = new HashSet<string> { "Sword", "Shield", "Potion", "Map" };

// Remove an element (returns true if removed, false if not found)
bool removed1 = inventory.Remove("Potion"); // true
bool removed2 = inventory.Remove("Armor");  // false (not in set)

// Clear all elements
inventory.Clear();

Checking for Elements​

HashSet<int> completedLevels = new HashSet<int> { 1, 2, 5, 7 };

// Check if an element exists (very fast operation)
bool isLevel2Completed = completedLevels.Contains(2); // true
bool isLevel3Completed = completedLevels.Contains(3); // false

// Check if the set is empty
bool noLevelsCompleted = completedLevels.Count == 0; // false

Set Operations​

One of the most powerful features of HashSet<T> is its ability to perform mathematical set operations:

Union (Combining Sets)​

HashSet<string> teamA = new HashSet<string> { "Alice", "Bob", "Charlie" };
HashSet<string> teamB = new HashSet<string> { "Charlie", "Dave", "Eve" };

// Create a new set with all elements from both sets
HashSet<string> allPlayers = new HashSet<string>(teamA);
allPlayers.UnionWith(teamB);
// allPlayers contains { "Alice", "Bob", "Charlie", "Dave", "Eve" }

// Note: UnionWith modifies the original set

Intersection (Common Elements)​

HashSet<string> groupA = new HashSet<string> { "Alice", "Bob", "Charlie", "Dave" };
HashSet<string> groupB = new HashSet<string> { "Bob", "Dave", "Eve", "Frank" };

// Find elements that exist in both sets
HashSet<string> commonMembers = new HashSet<string>(groupA);
commonMembers.IntersectWith(groupB);
// commonMembers contains { "Bob", "Dave" }

Difference (Elements in One Set but Not Another)​

HashSet<string> allItems = new HashSet<string> { "Sword", "Shield", "Potion", "Bow", "Arrow" };
HashSet<string> availableItems = new HashSet<string> { "Sword", "Potion", "Arrow" };

// Find items that are not available
HashSet<string> unavailableItems = new HashSet<string>(allItems);
unavailableItems.ExceptWith(availableItems);
// unavailableItems contains { "Shield", "Bow" }

Symmetric Difference (Elements in Either Set but Not Both)​

HashSet<string> aliceSkills = new HashSet<string> { "Fireball", "Heal", "Shield", "Teleport" };
HashSet<string> bobSkills = new HashSet<string> { "Heal", "Shield", "Lightning", "Invisibility" };

// Find skills that only one person has
HashSet<string> uniqueSkills = new HashSet<string>(aliceSkills);
uniqueSkills.SymmetricExceptWith(bobSkills);
// uniqueSkills contains { "Fireball", "Teleport", "Lightning", "Invisibility" }

Subset and Superset Checks​

HashSet<string> allWeapons = new HashSet<string> { "Sword", "Bow", "Axe", "Mace", "Dagger" };
HashSet<string> playerWeapons = new HashSet<string> { "Sword", "Bow", "Dagger" };
HashSet<string> basicWeapons = new HashSet<string> { "Sword", "Bow" };

// Check if one set is a subset of another
bool hasBasicWeapons = playerWeapons.IsSubsetOf(allWeapons); // true
bool hasAllWeapons = playerWeapons.IsSupersetOf(allWeapons); // false

// Check if one set is a proper subset (subset but not equal)
bool isProperSubset = basicWeapons.IsProperSubsetOf(playerWeapons); // true

// Check if sets overlap
bool hasCommonWeapons = basicWeapons.Overlaps(playerWeapons); // true

Iterating Through a HashSet​

You can iterate through a HashSet, but remember that the order is not guaranteed:

HashSet<string> achievements = new HashSet<string> { 
    "First Victory", 
    "Master Explorer", 
    "Treasure Hunter", 
    "Dragon Slayer" 
};

// Iterate through all elements
Console.WriteLine("Unlocked achievements:");
foreach (string achievement in achievements)
{
    Console.WriteLine(achievement);
}

// Convert to array or list if you need a specific order
string[] achievementsArray = achievements.ToArray();
Array.Sort(achievementsArray);

// Now iterate through the sorted array
Console.WriteLine("Sorted achievements:");
foreach (string achievement in achievementsArray)
{
    Console.WriteLine(achievement);
}

HashSet<T> in Game Development​

HashSets are particularly useful in game development for tracking states and ensuring uniqueness. Here are some practical examples:

Example: Fog of War System​

public class FogOfWarManager : MonoBehaviour
{
    [SerializeField] private int gridWidth = 20;
    [SerializeField] private int gridHeight = 20;
    [SerializeField] private GameObject fogTilePrefab;
    [SerializeField] private Transform fogParent;
    
    // Track which tiles have been revealed
    private HashSet<Vector2Int> revealedTiles = new HashSet<Vector2Int>();
    
    // Track which tiles are currently visible
    private HashSet<Vector2Int> visibleTiles = new HashSet<Vector2Int>();
    
    // Dictionary to store fog tile GameObjects
    private Dictionary<Vector2Int, GameObject> fogTiles = new Dictionary<Vector2Int, GameObject>();
    
    void Start()
    {
        // Initialize fog of war
        InitializeFog();
    }
    
    void InitializeFog()
    {
        // Create fog tiles for the entire grid
        for (int x = 0; x < gridWidth; x++)
        {
            for (int y = 0; y < gridHeight; y++)
            {
                Vector2Int position = new Vector2Int(x, y);
                GameObject fogTile = Instantiate(fogTilePrefab, new Vector3(x, 0, y), Quaternion.identity, fogParent);
                fogTile.name = $"Fog_{x}_{y}";
                fogTiles.Add(position, fogTile);
            }
        }
    }
    
    // Update visible tiles based on player units
    public void UpdateVisibility(List<Unit> playerUnits)
    {
        // Clear the currently visible tiles
        HashSet<Vector2Int> newVisibleTiles = new HashSet<Vector2Int>();
        
        // Calculate visible tiles for each unit
        foreach (Unit unit in playerUnits)
        {
            // Get the unit's position on the grid
            Vector2Int unitPosition = new Vector2Int(
                Mathf.RoundToInt(unit.transform.position.x),
                Mathf.RoundToInt(unit.transform.position.z)
            );
            
            // Add the tiles visible from this unit
            HashSet<Vector2Int> unitVisibleTiles = GetVisibleTilesForUnit(unit);
            newVisibleTiles.UnionWith(unitVisibleTiles);
        }
        
        // Update revealed tiles (once revealed, always revealed)
        revealedTiles.UnionWith(newVisibleTiles);
        
        // Find tiles that were visible but are no longer visible
        HashSet<Vector2Int> newlyHiddenTiles = new HashSet<Vector2Int>(visibleTiles);
        newlyHiddenTiles.ExceptWith(newVisibleTiles);
        
        // Find tiles that were not visible but are now visible
        HashSet<Vector2Int> newlyVisibleTiles = new HashSet<Vector2Int>(newVisibleTiles);
        newlyVisibleTiles.ExceptWith(visibleTiles);
        
        // Update the fog tiles
        foreach (Vector2Int tile in newlyVisibleTiles)
        {
            if (fogTiles.TryGetValue(tile, out GameObject fogTile))
            {
                // Make fully transparent
                SetFogAlpha(fogTile, 0f);
            }
        }
        
        foreach (Vector2Int tile in newlyHiddenTiles)
        {
            if (fogTiles.TryGetValue(tile, out GameObject fogTile))
            {
                // Make partially transparent (if revealed)
                if (revealedTiles.Contains(tile))
                {
                    SetFogAlpha(fogTile, 0.5f);
                }
                else
                {
                    SetFogAlpha(fogTile, 1f);
                }
            }
        }
        
        // Update the current visible tiles
        visibleTiles = newVisibleTiles;
    }
    
    // Get tiles visible from a unit's position
    private HashSet<Vector2Int> GetVisibleTilesForUnit(Unit unit)
    {
        HashSet<Vector2Int> visibleTiles = new HashSet<Vector2Int>();
        
        // Get the unit's position and vision range
        Vector2Int unitPosition = new Vector2Int(
            Mathf.RoundToInt(unit.transform.position.x),
            Mathf.RoundToInt(unit.transform.position.z)
        );
        int visionRange = unit.VisionRange;
        
        // Add all tiles within vision range
        for (int x = unitPosition.x - visionRange; x <= unitPosition.x + visionRange; x++)
        {
            for (int y = unitPosition.y - visionRange; y <= unitPosition.y + visionRange; y++)
            {
                // Check if the position is within the grid
                if (x >= 0 && x < gridWidth && y >= 0 && y < gridHeight)
                {
                    Vector2Int tilePosition = new Vector2Int(x, y);
                    
                    // Check if the tile is within the vision radius
                    float distance = Vector2Int.Distance(unitPosition, tilePosition);
                    if (distance <= visionRange)
                    {
                        // Check line of sight (simplified)
                        if (HasLineOfSight(unitPosition, tilePosition))
                        {
                            visibleTiles.Add(tilePosition);
                        }
                    }
                }
            }
        }
        
        return visibleTiles;
    }
    
    // Check if there's a clear line of sight between two positions
    private bool HasLineOfSight(Vector2Int from, Vector2Int to)
    {
        // Simplified implementation - in a real game, you would check for obstacles
        // This could use raycasting or a line-drawing algorithm
        
        // For this example, we'll just return true
        return true;
    }
    
    // Set the alpha value of a fog tile
    private void SetFogAlpha(GameObject fogTile, float alpha)
    {
        Renderer renderer = fogTile.GetComponent<Renderer>();
        if (renderer != null)
        {
            Color color = renderer.material.color;
            color.a = alpha;
            renderer.material.color = color;
        }
    }
    
    // Check if a tile is currently visible
    public bool IsTileVisible(Vector2Int position)
    {
        return visibleTiles.Contains(position);
    }
    
    // Check if a tile has been revealed
    public bool IsTileRevealed(Vector2Int position)
    {
        return revealedTiles.Contains(position);
    }
    
    // Reset fog of war (e.g., when starting a new level)
    public void ResetFogOfWar()
    {
        revealedTiles.Clear();
        visibleTiles.Clear();
        
        // Reset all fog tiles to fully opaque
        foreach (GameObject fogTile in fogTiles.Values)
        {
            SetFogAlpha(fogTile, 1f);
        }
    }
}

Example: Collision Detection Optimization​

public class CollisionManager : MonoBehaviour
{
    // List of all collidable objects
    private List<CollidableObject> collidableObjects = new List<CollidableObject>();
    
    // Spatial hash grid for broad-phase collision detection
    private Dictionary<Vector2Int, HashSet<CollidableObject>> spatialGrid = new Dictionary<Vector2Int, HashSet<CollidableObject>>();
    
    // Cell size for the spatial grid
    private float cellSize = 5f;
    
    // Track pairs of objects that are already colliding
    private HashSet<CollisionPair> activeCollisions = new HashSet<CollisionPair>();
    
    void Update()
    {
        // Clear the spatial grid
        spatialGrid.Clear();
        
        // Update the spatial grid with current object positions
        foreach (CollidableObject obj in collidableObjects)
        {
            // Skip inactive objects
            if (!obj.gameObject.activeInHierarchy)
                continue;
                
            // Get the grid cells this object occupies
            HashSet<Vector2Int> cells = GetCellsForObject(obj);
            
            // Add the object to each cell
            foreach (Vector2Int cell in cells)
            {
                if (!spatialGrid.TryGetValue(cell, out HashSet<CollidableObject> cellObjects))
                {
                    cellObjects = new HashSet<CollidableObject>();
                    spatialGrid[cell] = cellObjects;
                }
                
                cellObjects.Add(obj);
            }
        }
        
        // Track new collisions for this frame
        HashSet<CollisionPair> currentCollisions = new HashSet<CollisionPair>();
        
        // Check for collisions within each cell
        foreach (var cellObjects in spatialGrid.Values)
        {
            // Skip cells with fewer than 2 objects
            if (cellObjects.Count < 2)
                continue;
                
            // Check all pairs of objects in this cell
            foreach (CollidableObject objA in cellObjects)
            {
                foreach (CollidableObject objB in cellObjects)
                {
                    // Skip self-collision
                    if (objA == objB)
                        continue;
                        
                    // Create a collision pair (order doesn't matter)
                    CollisionPair pair = new CollisionPair(objA, objB);
                    
                    // Skip if we've already processed this pair
                    if (currentCollisions.Contains(pair))
                        continue;
                        
                    // Perform detailed collision check
                    if (CheckCollision(objA, objB))
                    {
                        // Add to current collisions
                        currentCollisions.Add(pair);
                        
                        // If this is a new collision, trigger OnCollisionEnter
                        if (!activeCollisions.Contains(pair))
                        {
                            objA.OnCollisionEnter(objB);
                            objB.OnCollisionEnter(objA);
                        }
                        // Otherwise, trigger OnCollisionStay
                        else
                        {
                            objA.OnCollisionStay(objB);
                            objB.OnCollisionStay(objA);
                        }
                    }
                }
            }
        }
        
        // Find collisions that were active but are no longer happening
        HashSet<CollisionPair> endedCollisions = new HashSet<CollisionPair>(activeCollisions);
        endedCollisions.ExceptWith(currentCollisions);
        
        // Trigger OnCollisionExit for ended collisions
        foreach (CollisionPair pair in endedCollisions)
        {
            pair.ObjectA.OnCollisionExit(pair.ObjectB);
            pair.ObjectB.OnCollisionExit(pair.ObjectA);
        }
        
        // Update active collisions
        activeCollisions = currentCollisions;
    }
    
    // Get the grid cells that an object occupies
    private HashSet<Vector2Int> GetCellsForObject(CollidableObject obj)
    {
        HashSet<Vector2Int> cells = new HashSet<Vector2Int>();
        
        // Get the object's bounds
        Bounds bounds = obj.GetBounds();
        
        // Calculate the min and max cells
        int minX = Mathf.FloorToInt(bounds.min.x / cellSize);
        int minY = Mathf.FloorToInt(bounds.min.z / cellSize);
        int maxX = Mathf.FloorToInt(bounds.max.x / cellSize);
        int maxY = Mathf.FloorToInt(bounds.max.z / cellSize);
        
        // Add all cells that the object overlaps
        for (int x = minX; x <= maxX; x++)
        {
            for (int y = minY; y <= maxY; y++)
            {
                cells.Add(new Vector2Int(x, y));
            }
        }
        
        return cells;
    }
    
    // Detailed collision check between two objects
    private bool CheckCollision(CollidableObject objA, CollidableObject objB)
    {
        // Get the bounds of both objects
        Bounds boundsA = objA.GetBounds();
        Bounds boundsB = objB.GetBounds();
        
        // Check if the bounds intersect
        return boundsA.Intersects(boundsB);
    }
    
    // Add a collidable object to the manager
    public void AddCollidableObject(CollidableObject obj)
    {
        if (!collidableObjects.Contains(obj))
        {
            collidableObjects.Add(obj);
        }
    }
    
    // Remove a collidable object from the manager
    public void RemoveCollidableObject(CollidableObject obj)
    {
        collidableObjects.Remove(obj);
        
        // Remove from active collisions
        activeCollisions.RemoveWhere(pair => pair.ObjectA == obj || pair.ObjectB == obj);
    }
}

// Represents a pair of colliding objects
public struct CollisionPair : IEquatable<CollisionPair>
{
    public CollidableObject ObjectA { get; private set; }
    public CollidableObject ObjectB { get; private set; }
    
    public CollisionPair(CollidableObject a, CollidableObject b)
    {
        // Ensure consistent ordering regardless of which object is passed first
        if (a.GetInstanceID() < b.GetInstanceID())
        {
            ObjectA = a;
            ObjectB = b;
        }
        else
        {
            ObjectA = b;
            ObjectB = a;
        }
    }
    
    public bool Equals(CollisionPair other)
    {
        return (ObjectA == other.ObjectA && ObjectB == other.ObjectB);
    }
    
    public override bool Equals(object obj)
    {
        if (obj is CollisionPair other)
        {
            return Equals(other);
        }
        return false;
    }
    
    public override int GetHashCode()
    {
        return ObjectA.GetHashCode() ^ ObjectB.GetHashCode();
    }
}

// Base class for objects that can collide
public abstract class CollidableObject : MonoBehaviour
{
    private CollisionManager collisionManager;
    
    void Start()
    {
        // Register with the collision manager
        collisionManager = FindObjectOfType<CollisionManager>();
        if (collisionManager != null)
        {
            collisionManager.AddCollidableObject(this);
        }
    }
    
    void OnDestroy()
    {
        // Unregister from the collision manager
        if (collisionManager != null)
        {
            collisionManager.RemoveCollidableObject(this);
        }
    }
    
    // Get the bounds of this object
    public abstract Bounds GetBounds();
    
    // Collision callbacks
    public virtual void OnCollisionEnter(CollidableObject other) { }
    public virtual void OnCollisionStay(CollidableObject other) { }
    public virtual void OnCollisionExit(CollidableObject other) { }
}

Example: Unique Item Database​

[System.Serializable]
public class Item
{
    public string Id;
    public string Name;
    public string Description;
    public ItemType Type;
    public int Value;
    
    public enum ItemType
    {
        Weapon,
        Armor,
        Consumable,
        Quest,
        Material
    }
    
    public Item(string id, string name, string description, ItemType type, int value)
    {
        Id = id;
        Name = name;
        Description = description;
        Type = type;
        Value = value;
    }
    
    // Override Equals and GetHashCode for proper HashSet behavior
    public override bool Equals(object obj)
    {
        if (obj is Item other)
        {
            return Id == other.Id;
        }
        return false;
    }
    
    public override int GetHashCode()
    {
        return Id.GetHashCode();
    }
}

public class ItemDatabase : MonoBehaviour
{
    // All items in the game
    private HashSet<Item> allItems = new HashSet<Item>();
    
    // Items grouped by type
    private Dictionary<Item.ItemType, HashSet<Item>> itemsByType = new Dictionary<Item.ItemType, HashSet<Item>>();
    
    // Fast lookup by ID
    private Dictionary<string, Item> itemsById = new Dictionary<string, Item>();
    
    void Awake()
    {
        // Initialize the database
        InitializeDatabase();
    }
    
    void InitializeDatabase()
    {
        // Initialize type groups
        foreach (Item.ItemType type in Enum.GetValues(typeof(Item.ItemType)))
        {
            itemsByType[type] = new HashSet<Item>();
        }
        
        // Add some example items
        AddItem(new Item("W001", "Iron Sword", "A basic sword made of iron.", Item.ItemType.Weapon, 50));
        AddItem(new Item("W002", "Steel Sword", "A sturdy sword made of steel.", Item.ItemType.Weapon, 100));
        AddItem(new Item("A001", "Leather Armor", "Basic armor made of leather.", Item.ItemType.Armor, 75));
        AddItem(new Item("C001", "Health Potion", "Restores 50 health points.", Item.ItemType.Consumable, 25));
        AddItem(new Item("Q001", "Ancient Artifact", "A mysterious artifact needed for a quest.", Item.ItemType.Quest, 0));
        
        Debug.Log($"Item database initialized with {allItems.Count} items");
    }
    
    // Add an item to the database
    public bool AddItem(Item item)
    {
        // Check if the item already exists
        if (allItems.Contains(item))
        {
            Debug.LogWarning($"Item with ID {item.Id} already exists in the database");
            return false;
        }
        
        // Add to collections
        allItems.Add(item);
        itemsByType[item.Type].Add(item);
        itemsById[item.Id] = item;
        
        return true;
    }
    
    // Remove an item from the database
    public bool RemoveItem(string itemId)
    {
        if (itemsById.TryGetValue(itemId, out Item item))
        {
            allItems.Remove(item);
            itemsByType[item.Type].Remove(item);
            itemsById.Remove(itemId);
            return true;
        }
        
        return false;
    }
    
    // Get an item by ID
    public Item GetItem(string itemId)
    {
        if (itemsById.TryGetValue(itemId, out Item item))
        {
            return item;
        }
        
        return null;
    }
    
    // Get all items of a specific type
    public HashSet<Item> GetItemsByType(Item.ItemType type)
    {
        if (itemsByType.TryGetValue(type, out HashSet<Item> items))
        {
            // Return a copy to prevent external modification
            return new HashSet<Item>(items);
        }
        
        return new HashSet<Item>();
    }
    
    // Get items that match a predicate
    public HashSet<Item> FindItems(Func<Item, bool> predicate)
    {
        HashSet<Item> result = new HashSet<Item>();
        
        foreach (Item item in allItems)
        {
            if (predicate(item))
            {
                result.Add(item);
            }
        }
        
        return result;
    }
    
    // Get items with value in a specific range
    public HashSet<Item> GetItemsInValueRange(int minValue, int maxValue)
    {
        return FindItems(item => item.Value >= minValue && item.Value <= maxValue);
    }
    
    // Get the difference between two sets of items
    public HashSet<Item> GetMissingItems(HashSet<Item> playerItems)
    {
        HashSet<Item> missingItems = new HashSet<Item>(allItems);
        missingItems.ExceptWith(playerItems);
        return missingItems;
    }
}

Performance Considerations​

When working with HashSets, keep these performance considerations in mind:

  1. Contains, Add, and Remove Operations: These are typically O(1) operations, making HashSets very efficient for lookups and modifications.

  2. Set Operations: Operations like UnionWith, IntersectWith, and ExceptWith are O(n) where n is the size of the other set.

  3. Memory Usage: HashSets use more memory than arrays or lists due to their hash table structure.

  4. Key Requirements: Like Dictionary keys, elements in a HashSet should properly implement Equals() and GetHashCode() methods for correct behavior.

  5. Order: HashSets do not maintain insertion order. If order is important, consider using a SortedSet<T> or maintaining a separate list.

HashSet<T> vs. Other Collections​

Here's how HashSets compare to other collection types:

CollectionStrengthsWeaknessesWhen to Use
HashSet<T>Fast lookups, unique elements, set operationsNo order, more memory usageWhen you need to track unique items with fast lookups
List<T>Ordered, direct indexingSlow lookups for large collectionsWhen order matters and you need indexed access
Dictionary<TKey, TValue>Fast lookups with associated valuesMore complex than HashSetWhen you need to associate values with keys
SortedSet<T>Ordered unique elementsSlower operations than HashSetWhen you need unique elements in sorted order

Practical Example: Pathfinding Optimization​

HashSets are commonly used in pathfinding algorithms to track visited nodes. Here's an example using A* pathfinding:

public class PathNode
{
    public Vector2Int Position { get; private set; }
    public bool IsWalkable { get; set; }
    public PathNode Parent { get; set; }
    
    // A* algorithm values
    public float GCost { get; set; } // Distance from start
    public float HCost { get; set; } // Estimated distance to goal
    public float FCost => GCost + HCost; // Total cost
    
    public PathNode(Vector2Int position, bool isWalkable = true)
    {
        Position = position;
        IsWalkable = isWalkable;
    }
    
    // Override Equals and GetHashCode for proper HashSet behavior
    public override bool Equals(object obj)
    {
        if (obj is PathNode other)
        {
            return Position.Equals(other.Position);
        }
        return false;
    }
    
    public override int GetHashCode()
    {
        return Position.GetHashCode();
    }
}

public class Pathfinder : MonoBehaviour
{
    [SerializeField] private int gridWidth = 20;
    [SerializeField] private int gridHeight = 20;
    
    private PathNode[,] grid;
    
    void Start()
    {
        // Initialize the grid
        InitializeGrid();
    }
    
    void InitializeGrid()
    {
        grid = new PathNode[gridWidth, gridHeight];
        
        // Create nodes
        for (int x = 0; x < gridWidth; x++)
        {
            for (int y = 0; y < gridHeight; y++)
            {
                // Randomly make some nodes unwalkable (obstacles)
                bool isWalkable = Random.value > 0.2f;
                grid[x, y] = new PathNode(new Vector2Int(x, y), isWalkable);
            }
        }
    }
    
    // Find a path using A* algorithm
    public List<PathNode> FindPath(Vector2Int start, Vector2Int goal)
    {
        // Validate input
        if (!IsValidPosition(start) || !IsValidPosition(goal))
        {
            Debug.LogError("Start or goal position is outside the grid");
            return null;
        }
        
        PathNode startNode = grid[start.x, start.y];
        PathNode goalNode = grid[goal.x, goal.y];
        
        // Check if start or goal is unwalkable
        if (!startNode.IsWalkable || !goalNode.IsWalkable)
        {
            Debug.LogError("Start or goal position is unwalkable");
            return null;
        }
        
        // Open set: nodes to be evaluated
        HashSet<PathNode> openSet = new HashSet<PathNode>();
        
        // Closed set: nodes already evaluated
        HashSet<PathNode> closedSet = new HashSet<PathNode>();
        
        // Initialize the start node
        startNode.GCost = 0;
        startNode.HCost = CalculateHCost(startNode, goalNode);
        startNode.Parent = null;
        
        openSet.Add(startNode);
        
        while (openSet.Count > 0)
        {
            // Get the node with the lowest FCost
            PathNode currentNode = GetLowestFCostNode(openSet);
            
            // Remove from open set and add to closed set
            openSet.Remove(currentNode);
            closedSet.Add(currentNode);
            
            // Check if we've reached the goal
            if (currentNode.Position.Equals(goalNode.Position))
            {
                // Path found, reconstruct and return it
                return ReconstructPath(currentNode);
            }
            
            // Check all neighbors
            foreach (PathNode neighbor in GetNeighbors(currentNode))
            {
                // Skip if not walkable or already evaluated
                if (!neighbor.IsWalkable || closedSet.Contains(neighbor))
                {
                    continue;
                }
                
                // Calculate the cost to reach this neighbor
                float tentativeGCost = currentNode.GCost + CalculateDistance(currentNode, neighbor);
                
                // If this path to the neighbor is better, or the neighbor is not in the open set
                if (tentativeGCost < neighbor.GCost || !openSet.Contains(neighbor))
                {
                    // Update the neighbor's values
                    neighbor.GCost = tentativeGCost;
                    neighbor.HCost = CalculateHCost(neighbor, goalNode);
                    neighbor.Parent = currentNode;
                    
                    // Add to open set if not already there
                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Add(neighbor);
                    }
                }
            }
        }
        
        // No path found
        Debug.Log("No path found");
        return null;
    }
    
    // Get the node with the lowest FCost from a set
    private PathNode GetLowestFCostNode(HashSet<PathNode> nodeSet)
    {
        PathNode lowestNode = null;
        float lowestFCost = float.MaxValue;
        
        foreach (PathNode node in nodeSet)
        {
            if (node.FCost < lowestFCost || 
                (node.FCost == lowestFCost && node.HCost < lowestNode.HCost))
            {
                lowestFCost = node.FCost;
                lowestNode = node;
            }
        }
        
        return lowestNode;
    }
    
    // Get walkable neighbors of a node
    private List<PathNode> GetNeighbors(PathNode node)
    {
        List<PathNode> neighbors = new List<PathNode>();
        
        // Check the eight adjacent nodes (including diagonals)
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                // Skip the node itself
                if (x == 0 && y == 0)
                    continue;
                
                int checkX = node.Position.x + x;
                int checkY = node.Position.y + y;
                
                // Check if the position is within the grid
                if (IsValidPosition(new Vector2Int(checkX, checkY)))
                {
                    neighbors.Add(grid[checkX, checkY]);
                }
            }
        }
        
        return neighbors;
    }
    
    // Calculate the heuristic cost (estimated distance to goal)
    private float CalculateHCost(PathNode a, PathNode b)
    {
        // Using Manhattan distance for a grid
        return Mathf.Abs(a.Position.x - b.Position.x) + Mathf.Abs(a.Position.y - b.Position.y);
    }
    
    // Calculate the distance between two nodes
    private float CalculateDistance(PathNode a, PathNode b)
    {
        // Using Euclidean distance for diagonal movement
        return Vector2Int.Distance(a.Position, b.Position);
    }
    
    // Reconstruct the path from the goal node back to the start
    private List<PathNode> ReconstructPath(PathNode endNode)
    {
        List<PathNode> path = new List<PathNode>();
        PathNode currentNode = endNode;
        
        while (currentNode != null)
        {
            path.Add(currentNode);
            currentNode = currentNode.Parent;
        }
        
        // Reverse to get path from start to goal
        path.Reverse();
        
        return path;
    }
    
    // Check if a position is within the grid
    private bool IsValidPosition(Vector2Int position)
    {
        return position.x >= 0 && position.x < gridWidth && 
               position.y >= 0 && position.y < gridHeight;
    }
}

In this A* pathfinding example, HashSets are used for two important purposes:

  1. The openSet tracks nodes that need to be evaluated
  2. The closedSet tracks nodes that have already been evaluated

Using HashSets for these collections provides very fast lookups when checking if a node is in either set, which is crucial for the algorithm's performance.

Conclusion​

HashSet<T> is a powerful collection type that excels at storing unique elements with fast lookups. It's particularly useful in game development for tracking states, eliminating duplicates, and performing set operations.

Key points to remember:

  • HashSets store unique elements with no duplicates
  • Lookups, additions, and removals are very fast (typically O(1))
  • HashSets support mathematical set operations like union, intersection, and difference
  • Elements in a HashSet should properly implement Equals() and GetHashCode()
  • HashSets do not maintain any specific order

In the next section, we'll explore how to choose the right collection type for different scenarios in your game development projects.