Procedural placement of objects with constraints

Question

I need to procedurally place some objects on a 2D plane based on constraints like:

1. Two objects should not be placed on the same line.
2. On specific object should always be placed on the border of the plane.
3. Another object should be placed close to the center (in some range).
4. Etc.

There are a lot of topics on procedural generation of landscapes/heightmaps or environmental objects (like trees, stones, rivers, etc.), but not too much on this topic. I've found the wave function collapse approach and it feels like it can solve such a problem, but I'm not sure.

Maybe there are some simpler algorithms to solve such a constraint-based placement on grids or maybe non-grid landscapes that can be adopted.

Answer 1

There are a lot of factors here like: object density, size, speed, memory, and storage types and amount.

For this example, I will assume "same line" is means both X and Y axes, the objects have the same size, should be fully populated(as many as possible), and the final size is square. If it is not square, some "holes" lines without objects will appear, populated to the fullest possible.

The grid is defined as the coordinates of the top left (X,Y) of each object scaled, integer divided by the object size (WIDTH, HEIGHT).

There is no requirement that the sprite WIDTH == HEIGHT for the grid to work.

MinDimension is the smaller of WorldWidth / WIDTH (BoundX), or WorldHeight / HEIGHT (BoundY).

For a single screen without scrolling, replace WorldWidth with ScreenWidth; the same goes for Height

Initialize Grid as a 2D array of zeroes. X,Y for row major Set the diagonals to 1.

for(int i = 0; i < MinDimension; i++)  Grid1[i][i] = 1;

Randomly swap the rows:

The next lines become language dependant. This example is in C# to describe the operation in simplistic terms.

for (int j = 0; j < MinDimension * 2)
{
   int tmpR = rnd.Next(MinDimension);
   var tmp = Grid[j];
   Grid[tmpR] = Grid[j];
   Grid[j] = Grid[tmpR];
}

Other languages may require en element by element swap in a loop to accomplish the same thing.

The rest of the conditions fall during the object creation loops:

Another object should be placed close to the center (in some range).

There is some uncertainty about this requirement conflicting with the first requirement. The word "another" meaning in addition to allows violation of the first rule. If not it will require randomly (in some range) selecting the grid close to the "center" square and zeroing the the rest of the row and column, and creating the object outside of the following loop.

Loop through the grid creating objects:

//prefer >> 1 over /2 if supported in the next lines(shown both ways): 

CenterObjectX = rnd.Next(range) + BoundX / 2; //in some range. 

CenterObjectY = rnd.Next(range) + BoundY >> 1; //in some range.


for(y = 0; y < BoundY; y++)
   for (x = 0; x < BoundX)
   {
      if (y == 0 || y == BoundY -1 || x == 0 || x == BoundX - 1)
      {
         if(Grid[x][y] == 1)
            //Create border object at x,y.
      }
      else
      {
         // check for additional center object position:
         if(CenterObjectX = x && CenterObjectY == y)
            // create center object at x,y
         else
            //create regular object at x,y
      }
   }