🧭 A* Pathfinding Algorithm

Informed search, heuristics, and grid-based pathfinding

Overview

A generic A* search implementation with multiple heuristics, grid-based pathfinding with obstacles, and ASCII visualization. A* combines Dijkstra's completeness with greedy best-first speed using an admissible heuristic.

Concepts Demonstrated

Min-heap priority queue — array-backed binary heap with sift-up/down
A* search — f(n) = g(n) + h(n) with open/closed sets
Heuristic functions — Manhattan, Euclidean, and Chebyshev distances
Grid pathfinding — obstacle avoidance with optional diagonal movement
Path reconstruction — predecessor map traversal
ASCII visualization — rendering paths and explored nodes on a grid

Key Functions

Function	Description
`PQ.create`	Create a min-heap priority queue
`PQ.push / PQ.pop`	Insert and extract-min operations
`astar`	Generic A* search over any graph
`grid_astar`	Grid-specific A* with obstacle support
`manhattan / euclidean / chebyshev`	Distance heuristic functions
`visualize_grid`	ASCII rendering of grid, path, and explored cells

How A* Works

(* A* maintains two costs per node:
   g(n) = actual cost from start to n
   h(n) = heuristic estimate from n to goal
   f(n) = g(n) + h(n) — nodes expanded in f-order *)

(* 1. Push start with f = h(start, goal) *)
(* 2. Pop node with lowest f from priority queue *)
(* 3. If it's the goal, reconstruct path *)
(* 4. Expand neighbors: if new g < known g, update *)
(* 5. Repeat until goal found or queue empty *)

let path = grid_astar grid start goal Manhattan in
visualize_grid grid path

Heuristics Comparison

Heuristic	Formula	Best For
Manhattan	\|dx\| + \|dy\|	4-directional grids
Euclidean	√(dx² + dy²)	Any-angle movement
Chebyshev	max(\|dx\|, \|dy\|)	8-directional grids