12
\$\begingroup\$

I've been prototyping a Match 3 game (Bejeweled clone) because I have an interesting concept for one, and because it is good practice. One key aspect of my version is that the matches must contain one of the swapped orbs. Therefore matches elsewhere on the board do not get destroyed (and for now there are no combos).

To solve this, I devised a special algorithm that searches for matches starting with the positions of the swapped orbs.

Since this is a naive implementation of Match 3, I am sure that there are lots of problems with the code and especially with the algorithm.

Here is the initial evaluation that happens when a player tries to swap two orbs:

-(BOOL) swapOrb:(DMOrb *)firstOrb withOrb:(DMOrb *)secondOrb {

    //if its the same orb, fail
    if ([firstOrb isEqual:secondOrb]) {
        return  NO;
   }
   //check and make sure that the orbs are next to each other
    if (![self orbAdjacent:firstOrb toOrb:secondOrb]) {
        return NO;
    }

    //potentially check and make sure they are not the same color here

    //makes a copy of the board inside the eval class
    _boardEval.board = self.board;

    //actually moves the pieces, but will only save the new board if there is a match
    if ([_boardEval swapHasMatchesForOrb:firstOrb withOrb:secondOrb]) {
        [_boardEval resolveSwapBetweenPosition:firstOrb.boardPosition position:secondOrb.boardPosition];
        self.board = _boardEval.board;
        return YES;
    }

    return NO;
}

And here is the board evaluator class. It is possible that all of this class should simply be in the GameBoard class, but I am unsure. Right now the Game class has both the GameBoard and the BoardEvaluator, and processes the moves of the game sent by the UI.

DMBoardEval.h

#import <Foundation/Foundation.h>
#import "DMGameBoard.h"

@interface DMBoardEval : NSObject

@property (nonatomic) DMGameBoard *board;

-(BOOL) swapHasMatchesForOrb:(DMOrb *)firstOrb withOrb:(DMOrb *)secondOrb;
-(void) resolveSwapBetweenPosition:(CGPoint)firstPosition position:(CGPoint)secondPosition;

@end

DMBoardEval.m

#import "DMBoardEval.h"
#import "DMRow.h"
#import "DMColumn.h"

static const int kNumOrbsPerRow = 9;

@implementation DMBoardEval

#pragma mark - Copy Board
-(void) setBoard:(DMGameBoard *)board {
    _board = [DMGameBoard boardWithBoard:board];
}

#pragma mark - Swap Orbs
-(BOOL) swapHasMatchesForOrb:(DMOrb *)firstOrb withOrb:(DMOrb *)secondOrb {
    [_board swapOrb:firstOrb withOrb:secondOrb];
    //dont need to switch them back because the board will be kept if there are matches and discarded if not
    //[_board swapOrb:secondOrb withOrb:firstOrb];
    return [self findMatchesInBoardForPosition:firstOrb.boardPosition secondPosition:secondOrb.boardPosition];
}

