Distributing cubes without overlaps


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


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.


So these were my steps to solve this:

1) Get a random position within the square

	Vector3 GetRandomPosition()
		return new Vector3(Random.Range(0f, 50f), Random.Range(0f, 50f), 0f);

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.

	Vector3 GetValidPositionInArea()
		Vector3 randomPosition = GetRandomPosition();
		// Using for loop with steps to ensure the loop exits 
		// and doesn't hang incase there are never any 
		// valid positions found
		for(int i = 0; i < m_numOfSteps; i++)
			// If the position is valid break and return 


			// else find another one
			randomPosition = GetRandomPosition();

		return randomPosition;


	// Test a random position against all the other 
	// cubes in the array to make sure there
	// is a valid distance between the random position 
	// and ALL other cubes
	bool IsPositionValid(Vector3 randomPos)
		int numOfValidPositions = 0;

		for(int i = 0; i < m_numberOfCubes; i++)
			// If the position is valid increment the number of valid positions
			if(IsPositionEmpty(randomPos, m_cubesTransforms*.position))*
  •  	{*
  •  		numOfValidPositions++;*
  •  	}*
  •  }*
  •  // If all the positions are valid the cubes* 
  •  // have been distributed correctly*
  •  return numOfValidPositions == m_numberOfCubes;*
  • }*

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

  • Vector3 GetValidPositionInArea()*

  • {*

  •  Vector3 randomPosition = GetRandomPosition();*
  •  // Using for loop with steps to ensure the loop exits* 
  •  // and doesn't hang incase there are never any valid positions found*
  •  for(int i = 0; i < m_numOfSteps; i++)*
  •  {*
  •  	// If the position is valid break and return* 
  •  	if(IsPositionValid(randomPosition))*
  •  	{*
  •  		correctNum++;*
  •  		break;*
  •  	}*
  •  	// else find another one*
  •  	randomPosition = GetRandomPosition();*
  •  }*
  •  return randomPosition;*
  • }*
    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!

So, a 50x50 area is 25 cube positions. There should be no problem placing 10 cubes.

My suggestion is this:

  1. Create a 5 x 5 array (or 6x6 as you prefer) of booleans, set all to false
  2. Loop 10 times
  3. Within each loop, loop again picking a random X and a random Y, if false, set true and exit inner loop

Now just scan the array and use that to place your cubes.

Sometimes, thinking data structures really helps, Not everything has to be done in-scenegraph.