Skip to main content

Data Structures

QWR Utilities provides specialized data structures for common needs in Unity development. These structures are designed to solve specific problems and improve performance in XR applications.

Data Structures Overview​

The QWR Utilities package includes the following data structures:

  • Object Pools
  • Priority Queues
  • Observable Collections
  • Serializable Dictionaries
  • Weighted Random Selection
  • Spatial Partitioning
  • State Machines

Object Pools​

Object pooling is a design pattern that improves performance by reusing objects instead of creating and destroying them repeatedly.

QWRObjectPool​

The QWRObjectPool<T> is a generic object pool for any MonoBehaviour:

using QWR.Utilities.Data;
using UnityEngine;

// Create a bullet pool
public class BulletManager : MonoBehaviour
{
    [SerializeField] private Bullet bulletPrefab;
    private QWRObjectPool<Bullet> bulletPool;
    
    private void Awake()
    {
        // Initialize pool with 20 bullets
        bulletPool = new QWRObjectPool<Bullet>(
            bulletPrefab,    // Prefab to instantiate
            20,              // Initial capacity
            transform,       // Parent transform
            true             // Auto-expand when empty?
        );
    }
    
    public void FireBullet(Vector3 position, Vector3 direction)
    {
        // Get bullet from pool
        Bullet bullet = bulletPool.Get();
        
        // Initialize bullet
        bullet.transform.position = position;
        bullet.direction = direction;
        bullet.gameObject.SetActive(true);
        
        // Bullet will return itself to the pool when done
    }
}

// Bullet implementation
public class Bullet : MonoBehaviour
{
    private QWRObjectPool<Bullet> pool;
    public Vector3 direction;
    
    // Called by the pool when the object is retrieved
    public void OnGetFromPool(QWRObjectPool<Bullet> sourcePool)
    {
        pool = sourcePool;
    }
    
    // Return to pool after 3 seconds or on collision
    private void OnCollisionEnter(Collision collision)
    {
        ReturnToPool();
    }
    
    private void ReturnToPool()
    {
        if (pool != null)
        {
            pool.Release(this);
        }
    }
}

Pool Configuration​

You can configure various aspects of the object pool:

// Configure pool behavior
QWRObjectPool<Enemy> enemyPool = new QWRObjectPool<Enemy>(
    enemyPrefab,
    initialCapacity: 10,
    parent: transform,
    autoExpand: true,
    maxSize: 50,
    prewarmCount: 5,
    resetOnRelease: true
);

// Preload additional objects
enemyPool.Preload(10);

// Clear the pool
enemyPool.Clear();

// Get pool statistics
int activeCount = enemyPool.ActiveCount;
int inactiveCount = enemyPool.InactiveCount;
int totalCount = enemyPool.TotalCount;

Non-MonoBehaviour Pools​

For non-MonoBehaviour objects, use the QWRGenericPool<T>:

// Pool of complex objects
QWRGenericPool<ParticleData> particlePool = new QWRGenericPool<ParticleData>(
    createFunc: () => new ParticleData(),
    resetAction: (data) => data.Reset(),
    initialCapacity: 100
);

// Get and release objects
ParticleData particle = particlePool.Get();
// Use particle...
particlePool.Release(particle);

Priority Queues​

Priority queues allow you to process items in order of priority.

QWRPriorityQueue​

The QWRPriorityQueue<T> is a generic priority queue:

using QWR.Utilities.Data;

// Create a priority queue for tasks
QWRPriorityQueue<Task> taskQueue = new QWRPriorityQueue<Task>();

// Add items with priorities (higher priority values are processed first)
taskQueue.Enqueue(new Task("High priority task"), 100);
taskQueue.Enqueue(new Task("Medium priority task"), 50);
taskQueue.Enqueue(new Task("Low priority task"), 10);

// Process tasks in priority order
while (taskQueue.Count > 0)
{
    Task nextTask = taskQueue.Dequeue();
    ProcessTask(nextTask);
}

// Peek at the highest priority item without removing it
Task highestPriorityTask = taskQueue.Peek();

// Check if the queue contains an item
bool containsTask = taskQueue.Contains(myTask);

// Clear the queue
taskQueue.Clear();

Custom Priority Comparison​

You can use a custom comparer for complex priority logic:

