# Data structure for bubble shooter game

I'm starting to make a bubble shooter game for a mobile OS. Assume this is just the basic "three or more same-color bubbles that touch pop" and all bubbles that are separated from their group fall/pop. What data structures are common for storing the bubbles?

I've considered using an undirected, connected graph where each node is a bubble. This seems like it could help answer the question "which bubbles (if any) should fall now?" after some arbitrary bubbles are popped and corresponding nodes are removed from the graph. I think the answer is all bubbles that were just disconnected from the graph should fall. However the graph approach might be overkill so I'm not sure.

Another consideration for the data structure is collision detection. Perhaps being able to grab a list of neighboring bubbles in constant time for a particular "bubble slot" is useful. So the collision detection would be something like "moving bubble is closest to slot ij, neighbors of slot ij are bubbles a,b,c, moving bubble is sufficiently close to bubble b hence moving bubble should come to rest in slot ij".

A game like this could be probably be made with a relatively crude grid structure as the primary data structure. However it seems like answering "which bubbles (if any) should fall now?" would be trickier with this data structure.

-

Finding connectivity in a general graph is usually done with floodfill-style algorithms (i.e., breadth- or depth- first search and variants thereof) anyway, so I don't think that abstracting out the process in the way you're describing is actually any great help. Instead I would maintain the core data structure in a grid; there are very standard approaches for storing hex grids (which is what the bubble grid amounts to - imagine 'inflating' the bubbles until the gaps between them fill in) in rectangular 2d arrays that are directly applicable here. (And I can fill in more details on the specific grid structure here if you need them, certainly.)

The one small 'catch' is that you probably want to initialize your flood fill/search structure by adding all nodes adjacent to the top or walls to your 'to be processed' queue; this is likely to be quicker and more straightforward than flood-filling from each of the connected bubbles in turn. Regardless of how you do it, though, the connectivity pass should be so fast (you're iterating over probably not more than 100 items!) that doing anything too complex with it smacks of premature optimization; this just shouldn't be a huge part of your frame time.

-
Is this an answer or an elaboration of the comments on my answer? – Byte56 Oct 9 '12 at 18:00
Well, it's certainly meant to be an answer; while I think our core conclusions (use a 2d array, not an arbitrary graph) are the same, it's an elaboration on how specifically to do the connectivity work in that 2d grid. Do you feel it serves poorly as an answer? – Steven Stadnicki Oct 9 '12 at 18:13
No, it's an OK answer. I just wanted to make sure. Since the question itself doesn't mention flood fill, and your answer covers it in detail. – Byte56 Oct 9 '12 at 18:19
True, but the question raises the issue of determining connectivity, and floodfill-type algorithms are the traditional way of handling that question. That said, this answer is definitely a little abstracted, and I'll try and flesh it out a little bit with respect to direct applicability. – Steven Stadnicki Oct 9 '12 at 19:04
@StevenStadnicki Yes elaborate on the hex grid storage approach please. I was thinking about using a 2D array where the even-indexed rows are understood to be staggered to the right (and the entry in the n-1st column is nil or ignored). However I'm not sure if this is the easiest way. – SundayMonday Oct 10 '12 at 5:40

Using a simple 2D array works. Then you don't have to walk a graph to get somewhere. Deciding what should fall next is as easy iterating up the current "column" of the array you're in.

You can easily step into the grid anywhere with the x/y coordinates and do your collision detection or whatever you need to. That means you can get neighbors in constant time.

If you need to know which bubbles should fall next it's as easy as starting at the bottom and iterating up, finding the first empty slot, and moving things down.

-
I think you're right. You'd probably still need to run some flood-fill algorithms on the array to determine which bubbles should fall after some arbitrary bubbles are popped. – SundayMonday Oct 9 '12 at 3:27
Do bubbles just fall straight down? Is so, flood-fill is a little overkill. Just start at the bottom. 1-Iterate up 'till you find an empty spot, mark it and continue until you find a bubble. Move the bubble to the marked spot. Repeat 1 until you're at the top. – Byte56 Oct 9 '12 at 3:38
I see what you're saying. I was referring to the case where some bubbles are popped and that separates some group G of bubbles from the main group. And all bubbles in G should fall/pop/be removed. I think flood-fill or similar is necessary to determine G. – SundayMonday Oct 9 '12 at 5:43
@SundayMonday is right - because the structure can be highly nonconvex there's no local means of determining popped bubbles, some sort of flood-fill style iteration is necessary. – Steven Stadnicki Oct 9 '12 at 17:44
@SundayMonday OK, I see what kind of game play you're talking about now. Yes, floodfill would work great for that. Of course the 2D array is still very suitable for floodfill. – Byte56 Oct 9 '12 at 17:56