Determining possible moves/path in grid based game

Question

BACKGROUND: I'm working on an game that drops 3 circles onto a grid and allows the user to move one circle at a time by tapping the circle and than tapping another space on the grid. Each move drops more circles on the grid.

The way the game works though is that if there is no clear path to the spot chosen (for instance your blocked in by other circles or your not blocked in but the way the board is at the moment theres no path of open spaces to that spot) the game will alert you that you have tried to make an invalid move and will reject the move.

MY PROBLEM: I can't figure out a way to get the code to check if the move that was played (tapped) was valid or invalid.

I have given each button a tag with a number corresponding to its spot on the grid (see code .m) Example: At this point of the game a move from space #70 - > #39 would be invalid where a move from #70 -> #71 would be fine.

-Note: Diagonal moves are invalid as well.

How could I get the code to determine this?

Code:(.m)

#import "ViewController.h"

@interface ViewController ()

@end
int name;
bool oneSelect;
UIImage *imageName;
UIButton *selectedButton;
NSArray *items;
NSMutableArray *occupied;
@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
items = [NSArray arrayWithObjects:@"marble_red",@"marble_blue",@"marble_yellow",@"marble_green",@"marble_purple",@"marble_black",@"marble_orange",nil];

    for (int y=0; y < 9; y++) {
        for (int x = 0; x < 9; x++) {
            UIButton * button = [UIButton buttonWithType:UIButtonTypeRoundedRect];
            button.frame = CGRectMake(22 + 30 * x, 100 + 30 * y, 30, 30);
            unsigned buttonNumber = name;
            button.tag = buttonNumber;
            [button setTitle:[NSString stringWithFormat:@"%u", buttonNumber] forState:UIControlStateNormal];
            [button addTarget:self action:@selector(buttonPressed:) forControlEvents:UIControlEventTouchUpInside];
            [self.view addSubview: button];
            name= name +1;
        }

    }

    for (int i = 0; i <= 2; i++) {
        int space = arc4random()%81;
        int pic = arc4random()%7;
        NSString *string = [items objectAtIndex:pic];
        UIButton *button = (UIButton *)[self.view viewWithTag:space];
        [button setBackgroundImage:[UIImage imageNamed:string] forState:UIControlStateNormal];
        NSLog(@"String(%@) / Button(%@)",string,button.description);

    }

}


-(void)buttonPressed:(UIButton *)button
{
    if (!oneSelect) {
        if ([button backgroundImageForState:UIControlStateNormal] != NULL) {
        button.selected = YES;
        imageName = [button backgroundImageForState:UIControlStateNormal];
        selectedButton = button;
        oneSelect = YES;
        }else{
            button.selected = NO;
        }
    }else{
        if ([button backgroundImageForState:UIControlStateNormal] ==  NULL) {
        oneSelect = NO;
        [button setBackgroundImage:imageName forState:UIControlStateNormal];
        button.selected = NO;

        [selectedButton setBackgroundImage:[UIImage imageNamed:@""] forState:UIControlStateNormal];
        selectedButton.selected = NO;
            [self nextMove];
        }else{
            selectedButton.selected = NO;
            button.selected = NO;
        }
    }
    NSLog(@"button %ld -- frame: %@", (long)button.tag, NSStringFromCGRect(button.frame));
}

-(void)nextMove{

    for (int i = 0; i <= 2; i++) {
        int space = arc4random()%81;
        int pic = arc4random()%7;
        NSString *string = [items objectAtIndex:pic];
        UIButton *button = (UIButton *)[self.view viewWithTag:space];
        if ([button backgroundImageForState:UIControlStateNormal] == NULL) {
            [button setBackgroundImage:[UIImage imageNamed:string] forState:UIControlStateNormal];
        }else{
            i = i - 1;
        }
        NSLog(@"String(%@) / Button(%@)",string,button.description);
    }
}

Also if theres anything I should fix in my code that would better the gameplay, let me know.

Answer 1

My approach was to implement an Iterative Deepening Depth First Search

First, I created a class to represent each 'cell' in the board (because I don't like using viewWithTag

BoardCell.h

#import <Foundation/Foundation.h>
#import <UIKit/UIKit.h>

@interface BoardCell : NSObject


@property (weak,nonatomic,readonly) UIButton *button;
@property BOOL occupied;


-(id) initWithButton:(UIButton *)button;

@end

BoardCell.m

#import "BoardCell.h"

@implementation BoardCell

-(id) initWithButton:(UIButton *)button {
    if (self=[super init]) {
        _button=button;
    }

    return self;
}

@end

Then I implemented my version of your game (I changed the images to use some that I already had, so I also changed the dimensions of the cell layout). I wasn't quite sure of the 'rules' of your game, so I made some up. It doesn't check for "game over" but that is trivial.

ViewController.m

#import "ViewController.h"
#import "BoardCell.h"

@interface ViewController ()

@property (strong,nonatomic) NSArray *imageNames;
@property (strong,nonatomic) NSMutableArray *board;
@property NSInteger lastMove;

#define BOARDWIDTH 9
#define BOARDHEIGHT 9

@end

static int moves[]={-BOARDWIDTH,-1,1,BOARDWIDTH};

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.

    self.imageNames = @[@"redhex",@"bluehex",@"purplehex",@"orangehex",@"greenhex"];

    self.board = [NSMutableArray new];

    for (int y=0; y < BOARDWIDTH; y++) {
        for (int x = 0; x < BOARDHEIGHT; x++) {
            UIButton * button = [UIButton buttonWithType:UIButtonTypeRoundedRect];
            button.frame = CGRectMake(40 * x, 100 + 40 * y, 60, 60);
            button.tag = y*BOARDWIDTH+x;
            [button setTitle:[NSString stringWithFormat:@"%ld", button.tag] forState:UIControlStateNormal];

            [button addTarget:self action:@selector(buttonPressed:) forControlEvents:UIControlEventTouchUpInside];
            [self.view addSubview: button];
            [self.board addObject:[[BoardCell alloc] initWithButton:button]];
        }
    }

    self.lastMove=arc4random_uniform(BOARDWIDTH*BOARDHEIGHT);
    UIButton *button=(UIButton *)[self.view viewWithTag:self.lastMove];
    [button setBackgroundImage:[UIImage imageNamed:@"greensquare"] forState:UIControlStateNormal];

    [self addRandoms:3];


}