// Custom comparer for tasks
public class TaskComparer : IComparer<Task>
{
    public int Compare(Task x, Task y)
    {
        // Compare by priority first
        int priorityComparison = y.Priority.CompareTo(x.Priority);
        if (priorityComparison != 0)
            return priorityComparison;
            
        // If priorities are equal, compare by creation time
        return x.CreationTime.CompareTo(y.CreationTime);
    }
}

// Create priority queue with custom comparer
QWRPriorityQueue<Task> taskQueue = new QWRPriorityQueue<Task>(new TaskComparer());

// Add items (no need to specify priority, it's in the Task object)
taskQueue.Enqueue(new Task("Task 1", priority: 10));
taskQueue.Enqueue(new Task("Task 2", priority: 20));

Observable Collections​

Observable collections notify you when their contents change.

QWRObservableList​

The QWRObservableList<T> is a list that raises events when modified:

using QWR.Utilities.Data;
using UnityEngine;

// Create an observable list
QWRObservableList<Enemy> enemies = new QWRObservableList<Enemy>();

// Subscribe to events
enemies.OnItemAdded += HandleEnemyAdded;
enemies.OnItemRemoved += HandleEnemyRemoved;
enemies.OnListCleared += HandleEnemiesCleared;

// Event handlers
private void HandleEnemyAdded(Enemy enemy)
{
    Debug.Log($"Enemy added: {enemy.name}");
    UpdateUI();
}

private void HandleEnemyRemoved(Enemy enemy)
{
    Debug.Log($"Enemy removed: {enemy.name}");
    UpdateUI();
}

private void HandleEnemiesCleared()
{
    Debug.Log("All enemies cleared");
    UpdateUI();
}

// Use like a normal list
enemies.Add(newEnemy);
enemies.Remove(enemy);
enemies.Clear();

QWRObservableDictionary​

The QWRObservableDictionary<TKey, TValue> is a dictionary that raises events when modified:

// Create an observable dictionary
QWRObservableDictionary<string, Player> players = new QWRObservableDictionary<string, Player>();

// Subscribe to events
players.OnItemAdded += HandlePlayerAdded;
players.OnItemRemoved += HandlePlayerRemoved;
players.OnItemChanged += HandlePlayerChanged;
players.OnDictionaryCleared += HandlePlayersCleared;

// Event handlers
private void HandlePlayerAdded(string playerId, Player player)
{
    Debug.Log($"Player added: {playerId}");
    UpdatePlayerList();
}

private void HandlePlayerChanged(string playerId, Player oldPlayer, Player newPlayer)
{
    Debug.Log($"Player updated: {playerId}");
    UpdatePlayerList();
}

// Use like a normal dictionary
players.Add("player1", new Player("Alice"));
players["player1"] = new Player("Alice Updated");
players.Remove("player1");

Serializable Dictionaries​

Unity doesn't serialize standard dictionaries, so QWR Utilities provides serializable alternatives.

QWRSerializableDictionary​

The QWRSerializableDictionary<TKey, TValue> is a dictionary that can be serialized by Unity:

using QWR.Utilities.Data;
using UnityEngine;
using System;

// Create a serializable dictionary type
[Serializable]
public class ItemDatabase : QWRSerializableDictionary<string, Item> { }

// Use in MonoBehaviour
public class InventoryManager : MonoBehaviour
{
    [SerializeField] private ItemDatabase items = new ItemDatabase();
    
    private void Start()
    {
        // Use like a normal dictionary
        if (items.ContainsKey("sword"))
        {
            Item sword = items["sword"];
            Debug.Log($"Found sword: {sword.name}");
        }
        
        // Add new items
        items.Add("potion", new Item("Health Potion"));
        
        // Iterate through items
        foreach (var pair in items)
        {
            Debug.Log($"{pair.Key}: {pair.Value.name}");
        }
    }
}

Custom Serializable Dictionaries​

You can create specialized serializable dictionaries for specific types:

// String to GameObject dictionary
[Serializable]
public class StringGameObjectDictionary : QWRSerializableDictionary<string, GameObject> { }

// Integer to AudioClip dictionary
[Serializable]
public class IntAudioClipDictionary : QWRSerializableDictionary<int, AudioClip> { }

// Enum to Sprite dictionary
[Serializable]
public class ItemTypeSpriteDictionary : QWRSerializableDictionary<ItemType, Sprite> { }

