This is my situation, I have a bunch of units, each with a radius Say I want to determine a free spot to say, build a building on The units positions are all continue, not in a discrete grid is there any algorithm that I can use to find basically a free space, of radius X, given a list of the units in the surrounding area?

I think you''re looking for collision detection.

I said "find a free space", not check if a space is free.
I can already check if a spot is occupied or not, not exactly hard to do a sphere-sphere check
What I need is a way, given a bunch of units in an area, find me a spot with radius X that isn''t occupied

it''s a question that i would like answered so that I can fix up my ai

Not an easy problem... at least not that I can see.

I presume you have a bounding volume within which you wish to place the new unit (or can easily define a reasonable one).

I have some rough ideas but they are computationally expensive... involving random sampling from within the bounding volume.

Basically generate a large sample of points within your bounding volume. Throw away those that fall inside other units.

For each point remaining, consider a line to each other point. Record how many of these intersect other units.
For any 2 points that have a line between them that intersects a unit, discard the point that has more lines intersecting units.

When this is done and you have a list of points that have lines that don''t intersect other units, find the mean of the distribution. Test that as a possible centre point for your new unit.

The problem with this algorithm is that it is still possible that the points remaining don''t define an open region... they could surround a unit. Obviously though, the more starting points you consider, the less likely this is.

Good luck,

Timkin

Just a random idea off the top of my head based on flocking ideas. First choose a point in the world at random or by some other heuristic method (i.e. the point the AI thinks is most suitable, ignoring potential collisions). Now recursively follow these two steps.

a) Check if the area is free based on your own algorithm for radius checking. If it is free, you''re there.

b) If it is not free, calculate a repulsion vector from every collidable object in the world. Basically take a vector from each collidable object to the point you''re currently at (point - collidable object position). Grab hold of the magnitude of this vector (i.e. the distance from the object to the point), normalise the vector (divide by its magnitude) then divide it by the square of the original magnitude (or simply divide by the cube of the magnitude in one go). This will form a vector that decreases over distance away from the collidable object with the square of the distance. Do this for every collidable object and sum the vectors to produce an overall repulsion vector. We''re going to move the point in the direction of this vector, but only by a small amount. So normalise this vector then multiply it by a set small amount and add it to the point. Go back to (a).

This will move the point away from all the collidable objects, bearing more regard to the closer objects. Hopefully this should result in moving the point to an empty space after only a few recursions of this alogrithm.

Mike