@techreport{TR-IC-PFG-26-20,
   number = {IC-PFG-26-20},
   author  =  {Jonathan Junio Guidolino Matos Nunes and Emanuel Felipe
                   Duarte},
   title = {{Comparação e Visualização de Algoritmos de Pathfinding em
                   Mapas Dinâmicos em Jogos 2D}},
   month = {July},
   year = {2026},
   institution = {Institute of Computing, University of Campinas},
   note = {In Portuguese, 31 pages.
    \par\selectlanguage{brazil}\textbf{Resumo}
       Algoritmos  de  busca  são  componentes  fundamentais em muitos
       jogos  digitais,  responsáveis  por mover agentes de um ponto a
       outro.  Em  mapas  estáticos,  algoritmos  como  Dijkstra  e A*
       oferecem  garantias  sobre sua otimalidade. Porém, jogos muitas
       vezes  possuem  mapas  dinâmicos,  com  objetos que se movem em
       tempo  real,  o  que  exige  o  replanejamento  do  caminho e a
       implementação  de  algoritmos  alternativos,  como  o HPA\* e o
       \textit{Flow Fields}. Este trabalho implementa e compara quatro
       algoritmos   de  \textit{pathfinding}:  Dijkstra,  A*,  HPA*  e 
       \textit{Flow  Fields},  assim  como sua visualização em um jogo
       simples  2D,  em  diferentes  tipos de simulação. Os resultados
       demonstram  que  não  existe  uma  solução  universal. Em mapas
       estáticos,  o  HPA*  apresentou  um  desempenho  até  18  vezes 
       superior  ao  Dijkstra.  Contudo, a necessidade de reconstrução
       integral da hierarquia em ambientes dinâmicos tornou o HPA* até
       39  vezes  mais lento em tempo de parede. O \textit{Flow Field}
       mostrou-se  o  mais  eficiente  para  dezenas de agentes com um
       destino compartilhado e estável (0,77\,ms por chamada), mas seu
       desempenho   degradou   drasticamente   para   6,1\,ms   com  a 
       movimentação do objetivo. Adicionalmente, confirmou-se que A* e
       Dijkstra  apresentam  desempenhos estatisticamente idênticos em
       mapas   com   alta   heterogeneidade   de  custos  de  terreno, 
       invalidando   a  vantagem  da  heurística  de  Manhattan  neste 
       contexto.
  }
}