Jump to content
  • Advertisement
Sign in to follow this  
Thunder0ne

How to spawn non overlapping randomly distributed objects

This topic is 2115 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

I would like to know if there is any common practice to achieve this:

I have objects spawners that spawn objects in a certain area in random positions, but I would like them not to overlap.

Is there any common known practice?

 

Many thanks.

Share this post


Link to post
Share on other sites
Advertisement
You could add fixed places to spawn your objects randomly on. If you want it to be completely random you just have to do a collision check or just check if there already is a object within the bounds. You could also add the locations you already have a object spawned added to a black list.

Share this post


Link to post
Share on other sites

A simple solution is to loop, generating candidate positions, doing a collision check - if there is no intersection, insert the object. One needs to be careful as there will be certain cases where the available area and object count can create unsolvable positions, essentially infinite loops. A simple demonstration case in point is if the area is slightly bigger than one object, and you try to insert two. An upper bound on the number of tests before bailing out would be a good idea.

 

Another solution is to spatially partition the area, and create an object or set of objects in each partition. Depending on how you partition, you may need to implement the above too.

Share this post


Link to post
Share on other sites

A bit more involved method, but that should be more predictable in its runtime (O(n)), and that cant enter infinite loops, could be to first subdivide the area into random rectangles by recursively random split until you have enough rectangles. Then place the objects in a random position of each rectangle, without overlapping the edge

Share this post


Link to post
Share on other sites

...

 

Another solution is to spatially partition the area, and create an object or set of objects in each partition. Depending on how you partition, you may need to implement the above too.

 

I suggest a kd-tree

Share this post


Link to post
Share on other sites

like ripoff says, the standard algo is:

 

location L;

do

    {

    generate random location L

    }

    while (something in way of L)

 

dividing the space using grids. trees, etc you still must select a partition at random, and track the used ones, or assign them in a pseudo-random fashion using some sort of hash type function.  and you still have to trap out the case of having more objects than space available.

 

probably best to do the check for objects vs space available first, or better yet, simply design it all from the get go so that you never have too many objects. that's the slick way to do stuff.

 

once you know there's room, the standard algo is fine unless you have something like a 10000x10000 grid with only two squares left open and your check for "something in way" is extremely slow.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!