// Use in a MonoBehaviour
public class GameManager : MonoBehaviour
{
    [SerializeField] private StringGameObjectDictionary prefabs;
    [SerializeField] private IntAudioClipDictionary soundEffects;
    [SerializeField] private ItemTypeSpriteDictionary itemIcons;
    
    public GameObject GetPrefab(string key) => prefabs.ContainsKey(key) ? prefabs[key] : null;
    public AudioClip GetSound(int id) => soundEffects.ContainsKey(id) ? soundEffects[id] : null;
    public Sprite GetIcon(ItemType type) => itemIcons.ContainsKey(type) ? itemIcons[type] : null;
}

Weighted Random Selection​

Weighted random selection allows you to pick items with different probabilities.

QWRWeightedList​

The QWRWeightedList<T> is a list where items have weights for random selection:

using QWR.Utilities.Data;
using UnityEngine;

// Create a weighted list of items
QWRWeightedList<string> lootTable = new QWRWeightedList<string>();

// Add items with weights
lootTable.Add("Common Item", 70);
lootTable.Add("Uncommon Item", 20);
lootTable.Add("Rare Item", 9);
lootTable.Add("Legendary Item", 1);

// Get random item based on weights
string randomLoot = lootTable.GetRandom();

// Get multiple random items
string[] multipleItems = lootTable.GetRandomMultiple(5);

// Get random with exclusion
string randomNonCommon = lootTable.GetRandomExcluding("Common Item");

// Update weights
lootTable.UpdateWeight("Legendary Item", 2); // Double the legendary drop rate

// Get total weight
float totalWeight = lootTable.TotalWeight; // 100

// Clear the list
lootTable.Clear();

QWRWeightedRandomSelector​

For more complex weighted selection scenarios:

// Create a weighted random selector for enemies
QWRWeightedRandomSelector<EnemyType> enemySelector = new QWRWeightedRandomSelector<EnemyType>();

// Add items with weights
enemySelector.AddItem(EnemyType.Minion, 70);
enemySelector.AddItem(EnemyType.Soldier, 20);
enemySelector.AddItem(EnemyType.Elite, 9);
enemySelector.AddItem(EnemyType.Boss, 1);

// Get random with custom random function
EnemyType randomEnemy = enemySelector.GetRandom(CustomRandomFunction);

// Get random with probability value
float randomValue = Random.value; // 0-1 range
EnemyType enemy = enemySelector.GetRandomWithProbability(randomValue);

// Remove item
enemySelector.RemoveItem(EnemyType.Boss);

// Check if contains item
bool containsElite = enemySelector.ContainsItem(EnemyType.Elite);

Spatial Partitioning​

Spatial partitioning structures help optimize spatial queries.

QWRSpatialGrid​

The QWRSpatialGrid<T> is a 2D grid-based spatial partitioning system:

using QWR.Utilities.Data;
using UnityEngine;

// Create a spatial grid (cell size 5x5, world bounds -100 to 100)
QWRSpatialGrid<GameObject> spatialGrid = new QWRSpatialGrid<GameObject>(
    cellSize: 5f,
    worldBounds: new Bounds(Vector3.zero, new Vector3(200, 0, 200))
);

// Add objects to the grid
foreach (GameObject obj in objects)
{
    Vector2 position = new Vector2(obj.transform.position.x, obj.transform.position.z);
    spatialGrid.Add(obj, position);
}

// Query objects in radius
Vector2 queryPosition = new Vector2(player.transform.position.x, player.transform.position.z);
List<GameObject> nearbyObjects = spatialGrid.GetObjectsInRadius(queryPosition, 10f);

// Update object position
void UpdateObjectPosition(GameObject obj)
{
    Vector2 oldPosition = new Vector2(obj.transform.position.x, obj.transform.position.z);
    // Move object...
    Vector2 newPosition = new Vector2(obj.transform.position.x, obj.transform.position.z);
    spatialGrid.UpdatePosition(obj, oldPosition, newPosition);
}

// Remove object
spatialGrid.Remove(obj, new Vector2(obj.transform.position.x, obj.transform.position.z));

// Clear the grid
spatialGrid.Clear();

QWROctree​

The QWROctree<T> is a 3D spatial partitioning structure:

