SX-BFS: A Boundary-Padded BFS with Atomic Work Queue Surpassing the Lee Algorithm on Modern Standard Hardware

Abstract We address the problem of optimal shortest-path computation on orthogonal grids, a task central to PCB routing, VLSI layout, robot navigation, and game AI. The Lee Algorithm, proposed in 1961, remains the industry standard for this class of problems due to its simplicity and guaranteed optimality. We propose the SX-BFS algorithm, which introduces two synergistic architectural modifications:(1) a sentinel-padded map that eliminates all boundary conditional checks from the inner BFS loop, removing four branch instructions and two integer divisions per node expansion; and(2) an atomic work queue for heterogeneous multi-core execution, which replaces static slice partitioning with a lock-free fetch_add counter enabling dynamic load balancing across asymmetric ARM big.LITTLE cores. We evaluate both algorithms exhaustively on the complete Moving AI Lab Benchmark, comprising 156 topological maps and 155,620 official scenarios. All experiments are executed single-threaded on a consumer-grade ARM mobile processor (8-core Snapdragon, no auxiliary cooling). Results show that SX-BFS in serial achieves 0.402 ns/cell versus 0.461 ns/cell for Lee (1.15× speedup, 155 map wins vs. 1). With 8 atomic threads, SX-BFS reaches 0.134 ns/cell, a 2.98× improvement over the Lee single-thread baseline, winning 95 of 156 rounds. 100% result equivalence is verified across all 155,620 instances. This work establishes open prior art for micro-architectural optimization of classical routing algorithms. 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-BFS algorithm and its associated micro-architectural optimizations. 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. 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.