Detect nearby identical objects

So I write a game once in while. Just for fun, so that I can learn new things. I have been able to make a working "Breakout" and "SpaceInvaders" game so far. So I know how to handle collision handling etc.

Now I would like to make a "Bubble Shooter" copy. alt text http://img13.imageshack.us/img13/8361/54611.gif

I hope you guys know the game.

I am having an issue about one aspect of the game. As you know, if colored ball hits a place where 2 or more same-colored balls are connected - they will all "pop/dissapear".

Now, how do I detect if there is any same-colored balls connected to the ball I collide with? Do I keep some sort of seperate list of all clashes of same-collored balls?

I will need to know some sort of hint to which object the different balls are, so that I can delete them all upon im开发者_JAVA百科pact.

So yeah, how should I go about this?

---

In my experience with such games, the bubbles that are part of the playfield (ie the ones that have already been fired and have landed) are not positioned arbitrarily, but instead fit in a well-defined grid. Which makes the problem to solve not one of geometry (which would be fiddly), but one of traversing a data structure.

I suggest you have something, possibly as simple as a two dimensional array, that represents the colours of the bubbles that have already landed. Once you have established where the new bubble lands, you can then just check neighbours in this array. You will need to be careful about the fact that alternate rows are offset, but there's nothing here a clear diagram won't solve.

(it may be that you do in fact want arbitrarily positioned bubbles! In which case you have more work to do...)

edit OK here is one approach to storing the grid:

We will use a two-dimensional array, indexed by row and column, except that to handle the fact that our grid as actually hexagonal rather than rectangular, alternate elements will be unused. In each element that is used we will store a simple integer, representing the colour index of the ball that is there, or -1 if the space is free. So a small playfield could look something like this:

    col  012345678901234567
row 0    2.3.-.5.3.-.3.-.-.
row 1    .2.1.4.-.3.2.5.-.-
row 2    4.1.2.3.2.6.-.-.-.
row 3    .2.1.3.4.4.-.-.-.-
row 4    -.-.-.-.-.-.-.-.-.

where . is an unused element (the value of which we never examine), and - is an element with value -1, representing an empty hex cell.

Note that for any hex cell at row r, column c, its neighbours are at

    [r-1, c-1]    [r-1, c+1]
[r, c-2]                [r, c+2]
    [r+1, c-1]    [r+1, c+1]

with due consideration for the edges of the playfield.

Now suppose we have established that the just-fired ball, of colour 3, has landed at row 4, column 6. Examining its neighbours, we see that the northwest neighbour is of colour 3, and examining its neighbours we see that its northeast neighbour is also also of colour 3, so we have a chain of three the same, and we can delete them.

You could either do this check recursively, or keep track within each hex cell of both the colour and additionally the 'same colour neighbour' count. Can't say off the top of my head which one will work out nicer - recursion, I suspect.

It remains to say how we establish where a fired ball lands; but we can now easily see that we simply make the code that computes the trajectory also determine which hex cell in turn the ball counts as being 'in', and stop as soon as soon as one such hex cell has a non-empty neighbour, assuming you want the ball to stick to the first already-landed ball it gets near.

Stuff that still needs to be thought about:

• When the player makes a chain and we delete balls, do the other balls collapse up? Or do no-longer-attached balls fall down? How can we determine if a landed ball is connected to the roof?
• Is this naive collision detection good enough? (I suspect it isn't - in that if a fired ball puts so much as one pixel into the southwest of a cell, and there is a northeast neighbour, it will leap over and stick to it)

Hope this gives you some ideas to go on.

---

Heres my psuedo c# implementation from the top of my head - self explanatory I hope.

Class Bubble
{
  Color bubbleColor;
  Bubble[] adjacentMatchedBubbles;
  Bubble[][] board;
  int posX, posY;

  destroyMatchedNeighbours()
  {
    foreach(Bubble i in adjacentMatchedBubbles)
    {
      i.destroyMatchedNeighbours();
    }
    destroySelf();
  }

  positionOnBoard(int x, int y)
  {
     animateTo(x,y);
     discoverMatchedNeighbours();
     if(adjacentMatchedBubbles.length > 2)
     {
       destroyMatchedNeighbours();
     }
  }

  discoverMatchedNeighbours()
  {
     // look in the board 2d array in the elements adjacent to posX and posY
     // if this.bubbleColor = other.bubbleColor add to the adjacentMatchedBubbles array
  }
}

---

I would use a 2 dimensional array to store the current game state and then when the bubble comes to a stop check the adjacent bubble for there colors and if they match check there adjacent colors till no more adjacent bubble of the same color.

You will have to keep in mind that every second row will be slightly offset when you do the check for adjacent bubbles.