// Create an octree (min node size 2, max objects per node 10)
QWROctree<GameObject> octree = new QWROctree<GameObject>(
    bounds: new Bounds(Vector3.zero, new Vector3(100, 100, 100)),
    minNodeSize: 2f,
    maxObjectsPerNode: 10
);

// Add objects to the octree
foreach (GameObject obj in objects)
{
    octree.Add(obj, obj.GetComponent<Collider>().bounds);
}

// Query objects in bounds
Bounds queryBounds = new Bounds(player.transform.position, new Vector3(10, 10, 10));
List<GameObject> objectsInBounds = octree.GetObjectsInBounds(queryBounds);

// Query objects in frustum
List<GameObject> objectsInFrustum = octree.GetObjectsInFrustum(camera.frustum);

// Update object position
void UpdateObjectPosition(GameObject obj)
{
    Bounds oldBounds = obj.GetComponent<Collider>().bounds;
    // Move object...
    Bounds newBounds = obj.GetComponent<Collider>().bounds;
    octree.UpdatePosition(obj, oldBounds, newBounds);
}

// Remove object
octree.Remove(obj, obj.GetComponent<Collider>().bounds);

// Visualize the octree (for debugging)
octree.DebugDraw(Color.green, 0.1f);

State Machines​

State machines help manage complex state-based behaviors.

QWRStateMachine​

The QWRStateMachine<TState, TContext> is a generic state machine:

using QWR.Utilities.Data;
using UnityEngine;

// Define states
public enum EnemyState
{
    Idle,
    Patrol,
    Chase,
    Attack,
    Dead
}

// Enemy controller using state machine
public class EnemyController : MonoBehaviour
{
    private QWRStateMachine<EnemyState, EnemyController> stateMachine;
    
    // Enemy properties
    public float health = 100f;
    public float detectionRange = 10f;
    public float attackRange = 2f;
    
    private void Awake()
    {
        // Create state machine
        stateMachine = new QWRStateMachine<EnemyState, EnemyController>(this);
        
        // Register states
        stateMachine.RegisterState(EnemyState.Idle, OnIdleEnter, OnIdleUpdate, OnIdleExit);
        stateMachine.RegisterState(EnemyState.Patrol, OnPatrolEnter, OnPatrolUpdate, OnPatrolExit);
        stateMachine.RegisterState(EnemyState.Chase, OnChaseEnter, OnChaseUpdate, OnChaseExit);
        stateMachine.RegisterState(EnemyState.Attack, OnAttackEnter, OnAttackUpdate, OnAttackExit);
        stateMachine.RegisterState(EnemyState.Dead, OnDeadEnter, null, null);
        
        // Set initial state
        stateMachine.SetState(EnemyState.Idle);
    }
    
    private void Update()
    {
        // Update state machine
        stateMachine.Update();
    }
    
    // Idle state methods
    private void OnIdleEnter()
    {
        Debug.Log("Entering Idle state");
    }
    
    private void OnIdleUpdate()
    {
        // Check for player in detection range
        if (IsPlayerInRange(detectionRange))
        {
            stateMachine.SetState(EnemyState.Chase);
        }
    }
    
    private void OnIdleExit()
    {
        Debug.Log("Exiting Idle state");
    }
    
    // Other state methods...
    
    // Helper methods
    private bool IsPlayerInRange(float range)
    {
        // Implementation...
        return false;
    }
    
    // Public methods
    public void TakeDamage(float amount)
    {
        health -= amount;
        
        if (health <= 0 && stateMachine.CurrentState != EnemyState.Dead)
        {
            stateMachine.SetState(EnemyState.Dead);
        }
    }
}

QWRHierarchicalStateMachine​

The QWRHierarchicalStateMachine<TState, TContext> supports parent-child state relationships:

// Create a hierarchical state machine
QWRHierarchicalStateMachine<AIState, AIController> hsmachine = 
    new QWRHierarchicalStateMachine<AIState, AIController>(this);

// Register states with parent-child relationships
hsmachine.RegisterState(AIState.Combat, OnCombatEnter, OnCombatUpdate, OnCombatExit);
hsmachine.RegisterState(AIState.Melee, OnMeleeEnter, OnMeleeUpdate, OnMeleeExit, AIState.Combat);
hsmachine.RegisterState(AIState.Ranged, OnRangedEnter, OnRangedUpdate, OnRangedExit, AIState.Combat);
hsmachine.RegisterState(AIState.Explore, OnExploreEnter, OnExploreUpdate, OnExploreExit);

