Busca de ruta
Es denomina pathfinding en anglés, al traçat per una aplicació de computadora, del camí més curt entre dos punts. Esta àrea d'investigació està basada majoritàriament en l'Algoritme de Dijkstra per a la busca de la ruta més curta.
En els videojocs
[editar | editar còdic]Busca de camins jeràrquica
[editar | editar còdic]
El concepte de busca de camins jeràrquica precedix a la seua adopció per l'indústria dels videojocs i té les seues raïls en l'investigació clàssica de l'inteligència artificial. Una de les primeres descripcions formals apareix en el treball de Sacerdoti sobre ABSTRIPS (Abstraction-Based Stanford Research Institute Problem Solver|STRIPS) en 1974,[1] que explora estratègies de busca jeràrquica en la planificació basada en llògica. Investigacions posteriors, com la de Hierarchical A* per Holte et al., varen desenrollar encara més la teoria de jerarquia d'abstracció en problemes de busca.
En el context dels videojocs, la necessitat de planificació eficient en mapes grans en temps de CPU llimitat va dur a l'implementació pràctica d'algoritmes de busca de camins jeràrquics. Un alvanç notable va ser l'introducció de Draft:Hierarchical Path-Finding A* (HPA*) per Botea et al. en 2004.[2] HPA* dividix el mapa en clústers i precalcula camins locals òptims entre punts d'entrada de clústers adjacents. En temps d'eixecució, planeja un camí abstracte a través del grafo de clústers i després ho refina dins de cada clúster. Açò reduïx significativament l'espai de busca i permet una planificació casi òptima en un rendiment molt més ràpit.
Partial-Refinement A* (PRA*), desenrollat per Sturtevant i Buro, pren un enfocament similar pero emfatisa la planificació i eixecució entrellaçades. En lloc de refinar tot el camí immediatament, PRA* refina solament els primers passos i continua refinant el restant segons siga necessari durant l'eixecució. Açò és especialment úctil en entorns dinàmics.
Tècniques similars inclouen l'us de navigation mesh és (navmesh), utilisades per a la planificació geomètrica en jocs, i la planificació de transport multimodal, com en variants del problema del viajante que involucren múltiples tipos de transport.
Un planificador jeràrquic realisa la busca de camins en dos fases: primer, entre clústers a un nivell alt; després, dins dels clústers individuals a nivell baix.[3] Esta estructura permet una busca local guiada en menys nodos, lo que dona com resultat un alt rendiment. El principal inconvenient és la complexitat d'implementar i mantindre capes d'abstracció i refinament.
Referències
[editar | editar còdic]- ↑ Sacerdoti, Earl D (1974). “Planning in a hierarchy of abstraction spaces”. Artificial Intelligence 5 (2): 115–135. doi:.
- ↑ Botea, Adi i Muller, Martin i Schaeffer, Jonathan (2004). “Near optimal hierarchical path-finding”. Journal of Game Development 1: 7–28.
- ↑ Pelechano, Nuria i Fonts, Carlos (2016). “Hierarchical path-finding for Navigation Meshes (HNA⁰)”. Computers & Graphics 59: 68–78. doi:.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Búsqueda de ruta» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.