Md Hasibuzzaman Ph.D. Candidate (National Taipei University, Taiwan)

The Enhanced Grassfire (EGF) algorithm produces a clean, connected, 1-pixel-wide medial axis from any binary occupancy grid using four sequential stages:

1. Wave Propagation — Grassfire BFS assigns every free cell an arrival-time label equal to its shortest obstacle distance (EDT-like, 8-connected).
2. Fat Skeleton — Local maxima of the distance field are retained; cells whose removal disconnects the skeleton are preserved (topology-safe pruning).
3. 1-Pixel Skeleton — Iterative parallel thinning reduces the fat skeleton to a single-pixel-wide medial axis without breaking connectivity.
4. Local Thinning (LUT) — A 3×3 look-up table removes redundant skeleton pixels while preserving branch endpoints and junctions, yielding a topologically correct Voronoi skeleton.

An interactive benchmark compares three skeletonization methods across 12 standard test shapes:

• EDT (Euclidean Distance Transform) — Classical distance-field skeleton using Euclidean metrics.
• H-Blum Grassfire — Original Blum's symmetric axis transform via isotropic wave propagation.
• EGF-MAT (Ours) — Enhanced Grassfire with 4-stage pipeline, measured on skeleton pixel count, branch count, connectivity, and computation time.

Test shapes include: circle, rectangle, L-shape, T-shape, cross, star, hand silhouette, ring, irregular polygon, composite maze, narrow corridor, and concave body. Results confirm EGF-MAT produces the thinnest, most connected skeleton with fewer spurious branches.

An interactive path-planning system tests 10 algorithms on the same N×N occupancy grid, comparing skeleton-guided vs. classical planners:

Metrics recorded: path length (cells), nodes expanded, computation time (ms). The EGF-skeleton-guided planner consistently reduces node expansions by channeling the search through the topological medial axis before local refinement.

The proposed Jan & Hasibuzzaman algorithm introduces a minimum-expansion moat strategy that drastically reduces the number of cells visited before a path is found:

1. EGF Skeleton Graph — The occupancy grid is skeletonized; the resulting 1-pixel medial axis becomes the search backbone.
2. Skeleton Path — A fast BFS/Dijkstra on the sparse skeleton graph finds a tentative skeleton-level route from source to target.
3. Moat Construction — A corridor (moat) of fixed width is dilated around the skeleton path to create a compact search region, discarding cells outside it.
4. Dial Wave (LL₀/LL₁/LL₂) — A 3-bucket circular Dial's algorithm propagates within the moat using fixed integer costs: straight = 100, diagonal = 141. Buckets cycle as (AT[n]/100) % 3. Only this final wave step is timed.

The moat restricts the Dial wave to a narrow band around the likely optimal path, achieving near-optimal path quality with a fraction of the node expansions compared to full-grid planners.