Im having a few issues trying to figure out what the best data structure to use for storing bubbles on the grid, and how to connect new bubbles to the grid when a moving ball collides with a ball on the grid.

My first implementation was to create a 2d array and populate it with a bunch of bubbles. I then iterate through the array and make a connection between bubbles only if there are adjacent bubbles in all directions from the current bubble. After Ive build the grid, and made all the connections, I added each bubble to list that I can look up and find connections between bubbles when a collision is detected.

When a moving ball collides with a stationary ball, I create a connection between the ball and then run a recursive BFS search from the colliding ball, finding all balls that are of the same color of the ball I just collided with. This works, but isnt very bulletproof, as I often get broken connections between balls when certain balls are deleted, or often groups of balls wont disappear that should.

My second implementation was to use a Hex grid. I had read similar questions on here where users suggested using a hex grid, so I thought I would try that approach. Again, I created a 2d array with a bunch of bubbles and tried running a mapper which mapped certain balls to each other depending on where they are in the grid. I still had a bunch of issues with connections, and often connection would end up getting broken or not connected properly.

Theres a lot of edge cases that Im still stuck on that im not exactly sure how to solve. For example, when I a colliding ball makes a connection with another ball, how should I deal with if that ball collides with a second ball at the same time. Or how should I look for balls within a certain area.

I feel like Im just overthinking this, and making the problem way more complex then it needs to be.

  • 1
    \$\begingroup\$ Related: gamedev.stackexchange.com/questions/38578/… gamedev.stackexchange.com/questions/34882/… \$\endgroup\$
    – House
    Feb 23 '15 at 5:39
  • \$\begingroup\$ I see how that works now. I'm still a bit confused how I'm supposed to handle bubbles that land directly on top of an other bubble. It doesn't make sense for the ball to be snapped to the left or right side . Maybe I'm just missing something here..... \$\endgroup\$
    – iNFiNiTY
    Feb 26 '15 at 3:34
  • 1
    \$\begingroup\$ Why don't you add an answer detailing your solution? Much better than a dead end "figured it out" comment :) \$\endgroup\$
    – House
    Mar 6 '15 at 17:13

I would try using an N-ary tree structure. The bubbles stack up in a skewed formation. If you take a bubble and surround it with other bubble, you will only get 6 possible connections: top left, top right, left, right, bottom left, and bottom right. Contrast this with a 2d grid and you get 8 possible connections: top left, top center, top right, left, right, bottom left, bottom center, and bottom right. This should make using a 2d array a bit cumbersome to keep track of the proper connections between nodes.

My approach would be to make each node have 6 connections, make the tree big enough to represent the entire play area, allow for empty nodes, and allow for edge nodes or null node connections.


Ive returned to answer my own question now.

I ended up using the resources found in this answer:

Creating a frozen bubble clone

I converted my 2D grid array into a hex array. I still used a 2D array to index into the hexes, but I made sure to make sure my hex grid function in a odd-r layout, and that I indexed my array properly based on that layout. All of this info is coverted in this article:


To detect collisions, I ended up doing some math, trying to find on which part of the hex that my colliding ball made contact with.

A way of doing this is found here:

How can I implement hexagonal tilemap picking in XNA?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.