Franco, Markus Xyren L.; Padron, Arvin; Poliquit, Kimberly Jane
Enhancement of Somosa Jump Point Search algorithm applied in emergency response routing system
- Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025
ABSTRACT: Traditional Jump Point Search (JPS) is an optimized pathfinding approach for uniform grid-based maps, but it faces challenges in scalability and efficiency, particularly in large-scale and dynamic environments. In emergency response routing systems, efficient and rapid pathfinding is critical foe ensuring timely assistance. The existing Somosa Jump Point Search Algorithm offers improvements over basic pathfinding techniques, yet it still faces limitations in terms of: (a) redundant node evaluation; (b) inefficiencies in obstacle handling and backtracking during pathfinding; (c) non-existent priority-based movement selection resulting in less efficient paths. These limitations can result in delayed responses, which are crucial in emergency scenarios. To address these issues, this study proposes an enhanced version of the Somosa Jump Point Search Algorithm through three main techniques by (a) Pruned Neighbor Selection minimizes computational overhead by ignoring already visited or irrelevant neighboring nodes; (b) Recursive Jump Optimization (RJO) improves traversal by bypassing obstructed or non-essential nodes and dynamically continuing the search through queued alternatives; (c) Stepwise Pruning Algorithm (SPA) refines the search process by progressively filtering out low-priority nodes at each step. The integration of these enhancements led to a more efficient and responsive routing system, demonstrating reduced search space and faster path generation in simulated emergency scenarios.