A* Pathfinding

Description

Demonstrates the A* search algorithm on a grid map with obstacles, navigating from source S to goal G. Shows the f=g+h cost function for each cell, contrasting the open set (frontier) and closed set (visited), and how the heuristic guides the search more efficiently than BFS. The final path is highlighted in gold.

---

Phases

#	Phase Name	Duration	Description
1	Intro	3s	Title, grid displayed with S, G, and obstacles
2	Algorithm Intro	4s	Show f = g + h formula, explain g (cost so far) and h (heuristic)
3	Search Loop	28s	Expand cells from open set: show f/g/h values, color open set cyan, closed set purple
4	Path Found	5s	Trace back final path, highlight in gold
5	Comparison	5s	Brief note showing A* explores fewer cells than BFS
6	Outro	3s	Final path displayed

---

Layout

+--------------------------------------------------+
|  Title: A* Pathfinding                           |
+--------------------------------------------------+
|  Formula: f = g + h  (top-right)                 |
|                                                  |
|  Grid (center):                                  |
|  +--+--+--+--+--+--+                            |
|  |S |  |##|  |  |  |                            |
|  |  |  |##|  |  |  |                            |
|  |  |  |  |  |##|G |                            |
|  +--+--+--+--+--+--+                            |
|                                                  |
|  Legend: [cyan]=open  [purple]=closed            |
|          [gold]=path  [dark]=obstacle            |
|                                                  |
|  Open set list (right panel)                     |
+--------------------------------------------------+

Area Descriptions

• Center: Grid with colored cells showing search progress
• Top right: f=g+h formula annotation
• Bottom: Legend for cell colors
• Right panel: Current open set contents

---

Assets & Dependencies

• Fonts: LaTeX / sans-serif
• Manim version: ManimCE 0.19.1

---

Notes

• Show small f/g/h numbers inside each explored cell
• Manhattan distance heuristic used
• Obstacles drawn as dark filled squares with hash pattern indication
• S and G labeled clearly with distinct colors