# Finding valid path on 2D Grid

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

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.

• Thank you very much. I really appreciate your time and I love the solution using the stride method. I previously tried an implementation with stride but it wasn't nearly as declarative as yours since i was not aware of the allSatisfy function. The start property is currently optional because there is also the possibility to place a tile instead of moving it. However this is technical debt I will remove as well. So thank you very much! Nov 5 '18 at 11:16
• I added this condition to the beginning of my isValidDiagonal function: if abs(move.start.row - move.end.row) != abs(move.start.column - move.end.column) { return false }. I think this way I can assure that I only walk the diagonal if it is a move along the diagonal. Nov 5 '18 at 11:52