Distributing cubes without overlaps

Hi,

Been trying to solve a problem and even though on paper the logic makes sense, I could really do with some fresh perspective.

Problem:

Distribute 10 cubes (local scale 10, 10, 10) in an square area of 50 x 50 without any overlap between the cubes (cubes must have a distance of 10 or more units for all other cubes). Note: don't need to worry about the z axis can it just be set to 0.

Solution:

So these were my steps to solve this:

1) Get a random position within the square

Code (CSharp):

1. Vector3 GetRandomPosition()
2. {
3.      return new Vector3(Random.Range(0f, 50f), Random.Range(0f, 50f), 0f);
4. }

2) Check if the random position is a valid one. The position must be at least 10 units for all other cubes in the square area.

Code (CSharp):

1. Vector3 GetValidPositionInArea()
2. {
3.     Vector3 randomPosition = GetRandomPosition();
4.  
5.      // Using for loop with steps to ensure the loop exits
6.      // and doesn't hang incase there are never any
7.      // valid positions found
8.      for(int i = 0; i < m_numOfSteps; i++)
9.      {
10.          // If the position is valid break and return
11.          if(IsPositionValid(randomPosition))
12.           {
13.               correctNum++;
14.  
15.                break;
16.            }
17.  
18.            // else find another one
19.            randomPosition = GetRandomPosition();
20.       }
21.  
22.       return randomPosition;
23. }

Code (CSharp):

1.  
2. // Test a random position against all the other
3. // cubes in the array to make sure there
4. // is a valid distance between the random position
5. // and ALL other cubes
6. bool IsPositionValid(Vector3 randomPos)
7. {
8.     int numOfValidPositions = 0;
9.  
10.     for(int i = 0; i < m_numberOfCubes; i++)
11.     {
12.          // If the position is valid increment the number
13.         //  of valid positions
14.          if(IsPositionEmpty(randomPos, m_cubesTransforms[i].position))
15.          {
16.              numOfValidPositions++;
17.          }
18.     }
19.  
20.     // If all the positions are valid the cubes
21.     // have been distributed correctly
22.     return numOfValidPositions == m_numberOfCubes;
23. }

3) If the random position tested is not valid, get another random position and keep doing this until a valid position is found for all cubes

Code (CSharp):

1. Vector3 GetValidPositionInArea()
2. {
3.      Vector3 randomPosition = GetRandomPosition();
4.  
5.       // Using for loop with steps to ensure the loop exits
6.       // and doesn't hang incase there are never
7.       // any valid positions found
8.       for(int i = 0; i < m_numOfSteps; i++)
9.       {
10.           // If the position is valid break and return
11.           if(IsPositionValid(randomPosition))
12.           {
13.                correctNum++;
14.  
15.                break;
16.            }
17.  
18.             // else find another one
19.             randomPosition = GetRandomPosition();
20.        }
21.  
22.        return randomPosition;
23. }

The problem I'm find now is that some cubes that are placed later on i.e. 8, 9 and 10 have **NO** valid place left in the square area and thus never find a valid position so are just placed randomly and thus overlap. What I guess I really need to do is run a distribution, check all cubes have a valid position and keep going through the loop until there placed correctly. Which I've tried and either using a while loop, it just never finds any where valid and locks up or using a for loop and a fixed number of steps it will still get an invalid place and overlap with another cube. Back to the drawing board!

 

psudo code:

Make a List of numbered positions

Randomly pick a number from 0 -> List.Count

Remove that item from list

Repeat until list empty

 

You mean a list of predefined positions for me to place the cubes in?

If so, I can't do that, as it wouldn't be completely random i.e. it could be anywhere within the 50 x 50 square. Pre-run time I have no idea where the cubes may end up, as long as they have an adequate distance between them, that's all that matters

 

Yes, it would be completely random... it gets randomized through the selection process.

Anyway, to fix the other problem..

When you pick a spot, remove the 5 numbers either side as well.

 

I can't predetermine the positions beforehand though. So I couldn't hard code a bunch of Vector3s to choose from.

I like the idea of removing ranges of numbers from the selection process. The problem I was coming up against is that the for loop would run out of steps trying to find a random spot that was suitable.

I've also thought about dividing the square up into X quadrants and then only choosing quadrants that have the least number of neighbouring cubes.

I guess this problem is like one of those weird cognitive tests. The examiner would draw a 50 x 50 square on a table and give you 10 blocks, and then tell you to place all 10 blocks in the square always insuring the blocks have a distance of 10 units between them. Obviously, we have spatial awareness and would just plonk them in empty areas in the square. Whereas my dumb logic of basically, putting a cube in a random position in the squaring, checking if it's near any other cubes and then repeating it say 500 times would work for say 8 of the cubes but fail for the others, as it ran out of areas to place the cubes effectively. Whereas we could move other cubes, find open spaces in the square much easier. So it seems like I need to make the program a bit more spatially aware (just like you pointed out with removing a range of numbers which are now "occupied" or using a grid / division system).

Thanks for the tips so far, it's an interesting problem

 

You can pre-determine the available positions... they are 1 to 50 * 1 to 50. The trick is removing the unavailable positions once you use a position.

It would then follow a pattern like so:

1. You then choose a random x value of 0 to 50 (lets say 35), You remove the x values 30-40. You want to remove the values completely, shrinking the list size (so now your arrays or whatever you use are 40 in length. x values of 0..30 [gap] 40..50.

2. You the choose a random x value of 0 to 40 (length of list). lets say 40. That will give you an X value of 50 (since 50 is now the 40th value in the array).

Hopefully that makes sense.

The problem as I see it, is you wont be able to put all the needed blocks in if you dont put them in carefully... which I dont know how you would solve.

ie. if you put one right in the center, the end result is you might only be able to place 8 more blocks in the surrounding area that meet your rules, where as if you put one right on the edge, you have a lot more space to use around it.

Your example of if we just sat that placing blocks and what I said above points to the fact that there is a finite set of possible solutions anyway (assuming you have a minimum number of blocks to place)