# How do I efficiently collide and match groups of coloured circles?

I am new to game programming and working on clone of this game in libgdx.

The game has some static balls and one ball that moves. I want to check if the moving ball collides with any static ones, but I'm concerned about the performance of my method.

I could put the positions of the static balls in an array or ArrayList and iterate over each of them in the moving ball's update()-method. However, this seems too slow to me when there are more than 10 balls.

A second issue is with how to detect the colliding balls' colours to check if 3 or more with similar colors collide. How should I approach that?

For your first question you can optimize your method by only checking collisions with the border bubbles (only the bubbles that are actually exposed and not ones that are entirely surrounded). However, you can optimize this even further by using the fact that you know the coordinates of the bubble to find out approximately (or precisely, with some math) where it's going to hit. Then you can only check collisions with the bubbles in that area. Of course, this will only work if you use a sorted data structure.

A two-dimensional array will work as a sorted structure without much additional effort because it will directly correspond to the ordering in the field. However, there are other structures that you can use, albeit they might be less efficient for this scenario.

For the second question there are many possible solutions. Here's a simple one that I can think of:

Let each bubble have 3 properties: position, color, and group. Position defines the bubble's position in the array, color defines the bubble's color, and group is a reference to an ArrayList of bubbles' positions.

Each time a bubble "hits", check the colors of all bubbles around it. If a bubble with the same color is found, then add the current bubble to it's group.

There are some additional special cases to handle, but I will leave them up to you to figure out.

• Ok i understand what you mean, but do you have solution for second problem? Thanks anyway. – Zohaib Amir Jul 8 '14 at 9:43
• @Zohaib Edited answer – d3dave Jul 8 '14 at 9:58
• Do you have any suggestion on how to implement "groups"? – Zohaib Amir Jul 8 '14 at 11:18
• Ad #2. If you percieve the field as a graph, you can use breadth- or depth- first search. In burst() method of bubble, you check all neighbors and call their burst(). You have to exclude already bursted bubbles though, as it will cause infinite recursion. Easiest way is to use boolean flag - bursted. – jnovacho Jul 8 '14 at 12:24