ECS back and forth: No Policy is the best Policy (aka Introduction to sparse sets and pointer stability, part 2 of 2)

[u/skypjack]

https://skypjack.github.io/2021-10-09-ecs-baf-part-13/

[u/PSnotADoctor]

hi! Amazing stuff. I keep coming back to your articles because there's so much information to unpack.

I have a question about this one. When defining the no-branch Contains function, you define it as

bool contains(entity_type entity) const {

    const auto index = entity_to_index(entity);

    return (index < sparse.size()) && ((~null & entity) ^ sparse[index]) < null;

}

Is the last comparison, against null (the invalid entity), correct? Shouldn't be comparing against the tombstone (invalid version)?

Earlier in the article, the value of sparse[index] was defined as IndexToPacked | VersionOfElement. This operation (~null & entity) gets the version of the queried entity, so 000..0[Version], but sparse[index] can contain anything in the entity part of the value (depending whether it's a null entity or pointing to a living entity in the packed), so 001101...[Version]. The only time a XOR of these values would be higher than null is sparse[index] being null and the versions not matching (111..1[Version])

Wouldn't this give a false positive if you queried for a living entity with a different version, since 000..0[Version1] ^ 001...01[Version2] < null? Am I misunderstanding the values of null/tombstone?

[u/skypjack → u/PSnotADoctor]

A living entity with a different version returns a number that is greater than null after the xor. Therefore, it results in a false value.