#pragma mark - Quick Search for Matches
-(BOOL) findMatchesInBoardForPosition:(CGPoint)firstPos secondPosition:(CGPoint)secondPos {
    DMRow *firstRow = _board.rows[(int)firstPos.y];
    DMOrb *firstOrb = firstRow.orbs[(int)firstPos.x];
    DMRow *secondRow = _board.rows[(int)secondPos.y];
    DMOrb *secondOrb = secondRow.orbs[(int)secondPos.x];

    if ([self findMatchesForOrb:firstOrb] ||
        [self findMatchesForOrb:secondOrb]) {
        return YES;
    }

    return NO;
}
-(BOOL) findMatchesForOrb:(DMOrb *)orb {
    if ([self searchRowForMatchesWithOrb:orb]) {
        return YES;
    }
    if ([self searchColumnForMatchesWithOrb:orb]) {
        return YES;
    }
    return NO;
}
-(BOOL) searchRowForMatchesWithOrb:(DMOrb *)orb {
    DMRow *row = _board.rows[(int)orb.boardPosition.y];
    //search right in row
    BOOL otherColorFound = NO;
    int numberOfOrbs = 0;
    for (int i = orb.boardPosition.x; i < kNumOrbsPerRow; i++) {
        if (!otherColorFound) {
            if (orb.type == ((DMOrb *)row.orbs[i]).type) {
                numberOfOrbs++;
            } else {
                otherColorFound = YES;
            }
        }
    }
    if (numberOfOrbs >= 3) {
        return YES;
    }
    //search left in row
    otherColorFound = NO;
    numberOfOrbs = numberOfOrbs - 1; //because it is going to count self again
    for (int i = orb.boardPosition.x; i >= 0; i--) {
        if (!otherColorFound) {
            if (orb.type == ((DMOrb *)row.orbs[i]).type) {
                numberOfOrbs++;
            } else {
                otherColorFound = YES;
            }
        }
    }
    if (numberOfOrbs >= 3) {
        return YES;
    }

    return NO;
}
-(BOOL) searchColumnForMatchesWithOrb:(DMOrb *)orb {
    //create columns
    NSMutableArray *columns = [[NSMutableArray alloc]init];
    for (int i = 0; i < kNumOrbsPerRow; i++) {
        [columns addObject:[[DMColumn alloc]initWithRows:_board.rows number:i]];
    }

    DMColumn *column = columns[(int)orb.boardPosition.x];
    //search up in column
    BOOL otherColorFound = NO;
    int numberOfOrbs = 0;
    for (int i = orb.boardPosition.y; i < kNumOrbsPerRow; i++) {
        if (!otherColorFound) {
            if (orb.type == ((DMOrb *)column.orbs[i]).type) {
                numberOfOrbs++;
            } else {
                otherColorFound = YES;
            }
        }
    }
    if (numberOfOrbs >= 3) {
        return YES;
    }
    //search down in column
    otherColorFound = NO;
    numberOfOrbs = numberOfOrbs - 1; //because it is going to count self again
    for (int i = orb.boardPosition.y; i >= 0; i--) {
        if (!otherColorFound) {
            if (orb.type == ((DMOrb *)column.orbs[i]).type) {
                numberOfOrbs++;
            } else {
                otherColorFound = YES;
            }
        }
    }
    if (numberOfOrbs >= 3) {
        return YES;
    }

    return NO;
}

#pragma mark - Resolve Move
-(void) resolveSwapBetweenPosition:(CGPoint)firstPos position:(CGPoint)secondPos {
    DMRow *firstRow = _board.rows[(int)firstPos.y];
    DMOrb *firstOrb = firstRow.orbs[(int)firstPos.x];
    [self markMatchesForOrb:firstOrb];

    DMRow *secondRow = _board.rows[(int)secondPos.y];
    DMOrb *secondOrb = secondRow.orbs[(int)secondPos.x];
    [self markMatchesForOrb:secondOrb];

    [self destroyMarkedOrbs];
}
-(void) destroyMarkedOrbs {
    for (DMRow *row in _board.rows) {
        for (DMOrb *orb in row.orbs) {
            if (orb.markedForDestruction) {
                //placeholder until block settling is in place
                orb.type = DMOrbTypeNumTypes;
            }
        }
    }
}

