Logic behind a bejeweled-like game

In a prototype I am doing, there is a minigame similar to bejeweled. Using a grid that is a 2d array (int[,]) how can I go about know when the user formed a match? I only care about horizontally and vertically.

Off the top of my head I was thinking I would just look each direction. Something like:

int item = grid[x,y];
if(grid[x-1,y]==item)
{
int step=x;
int matches =2;
while(grid[step-1,y]==item)
{
step++;
matches++
}
if(matches>2)
//remove all matching items
}
else if(grid[x+1,y]==item
//....
else if(grid[x,y-1==item)
//...
else if(grid[x,y+1]==item)
//...


It seems like there should be a better way. Is there?

• I remembered I wrote tedious for loop to do that (for a connect-n) Commented Jul 17, 2011 at 23:50

Loop through each item in the same axis (x or y), if they are the same as the previous item them increment matches. When the next item becomes different, check if matches is or greater than 3, call a function that removes matching items, and continue.

AS3 code:

var grid:Array = [[2,3,2,2,2,4],
[ .. ]]; //multidimensional array
var matches:uint;
var gemType:uint;
for(col = 0; col < grid.length; col++){
matches = 0;
gemType = 0; //Reserve 0 for the empty state. If we make it a normal gem type, then only 2 are needed to match for the start.
for(i = 0; i < grid[0].length; i++){
if(grid[col][i] == gemType){
matches++;
}
if(grid[col][i] != gemType || i == grid[0].length - 1){ //subtract 1 because arrays start at 0
if(matches >= 3){
removeMatches(blah);
}
gemType = grid[col][i];
matches = 1;
}
}
}


This is only for the x axis, for y, grid[col][i] would become grid[i][row], etc. I'm sure you can figure that out :)

• Very old post I know, but wanted to point out the flaw in removing items as soon as a match is found. If you had a match along the x-axis you can still potentially have a match on the y-axis that may utilize one of the same tiles. Removing the first match breaks the other from being found. I would flag all matches then remove them after the entire puzzle has been searched. Commented Jan 5 at 18:53

Just thought I'd weigh in with our experience in building a Match-3-like game.

We have built a prototype for a Match-3 based word game, a little like mashing up scrabble and Bejeweled. We realized very early on that the engine that supplies new gems/tiles to fill empty spaces would have to be highly introspective (we run hybrid heuristics and MonteCarlo sampling) in order to create actual opportunities for a player to string letters to form words through the Match-3 mechanic. It's way more elaborate than the description but I'm keeping it brief because we'd have to write a paper.

To answer the OP -- we are doing pattern checks to score how many matches there are on any given gird, at the current time, through a method very similar to "gladoscc" code snippet. While it works robustly, the computational cost for running that recursively during the tree-search play-out becomes a substantial burden, so we are in the process of rewriting this portion of the logic and the data-representation with the bit-board methodology (commonly implemented in other-grid like games like chess, checkers, Othello, etc.) In tests we have shown that it can run over 20 times faster in ActionScript, and so for us the need to do it is a slam-dunk -- and frees up essential cycles for responsiveness, sound, animation, etc.

• Your answer should be an answer and not adding another question. If you have a question, please create a new question using the "ASK QUESTION" button. This is not a discussion forum. Commented Mar 28, 2012 at 7:13
• bummzack.... thank you for that. My rationale was that we had an insight to offer, especially as it relates to the performance of what was earlier proposed when tree-search/introspection was added to the context. And it continued to be relevant since we're still talking essentially about the "Logic behind a Bejeweled game". If this continues to be bad-form, I will be happy to edit/re-post as per your advice. Commented Mar 28, 2012 at 8:19
• That's fine. But you should remove the "question" part from your answer. Questions should be new questions and not part of an answer... Commented Mar 28, 2012 at 8:23
• edited and posted the question elsewhere Commented Mar 28, 2012 at 8:42

Recursion, yo. It's for when you don't know your boundaries.

   public int getHMatchSize(int row, int column)
{
int returnMe = getMatchValue(row, 0, column, 1);

if (returnMe < 3)
{
return 0;
}
else return returnMe;
}

public int getVMatchSize(int row, int column)
{
int returnMe = getMatchValue(row, 1, column, 0);

if (returnMe < 3)
{
return 0;
}
else return returnMe;
}

/// <summary>
/// I return the match size.
/// </summary>
/// <param name="row"></param>
/// <param name="rowDelta">1 means look vertically.  Dont set both deltas to 1.</param>
/// <param name="column"></param>
/// <param name="columnDelta">1 means look horizontally.  Dont set both deltas to 1.</param>
/// <returns>The number of contiguous matching things</returns>
public int getMatchValue(int row, int rowDelta, int column, int columnDelta)
{
int[] start = getEndItem(row, -1 * rowDelta, column, -1 * columnDelta);
int[] end = getEndItem(row, rowDelta, column, columnDelta);

int returnMe = 0;
returnMe += end[0] - start[0];
returnMe += end[1] - start[1];
return returnMe;
}

/// <summary>
/// I will return the end of a sequence of matching items.
/// </summary>
/// <param name="row">start here</param>
/// <param name="column">start here</param>
private int[] getEndItem(int row, int rowDelta, int column, int columnDelta)
{
Gem matchGem = new Gem(-1);
int[] returnMe = new int[2];

if (boardSpace[row + rowDelta][column + columnDelta] == boardSpace[row][column])
{
return getEndItem(row + rowDelta, rowDelta, column + columnDelta, columnDelta);
}
else
{
returnMe[0] = row;
returnMe[1] = column;
return returnMe;
}
}


You can use the flood fill algorithm. It's really useable to this type of problem.

• No, actually it has nothing to do with the Question. The OP is asking how to detect three matching items in a row. Commented Jul 17, 2011 at 20:05
• If you start the fill with the flipped element(s), the algorithm goes through the matching elements. But just to check 3 (and no more) matching element in a row (and no crossing columns), it is maybe an overkill. We use this in a Bubble Puzzle like game, and does exactly what we need. Commented Jul 17, 2011 at 20:35
• You should maybe explain a bit more than just "use the flood fill" because I was confused for a second how that is relevant to this problem. Commented Mar 28, 2012 at 11:33