SX-A*: Sentinel-eXtended A* Algorithm

paper / Zenodo.AbstractWe extend the Sentinel-eXtended (SX) framework introduced in Pirolo (2026a) to the A* algorithm, the dominant heuristic-guided pathfinding standard. While SX-BFS demonstrated a 1.15× serial speedup over the Lee algorithm on orthogonal 4-directional grids, this work applies the sentinel-padded map technique to A* using a full 8-directional octile heuristic, the native domain of A* in the Moving AI Lab Benchmark.We propose SX-A* (Sentinel-eXtended A*), which eliminates all eight boundary conditional checks per node expansion—doubling the branch reduction achieved by SX-BFS—by surrounding the grid with an obstacle sentinel frame, rendering boundary guards structurally unnecessary. Additionally, SX-A* avoids the division (/) and modulo (%) operations required by classical A* to decompose flat indices into coordinates by storing coordinates explicitly within each priority-queue node.We evaluate both algorithms on the complete Moving AI Lab Benchmark: 156 maps and 155,620 scenarios, validated on two independent hardware platforms (ARM Snapdragon mobile / Android Cxxdroid and Intel Core i5 5th generation / Linux GCC). Results: SX-A* outperforms the baseline on 155 of 156 maps, achieving a global speedup of 1.306× (from 8.04 ns/cell to 6.15 ns/cell), with 100% result equivalence verified across all 155,620 instances.The sentinel technique, originally proposed for BFS, proves even more effective for A* due to the doubling of boundary checks inherent to 8-directional traversal. To the best of the author’s knowledge, following an exhaustive literature search assisted by Anthropic Claude (Sonnet) on February 26, 2026, no openly published implementation achieves equivalent throughput on modern consumer hardware.This work is deposited on Zenodo as open prior art under the PolyForm Noncommercial License 1.0.0.Keywords: A* Algorithm, SX-A*, Sentinel Pattern, Octile Heuristic, 8-Directional Pathfinding, ARM Architecture, x86, Moving AI Lab Benchmark, Branchless Optimization, Prior Art, SX-BFS, Heuristic Search