# Distribute circles evenly on Screen - circle packing

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?

• Is it possible to shrink the circles? In your example, would it be possible to shrink circle 2 so it fits between circle 1 and the wall? By the way, I believe the technique you are referring to is "circle packing". – Apples Feb 12 '13 at 13:45
• No it is not possible to shrink the circles, but there is always enough room so that the circles don't have to overlap. Thanks for the keyword, I will search for that.. – mbert Feb 12 '13 at 13:58

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.

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

• have you looked into the code to tell me where to start looking? I will try that game later, I dont have a windows machine around where I can install things – mbert Feb 12 '13 at 14:22
• Sorry, I haven't looked yet. But take a look, and I can help out if you need when I get time tomorrow. – Jason Coombes Feb 12 '13 at 15:23