ECS 中的稀疏集

引言

在 ECS 中，Entity 通常只是一个整数 ID，Component 则按类型分开存储。于是每一种 Component 都需要解决同一个问题：如何通过 Entity ID 快速找到数据，同时又能连续遍历所有 Component？

最直觉的做法是使用 Dictionary<int, T>。它确实能完成 Entity 到 Component 的映射，但 ECS 的 System 往往会在每一帧遍历成千上万个 Component。相比单次查询，遍历时的内存布局和缓存命中率更加重要。

稀疏集（Sparse Set）正好同时满足这两个需求：通过稀疏数组完成 O(1) 查询，通过稠密数组保存连续的 Entity 和 Component 数据。

基本结构

一个稀疏集由三部分组成：

• sparse：下标是 Entity ID，值是该 Entity 在稠密数组中的位置
• denseEntities：连续保存当前拥有该 Component 的 Entity ID
• denseComponents：与 denseEntities 一一对应，连续保存 Component

假设稠密数组中依次存放 Entity 5、2、8，那么它们之间的关系是：

sparse[2] = 1
sparse[5] = 0
sparse[8] = 2

denseEntities:   [5, 2, 8]
denseComponents: [A, B, C]

查询 Entity 2 时，先通过 sparse[2] 得到稠密下标 1，再访问 denseComponents[1] 即可。整个过程只需要数组索引，不需要计算哈希值，也不需要沿着树节点查找。

为了避免删除后残留的旧下标造成误判，成员判断通常还会验证：

denseEntities[sparse[entity]] == entity

与常见容器的对比

容器	查询	遍历与内存布局	适用场景
直接数组	O(1)	连续，但需要为空槽位付出空间和遍历成本	ID 范围很小且数据接近满载
哈希表	平均 O(1)	需要桶、哈希和冲突处理，条目还会携带额外元数据	ID 范围很大或无法控制，随机查询较多
红黑树	O(log n)	节点包含链接信息，局部性较差，但可以有序遍历	需要按 Entity ID 排序、范围查询或稳定的最坏复杂度
稀疏集	O(1)	Component 紧密排列，适合连续遍历	ID 范围可控，并且遍历远多于结构修改的 ECS

以 C# 容器为例，哈希表通常对应 Dictionary<int, T>，红黑树可以对应 SortedDictionary<int, T>。两者都是通用容器，而稀疏集利用了 ECS 的额外条件：Entity ID 是非负整数，System 不要求按 ID 顺序遍历，并且 Entity ID 的上界可以由 World 控制。

稀疏集并不是在所有方面都更好。它的 sparse 数组大小取决于 Entity ID 的范围。如果只创建了几个 Entity，ID 却已经增长到几千万，内存占用会非常不划算。因此实际 ECS 通常会限制 World 的 Entity 容量，并用空闲列表复用 Entity ID。

C# 实现

下面是一份简化的 Component 存储。构造时需要传入 World 支持的 Entity 容量，避免某个异常 ID 让 sparse 无限制扩张。稠密数组按需扩容，因此新增为均摊 O(1)，删除和查询为 O(1)；发生扩容的那次新增仍然需要复制数组。

示例使用 where T : struct，让 Component 值直接连续存放在数组中。如果允许 class Component，连续排列的只是对象引用，对象本身仍可能分散在托管堆上。

using System;
using System.Collections.Generic;

public sealed class SparseSet<T> where T : struct
{
    private readonly int[] _sparse;
    private int[] _denseEntities = Array.Empty<int>();
    private T[] _denseComponents = Array.Empty<T>();
    private int _count;

    public SparseSet(int entityCapacity)
    {
        if (entityCapacity < 0)
            throw new ArgumentOutOfRangeException(nameof(entityCapacity));

        _sparse = new int[entityCapacity];
    }

    public int Count => _count;

    public ReadOnlySpan<int> Entities =>
        _denseEntities.AsSpan(0, _count);

    public Span<T> Components =>
        _denseComponents.AsSpan(0, _count);

    public bool Contains(int entity)
    {
        return TryGetDenseIndex(entity, out _);
    }

    public void Add(int entity, T component)
    {
        if ((uint)entity >= (uint)_sparse.Length)
        {
            throw new ArgumentOutOfRangeException(
                nameof(entity),
                "Entity ID is outside the configured capacity.");
        }

        if (Contains(entity))
            throw new InvalidOperationException(
                $"Entity {entity} already has {typeof(T).Name}.");

        EnsureDenseCapacity(_count + 1);

        int denseIndex = _count++;
        _sparse[entity] = denseIndex;
        _denseEntities[denseIndex] = entity;
        _denseComponents[denseIndex] = component;
    }

