Physics-Aware A*: Sequential Filtering for Jump Feasibility in 2D Platformers

• Gabriel Barbosa de Oliveira USP
• Leonardo Tortoro Pereira UNESP
• Maria Victória Brandão Barros USP

DOI: https://doi.org/10.5753/sbgames.2026.26411

Resumo

Introduction: In 2D platform games, movement is governed by physics (gravity, limited jumps, air momentum). Traditional pathfinding algorithms like A* assume free movement, generating geometrically valid but physically impossible paths. Objective: We propose an incremental physical validation approach integrated into A*, using augmented states and a modular filter chain to find traversable paths in platformer levels. Methodology: The algorithm augments states with movement phases (grounded/jumping/falling), jump origin, and initial velocity. A sequential filter chain validates collisions, reachability (via UAM equations), momentum conservation, and trajectory blocking. Experiments on four classic maps compare our method against standard A*. Results: Our method finds 3–13× more physically valid paths than A*, but at the median consumes 10–35× more memory and runs 21–97× slower. The trade-off is acceptable for offline pre-computation and individual NPCs.

Palavras-chave: Pathfinding, Platform Games, A* Algorithm, Physical Simulation, Game AI

Referências

Athaillah, I., Kholil, M., Akhsani, R., Ismanto, I., Waspada, H. P., e Muluk, M. S. (2025). Checkjump: An approach to real-time pathfinding for 2d grid-based platformer games. In AIP Conference Proceedings, volume 3250, pages 020008–1–020008–8.

Eberly, D. H. (2003). Game Physics. Morgan Kaufmann, Burlington.

Harabor, D. D. e Grana, A. (2011). Online graph pruning for pathfinding on grid maps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 1114–1119.

Hart, P. E., Nilsson, N. J., e Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107.

Iskandar, U. A. S., Diah, N. M., e Ismail, M. (2020). Identifying artificial intelligence pathfinding algorithms for platformer games. In 2020 IEEE International Conference on Automatic Control and Intelligent Systems (I2CACIS), Shah Alam. IEEE.

Millington, I. e Funge, J. (2016). Artificial Intelligence for Games. CRC Press, Burlington, 3 edition.

Moghadam, S. K., Ebrahimi, M., e Harabor, D. D. (2024). Guards: Benchmarks for weighted grid-based pathfinding. Expert Systems with Applications, 247:123719.

Russell, S. J. e Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Pearson, Upper Saddle River, 4 edition.

Sturtevant, N. R. (2012). Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 4(2):144–148.

Tremblay, J., Borodovski, A., e Verbrugge, C. (2014). I can jump! exploring search algorithms for simulating platformer players. In AIIDE Workshop: Artificial Intelligence in the Game Design Process.