# Finding empty space

So this is probably a question with a relatively easy solution since I’m a newbie to Panda3D but I’m trying to figure out how to find an empty spot that can fit an object in a scene. This would be useful both to spawn new objects (which will occur regularly) and for some basic pathfinding (can a moving creature fit into the space it wants to go into?).

I can think of a brute-force way to do this: add collision solids at possible locations, check for collisions, and then accept any collision-free entries (and then pick within those to create the required behavior). However, that will rapidly become prohibitively time-consuming (some of those operations might easily require 3,000 individual collision solids to check all possibly locations).

It might also be possible to create a larger collision solid, check all collisions with that, calculate tighBounds on those, and figure out where the “holes” are between them. For instance, a creature could create a collision sphere with radius equal to its body length, check all objects that collide with it (i.e., every object within one body length), check the positions of those objects and their dimensions and calculate where there is space to fit itelf.

However, what I think should be fastest would be if I could somehow restrict the behavior of a collision traverser so that I could pick the desired location, spawn a collision solid, check very quickly if that solid collides with anything, and keep doing this until there is no collision. This is where a lot of my question comes in: is this possible or will this actually be extremely slow because I will end up running the collision traverser on every object everywhere multiple times? Can I write a limited collision traverser (somehow) that lets me quickly check on a single location without having to check every single item in the scene?

Or, perhaps, there’s some other standard way to do this that I’m unaware of and I should even be using collision detection to figure this out. Anyway, some help would be appreciated. I’m porting a simulator over from a 2D environment and I’m aware that dealing with the large number of moving objects in the simulator is always the slowest part of the code so I’d like to keep it as clean as possible.