#pragma mark - Mark Complete Matches
-(void) markMatchesForOrb:(DMOrb *)orb {
    [self markRowForMatchesWithOrb:orb];
    [self markColumnForMatchesWithOrb:orb];
}
-(void) markRowForMatchesWithOrb:(DMOrb *)orb {
    DMRow *row = _board.rows[(int)orb.boardPosition.y];
    //search right in row
    BOOL otherColorFound = NO;
    NSMutableSet *orbsToMark = [[NSMutableSet alloc]init];
    for (int i = orb.boardPosition.x; i < kNumOrbsPerRow; i++) {
        if (!otherColorFound) {
            DMOrb *nextOrb = row.orbs[i];
            if (orb.type == nextOrb.type) {
                [orbsToMark addObject:nextOrb];
            } else {
                otherColorFound = YES;
            }
        }
    } 
    //search left in row
    otherColorFound = NO;
    for (int i = orb.boardPosition.x; i >= 0; i--) {
        if (!otherColorFound) {
            DMOrb *nextOrb = row.orbs[i];
            if (orb.type == nextOrb.type) {
                [orbsToMark addObject:nextOrb];
            } else {
                otherColorFound = YES;
            }
        }
    }
    //mark the appropriate orbs
    if (orbsToMark.count >= 3) {
        for (DMOrb *orb in orbsToMark) {
            orb.markedForDestruction = YES;
        }
    }
}
-(void) markColumnForMatchesWithOrb:(DMOrb *)orb {
    //create columns
    NSMutableArray *columns = [[NSMutableArray alloc]init];
    for (int i = 0; i < kNumOrbsPerRow; i++) {
        [columns addObject:[[DMColumn alloc]initWithRows:_board.rows number:i]];
    }

    DMColumn *column = columns[(int)orb.boardPosition.x];
    //search up in column
    BOOL otherColorFound = NO;
    NSMutableSet *orbsToMark = [[NSMutableSet alloc]init];
    for (int i = orb.boardPosition.y; i < kNumOrbsPerRow; i++) {
        if (!otherColorFound) {
            DMOrb *nextOrb = column.orbs[i];
            if (orb.type == nextOrb.type) {
                [orbsToMark addObject:nextOrb];
            } else {
                otherColorFound = YES;
            }
        }
    }
    //search down in column
    otherColorFound = NO;
    for (int i = orb.boardPosition.y; i >= 0; i--) {
        if (!otherColorFound) {
            DMOrb *nextOrb = column.orbs[i];
            if (orb.type == nextOrb.type) {
                [orbsToMark addObject:nextOrb];
            } else {
                otherColorFound = YES;
            }
        }
    }
    //mark the appropriate orbs
    if (orbsToMark.count >= 3) {
        for (DMOrb *orb in orbsToMark) {
            orb.markedForDestruction = YES;
        }
    }
}

@end

There is a bit of code duplication inside the BoardEval class in the methods that search for a match and the methods that mark the orbs that will be destroyed due to a match. I could not figure out a good solution for this. I wanted the search for any match to return as soon as it found one, because any match will cause a swap to be valid. It is only after the swap is valid that it needs to calculate all of the orbs that will be destroyed. Part of the reason for this setup is that the UI will animate an attempted swap when a swap is invalid, and will otherwise animate the completed swap. However, my approach may not be the best way to approach the problem.

\$\endgroup\$
8
\$\begingroup\$

This can be 100% eliminated:

-(void) setBoard:(DMGameBoard *)board {
    _board = [DMGameBoard boardWithBoard:board];
}

And instead, change the property declaration to look like this:

@property (copy) DMGameBoard *board;

I'd rewrite this method:

-(BOOL) findMatchesForOrb:(DMOrb *)orb {
    if ([self searchRowForMatchesWithOrb:orb]) {
        return YES;
    }
    if ([self searchColumnForMatchesWithOrb:orb]) {
        return YES;
    }
    return NO;
}

As this (notice I'm also renaming... "find matches" implies we'll return matches):

- (BOOL)hasMatchesForOrb:(DMOrb *)orb {
    return [self searchRowForMatchesWithOrb:orb] || 
        [self searchColumnForMatchesWithOrb:orb];
}

for (int i = orb.boardPosition.x; i < kNumOrbsPerRow; i++) {
    if (!otherColorFound) {
        if (orb.type == ((DMOrb *)row.orbs[i]).type) {
            numberOfOrbs++;
        } else {
            otherColorFound = YES;
        }
    }
}
if (numberOfOrbs >= 3) {
    return YES;
}

This is just a subsection of one of your methods, but it's a little confusing. Let' see if we can clear it up and make it a little more efficient.

for (int i = orb.boardPosition.x; i < kNumOrbsPerRow; ++i) {
    if (orb.type == ((DMOrb *)row.orbs[i]).type) {
        if (++numOrbs >= 3) {
            return YES;
        }
    } else {
        break;
    }
}

This pattern can be applied in 3 other places. This pattern eliminates the otherColorFound variable and saves us a lot of iterations. Consider if your row is say 20 orbs wide, and I move an orb into the 20th spot. Your original implementation will iterate 20 times no matter what. With this implementation, we stop as soon as we find a different .type or as soon as we find 3 in a row.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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