> So I wonder, if there are other, more advanced algorithms out there, which
are
> faster ...

Here's an idea I just came up with.

Do it just like you are. Except, as you place the spheres, keep the array
that holds their positions *sorted*. So, when you add a new value to the
array, use some sort of binary search to find the part of the array where
the new position should be kept. (To sort the array, do something like
sorting first in the X direction, and then in the Z direction.) Then insert
the new value there, pushing the rest of the values ahead.

Then, when you have a new position, you still have to check the array to
make sure it doesn't conflict with any of the positions already there.
However, you no longer have to check the whole array - you only have to
check the part of the array that's within twice the maximum possible radius
from the new position you're testing.

It might be difficult to implement, but it might really speed it up. The key
thing here is to search the array with a binary search or something else
that takes advantage of its sortedness.

- Slime
[ http://www.slimeland.com/ ]
[ http://www.slimeland.com/images/ ]

Post a reply to this message