Pathfinding on a Grid

Function Name: findShortestPath

Description

Write a function that takes a grid of walkable and non-walkable cells, as well as a start and an end position. The grid will be represented as a 2D array where 0s are walkable spaces and 1s are barriers. The start and end positions will be given as tuples (row, column). Your function should compute the shortest path from start to end and return the path as a list of tuples, detailing each step taken. If there is no path, return an empty list.

Requirements

• The function 'findShortestPath' should take four parameters: grid, start, end, and allowDiagonal, where 'grid' is a list of lists of integers, 'start' and 'end' are tuples representing the grid coordinates, and 'allowDiagonal' is a boolean indicating whether diagonal movement is allowed.
• Do not alter the original grid.
• Your solution should implement a breadth-first search algorithm to guarantee the shortest path.
• If multiple shortest paths exist, the function may return any of them.
• If allowDiagonal is true, the path can include diagonal moves; otherwise, it should only include up, down, left, and right moves.
• Optimize the function for time and space complexity.

Examples

Example call: findShortestPath([[0, 0, 0], [1, 1, 0], [0, 0, 0]], (0, 0), (2, 2), false)Example output: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]

Links