• Create Account

### #ActualBacterius

Posted 10 September 2012 - 08:27 PM

This is actually an interesting problem if you want to solve it efficiently. There is a trivial method but which takes O(n^2) time (generating each object at random and checking against all existing ones until no collision occurs). Another, smarter method is to generate an AABB and subdivide it at random (making sure each subdivision has a minimum volume) generating some form of tree structure, and once you're subdivided enough, place planets at random in any of the leafs - guaranteed to be collision-free, but since you use AABB's some patterns can appear.

Of course, if you don't care about performance, and if there is no STL method for doing this, you can wrap the naive algorithm around a vector relatively easily if you have the generation method and the collision method. Here's an example with arrays, since I don't do C++...

// generates a random, collision-free position for all objects
for (int t = 0; t < objectCount; t++)
{
do { objects[t].randomizePosition(); } while (Collides(t));
}

// checks collision of object at index t with all previous objects
bool Collides(int t)
{
for (int k = 0; k < t; k++)
if (collision(objects[t], objects[k])) return true;

return false;
}


### #1Bacterius

Posted 10 September 2012 - 08:26 PM

This is actually an interesting problem if you want to solve it efficiently. There is a trivial method but which takes O(n^2) time (generating each object at random and checking against all existing ones until no collision occurs). Another, smarter method is to generate an AABB and subdivide it at random (making sure each subdivision has a minimum volume) generating some form of tree structure, and once you're subdivided enough, place planets at random in any of the leafs - guaranteed to be collision-free, but since you use AABB's some patterns can appear.

Of course, if you don't care about performance, and if there is no STL emthod for doing this, you can wrap the naive algorithm around a vector relatively easily if you have the generation method and the collision method. Here's an example with arrays, since I don't do C++...

	// generates a random, collision-free position for all objects
for (int t = 0; t < objectCount; t++)
{
do { objects[t].randomizePosition(); } while (Collides(t));
}

// checks collision of object at index t with all previous objects
bool Collides(int t)
{
for (int k = 0; k < t; k++)
if (collision(objects[t], objects[k])) return true;

return false;
}


PARTNERS