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]

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.

Thank you for your suggestions

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

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)

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

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]

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]