Avoid overlapping of squares within a boundary

I’m currently trying to complete an assignment that I don’t quite understand, because I’m new to Grasshopper and Galapagos. The assignment requires 9 squares that are spread out within another big square that acts as a boundary not to be crossed. In short, these are the requirements:

  • squares should stay within boundary square
  • squares need to be spread out within the boundary
  • squares shouldn’t overlap
  • sqaures should have maximum distance between each other
  • use Galapagos for this task

Can someone help solve this?

Don’t mind the notes on the canvas. They are for my understanding :sweat_smile:

Space assignment.gh (53.3 KB)

Since it’s homework I probably shouldn’t be doing it for you, but the problem to be solved in any Galapagos project is the creation of the fitness function. You somehow need to encode any state your model might be in into a single number; the fitness value. Then, once that function exists, Galapagos can go and twiddle with sliders for a bit to see if it can maximise this fitness number.

There are three important rules to keep in mind when designing this fitness function:

  1. Ideally every state should result in a fitness. If certain states yield a null value or a NaN value, Galapagos will definitely have a much harder time figuring stuff out. Usually when a fitness function fails to do this we call it “overconstrained”.
  2. Ideally a small change in any input slider results in a small change in the fitness value. If that’s not the case then there will be sudden jumps in the fitness space. Galapagos can handle this, but the more discontinuities like this, the harder it is to solve.
  3. Ideally small changes to any input slider yield a difference in fitness. If neighbouring states are equally fit then Galapagos doesn’t know in which direction to look for even better states. Fitness functions which contain plateaus like this are called “underconstrained”.

Now to your specific problem, which is slightly more complicated than usual since it contains “hard” constraints, i.e. the squares aren’t allowed to intersect each other or the boundary. This is not something that happens gradually, but rather suddenly. One moment the squares don’t intersect and all is well, the next you move a square half a millimetre to the left and suddenly they do intersect. The usual solution to adding such hard constraints is to just subtract either zero if the constraint is obeyed, or a huge number if it’s violated. For this you’ll need some sort of conditional somewhere, possibly an expression with an IF statement, possibly a Smaller Than component hooked up to a multiplier, possibly something else still.

Let’s look at a simpler case first; distributing 9 points inside a rectangular boundary. By setting up our sliders so that the points cannot leave the boundary no matter what, we remove that complexity from the system. The next thing we need to decide is what “[points] should have maximum distance between each other” actually means. Does it mean:

  1. The distance between the two nearest points needs to be as large as possible.
  2. The sum of the distances between each point and its nearest neighbour needs to be as large as possible.
  3. The sum of the distances between each point and all other points needs to be as large as possible.
  4. Same as [2] but using the square of the distance.
  5. Same as [3] but using the square of the distance.
  6. … soooo many more options.

Whatever option we choose, here’s a good file to start experimenting with:
Nine Points 01.gh (29.1 KB)

By using the Proximity 2D component and changing the G input we can construct the lines connecting points to their nearest N neighbours, or indeed all other points if G > 9.

Here’s an example on how to modify that base file if you want to maximize the sum of the linear distances from each point to its nearest beighbour:
Nine Points 02.gh (37.0 KB)

1 Like

In order to bridge the gap between my simplified example and your actual problem, you need to add the following things to your file:

  • Distances between points needs to be replaced by distances between squares. You can probably use the Curve Proximity component for this to compute the distance between any two curves.
  • Intersections between the square and the boundary must either be added to the fitness function, or be made impossible by cleverly positioning the rectangles in such a way that every possible slider layout always places the rectangles only on the inside of the boundary (see below).

It is a fair assumption that if you maximise the distances between squares, that you’ll also avoid square/square intersections, but you may still need to add an additional term to your fitness function for this. Be careful, squares entirely inside other squares will not intersect, but you probably still want to avoid those cases.

Here’s a setup which makes it impossible to specify squares outside of the boundary. The logic here is that for each square I create an offsetted boundary within which the square centre is picked using normalised (i.e. zero-to-one) uv coordinates.
Six Rectangles 01.gh (27.7 KB)

thanks for the very helpful tips! :slightly_smiling_face: I also attempted to solve this in another way, more specifically, by using the ‘solid difference’ component (to get the total space area when all the squares are not overlapping → ideal sum of area to maintain) and linking it to the distance requirements (by making a list) and applying galapagos to one component that contains both requirements (a little bit more complicated but in theory it should work). Unfortunately, when I apply galapagos (maximize) the squares get together in pairs and place themselves in a corner. At least they don’t overlap but the maximum distance requirement between the squares is not fulfilled. What could be the problem? Any guesses?
9 squares.gh (67.7 KB)

Part of your fitness function is the wrong way around then. Do note that Galapagos can both minimize and maximize the fitness. Along the top edge of the first tab in the Galapagos window you can click on the minus sign or the plus sign to minimize or maximize the fitness.

I needed to maximize in Galapagos (maximum distance) but it still creates four local optima (square corners). I also tried it with ‘minimize’ but then they start overlapping. But still, thanks for the useful hints :blush: