Distribute circles evenly on Screen - circle packing

Question

I want to evenly distribute a random amount of circles with random diameter on the screen for. This level doesn't scroll so the users screen resolution sets the limits. Further I would like the circles to be as big as possible to fill out the screen.

I have no problem writing the code for collision detection and so on, my problem is the basic theory to solve this kind of problem.

My current approach doesn't work properly because the problem could be the following thing, where (1) is the first circle and (2) is the second circle and | is the "wall" or screen edge.

(1) (2)|
So if 1 and 2 overlap, I would move 1 half of the overlapping distance to the left, 2 with the other half to the right. I then see that 2 is already at the wall and can't be moved, so 1 must move the whole overlapping distance to the left.

How would I correctly approach this situation?

Answer 1

Here is a very simple way to do what you want.

1. Pick a random point inside the rectangle (screen) & instance a 1-radius-circle at that point.
2. Grow the radius of that circle till it satisfies these criteria:
   • Does not overlap any of the other chosen circles.
   • Does not extend outside the rectangle.
   • Touches at-least one other chosen circle or a rectangle boundary.
3. Choose the circle if it satisfies these criteria.

Repeat 1-3 till you get sufficient circles covering the rectangle. You can optimize and tweak this as needed. For e.g. you might want to specify a range of accepted radii, or you might want to choose the radius based on the number of surfaces/circles it touches, etc, etc.

Answer 2

There was a game in the Ludum Dare "Evolution" contest that had various circles evolving (growing) when colliding with other circles. The code in that game should provide a good example of how to solve what you are asking.

Here is the link to the game: http://www.ludumdare.com/compo/ludum-dare-24/?action=preview&uid=14673