Spawn non-colliding entities

[umut-sahin]

Hi,

First of all, thanks for the lovely library!

I'm writing a game like Brotato and I'm spawning enemies randomly. The issue is I want to have a dynamic map and I want to avoid spawning entities that overlap with other entities. What's the best way to find a suitable spot to spawn the enemies?

Also, I'm setting the velocity of entities every frame, so in practice it's not an issue, but I'd prefer to have a proper way to spawn entities without colliding.

Also, I might introduce pre-spawn indicator (red x in Brotato), and those shouldn't move until the entities actually spawn.

Thanks!

[Jondolf]

Hi! I have two solutions depending on your requirements.

Pick random positions until free space is found (easy)

If it's enough to pick random positions until a suitable spot is found, you can use SpatialQuery::shape_intersections:

fn spawn_enemy(mut commands: Commands, spatial: SpatialQuery) {
    let enemy_shape = Collider::ball(50.0);

    // You can filter by layer etc.
    let filter = SpatialQueryFilter::default();

    // Try 1000 times
    for _ in 0..1000 {
        let position = random_position();

        // If space is empty, spawn enemy
        if spatial.shape_intersections(&enemy_shape, initial_guess, 0.0, filter).is_empty() {
            commands.spawn(...);
            return;
        }
    }
}

This is a simple approach, but it has no guarantee of ever finding a suitable spot because it's fully random, and you might still want the spawn position to be near the initial target position.

Iteratively adjust target until free space is found (more robust but more complex)

If you want to spawn near the initial guess but adjusted so that there is no intersection, you'll probably need to make an iterative algorithm like this:

1. Compute intersections at initial guess.
   • If there are no intersections, free space has been found!
2. Compute contacts between the entity to spawn and the entities intersecting with it.
3. Use returned contact data to nudge the position away from the intersecting colliders.
4. Repeat with new guess, continuing the process until there is no intersection or some maximum iteration count is reached.

I went ahead and implemented this algorithm:

/// Finds a free space where an entity can be spawned without intersections.
///
/// The `target_transform` will be used as an initial guess. If there are intersections,
/// the position will be iteratively adjusted until a free space is found or `max_iterations`
/// is reached.
///
/// The given `collider` will be scaled by `margin` to maintain a minimum spawning distance
/// to nearby entities and to avoid floating point precision issues.
///
/// If no free space can be found before `max_iterations` is reached, `None` is returned.
fn find_free_space(
    spatial: &SpatialQuery,
    query: &Query<(&Collider, &Transform)>,
    target_transform: Transform,
    collider: &Collider,
    margin: Scalar,
    max_iterations: usize,
) -> Option<Transform> {
    let mut target_position = target_transform.translation.truncate();
    let rotation = Rotation::from(target_transform.rotation);

    // Scale collider by margin
    let mut collider = collider.clone();
    collider.set_scale(Vector::ONE + margin, 8);

    let filter = SpatialQueryFilter::default();

    // Iteratively update the position by computing contacts against intersecting colliders
    // and moving the target position based on the data.
    // The algorithm stops once there are no intersections or `max_iterations` is reached.
    for _ in 0..max_iterations {
        // Get entities intersecting the space
        let intersections = spatial.shape_intersections(
            &collider,
            target_position,
            rotation.as_radians(),
            filter.clone(),
        );

        if intersections.is_empty() {
            // No intersections, free space found
            return Some(target_transform.with_translation(target_position.extend(0.0)));
        } else {
            // Iterate over intersections and move the target position
            // based on computed contact data.
            for entity in intersections {
                // Get collider of intersecting entity
                let Ok((hit_collider, hit_transform)) = query.get(entity) else {
                    continue;
                };
                let hit_translation = hit_transform.translation.truncate();

                // Compute contact between the entity to spawn and the intersecting entity
                if let Ok(Some(contact)) = contact_query::contact(
                    &collider,
                    target_position,
                    rotation,
                    hit_collider,
                    hit_translation,
                    hit_transform.rotation,
                    0.0,
                ) {
                    let normal = contact.global_normal2(&hit_transform.rotation.into());

                    // Epsilon to avoid floating point precision issues
                    let delta = normal * (contact.penetration + 0.00001);

                    // Move target position to solve overlap
                    target_position += delta;
                }
            }
        }
    }

    None
}

You could then use it like this:

fn spawn_enemy(
    mut commands: Commands,
    spatial: SpatialQuery,
    query: Query<(&Collider, &Transform)>,
) {
    let target_transform = random_position();

    if let Some(transform) = find_free_space(
        &spatial,
        &query,
        target_transform,
        &collider,
        0.25,
        500,
    ) {
        commands.spawn((EnemyBundle::default(), transform));
    }
}

I made a quick demo for this where you can spawn several different shapes:

2023-12-03.17-41-13.mp4

As you can see, it can't always find a free space at the moment, but you could fall back to testing another random position in those cases. The issue could also probably be resolved by tweaking the algorithm a bit to avoid getting stuck in some places.

Another slight limitation is that the algorithm currently only checks for intersections against existing entities, so if you were to spawn e.g. 100 enemies at once, it's likely that some of them would be intersecting. To fix this, you could modify the logic to also compute intersections against enemies that you have already found a position for, but this would add some extra complexity.

I've seen this question a few times now, so I'll add my demo as an example in the repo soon :)

[umut-sahin]

What an amazing answer, thanks a lot!

For spawning multiple enemies, would running apply_deferred between each spawn help? I already have exclusive world access.

[Jondolf]

I think you also need to run spatial_query.update_pipeline() (after the apply_deferred) to make sure that the new entities are included in the queries. Normally it's run once per frame in the physics schedule, but here you need to access the entities immediately. Other than that, I believe it should work :)

[umut-sahin]

Just tried it, doesn't work unfortunately.

intersections is empty when I try to spawn the second entity in this configuration: https://www.desmos.com/calculator/tsftr5uqby. Here are the relevant piece of code in my branch:

• https://github.com/umut-sahin/mythmallow/blob/fb6ebce07e628f4c79f48b78622e2b4b5247fc76/game/src/enemy/systems.rs#L206-L218
• https://github.com/umut-sahin/mythmallow/blob/fb6ebce07e628f4c79f48b78622e2b4b5247fc76/game/src/enemy/systems.rs#L52-L57

Not sure why it's not working, I'd have guessed it's related to entity not yet registered to physics world somehow, but I guess spatial_query.update_pipeline() was for that. Maybe I'm not calling it appropriately?

It is very easy to reproduce if needed:

git clone --single-branch --branch better-enemy-spawn https://github.com/umut-sahin/mythmallow.git
cd mythmallow
cargo run -- --seed 42

Thanks for the amazing answers btw, that video was one of the coolest demos created for an issue IMO!

[umut-sahin]

Solved the issue by adding a spawn interval between the enemies within a group. This also improved the feel of the game IMO. Thanks for the help ❤️

(here is the PR, in case anyone is interested umut-sahin/mythmallow#40)