Q: How to iter over every component against every other only once, excluding self?

[EriKWDev]

Hi!
When doing collision testing, it is common to do a collision check for every collider against every other collider, ignoring checking self against self and ignoring the order of the colliders.
I would normally write code like the following to accomplish that:

for id_1 in 0..num_ids - 1 {
    for id_2 in id_1 + 1..num_ids {
        // check collider with id_1 against collider with id_2
    }
}

The above loop is nice since it avoids any unnecessary iterations and combinations of id_1 and id_2.
id_1 vs id_2 is the same as id_2 vs id_1 and this loop nicely ignores those.

With shipyard, I'm struggling to do this consisely.

Idea 1

Keep track of which id combos we have checked and continue if we detect it's already done

pub fn system_test_collisions_1(colliders: View<Collider>, mesh_storage: UniqueView<MeshStorage>) {
    let mut done = std::collections::HashSet::new();
    let mut results = vec![];

    for (id_a, collider_a) in colliders.iter().with_id() {
        for (id_b, collider_b) in colliders.iter().with_id() {
            let (key_ab, key_ba) = ((id_a, id_b), (id_b, id_a));

            if done.contains(&key_ab) || done.contains(&key_ba) {
                continue;
            }

            done.insert(key_ab);
            done.insert(key_ba);

            if let Some(result) = test_collision(&collider_a, id_a, &collider_b, id_b, &mesh_storage) {
                results.push(result);
            }
        }
    }
}

Idea 2

Create a list of all ids with a collider, build up pairs of ids and components according to the loop above, then finally iterate over the pairs.

fn system_test_collisions_2(colliders: View<Collider>, mesh_storage: UniqueView<MeshStorage>) {
    let ids = colliders
        .iter()
        .with_id()
        .map(|(id, _)| id)
        .collect::<Vec<_>>();

    let mut pairs = vec![];
    for i in 0..ids.len() - 1 {
        let id_a = ids[i];
        let Ok(collider_a) = colliders.get(id_a) else { continue };

        for j in i + 1..ids.len() {
            let id_b = ids[j];
            let Ok(collider_b) = colliders.get(id_b) else { continue };

            pairs.push((id_a, collider_a, id_b, collider_b));
        }
    }

    let results = pairs
        .iter()
        .filter_map(|(id_a, collider_a, id_b, collider_b)| {
            test_collision(&collider_a, id_a, &collider_b, id_b, &mesh_storage)
        })
        .collect::<Vec<_>>();
}

---

Idea 1 seems unnecessarily slow with hashing and allocations, Idea 2 seems a bit convoluted but is perhaps better since it can easily be parallellized with par_iter if I want to.

I feel like one could do better. I would like to do the above more idiomatically or in a more performant way with less allocations if possible. How would you do this kind of iteration in shipyard? Also, next level: what if I want to do mutable borrows of the colliders? xP

[leudz]

Hi!
I just want to preface this message by saying that an ECS is not the best data-structure for collision. For prototyping it's fine but you might want to move to a dedicated data-structure in the future.

I agree idea 1 would be pretty slow but idea 2 will be good once simplified a bit.

Let's start with the immutable version:

fn system_test_collisions(colliders: View<Collider>) {
    let results = (0..colliders.len() - 1)
        .zip(colliders.iter().with_id())
        .filter_map(|(i, (id_a, colliders_a))| {
            colliders.as_slice()[i + 1..]
                .iter()
                .map(|collider_b| (colliders.id_at(i).unwrap(), collider_b))
                .find_map(|(id_b, colliders_b)| test_collision(colliders_a, colliders_b))
        })
        .collect::<Vec<_>>();
}

Since it's not easy to ignore the last value of an iterator I use a range instead of enumerate.
For the inner iteration you could use colliders.iter().skip(i + 1) but I haven't optimized it so using as_slice() will be faster for now.

And that's it for the immutable version. For the mutable version it's a bit more complicated.
We can't both iterate over the ids and access components at the same time. So we'll do it in two steps like idea 2.

fn system_test_collisions2(mut colliders: ViewMut<Collider>) {
    let ids = colliders.iter().ids().collect::<Vec<_>>();

    let results = ids[0..ids.len() - 1]
        .iter()
        .enumerate()
        .filter_map(|(i, id_a)| {
            ids[i + 1..].iter().find_map(|id_b| {
                colliders.apply_mut(*id_a, *id_b, |collider_a, collider_b| {
                    test_collision2(collider_a, *id_a, collider_b, *id_b)
                })
            })
        })
        .collect::<Vec<_>>();
}

I start by collecting the ids, ids method is the same as .with_id().map(|(id, _)| id).
apply_mut takes 2 different EntityId and a closure to apply to the 2 components.