Finding a path in a 2d grid and returning all matched nodes

Question

Say I have an rows*columns grid, and each node on the grid has an integer (state) value.

state[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]

If the value of

state[row][0] == state[row][NUMBER_OF_COLUMNS -1]

I want to check if there is a "path" consisting of only the same state from these two points..

By path, I mean the state to the left, right, bottom, or top is the same as the origin state.

I'm not sure if it matters, but lets say the state is binary (# or -) So if I'm checking for a path of state == "-", we can continue the path if the state to the N,E,S,W is also == "-"

The end row must equal the start row.

Examples of success:

|# # # # #|    
|# # # # #|    
|# # # # #|
|- # # # #|
|- - - - -|

or

|# # # # #|
|# # # - #|
|# - - - #|
|- - # - -|
|# # # - -|

or

|# # # # #|
|# # # - #|
|# # # - #|
|- - - - #|
|- # # - -|

Examples of fail:

|# # # # #|
|# # # # #|
|# # # # #|
|- - - - #|
|# # - - -|

or

|# # # # #|
|# # # - #|
|# # # - #|
|# - - - #|
|- # # - #|

or

|# # # # #|
|# # - # #|
|# # # # #|
|# - # - #|
|- # - # -|

would fail.

How do I do this? I code in Objective C, but pseudo code to help me understand the steps will be sufficient.

Besides checking for the BOOL existence of a path, I'd want to return an array of all grid coordinate in the path..

Is this easy to implement or am I in way over my head?

Answer 1

So here's the solution that worked from me - based off the maze solving algorithm linked to by @Floris.

There may be a bug or two, and it's certainly not optimized, but it works for now.

Should be pretty easy to follow, thanks for everyone's help:

-(BoardState)solutionPathExistsForColor {
    //create a board copy where the last column equals the first

    for (int i = 0; i < BOARD_ROWS+1; i++) {
        for (int j = 0; j < BOARD_COLUMNS+1; j++) {
            if (j == BOARD_COLUMNS) {
                loopedBoard[i][j] = landed[i][0];
            } else {
                loopedBoard[i][j] = landed[i][j];
            }
        }
    }

    for (BoardState state = 1; state < kBoardStateCount; state++) {
        //first check if it is possible there is a path


        //for each row
        for (int row = 0; row < BOARD_ROWS; row++) {

            //set solution path to zero
            for (int i = 0; i < BOARD_ROWS; i++) {
                for (int j = 0; j < BOARD_COLUMNS; j++) {
                    solutionPath[i][j] = 0;
                }
            }
            BOOL aTest = [self findPathToGoalRow:row //iterate
                                   andGoalColumn:BOARD_COLUMNS  //always the same
                                         fromRow:row  //iterate
                                       andColumn:0  // always the same
                                         ofState:state]; //iterate
            if (aTest) {
                CCLOG(@"Success! State %i", (int)state);
                //now that you know a path exists, modify the path to contain all correct adjacent cells
                [self fixSolutionPathOfColor:state];
                return state;
            } else {
                CCLOG(@"Failure!");
            }
        }
    }
    return kBoardStateVOID;
}

-(BOOL)findPathToGoalRow:(int)goalRow
           andGoalColumn:(int)goalColumn
                 fromRow:(int)fromRow
               andColumn:(int)fromColumn
                 ofState:(BoardState)state {


    //check to see if we've already seen this row and column
    if (solutionPath[fromRow][fromColumn] == 1) {
        return NO;
    }

//  if (x,y outside maze) return false
    if (fromRow > BOARD_ROWS -1 || fromColumn > BOARD_COLUMNS || fromRow < 0 || fromColumn < 0) {
        return NO;
    }
//  if (x,y is goal) return true
    if (fromRow == goalRow && fromColumn == goalColumn) {
        return YES;
    }
//  if (x,y not open) return false
    //if ([self boardStateAtRow:fromRow andColumn:fromColumn] != state) {
    if (loopedBoard[fromRow][fromColumn]!=state) {
        return NO;
    }


//  mark x,y as part of solution path
    solutionPath[fromRow][fromColumn] = 1;

//  if (FIND-PATH(North of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow+1
                      andColumn:fromColumn
                        ofState:state]) {
        return YES;
    }
//  if (FIND-PATH(East of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow
                      andColumn:fromColumn+1
                        ofState:state]) {
        return YES;
    }
//  if (FIND-PATH(South of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow-1
                      andColumn:fromColumn
                        ofState:state]) {
        return YES;
    }
//  if (FIND-PATH(West of x,y) == true) return true
    if ([self findPathToGoalRow:goalRow
                  andGoalColumn:goalColumn
                        fromRow:fromRow
                      andColumn:fromColumn-1
                        ofState:state]) {
        return YES;
    }
//  unmark x,y as part of solution path
    solutionPath[fromRow][fromColumn] = 0;
    return NO;
}

-(void)fixSolutionPathOfColor:(BoardState)color {

    for (int column = 0; column < BOARD_COLUMNS; column++) {
        BOOL bottomColumnOfSolutionPathFound = NO;
        int checkingRow = 0;
        while (!bottomColumnOfSolutionPathFound) {
            if ([self solutionCellAtRow:checkingRow andColumn:column] == 1) {
                bottomColumnOfSolutionPathFound = YES;
            } else {
                checkingRow++;
            }
        }

        //you'll start with this bottom row and look below
        if (solutionPath[checkingRow][column] == 1) {
            int nextRowToCheck = checkingRow-1;
            BOOL keepChecking = YES;
            while (nextRowToCheck >= 0 && keepChecking) {
                if ([self boardStateAtRow:(nextRowToCheck) andColumn:column] == color) {
                    if ([self solutionCellAtRow:(nextRowToCheck) andColumn:column] != YES) {
                        solutionPath[nextRowToCheck][column] = 1;
                    }
                    nextRowToCheck--;
                } else {
                    keepChecking = NO;
                }
            }
            //now repeat for above
            nextRowToCheck = checkingRow+1;
            keepChecking = YES;
            while (nextRowToCheck < BOARD_ROWS && keepChecking) {
                if ([self boardStateAtRow:(nextRowToCheck) andColumn:column] == color) {
                    if ([self solutionCellAtRow:(nextRowToCheck) andColumn:column] != YES) {
                        solutionPath[nextRowToCheck][column] = 1;
                    }
                    nextRowToCheck++;
                } else {
                    keepChecking = NO;
                }
            }
        }
    }
}

Thanks!

Answer 2

It sounds like you are looking at a specific case of a very common general programming problem. Your grid is a specific type of graph; each cell is a node which may be connected to adjacent nodes. Start by looking at the simplest graph traversal strategies; a breadth-first or depth-first search. Those two algorithms are simple tools you should be familiar with and problem all you need to solve this specific problem. In your case you could restrict the search to only be able to explore nodes containing equal values to the current node and see if you are able to reach your destination.

Now either of those algorithms will tell you if a path exists. That's a good start but what if you want to find the shortest path? For that we have Dijkstra's Algorithm.

That's pretty good but we still have to traverse the entire graph to find the shortest path. Not a problem if the graph is small but as it grows that is going to become an expensive operation. Is there some way we can find the shortest path without searching everywhere? There is: take a look at the A* ("A star") algorithm.