// Set initial state
hsmachine.SetState(AIState.Explore);

// Update
void Update()
{
    hsmachine.Update();
}

// When transitioning to Melee, Combat's Enter method will also be called if not already in Combat
void SwitchToMelee()
{
    hsmachine.SetState(AIState.Melee);
}

Creating Custom Data Structures​

You can create your own data structures that integrate with QWR Utilities:

using QWR.Utilities.Data;
using System.Collections.Generic;
using UnityEngine;

// Example: Custom spatial hash grid for 2D games
public class SpatialHashGrid2D<T>
{
    private Dictionary<int, List<T>> cells = new Dictionary<int, List<T>>();
    private float cellSize;
    
    public SpatialHashGrid2D(float cellSize)
    {
        this.cellSize = cellSize;
    }
    
    // Hash function to convert position to cell key
    private int GetCellKey(Vector2 position)
    {
        int x = Mathf.FloorToInt(position.x / cellSize);
        int y = Mathf.FloorToInt(position.y / cellSize);
        return (x * 73856093) ^ (y * 19349663); // Spatial hash function
    }
    
    // Add object to the grid
    public void Add(T obj, Vector2 position)
    {
        int key = GetCellKey(position);
        
        if (!cells.TryGetValue(key, out var list))
        {
            list = new List<T>();
            cells[key] = list;
        }
        
        list.Add(obj);
    }
    
    // Get objects near position
    public List<T> GetNearby(Vector2 position, float radius)
    {
        List<T> result = new List<T>();
        float radiusInCells = radius / cellSize;
        
        // Calculate cell range to check
        int minX = Mathf.FloorToInt((position.x - radius) / cellSize);
        int maxX = Mathf.FloorToInt((position.x + radius) / cellSize);
        int minY = Mathf.FloorToInt((position.y - radius) / cellSize);
        int maxY = Mathf.FloorToInt((position.y + radius) / cellSize);
        
        // Check all cells in range
        for (int x = minX; x <= maxX; x++)
        {
            for (int y = minY; y <= maxY; y++)
            {
                Vector2 cellPos = new Vector2(x * cellSize, y * cellSize);
                int key = GetCellKey(cellPos);
                
                if (cells.TryGetValue(key, out var list))
                {
                    result.AddRange(list);
                }
            }
        }
        
        return result;
    }
    
    // Remove object
    public bool Remove(T obj, Vector2 position)
    {
        int key = GetCellKey(position);
        
        if (cells.TryGetValue(key, out var list))
        {
            return list.Remove(obj);
        }
        
        return false;
    }
    
    // Clear the grid
    public void Clear()
    {
        cells.Clear();
    }
}

Best Practices​

Choosing the Right Data Structure​

  • Use Object Pools for frequently created and destroyed objects
  • Use Priority Queues when items need to be processed in a specific order
  • Use Observable Collections when you need to react to collection changes
  • Use Serializable Dictionaries for editor-configurable key-value pairs
  • Use Weighted Lists for random selection with different probabilities
  • Use Spatial Partitioning for efficient spatial queries
  • Use State Machines for complex state-based behaviors

Performance Considerations​

  • Pre-allocate capacity for collections when the size is known
  • Reuse objects with object pools instead of instantiating new ones
  • Use spatial partitioning to reduce the number of objects checked in queries
  • Consider memory usage when choosing data structures

Thread Safety​

Most data structures in QWR Utilities are not thread-safe by default. If you need thread safety:

// Example: Thread-safe object pool
public class ThreadSafeObjectPool<T> where T : MonoBehaviour
{
    private readonly QWRObjectPool<T> pool;
    private readonly object lockObject = new object();
    
    public ThreadSafeObjectPool(T prefab, int initialCapacity)
    {
        pool = new QWRObjectPool<T>(prefab, initialCapacity);
    }
    
    public T Get()
    {
        lock (lockObject)
        {
            return pool.Get();
        }
    }
    
    public void Release(T obj)
    {
        lock (lockObject)
        {
            pool.Release(obj);
        }
    }
}

Next Steps​

Now that you understand data structures, you can explore: