#### Archived

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

# Problem, need help

This topic is 5707 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

##### Share on other sites
quote:
Original post by MikeD
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.

Damn Mike... that was my first idea... except that I only considered computing the repulsion vector to the nearest unit's circle... which could be found by expanding out concentric circles from the guess point. If you get to the radius of the object you want to place, your home free... otherwise move away from the first object you intersect (by the difference in achieved radius to target radius) and try again.

I disregarded this idea because there seemed no guarantee to be able to place the unit within a bounding volume... but I believe your method will find a location, if it exists, within the bounding volume enclosing all current units with less iterations than checking only one unit... unless the starting point lies outside this volume of course.

fup, you really must have too much time on your hands! If you do, I can suggest a little project for you... that is in line with your GA-ANN bot work!

Cheers,

Timkin

[edited by - Timkin on June 2, 2002 1:05:38 AM]

##### Share on other sites
A simple remark (which I hope can help) :

The problem is equivalent to "find a point outside a set of circle".
Say you wan to build a house whose radius is R, and there''s a unit whose radius is r... You have to find the center of the house, and it must be at a distance of at least R+r.
You no longer have to find a place to put a circle, but a point (isn''t it cool ?)

Another remark : I''m pretty sure that such a point always exists on one of the unit''s circles.

##### Share on other sites

MikeD: that was the first thing I tried, with some success
Very often it would find an open spot, but not always, so I was hoping that there was some well established algorithm (that I just had never heard of) that accomplished the same goal
I didn''t think to try a GA, I''d love to see your results

sam_sam83

##### Share on other sites
Just to go on with my ideas :

You could, for each circle''s unit, have a set of impossible segments : let''s say there are two units (A and B), at a distance of 10 and whose radius are both 4. You want to build a house (radius 4 too). So, you have to find a point at more than 8 from a unit.
What you need is : a unit number and an angle (it defines one point on the circle of that unit). Let''s talk in degrees : the angle''s value is between 0 and 360°.

If you have n units, you can think of the problem as a 1D problem : you must find a number X in [0,360*n] (the unit number would be X/360 and the angle X%360), knowing that there are some prohibited values. What you could do is find this prohibited values (by intersecting every unit''s circle with every other unit''s circle) and then find a X which is not prohibited.

Hope this will help (and this is clear)

##### Share on other sites
Actually, I think I have another idea that isn''t TOO computationally expensive... triggered by Vincent''s thoughts...

Consider each unit you have already placed. You know that you can define a region around each of these that you cannot place the new unit into, since it would cause intersection. So, for each placed unit, define a circle by an appropriate radius to represent this forbidden region. You don''t need to represent the circle, just the radius. Then, start generating points at random within some bounding volume that encompasses all units. Test the distance from this point to the centre of each placed unit against its forbidden region radius. If there is at least one test that fails (i.e. the distance to the unit from the test point is less than the radius of the forbidden region circle, then reject the point. If all tests pass, place the unit at the test point.

The problem with this method is that it does not guarantee to use space efficiently. The only way to do that would be to use a packing algorithm to determine optimal placing BEFORE placing any units.

Of course, you could do something like this offline to generate a set of constraints for placing of units. I presume these units are immovable objects, like buildings? Just define for each building type a set of constraints about how far away it should be from other building types, so that when you place the buildings down in any order, there is always a place to put a new building.

Cheers,

Timkin

##### Share on other sites
Perhaps you could discretize the problem.

I'm assuming all circles must be contained within a bounding AABB? Split this box into a grid, such that each square grid cell can contain exactly one of the circles you want to place (eg, the width and height of each cell are both 2r ). Now rasterize all circles (using a "total coverage" algorithm) onto this grid. Then you just need to find the first empty spot in the grid.

This method isn't guaranteed to find a solution, but it ought to do a pretty good job, and it seems as though it might be more reliable than the other techniques.

EDIT: Come to think of it, this is very similar to VincentLascaux's solution. Vincent just used a discrete set of polar coordinates, whereas mine was a set of rectangular ones.

[edited by - TerranFury on June 3, 2002 6:14:25 PM]

##### Share on other sites
I'd say that if you want a polynomial time search for a given region, discretisation would be the way to go. At least it guarantees to find a place if one exists... or to tell you that one doesn't exist...

Cheers,

Timkin

EDIT: Actually, come to think of it, I suspect that the worst case would be O(nlog(n)) search.

[edited by - Timkin on June 3, 2002 9:50:11 PM]

##### Share on other sites
quote:
Original post by Timkin
fup, you really must have too much time on your hands! If you do, I can suggest a little project for you... that is in line with your GA-ANN bot work!

Timkin

Like I said, It makes for a more interesting project for my GA tutorial. Its probably overkill for the problem but it''s great for observing how a GA works.

Time on my hands? I wish. I haven''t been able to do any work on the bot in weeks.

Stimulate