Bubble shooter clone, structure for storing/adding of bubbles

Question

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.

Answer 1

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.

Answer 2

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:

http://www.redblobgames.com/grids/hexagons/

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?