Find the nearest transform

[violet remnant]

I'm looking for a generic way to find the nearest transform to a given one. Say I have a Transform of an entity and a Query<&Transform>. Within the query I want to find the nearest target. I guess it must be a very common operation in games. Is there a common (built in?) way to do this?

Below is my attempt to reinvent the wheel. Excuse my Rust. I'm still learning.

fn nearest<'a, I>(origin: &Transform, candidates: &I) -> Option<Transform>
where
    I: IntoIterator<Item = &'a Transform> + Clone ,
{
    let mut best_candidate: Option<Transform> = None;
    let mut shortest_distance = INFINITY;

    for candidate in candidates.clone().into_iter() {
        if best_candidate == None {
            // Anything is better than nothing
            best_candidate = Some(*candidate);
            shortest_distance = candidate.translation.distance(origin.translation);
        } else {
            let distance = candidate.translation.distance(origin.translation);
            if distance < shortest_distance {
                shortest_distance = distance;
                best_candidate = Some(*candidate);
            }
        }
    }

    best_candidate
}

And here's how I am trying to use it:

nearest(transform, &targets.iter())

The type of targets is Query<&Transform, With<Target>>.

This gives me:

the trait `Clone` is not implemented for `QueryIter<'_, '_, &bevy::prelude::Transform, bevy::prelude::With<Target>>`

It seems to me that Clone should not be required, but as I said, I'm still green when it comes to borrowing and the like.

Find the nearest transform

[charred lagoon]

Have you seen query.iter_combinations?

[violet remnant]

Hi, Alice! I was just looking at https://github.com/bevyengine/bevy/issues/1631 and realized it's you 🙂 Anyway, thanks, but I'm not sure how to use your advice. In my case the first transform is not a member of the targets query. It comes from a different query. Am I missing something?

[swift current]

Some amateur commentary here, but I was curious enough to dig in. Take with a grain of salt.

IntoIterator is implemented for &Query, so if you use I rather than &I you seemingly don't need Clone or to do any cloning.

Also, https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.min_by may be of use here.

As a side-note, that loop can be cleaned up quite a bit

for candidate in candidates.into_iter() {
    let distance = candidate.translation.distance(origin.translation);

    if best_candidate == None || distance < shortest_distance {
        best_candidate = Some(*candidate);
        shortest_distance = distance;
    }
}

[charred lagoon]

(thanks, I was skimming and missed the critical distinction)

[violet remnant]

NP. The iter_combinations is worth knowing about.

[swift current]

This is a naive approach to the "nearest neighbor search" which can be accelerated with a spatial data structure.

[drifting compass]

Normally you'd query GlobalTransform if you are retrieving the position of entities

not Transform

[oak fox]

do iterators in rust not have a sort method that takes a custom comparator?

[swift current]

of course, also min_by

[oak fox]

i would probably prefer that over manually iterating

the end result is the same it's just a bit cleaner

[violet remnant]

Thanks for all the tips! Regarding the code cleanliness, let's say I follow the Unix philosophy: "make it work, then make it right" 😉

But seriously, everything you all said is very useful.

Solved, mostly thanks to @swift current's remark about &Query implementing IntoIterator. Here is my spaghetti. I'll clean it up later, but please feel free to roast it: https://gitlab.com/tad-lispy/bevy-animated-sprite-playground/-/commit/be3ba1e1d3513f406bf833205f415bfbf1605042

[sullen ember]

You can't sort an iterator I think

iterators are lazy concepts, in principle just reading things 1 by 1, it would have to jump all over to do a sort

But also sorting everything just to find the one nearest is extremely wasteful, .min_by is correct

[swift current]

ah yeah, oops.

[quick kettle]

You might want to look at https://crates.io/crates/bevy_spatial which has a way to get the nearest neighbour without having to iter everything

[violet remnant]

Thanks for the suggestion @quick kettle (also mentioned by @swift current before). The bevy_spatial crate looks like a right tool for me, but I can't figure out how to use it with WASM target. It has something to do with the rayon crate. I made an issue here: https://github.com/laundmo/bevy-spatial/issues/6

BTW I'm really impressed by the performance of Bevy. Even without the use of spatial tree (i.e. with naive iteration over everything) I can get up to 3000 zombies go smooth on my laptop and ~1000 on my 3 YO phone. This includes rapier colliders and application of forces. Super cool! https://tad-lispy.gitlab.io/bevy-animated-sprite-playground/?scale=0.1&zombies=400&spread=1000. I would really love to see how many I can get with the KDTree in place.

[swift current]

Hm, it would be nice if they had kd-tree's rayon feature behind a feature gate.

But it's only the kd-tree dependency bringing that in, so you could try the rstar feature instead.

Also if you're already using rapier you could probably use a big circle sensor collider for the same purpose? Haven't looked very hard at what's going on in your project, but rapier is already managing a spatial data structure (qbvh) for its broad phase.

[violet remnant]

I tried using the rstar feature, but the game became significantly slower. I guess it's because the rstar is designed for static entities. But my zombies are moving a lot 😅 I'm chatting with @dusty portal on GitHub about the KDTree on the web. In the meantime I'll try the collider idea.

[dusty portal]

Hm, it would be nice if they had kd-tree's rayon feature behind a feature gate.

that's what im planning to do, really should have considered that initially 😅

[dusty portal]

yeah, rstar is great for fast queries but it's really slow to rebuild from scratch (which it has to if locations update)

kd-tree is rebuilt each update anyways, but it's a bit slower to query in my experience.

there's also some settings you can tweak to make it update less often if you don't need it to be as accurate.

[swift current]

you're already paying the overhead of maintaining a spatial index if your entities are rapier colliders though, so probably best to make use of that if possible.

[violet remnant]

I've been reading the Rapier guide. Is it the intersection graph that I need to use, as described here: https://rapier.rs/docs/user_guides/bevy_plugin/advanced_collision_detection#the-intersection-graph? Or did you have something else in mind?

[swift current]

Seems like that could work, but maybe you'd need to keep track of the entity of a child-sensor separately or something.

https://rapier.rs/docs/user_guides/bevy_plugin/scene_queries#intersection-test might be easier, not sure.

I've only dealt with collision events in rapier which don't seem appropriate here.

[violet remnant]

Thanks again. I opted to use AABB test with some extra optimizations and went from ~2k to ~10k with the same frame rate. Big gain!

Here's the commit: https://gitlab.com/tad-lispy/bevy-animated-sprite-playground/-/commit/b9e030ddc7f47aac94f6ebbc59b6683204e6e867

[violet remnant]

Interestingly it seems that the debug build got significantly slower. But that's not a big deal, given the gains in production. For anyone following the same approach, it's important to measure the release build, not the debug.