#### Archived

This topic is now archived and is closed to further replies.

# Problem, need help

This topic is 6037 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
I think you''re looking for collision detection.

##### Share on other sites
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

##### Share on other sites
It''s not really AI though is it. Your best answers will come from somewhere like comp.graphics.algorithms.

Stimulate

##### Share on other sites
it''s a question that i would like answered so that I can fix up my ai

##### Share on other sites
I''m sure it is. All I''m saying is if you have a burst pipe in your bathroom you don''t get an electrician around to fix it...

Although someone on this forum may be able to answer your question you are more likely to get a quicker (and better) response from the experts. The experts in this case are the graphics guys.

(you could use a GA to solve your problem btw, although I''m sure that''s not the best way of doing it)

Stimulate

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
oo nice idea!

let us know if it works sam.

Stimulate

##### Share on other sites
I quite like this problem. I''ve been thinking of rewriting my GA tutorial as I''ve never been happy with the boring example I used so I''ve spent a lazy afternoon coding a GA to solve a version of the one on this thread. Much more interesting.

Basically I''ve made it a little more interesting as the GA has to find the largest circle which will fit amongst 20 other circles of varying radius.

It''ll take me to write up the project and tidy up the source for the website but if anyone is interested in seeing it get in touch and I''ll email it to you.

fup@btinternet.com

Oh, you can find the executable here

http://www.btinternet.com/~fup/tiddlywinks.exe

Stimulate

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633701
• Total Posts
3013450
×