match 3 / bust-a-move algorithm to match connecting same colored bubbles

Probably the most difficult parts about making a puzzle bobble/bust-a-move clone is 1) determining when 3 or more of the same color nodes in the grid are matched and removing them and then 2) determining which nodes are no longer connected to the grid after a match/removal has been made.

In my match 3 game, the player fires a bubble and when the bubble hits a target, we check if it has hit to the left/right and spawn on the left/right (of course also check to make sure if it’s the right most / left most node with no room).  Then spawn a new target node at this point.  All target nodes are stored in a 1d sparse array.

When the target node is spawned, we want to check if there is a match of 3 or greater nodes (including this newly spawned one).

The steps for this are:

  1. Get the surrounding nodes indeces (indexes in the 1d sparse array)
  2. Loop through each index
  3. Check if the index contains a target, and get a pointer to it.
  4. If a target exists, get it’s color (in my example, this is the enemyNum property)
  5. If the target can match any color (in my example, GameRoleMultiEnum) set it to the color of the newly spawned ball’s color (heroNum)
  6. Check if the target’s color matches the newly spawned color and make sure it’s not already added to a list to die.
  7. If there is a match in step 6, add the target to a list to be killed.

In my example, I am storing the array of targets to be killed in a dictionary (dict_) with the key as the color (enemyNum) .  The reason for this is because after using this method, I call another method, clearEnemies.  In clearEnemies, we check the count of the array stored in dict_ for the color key.  If it’s count is >= 3, we clear those enemies.  If it’s not, we don’t.

Some other notes about the code:

As this is a puzzle bobble/bust-a-move type of game, I want the effect whereby enemies/targets will be destroyed in a chain.  This means that if a new target /bubble is spawned in the middle of 6 other bubbles, they will be destroyed from the center, starting with the newly spawned, then the left/right nodes will be destroyed, and so on.  Just as they are matched in the recursive method.  To do this, we keep track of the iterations in the recursive method.  With each iteration, the delayToRemove the bubble increases.

Example implementation:

-(void) flagEnemiesWithNumber:(int)heroNum index:(int)index iter:(int)iter
{
	NSMutableArray *eToKillArr = [dict_ objectForKey:[NSNumber numberWithInt:heroNum]];

	if(iter == 0) {

		Enemytarget *enemy = [arrayEnemyTargets_ objectAtIndex:index];
		enemy.delayToRemove = 0.05;
		[eToKillArr addObject:enemy];
	}
	iter++;

	NSMutableArray *surroundingIndices = [self getSurroundingIndices:index];

	for(NSNumber *num in surroundingIndices) {
		int indexNum = [num intValue];

		id obj = [arrayEnemyTargets_ objectAtIndex:indexNum];
		if(obj != [NSNull null]) {
			Enemytarget *t = obj;

			int enemyNum = t.enemyNum;

			if(enemyNum == GameRoleMultiEnum)
				enemyNum = heroNum;

			if(enemyNum == heroNum && ![eToKillArr containsObject:t] /* && !t.isDead */) {
				t.delayToRemove = iter * 0.05 + 0.05;
				[eToKillArr addObject:t];
				[self flagEnemiesWithNumber:heroNum index:t.index iter:iter];
			}
		}
	}

}

-(int) clearEnemies
{
	int totalKilled = 0;
	for(id key in dict_) {
		NSMutableArray *eToKillArr = [dict_ objectForKey:key];
		int numKilled = [eToKillArr count];

		if(numKilled >= 3) {
			for(Enemytarget *t in eToKillArr) {
				[self removeEnemy:t delay:t.delayToRemove showPopAnim:YES];
				totalKilled++;
			}
		}
		[eToKillArr removeAllObjects];
	}

	return totalKilled;
}

The reason we are keeping track of the total number killed is that we only want to begin an animation to clear unconnected nodes after all of the matched enemies have been cleared.

You will remember the second major problem in developing this kind of game: 2) determining which nodes are no longer connected to the grid after a match/removal has been made.

This can be achieved using virtually the same recursive method to match same colored bubbles.  But for this, we want to begin our search at the top most node, and match any neighboring bubble not already flagged as matched, flag the bubble as matched, and call ourself with this new bubbles index.  After this is finished, we can just loop through all of the bubbles, and any bubble not flagged as matched can be removed.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: