Beyond the shortest path: a non-linear altimetric effort model for multi-objective pathfinding in digital games
| dc.contributor.advisor | Ferreira, Mateus Felipe Tymburibá | |
| dc.contributor.advisorLattes | http://lattes.cnpq.br/5863316017246857 | |
| dc.contributor.author | Magalhães, Paulo Renato Souza | |
| dc.contributor.referee | Ferreira, Mateus Felipe Tymburibá | |
| dc.contributor.referee | Cruz, André Rodrigues da | |
| dc.contributor.referee | Wanner, Elizabeth Fialho | |
| dc.date.accessioned | 2026-08-26T00:09:22Z | |
| dc.date.available | 2026-08-26T00:09:22Z | |
| dc.date.issued | 2026-06-11 | |
| dc.description.abstractother | Pathfinding in digital games is usually treated as a single-objective shortest-path problem, but navigation over three-dimensional terrain must balance competing criteria: distance, exposure to danger, and the metabolic effort imposed by slope. Weighted-sum scalarization, the dominant production approach, is efficient but structurally unable to reach Pareto-optimal solutions in non-convex regions of the objective space. This work brings exact multi-objective search (NAMOA* and LazyLTMOA*) together with a novel biomechanically grounded non-linear altimetric cost model, inspired by metabolic measurements, and evaluates the combination over 3,120 scenarios from the Dragon Age: Origins benchmark (Moving AI Lab). Two findings stand out. First, the fraction of Pareto-optimal solutions that no weighted sum query can reach is large and strongly map-dependent: it reaches 99.88% in extreme scenarios, and 107 of 143 maps show a median above 90%, reframing the choice between scalarization and exact search as a map-conditional decision rather than a universal trade-off. Second, the proposed effort model does not merely re scale the linear baseline; it produces geometrically distinct paths, cutting the mean absolute slope along the chosen route by 41.7% in mountainous terrain at a modest distance cost. We further confirm that NAMOA* and LazyLTMOA* return identical frontiers, that the lazy variant is faster in 88.4% of non-trivial scenarios (median 1.08×), and that exact search becomes intractable beyond short path lengths under an interactive time budget. | |
| dc.identifier.uri | https://repositorio.cefetmg.br//handle/123456789/2925 | |
| dc.language.iso | en | |
| dc.publisher | Centro Federal de Educação Tecnológica de Minas Gerais | |
| dc.publisher.country | Brasil | |
| dc.publisher.department | Departamento de Computação | |
| dc.publisher.initials | CEFET-MG | |
| dc.subject | Modelos matemáticos | |
| dc.subject | Programação não-linear | |
| dc.subject | Jogos Digitais | |
| dc.title | Beyond the shortest path: a non-linear altimetric effort model for multi-objective pathfinding in digital games | |
| dc.type | Trabalho de Conclusão de Curso da Graduação |