> I have no experience at all with collision avoidance methods and just did
> the first thing that came to mind.  Doubtless it is hideously inefficient.
> I just calculated the distance from each newly generated location to each
> of the previous ones...   I can already think of a couple of ways to
> improve on it.  I didn't even exit the loop as soon as a failure was
> detected and just continued on checking all the previous locations!  haha.
> If you have some information on different algorithms for this sort of
thing
> I'd be happy to see them.

Well, there are several ways to do this. The one you used is brute force,
just place and check. An advantage would have been stopping the comparisons
once it has been determined that the current position is invalid.

Another fast method (though I don't have the script for that right now) is
to use functions. Similiar to the approach of saving all positions and
checking those, you could use a function to keep track where the posititions
are. In this manner, all positions get added to that function via
redeclaration, and to check, you just have to do one call to the function.
But this is just a speed-enhancement, the method is essentially the same.

You could also divide the space in which you place the eggs into cubes.
Determine in which cube the new position is and only check that cube and the
neighbourig cubes. Thus you don't check with positions which are too far
away anyway.

Another method, which works in many cases, is just calculate a grid of
positions with enough distance to each other, and then randomize those
points slightly. If done correctly, the observer won't notice the underlying
pattern and it will seem random. There no checking with other positions
done, which is a major speed up.

That's about it. I think there are some more variations to these methods,
but essentially, that wraps it up, I guess.

Regards,
Tim

-- 
"Tim Nikias v2.0"
Homepage: <http://www.nolights.de>

Post a reply to this message