-(void) addRandoms:(NSInteger)randomCount {
    for (int i = 0; i < randomCount; i++) {
        int space = arc4random_uniform(BOARDWIDTH*BOARDHEIGHT);
        BoardCell *cell=self.board[space];
        if (!cell.occupied) {
            int pic = arc4random_uniform((u_int32_t)self.imageNames.count);
            NSString *string = [self.imageNames objectAtIndex:pic];
            [cell.button setBackgroundImage:[UIImage imageNamed:string] forState:UIControlStateNormal];
            cell.occupied=YES;
        }
        else {
            i--;
        }

    }
}



-(void)buttonPressed:(UIButton *)button
{
    NSInteger buttonId=button.tag;
    BoardCell *cell=self.board[buttonId];

    if (!cell.occupied) {

        BoardCell *startCell=self.board[self.lastMove];
        startCell.occupied=NO;

        if ([self validMoveFromSquare:self.lastMove toDestination:buttonId]) {
            [startCell.button setBackgroundImage:[UIImage imageNamed:@"orangesquare"] forState:UIControlStateNormal];
            [cell.button setBackgroundImage:[UIImage imageNamed:@"greensquare"] forState:UIControlStateNormal];

            self.lastMove=buttonId;
            cell.occupied=YES;
        }
        startCell.occupied=YES;

    }

    [self addRandoms:3];
}


-(BOOL) validMoveFromSquare:(NSInteger)startSquare toDestination:(NSInteger)destination {

    for (int limit=1;limit<50;limit++ ) {
        NSMutableIndexSet *visitList=[NSMutableIndexSet new];
        if ([self DFSFromStart:startSquare toGoal:destination withLimit:limit andVisitList:visitList]) {
            return YES;
        }
    }

    return NO;

}

-(BOOL) DFSFromStart:(NSInteger)start toGoal:(NSInteger)goal withLimit:(NSInteger)limit andVisitList:(NSMutableIndexSet *)visitList {

    if (start==goal) {
        return YES;
    }

    if (limit >=0) {

        if (((BoardCell *)self.board[start]).occupied) {
            return NO;
        }

        [visitList addIndex:start];

        for (int i=0;i<4;i++) {
            NSInteger nextPosition=start+moves[i];

            if ([self validDestination:nextPosition withMove:moves[i] fromSquare:start]) {
                if (![visitList containsIndex:nextPosition]) {
                    if ([self DFSFromStart:nextPosition toGoal:goal withLimit:limit-1 andVisitList:visitList]) {
                        return YES;
                    }
                }

            }
        }
    }
    return NO;

}
-(BOOL) validDestination:(NSInteger)destination withMove:(int)move fromSquare:(NSInteger)start {

    if (destination <0 || destination >= BOARDWIDTH*BOARDHEIGHT) {
        return NO;
    }

    if (abs(move)==1) {
        int sourceRow= (int)start / BOARDWIDTH;
        int destinationRow=(int)destination / BOARDWIDTH;
        if (sourceRow != destinationRow) {
            return NO;
        }
    }

    return YES;
}

- (void)didReceiveMemoryWarning {
    [super didReceiveMemoryWarning];
    // Dispose of any resources that can be recreated.
}

@end

EDIT I misread your question initially, so my code permitted diagonal moves. I have fixed this

EDIT 2 I have increased the DFS limit to 50 and added a new method to correctly check for valid moves - you can't move 'left' or 'right' to a different row. - See the new method at the end and the call to that method in DFSFromStart

EDIT 3 DFSFromStart didn't consider the validity of a move before comparing if the goal had been reached.

Answer 2

Basically, you want to see if the current position is one tile away from the selected position.

There are a few steps to validate this. First, find the difference of the two positions. If the absolute difference of the two spots equals the length of each row (in this case, 9), then that means the selected position is either above or below your current position, making the move valid.

If that step fails, then you need to check if the two spots are next to each other, and if they are, make sure that they are in the same row. To do this, you see if the difference equals 1, and if it does, you divide each position by the length of the row and see if they are equal. What you're left with is something that would be similar to this:

int difference = Absolute(CURRENT - SELECTED)

int CURRENT_ROW_NUMBER = CURRENT / ROW_LENGTH
int SELECTED_ROW_NUMBER = SELECTED / ROW_LENGTH

if(difference == ROW_LENGTH)
{
    ValidMove();
}
else if(difference == 1 && CURRENT_ROW_NUMBER == SELECTED_ROW_NUMBER))
{
    ValidMove();
}
else
{
    InvalidMove();
}

I'm not too familiar with the language, but that's the logic behind what you're attempting.

Good luck with your game!