Pathfinding in a Grid with Obstacles

This challenge focuses on implementing pathfinding algorithms in a 2D grid environment with obstacles. The goal is to find a clear, unobstructed path between a starting point and an ending point. This is a fundamental problem in robotics, game development, and navigation systems.

Problem Description

You are tasked with creating a Go program that determines if a path exists between a starting cell and an ending cell in a grid, avoiding obstacles. The grid is represented as a 2D slice of booleans, where true represents an open cell (passable) and false represents an obstacle (impassable). Your program should implement a Breadth-First Search (BFS) algorithm to find the shortest path.

What needs to be achieved:

• Implement a function FindPath(grid [][]bool, startRow, startCol, endRow, endCol int) []([]int) that takes a grid, starting coordinates (row, column), and ending coordinates (row, column) as input.
• The function should return a slice of coordinate pairs []([]int) representing the path from the start to the end. Each coordinate pair is represented as []int{row, col}.
• If a path exists, the returned slice should contain the coordinates in the order they should be visited, starting with the start coordinate and ending with the end coordinate.
• If no path exists, the function should return an empty slice []([]int).

Key Requirements:

• Use Breadth-First Search (BFS) to explore the grid.
• The algorithm should find the shortest path (in terms of number of steps).
• The grid is rectangular (all rows have the same number of columns).
• The start and end coordinates must be within the bounds of the grid.
• The start and end coordinates cannot be obstacles.

Expected Behavior:

The FindPath function should systematically explore the grid, expanding outwards from the starting cell. It should keep track of visited cells to avoid cycles. When the ending cell is reached, the path taken to reach it should be reconstructed and returned.

Edge Cases to Consider:

• Start and end are the same: Return a slice containing only the start coordinate.
• No path exists: Return an empty slice.
• Start or end is an obstacle: Return an empty slice.
• Invalid start/end coordinates (out of bounds): Return an empty slice.
• Grid is empty: Return an empty slice.

Examples

Example 1:

Input: grid = [][]bool{{true, true, true}, {true, false, true}, {true, true, true}}, startRow = 0, startCol = 0, endRow = 2, endCol = 2
Output: []([]int){[0 0], [1 0], [2 0], [2 1], [2 2]}
Explanation: A valid path exists from (0,0) to (2,2) avoiding the obstacle at (1,1).  BFS guarantees the shortest path.

Example 2:

Input: grid = [][]bool{{true, false, true}, {true, false, true}, {true, true, true}}, startRow = 0, startCol = 0, endRow = 2, endCol = 2
Output: []([]int){[0 0], [1 0], [2 0], [2 1], [2 2]}
Explanation:  A valid path exists, even with obstacles present.

Example 3:

Input: grid = [][]bool{{true, false, true}, {true, false, true}, {true, false, true}}, startRow = 0, startCol = 0, endRow = 2, endCol = 2
Output: []([]int){}
Explanation: No path exists from (0,0) to (2,2) because all possible routes are blocked.

Constraints

• The grid will have dimensions between 1x1 and 100x100.
• startRow, startCol, endRow, and endCol will be integers between 0 and the respective grid dimensions minus 1.
• The grid will contain only true and false values.
• The algorithm should complete within 1 second for all valid inputs.

Notes

• Consider using a queue to implement BFS.
• A visited set (or similar data structure) is crucial to prevent cycles and ensure efficiency.
• Think about how to reconstruct the path after the end node is found. A parent map can be helpful.
• Error handling for invalid inputs (out-of-bounds coordinates, start/end being obstacles) is important. Return an empty slice in these cases.
• Focus on clarity and readability of your code. Good variable names and comments are appreciated.