Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

This is a bit more difficult than it seems and the one other post on here isn't sufficient. You have a row of n items, and each item could be any one of 5 colors. You need to find if there are any runs of 3 or more items together of the same color and destroy them.

Yellow, Red, Blue, Green, Red, Red - destroy nothing

Red, Red, Red, Green, Yellow, Red - destroy the first set of 3 Red, but not the 6th red

Red, Purple, Red, Red, Red, Red - destroy only the set of 4 Red

You can't simply check each item to see if the item previous to it has the same color, and destroy them when that happens twice in a row (meaning 3 matching items), because then you are not accounting for the fact that there could be 4 or more in a row. Are there any robust algorithms out there for this?

share|improve this question
1  
Very related (dup?): gamedev.stackexchange.com/questions/14932/… –  Byte56 Feb 6 '13 at 17:54
    
Related yes, but like I said it's not robust. It only accounts for 3 in a row and not more. –  soleil Feb 6 '13 at 18:01
1  
Also this might be useful: gamedev.stackexchange.com/questions/43220/… –  Sidar Feb 6 '13 at 18:01
add comment

4 Answers

up vote 4 down vote accepted

This is a very simple programming problem.

Here's a straight forward solution.

For every piece

  1. check if previous two pieces are same color
  2. if true, destroy those three pieces.
  3. for every piece after that, if current color == destroyed color, destroy it. If not, break out of the loop.

If it's possible to have more than one set of three at once in a single row (e.g. 3 reds then 3 blues), you'll have to run the loop multiple times until it doesn't destroy anything.

share|improve this answer
    
This got me on the right track. I wouldn't actually "destroy" them right when I found two previous matches, but I mark them for destruction. Then when I'm finished I loop back through and destroy everything that was marked for destruction. –  soleil Feb 6 '13 at 18:58
add comment

I think this can be done amazingly easy with regular expressions (provided you can provide the gameboard as string).

Once you have the board in stringform, use the following regex:

(\w)         //capture any letter
(\1{2,})     //capture that letter again twice or more.

The beauty of this is that it works on any number of items, and any amount of different items/colours.

share|improve this answer
3  
Seems like overkill to represent your board as a string; and a very.. unusual requirement. +1 for a different solution, though! –  Vaughan Hilts Feb 6 '13 at 21:23
add comment

Use two nested loops. The outer one will loop over the array and will be treated as the beginning position for a possible run. The inner will look for the end of the run by starting at the current beginning position and iterating as far as it can on the same color.

for (int i = 0; i < n;)
    int j = i+1;
    for (; j < n; ++j)
        if (color[j] != color[i])
            break;
    // at this point, there is a run of size j - i from element i to j - 1
    if (j - i >= 3)
        // mark elements for destruction
    // start looking for more runs at the end of the current run
    i = j;

This should find all the runs of 3 or more. I wrote "mark elements for destruction" rather than "destroy elements" because it's simpler to find multiple runs this way, since you don't have to worry about the loop indices changing due to destroying a bunch of elements in the middle of iteration. You can go back through in a second pass and actually destroy them.

share|improve this answer
add comment

While I basically agree with Nathan's answer, I wanted to emphasize that (a) another reason to find all the matches at once is for presentation purposes: it just looks better to blow them all up together — and in the more-than-one-dimensional case, it can be relevant because not all matches will stay matches after partial destruction (think of a plus shape on a 2d match-3), and (b) if this is like most match-3s, you'll probably need an outer-outer loop for handling the 'nested' matches that appear (imagine a situation like RGGGRR). What's more, in the 1d case you can actually get by with a single loop through the interior and some careful tests. My structure would look something like this:

bool bMatchesFound;
matchList.clear();
do {
  bMatchesFound = false;
  eColor matchColor = gameBoard[0].color;
  int startPos = 0;
  for ( int curPos=1; curPos < gameBoard.len(); curPos++ ) {
    if ( gameBoard[curPos].color != matchColor ) {
      // we've ended a run; now check to see if it was long enough
      if ( curPos-startPos >= 3 ) {
        // It was - go ahead and add it to our list of matches
        matchList.add(Match(startPos, curPos-1, matchColor));
        bMatchesFound = true;
      }
      // now, regardless, make sure we start a new match-run here
      startPos = curPos;
      matchColor = gameBoard[curPos].color;
    }
  }
  // Finally, check for a match at the end - if our 'last' startPos
  // was far enough back.
  if ( startPos <= gameBoard.len()-3 ) {
    matchList.add(Match(startPos, gameBoard.len()-1, matchColor);
    bMatchesFound = true;
  }
  // 'destroy' all our matches (with suitable pyrotechnics)
  destroyMatches(matchList);
  // and keep doing this until we run out of matches
} while ( bMatchesFound );
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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