Finding valid path on 2D Grid

Question

I got a 2D grid (n x n matrix). The user selects his player in this 2D grid and after that selects another node in this grid to mark his destination position. The player is allowed to move horizontally, vertically or if the player is standing in one of the 4 corners of this grid also diagonally. Also the player can only reach the selected destination if there are no other nodes in the grid blocking the way.

I need to know whether the player can reach the destination or not. To summarize the following needs to be solved:

Input:

• Start (row: Int, column: Int)

• Destination (row: Int, column: Int)

• func isValidMove(from: Start, to: Destination) -> Bool

I have a working implementation however I am more than unhappy with the current state. I think there should be a way more declarative and mathematically correct way to achieve that.

This is what I came up with:

private func isValidHorizontal(move: GameMove, board: GameBoard) -> Bool {
    guard let start = move.start else { return false }
    guard start.row == move.end.row else { return false }

    var from: Int = start.column
    var to: Int = move.end.column + 1
    if start.column < move.end.column {
        from += 1
    } else {
        from = move.end.column
        to = start.column
    }

    for column in from..<to {
        if board.tileType(at: GameBoardPosition(row: start.row, column: column)) != .empty {
            return false
        }
    }
    return true
}

private func isValidVertical(move: GameMove, board: GameBoard) -> Bool {
    guard let start = move.start else { return false }
    guard start.column == move.end.column else { return false }

    var from: Int = start.row
    var to: Int = move.end.row + 1
    if start.row < move.end.row {
        from += 1
    } else {
        from = move.end.row
        to = start.row
    }

    for row in from..<to {
        if board.tileType(at: GameBoardPosition(row: row, column: start.column)) != .empty {
            return false
        }
    }

    return true
}

private func isValid(position: GameBoardPosition, on board: GameBoard) -> Bool {
    return position.row >= 0 && position.row <= board.rows - 1 && position.column >= 0 && position.column <= board.columns - 1
}

private func isValidDiagonal(move: GameMove, board: GameBoard) -> Bool {
    guard let start = move.start else { return false }
    var currentPosition = start

    var walkingIncrement: WalkingIncrement!
    if start.row == 0 && start.column == 0 {
        walkingIncrement = WalkingIncrement(dx: 1, dy: 1)
    } else if start.row == 0 && start.column == board.columns - 1 {
        walkingIncrement = WalkingIncrement(dx: -1, dy: 1)
    } else if start.row == board.rows - 1 && start.column == 0 {
        walkingIncrement = WalkingIncrement(dx: 1, dy: -1)
    } else if start.row == board.rows - 1 && start.column == board.columns - 1 {
        walkingIncrement = WalkingIncrement(dx: -1, dy: -1)
    } else {
        return false
    }

    currentPosition = currentPosition.walk(increment: walkingIncrement)
    while(isValid(position: currentPosition, on: board) && currentPosition != move.end) {
        if board.tileType(at: currentPosition) != .empty {
            return false
        }

        currentPosition = currentPosition.walk(increment: walkingIncrement)
    }

    return true
}

Do you have any advice for me to solve this more practical ?

As asked in the comments I provided a sample playground with a self contained example to better understand the problem and to get a compilable example:Playground Gist

Answer 1

At several places in your code the explicit type annotation is not needed, for example

var from: Int = start.column
var to: Int = move.end.column + 1

can be simplified because the compiler infers the type automatically:

var from = start.column
var to = move.end.column + 1

Checking for empty fields along the move can be simplified if you iterate over a stride(), that allows stepping both in increasing and decreasing order. In func isValidHorizontal() that would be

let direction = (move.end.column - start.column).signum()
for column in stride(from: start.column + direction,
                     to: move.end.column,
                     by: direction) {
    if board.tileType(at: GameBoardPosition(row: start.row, column: column)) != .empty {
        return false
    }
}
return true

This can further be shortened to

return stride(from: start.column + direction,
                to: move.end.column,
                by: direction).allSatisfy {
    board.tileType(at: GameBoardPosition(row: start.row, column: $0)) == .empty
}

using the allSatisfy(_:) method introduced in Swift 4.2.

This approach can be applied to the other methods as well.

In func isValidDiagonal() you can check if a destination position can be reached before walking along the diagonal. For example, if the start position is (0, 0) then an end position (x, y) can be reached only if x == y.

Further remarks:

You have defined the start property in GameMove as optional (in contrast to the end property). Does it really make sense to specify only the end position in a move? If not then make that property non-optional, that would also make several guard statements like

guard let start = move.start else { return false }

obsolete.