Jondolf
commented
9 months ago 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:
- Compute intersections at initial guess.
- If there are no intersections, free space has been found!
- Compute contacts between the entity to spawn and the entities intersecting with it.
- Use returned contact data to nudge the position away from the intersecting colliders.
- 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:
https://github.com/Jondolf/bevy_xpbd/assets/57632562/18742685-6601-4f38-923e-0544a298bbe2
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
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!