This project implements the Grassfire (BFS) Algorithm for pathfinding in a grid-based environment, simulating the movement of a robot from a start cell to a goal cell while avoiding obstacles. The simulation visualizes the grid, the distances calculated by the Grassfire algorithm, and the shortest path found.

• Introduction
• Features
• Requirements
• Usage
  • Parameters
  • Example
• How Grassfire Works
• File Structure
• Results
  • Calculated Distances from Grassfire Algorithm
  • Shortest Path
  • Shortest Path Simulation
• License
• Acknowledgments
• References

This project implements a robot pathfinding simulation using the Grassfire (Breadth-First Search) algorithm on a grid-based environment. The algorithm floods outward from the goal cell, computing the shortest distance to every reachable cell. The robot then follows the gradient of decreasing distance from the start cell to the goal, guaranteeing an optimal shortest path.

• Grid Visualization: Displays a grid with start (green), goal (red), and obstacle (black) cells.
• Distance Calculation: Implements the Grassfire algorithm using BFS to compute distances from the goal to each cell.
• Shortest Path Simulation: Visualizes the robot's movement along the shortest path to the goal.
• Robot Representation: The robot is represented as a blue rectangle with wheels and an orange top mount.
• MATLAB Graphics: Utilizes MATLAB's graphical capabilities to create an interactive simulation experience.

• MATLAB (preferably R2018b or later)

Clone this repository and run the start_simulation.m file, providing the grid dimensions, start cell, goal cell, and obstacles as input parameters.

To run the simulation, call the start_simulation function with the appropriate parameters:

start_simulation(m, n, startCell, goalCell, obstacles)

• m: Number of rows in the grid.
• n: Number of columns in the grid.
• startCell: Linear index of the start cell (row-major order).
• goalCell: Linear index of the goal cell (row-major order).
• obstacles: Array of linear indices representing obstacle cells.

m = 5; % Number of rows
n = 5; % Number of columns
startCell = 1; % Start cell index
goalCell = 13; % Goal cell index
obstacles = [7, 8, 12, 14]; % Obstacle cells

start_simulation(m, n, startCell, goalCell, obstacles);

The Grassfire algorithm is a Breadth-First Search (BFS) that computes shortest distances on a uniform-cost grid:

1. Initialize: Set the goal cell distance to 0, all others to Inf. Mark obstacles as impassable.
2. BFS Flood-Fill: Using a FIFO queue, process cells level by level. For each cell, set each unvisited neighbor's distance to current + 1.
3. Propagation: The "fire" spreads uniformly outward from the goal until all reachable cells have been assigned a distance.
4. Path Extraction: From the start cell, greedily move to the neighbor with the smallest distance value until the goal is reached.

The project consists of the following MATLAB functions:

• start_simulation.m: The main entry point that initiates the simulation, calling other functions to display the grid, run the Grassfire algorithm, and visualize the robot's path.

• display_grid.m: Displays the grid with the start cell (green), goal cell (red), and obstacles (black). Validates input parameters and ensures proper visualization.

• grassfire_algorithm.m: Implements the Grassfire algorithm using BFS to calculate the distance of each cell from the goal while considering obstacles. Obstacles are marked as impassable, and distances propagate uniformly to all reachable cells.

• display_distances.m: Overlays the computed distance values on the grid, showing the distance from each cell to the goal.

• shortest_path.m: Visualizes the shortest path from the start cell to the goal cell by following the gradient of decreasing distances. Animates the robot step-by-step along the optimal path.

• draw_robot.m: Draws the robot's representation on the grid. The robot features a blue rectangular body, black wheels, and an orange circular top mount.

• index_to_rowcol.m: Converts a linear cell index to its corresponding row and column indices using row-major order (left-to-right, top-to-bottom).

This project is licensed under the MIT License. See the LICENSE file for details.

• Inspired by algorithms for pathfinding and robotics.

1. Grassfire Algorithm:

   • H. Edelsbrunner, "Algorithms in Combinatorial Geometry," Springer-Verlag, 1987.
   • Wikipedia: Grassfire algorithm

2. Pathfinding Algorithms:

   • R. Hart, N. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968.

3. Mobile Robots:

   • B. Siciliano et al., Springer Handbook of Robotics, 2nd ed. Springer, 2016.
   • R. Siegwart, I. R. Nourbakhsh, and D. Scaramuzza, Introduction to Autonomous Mobile Robots, 2nd ed. MIT Press, 2011.

4. MATLAB Graphics:

   • MATLAB Documentation: Graphics