SX-A*: Sentinel-eXtended A* Algorithm Surpassing Classic A* on Modern Standard Hardware

Abstract We 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, we now apply the sentinel-padded map technique to A* with 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—double the branch reduction of SX-BFS—by surrounding the grid with obstacle sentinels. Additionally, SX-A* avoids the division ( / ) and modulo ( % ) operations required by classic A* to decompose flat indices into coordinates by storing coordinates explicitly in the priority-queue node. Results demonstrate that SX-A* wins 155 of 156 maps, achieving a global empirical speedup of 1.306× . 100% result equivalence is strictly verified across all 155,620 scenario instances. This work is deposited at Zenodo as open prior art under the PolyForm Noncommercial License 1.0.0. STATEMENT OF PRIOR ART AND LICENSE TERMS (Aligned with PolyForm Noncommercial License 1.0.0) 1. Permitted Noncommercial Use Use of this work for noncommercial purposes, including academic research, independent study, education, benchmarking, validation, and experimental evaluation, is permitted under the terms of the PolyForm Noncommercial License 1.0.0, provided proper attribution is given. 2. Statement of Prior Art This document constitutes a formal public disclosure establishing prior art for the SX-A* algorithm and its associated micro-architectural optimizations (including, but not limited to, 8-directional boundary-frame elimination and explicit coordinate caching). This disclosure is intended solely to prevent third-party patent claims and does not grant any commercial rights. 3. Scope of the License All implementations of the methods described herein—whether in software or hardware—are governed exclusively by the PolyForm Noncommercial License 1.0.0. This includes any implementation, in any programming language, and on any programmable or dedicated hardware platform, including FPGA or similar architectures. 4. Noncommercial Restriction Any use of this work that falls outside the definition of noncommercial use, as defined by the PolyForm Noncommercial License 1.0.0, is not permitted under this license. 5. Commercial and Operational Use Any commercial, operational, institutional, governmental, regulatory, or production deployment of this work constitutes use outside the scope of the PolyForm Noncommercial License 1.0.0 and therefore requires separate authorization from the authors, in accordance with the terms of that license.For the purposes of this document, authors refers to the original author and any officially recognized co-authors or principal contributors, as reflected in the associated public repository and its contribution records. 6. Derivative Works and Functional Equivalence Reimplementation, translation, refactoring, architectural modification, or functional equivalence does not remove a work from the scope of the PolyForm Noncommercial License 1.0.0. Any such implementation remains subject to the same license terms. 6.a. Code Size Irrelevance (No Minimum Threshold) For the avoidance of doubt, the applicability of the PolyForm Noncommercial License 1.0.0 is independent of code size, number of lines, percentage of implementation, degree of literal similarity, or partial extraction. There is no minimum threshold of code volume or implementation extent required for a work to fall within the scope of this license. Any use, reproduction, reimplementation, refactoring, selective reuse, architectural translation, or functional incorporation of the disclosed concepts—regardless of size or extent—is subject to the terms of the PolyForm Noncommercial License 1.0.0. 7. Knowledge Contamination and Attribution Exposure to this work constitutes prior knowledge of the disclosed methods. Subsequent implementations making material use of the disclosed concepts remain subject to attribution and license requirements as defined by the PolyForm Noncommercial License 1.0.0. 8. Intellectual Property Ownership Nothing in this document shall be construed as transferring ownership of intellectual property. All intellectual property rights remain with the authors, subject only to the permissions explicitly granted under the PolyForm Noncommercial License 1.0.0. 9. No Additional Rights Granted This document does not grant any rights beyond those expressly provided by the PolyForm Noncommercial License 1.0.0. In the event of any conflict, the terms of the PolyForm Noncommercial License 1.0.0 shall control. 10. Enforcement and Remedies Any use of this work in violation of the PolyForm Noncommercial License 1.0.0 shall be addressed exclusively through the remedies and enforcement mechanisms provided by that license and by applicable law.