    public ref T Get(int entity)
    {
        if (!TryGetDenseIndex(entity, out int denseIndex))
        {
            throw new KeyNotFoundException(
                $"Entity {entity} does not have {typeof(T).Name}.");
        }

        return ref _denseComponents[denseIndex];
    }

    public bool Remove(int entity)
    {
        if (!TryGetDenseIndex(entity, out int denseIndex))
            return false;

        int lastIndex = --_count;

        if (denseIndex != lastIndex)
        {
            int lastEntity = _denseEntities[lastIndex];

            _denseEntities[denseIndex] = lastEntity;
            _denseComponents[denseIndex] = _denseComponents[lastIndex];
            _sparse[lastEntity] = denseIndex;
        }

        Array.Clear(_denseEntities, lastIndex, 1);
        Array.Clear(_denseComponents, lastIndex, 1);
        return true;
    }

    private bool TryGetDenseIndex(int entity, out int denseIndex)
    {
        if ((uint)entity >= (uint)_sparse.Length)
        {
            denseIndex = -1;
            return false;
        }

        denseIndex = _sparse[entity];
        return (uint)denseIndex < (uint)_count
            && _denseEntities[denseIndex] == entity;
    }

    private void EnsureDenseCapacity(int required)
    {
        if (required <= _denseEntities.Length)
            return;

        long doubled = Math.Max(4L, (long)_denseEntities.Length * 2);
        int newCapacity = (int)Math.Min(
            _sparse.Length,
            Math.Max(required, doubled));

        Array.Resize(ref _denseEntities, newCapacity);
        Array.Resize(ref _denseComponents, newCapacity);
    }
}

删除时不需要移动后面的所有元素。假设删除稠密数组中间的 Entity，只要将最后一个 Entity 和 Component 搬到被删除的位置，再修改它在 sparse 中记录的下标即可。这就是常见的 swap-back 删除。

它的代价是遍历顺序会发生变化。如果业务依赖稳定顺序，就需要额外维护顺序，或者改用其他容器。

在 System 中遍历

下面用 Position 和 Velocity 演示一个最简单的移动系统。这里假设拥有 Velocity 的 Entity 更少，因此从 Velocity 开始遍历：

public struct Position
{
    public float X;
    public float Y;
}

public struct Velocity
{
    public float X;
    public float Y;
}

public static class MovementSystem
{
    public static void Update(
        SparseSet<Position> positions,
        SparseSet<Velocity> velocities,
        float deltaTime)
    {
        ReadOnlySpan<int> entities = velocities.Entities;
        Span<Velocity> velocityData = velocities.Components;

        for (int i = 0; i < entities.Length; i++)
        {
            int entity = entities[i];
            if (!positions.Contains(entity))
                continue;

            ref Position position = ref positions.Get(entity);
            ref Velocity velocity = ref velocityData[i];

            position.X += velocity.X * deltaTime;
            position.Y += velocity.Y * deltaTime;
        }
    }
}

Velocity 在内存中连续排列，System 可以直接顺序扫描；对于同时拥有 Position 的判断，则通过另一个稀疏集进行 O(1) 查询。实际实现查询更多 Component 时也是同样的思路：选择数量最少的稠密数组进行遍历，再到其他稀疏集中检查 Entity 是否存在。

实际使用中的限制

1. Entity ID 的范围必须可控。 本文代码在构造时固定稀疏数组容量，通常需要配合 World 容量和 ID 回收机制。

2. 删除会改变遍历顺序。 swap-back 删除很快，但不能依赖 Component 的插入顺序。

3. Entity ID 复用通常需要版本号。 完整 ECS 通常把 Entity 表示为“索引 + Generation”，防止旧 Entity 引用误操作复用后的新 Entity。

4. 遍历期间不要直接增删。 结构变化可能使 Span 和稠密下标失效，实际项目中一般使用 Command Buffer，在 System 执行完以后统一修改。

总结

哈希表擅长处理通用的键值映射，红黑树适合需要有序访问的场景；稀疏集则针对 ECS 的使用方式做了取舍。它用额外的稀疏索引换取 O(1) 查询，并让真正需要逐帧遍历的 Component 保持紧密排列。

其核心可以概括为一句话：稀疏数组负责找到数据，稠密数组负责高效遍历数据。