Age of Empires: 25 anys de problemes de recerca de camins amb C++ [vídeo]

Age of Empires ha lluitat contra un dels reptes en temps real més difícils de la informàtica durant més de dues dècades: aconseguir unitats del punt A al punt B sense semblar del tot ximple. La lluita contínua de la llegendària franquícia RTS amb els algorismes de recerca de camins C++ revela profundes lliçons sobre escalabilitat, deute tècnic i disseny de sistemes que tots els creadors de programari moderns haurien d'interioritzar.

Un vídeo d'immersió profunda que ha aparegut recentment recorre l'evolució de la recerca a Age of Empires, des del llançament original de 1997 fins a Age of Empires IV, exposant com fins i tot equips d'enginyeria de classe mundial lluiten amb la complexitat quan els sistemes han d'escalar. Per a qualsevol persona que creï programari empresarial, gestioni operacions o arquitecte fluxos de treball, els paral·lelismes són sorprenents.

Per què Pathfinding ha estat tan difícil de resoldre a Age of Empires?

La recerca de camins en un joc d'estratègia en temps real no és el mateix que l'encaminament d'una única direcció GPS. Age of Empires ha de calcular les rutes de moviment de centenars, de vegades milers, d'unitats simultàniament, a través d'un terreny que canvia dinàmicament, evitant alhora col·lisions amb edificis, arbres, altres unitats i entre si. Tot això ha de passar en mil·lisegons per mantenir una experiència de joc fluida.

L'Age of Empires original utilitzava un algorisme A* (estrella A) modificat, l'estàndard d'or per a la recerca de camins basada en quadrícula. Però només A* s'enfonsa sota la pressió quan escales des d'un grapat d'unitats a grans exèrcits navegant per mapes complexos. Ensemble Studios, el desenvolupador original, va passar anys arreglant casos de punta: unitats caminant en cercles, enganxades a les parets, formant estranyes línies de conga a través de passadissos estrets o simplement negant-se a moure's.

El problema principal és l'explosió combinatòria. Cada unitat addicional del mapa multiplica el cost computacional. Cada edifici col·locat canvia el gràfic de navegació. Cada fotograma requereix un recàlcul. C++ ofereix als desenvolupadors un control de baix nivell sobre la memòria i el rendiment, però fins i tot aquest avantatge té límits quan l'enfocament algorítmic fonamental no pot seguir el ritme de l'escala.

Quins enfocaments algorítmics han provat els desenvolupadors durant 25 anys?

El vídeo narra una evolució fascinant de les estratègies de recerca de camins a tota la franquícia:

• Cerca A* bàsica (1997): la implementació original va gestionar els grups petits raonablement bé, però es va degradar ràpidament amb les seleccions de la mida de l'exèrcit, produint els infames errors "de poble encallat" que els jugadors recorden fins avui.
• Recerca jeràrquica: les iteracions posteriors van introduir malles de navegació de diversos nivells, dividint els mapes en sectors perquè les unitats poguessin planificar rutes a un alt nivell abans de perfeccionar el moviment localment, reduint dràsticament el càlcul per fotograma.
• Camps de flux: en lloc de calcular camins individuals per a cada unitat, els algorismes de camp de flux calculen un mapa direccional únic que poden seguir totes les unitats d'un grup, convertint un problema O(n) en quelcom més proper a O(1) per unitat.
• Comportaments de direcció i evitació local: aquests sistemes, a la part superior de la cerca global, gestionen l'evitació de col·lisions moment a moment perquè les unitats no s'enganxin entre si ni s'apilen en fitxes individuals.
• Sistemes híbrids a AoE IV: l'última entrega combina diverses tècniques (malles de navegació, camps de flux i direcció local) en una arquitectura en capes que delega diferents escales de moviment a diferents subsistemes.

Cada generació del joc bàsicament va reconstruir el seu sistema de moviment des de zero, i va portar endavant lliçons guanyades amb esforç sobre què es trenca a escala.

Què poden aprendre els equips de programari empresarial de Game Engine Pathfinding?

La saga de recerca d'Age of Empires és una classe magistral sobre un problema al qual s'enfronten totes les empreses en creixement: el que funciona a petita escala es trenca a gran escala. Un procés manual que gestiona 10 clients per setmana s'enfonsa a 500. Un full de càlcul que fa el seguiment d'un projecte es fa inmanejable en 50. Un flux de treball d'aprovació dissenyat per a un equip de 5 persones crea colls d'ampolla a 50 persones.