Sparse set を利用した構造

[rrbox]

辞書よりもイテレーションに特化しているかもです。パフォーマンス比較してみたいところです。 また entity の実装を UUID ではなく、加算される数値を利用できるようにもし、衝突を完全に回避します。

下のは試しに考えた見たやつです。

import Foundation

class World {
    let buffer = WorldBuffer()
}

struct SparseSet<T: Component> {
    var indices: [Entity] = []
    var data: [T] = []
}

class SparseSetRef<T: Component>: BufferElement {
    var sparseSet: SparseSet<T>
    init(sparseSet: SparseSet<T>) {
        self.sparseSet = sparseSet
        super.init()
    }

    required init?(coder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }
}

class SparseSetBuffer {
    let buffer: Buffer
    init(buffer: Buffer) {
        self.buffer = buffer
    }

    func addComponentStrage<T: Component>(typeOf type: T.Type) {
        self.buffer.addComponent(SparseSetRef(sparseSet: SparseSet<T>()))
    }

    func sparseSetRef<T: Component>(typeOf type: T.Type) -> SparseSetRef<T>? {
        self.buffer.component(ofType: SparseSetRef<T>.self)
    }
}

extension WorldBuffer {
    var sparseSetBuffer: SparseSetBuffer { SparseSetBuffer(buffer: self) }
}

final class Query<C: Component>: SystemParameter {
    let ref: SparseSetRef<C>
    init(ref: SparseSetRef<C>) {
        self.ref = ref
    }

    static func register(to worldBuffer: WorldBuffer) {
        guard worldBuffer.sparseSetBuffer.sparseSetRef(typeOf: C.self) == nil else { return }
        worldBuffer.sparseSetBuffer.addComponentStrage(typeOf: C.self)
    }

    static func getParameter(from worldBuffer: WorldBuffer) -> Query<C>? {
        Query<C>(ref: worldBuffer.sparseSetBuffer.sparseSetRef(typeOf: C.self)!)
    }
}

final class Query2<C0: Component, C1: Component>: SystemParameter {
    let ref: (SparseSetRef<C0>, SparseSetRef<C1>)
    init(ref: (SparseSetRef<C0>, SparseSetRef<C1>)) {
        self.ref = ref
    }

    static func register(to worldBuffer: WorldBuffer) {
        guard worldBuffer.sparseSetBuffer.sparseSetRef(typeOf: C0.self) == nil else { return }
        guard worldBuffer.sparseSetBuffer.sparseSetRef(typeOf: C1.self) == nil else { return }
        worldBuffer.sparseSetBuffer.addComponentStrage(typeOf: C0.self)
        worldBuffer.sparseSetBuffer.addComponentStrage(typeOf: C1.self)
    }

    static func getParameter(from worldBuffer: WorldBuffer) -> Query2<C0, C1>? {
        Query2<C0, C1>(ref: (worldBuffer.sparseSetBuffer.sparseSetRef(typeOf: C0.self)!,
                         worldBuffer.sparseSetBuffer.sparseSetRef(typeOf: C1.self)!))
    }
}

[rrbox]

Entity の管理方法を検討するべきだと思います（Entity mapper）。 Sparse set の場合はインクリメント方式が相性がいいかもしれません。

[rrbox]

Filter についても考察すべきです

[rrbox]

v0.1 時点の query の辞書部分を sparse set に置き換えることができるかと思います。Entity に sparse index に変換するルールも同時に作る必要がありそう。

[rrbox]

Sparse set の最小実装を考えました。Swift playgrounds では正常な動作が確認されています。

構造体で実装されており、entity を key にした Dictionary と完全に置き換えることができます。運用の際は、Query などで使用されている dictionary と置き換える形となります。

Entity の slot をインクリメントする仕組みは別途用意する必要があります。Entitiesという構造体を作り、そこに実装しましょう。World に Entities のインスタンスを配置し、entity を生成するたびにインクリメントしていきます。

Entity を生成する際は、ただインクリメントするだけでなく、再利用することも考慮にいれましょう。下記の SparseSet は pop で空いた slot を再利用できるようにはしていますが、Entity の生成については責任をもたないです。

struct Entity: Equatable {
    let slot: Int
    let generation: Int
}

struct SparseSet<T> {
    typealias DenseIndex = Int

    var sparse: [DenseIndex?]
    var dense: [Entity]
    var data: [T]

    func value(forEntity entity: Entity) -> T? {
        guard let i = self.sparse[entity.slot] else { return nil }
        guard self.dense[i] == entity else { return nil }
        return self.data[i]
    }

    mutating func update(forEntity entity: Entity, _ execute: (inout T) -> ()) {
        guard let i = self.sparse[entity.slot] else { return }
        guard self.dense[i].generation == entity.generation else { return }
        execute(&self.data[i])
    }

    mutating func update(_ execute: (inout T) -> ()) {
        for i in self.data.indices {
            execute(&self.data[i])
        }
    }

    mutating func allocate() {
        self.sparse.append(nil)
    }

    mutating func insert(_ value: T, withEntity entity: Entity) {
        let denseIndex = self.dense.count
        self.sparse[entity.slot] = denseIndex
        self.dense.append(entity)
        self.data.append(value)
    }

    mutating func pop(entity: Entity) {
        assert(entity.generation == self.dense[self.sparse[entity.slot]!].generation)
        let denseIndexLast = self.dense.count-1
        let removeIndex = self.sparse[entity.slot]!

        self.sparse[self.dense[denseIndexLast].slot] = removeIndex
        self.dense.swapAt(removeIndex, denseIndexLast)
        self.data.swapAt(removeIndex, denseIndexLast)
        self.data.removeLast()
        self.dense.removeLast()
    }
}

ついでに、デバッグ用にどうぞ。

#if DEBUG
extension SparseSet: CustomStringConvertible {
    var description: String {
        let s = self.sparse.map { denseIndex in
                if let i = denseIndex { return "\(i) " }
                else { return "- " }
            }
        .reduce(into: "[ ") {
            $0 += $1
        } + "]"
        return "SparseSet<\(T.self)> {\n\tentities: \(self.dense.map { "(\($0.slot) \($0.generation))" })\n\tsparseMap: \(s)\n\tdata: \(self.data)\n}"
    }
}
#endif

---

pop すると正しく検索できなくなるようです。ただしいコードに書き直します... ↑修正しました。

[rrbox]

Entity を生成する方法

Sparse set を用いた場合、Entity は sparse index を内部にもつ構造体になります。sparse index はインクリメントで生成できます。問題は、一度削除された slot を再利用する場合のアルゴリズムを考える必要があることです。現状の考えは、entity を despawn するたびに削除した entity の slot を何かしらの方法で保持しておくことです。初めに単方向連結リストを使用した方法を考えたいです。

---

単方向連結リストでなくとも、スタックで実装できそうです。

• 最初は entity (slot 0, generation 0) をスタックしておく。
• entity が despawn したらその entity の generation がインクリメントされた新たな entity をスタックする。
• 新たに entity を生成する際は、スタックされた entity を取り出し、スタックをポップする。
• スタック数がゼロになったら、slot を +1 した新たな entity をスタックする。

[rrbox]

ちなみに、Array は RandomAccessCollection に準拠しているので、辞書よりも効率の良い部分がいくつかありそうです。

• randomElement() の計算量が O(1) になる
• count も O(1) で計算される

[rrbox]

69 で達成しました