Skip to content

README.md

Latest commit

 

History

History
142 lines (106 loc) · 4.84 KB

README.md

File metadata and controls

142 lines (106 loc) · 4.84 KB

Path Planning Visualization (GIF Output) English | 繁體中文

A Python-based path planning simulation that runs A* and BFS on the same randomly generated grid, animates the search process step by step, and exports the result as a GIF. Designed to make the internal logic of path planning algorithms visible and comparable.

Features

  • Dual algorithm comparison : A* and BFS run on the identical obstacle map so exploration behavior can be directly contrasted.
  • Step-by-step GIF output : every explored node is captured as a frame; the final path lingers for 3 seconds at the end.
  • Terminal emoji animation : real-time 🟦 / 🟨 overlay printed to the console while frames are being saved.
  • Auto screenshots : three representative frames (initial / mid-exploration / final path) are saved automatically under outputs/screenshots/.
  • Random obstacle generation : a new map is created on every run; no-path cases are handled gracefully.
  • Modular codebase : grid, planner, visualizer, and GIF generator are fully separated.

GIF Preview


A* Path Planning
BFS Path Planning

Getting Started

Requirements

  • Python 3.8+

Install Dependencies

pip install numpy matplotlib imageio

Run

python main.py

GIFs will be saved to outputs/result_astar.gif and outputs/result_bfs.gif.

Project Structure

project/
│
├── main.py              
├── grid.py              
├── planner.py           
├── visualizer.py        
├── gif_generator.py     
│
└── outputs/
    ├── frames_A*/          
    ├── frames_BFS/         
    ├── result_astar.gif
    ├── result_bfs.gif
    └── screenshots/
        ├── astar/
        │   ├── 01_initial.png
        │   ├── 02_exploring.png
        │   └── 03_final.png
        └── bfs/
            ├── 01_initial.png
            ├── 02_exploring.png
            └── 03_final.png

File Descriptions

File Description
grid.py Defines the Grid class; manages cell states (free, obstacle, start, goal) and provides neighbor queries for the planner
planner.py Implements astar() and bfs(); both return explored_order and final_path
visualizer.py Two outputs: ① terminal emoji print ② matplotlib frame renderer that saves each step as a PNG
gif_generator.py Combines PNG frames into a GIF; picks 3 screenshots automatically
main.py Entry point — initializes grid, runs both algorithms, animates, and triggers GIF export

Data Flow

main.py
  ↓ initialize
grid.py  →  Grid object (random obstacles)
  ↓ input
planner.py  →  explored_order, final_path   (A* and BFS)
  ↓ input
visualizer.py  →  render frame PNG per step  +  print emoji
  ↓ frames
gif_generator.py  →  result_astar.gif / result_bfs.gif  +  3 screenshots

Design Notes

BFS vs A*

BFS A*
Data structure Queue (FIFO) Priority Queue (ordered by f)
Exploration pattern Expands level by level outward Concentrates toward the goal
Shortest path ✓ ✓ (with admissible heuristic)
Nodes explored More (blind) Fewer (guided)

Both algorithms guarantee the shortest path on an unweighted grid. The difference is efficiency: A* uses f(n) = g(n) + h(n) where h is the Manhattan distance heuristic, so nodes closer to the goal are expanded first. BFS has no such guidance and explores radially.

A* Tunable Parameters

Parameter Location Effect
Heuristic function h(n) planner.py · _manhattan() Controls how directed the search is; swap to Euclidean or weighted Manhattan to change exploration shape
Edge cost g(n) planner.py · tentative_g Currently uniform (1 per step); change to support weighted grids

Notes

  • Each run generates a new random obstacle map. Occasionally no path exists — this is expected behavior; simply re-run.
  • To reproduce a specific map, pass seed=<int> to Grid(...) in main.py.
  • Path length reported by the program counts both start and goal nodes (steps = len(path) - 1).

Acknowledgements

This project was developed by AdevLog. Documentation and code suggestions were assisted by ChatGPT and Claude.

License

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