AnimGロゴAnimG

A* Pathfinding

対象: Software Engineerカテゴリ: Computer Science

説明

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.

このアニメから作る

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