2
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
1

2 Answers 2

Reset to default
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Is this an answer or an elaboration of the comments on my answer? \$\endgroup\$
    – House
    Oct 9, 2012 at 18:00
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Steven Stadnicki
    Oct 9, 2012 at 18:13
  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    Oct 9, 2012 at 18:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Steven Stadnicki
    Oct 9, 2012 at 19:04
  • \$\begingroup\$ @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. \$\endgroup\$
    – SundayMonday
    Oct 10, 2012 at 5:40
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – SundayMonday
    Oct 9, 2012 at 3:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – House
    Oct 9, 2012 at 3:38
  • \$\begingroup\$ 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. \$\endgroup\$
    – SundayMonday
    Oct 9, 2012 at 5:43
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Steven Stadnicki
    Oct 9, 2012 at 17:44
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – House
    Oct 9, 2012 at 17:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .