ActionRPG Pathfinding e NPC

ActionRPG: pathfinding e NPC

Il Soldier è il caso di studio per l'AI di ActionRPG. La sua state machine decide quando inseguire; Pathfinding decide quale cella raggiungere; MovableObject e le collisioni determinano il movimento effettivo. Il quadtree non calcola il percorso: accelera alcune query di occupazione usate dalla griglia.

La state machine del Soldier

LevelLoader crea un Soldier dalla regione di categoria Soldier in levels/overworld.json: legge la posizione dal rettangolo e l'area di pattugliamento da patrolRect. Quest'ultimo usa gli stessi campi di rect (x, y, width, height, yUp). Il costruttore prepara sprite direzionali, restringe il collider, imposta velocità massima di patrol a 2 e crea Pathfinding(this, 50, 0.5): area locale di ricerca larga 50 unità, celle di lato 0,5.

Stato	Target e velocità	Transizioni principali
PATROL	Vertici successivi del rettangolo di patrol; limite 2.	Passa a CHASING quando Link è entro la distanza di attivazione; può programmare SLEEP quando è lontano.
CHASING	Prossimo waypoint restituito da Pathfinding; limite 3.5.	Ricalcola un target quando raggiunge quello corrente; torna a PATROL se Link si allontana; passa a SLEEP se non trova il prossimo target.
SLEEP	Velocità massima zero, animazione in pausa.	Si risveglia dopo un ritardo casuale o subito se Link è molto vicino.

Soldier::update() cerca di raggiungere _target prima sull'asse Y e poi su X; quando è abbastanza vicino invoca AI(targetReached). Gli scheduler del core gestiscono le transizioni ritardate, non ci sono thread. Le animazioni usano _facingDir; lo stato CHASING seleziona lo sprite di attacco, ma la classe non implementa un sistema autonomo di danno al player.

L'NPC della casa è un'altra classe: non usa Pathfinding. È un DynamicObject fermo che apre un DialogBox quando Link interagisce. Non confondere quindi il nome generico NPC con la state machine del Soldier.

La griglia di Pathfinding

Nel costruttore, Pathfinding alloca una griglia che copre il rettangolo nominale della scena. Con 256 x 256 unità e celle da 0,5, contiene 512 x 512 celle. Ogni Cell conserva centro, free, synced, visited e distance. La griglia completa definisce gli indici possibili; non viene necessariamente controllata tutta in una volta.

update() centra un quadrato _searchExtent x _searchExtent sull'actor e ne limita gli indici alla griglia. Alla prima chiamata marca le celle locali come libere e sincronizzate, scorre gli oggetti statici della scena, espande i loro AABB secondo la dimensione del collider dell'actor e verifica con scene()->isEmpty(rect) solo le celle candidate vicine agli ostacoli. Nelle chiamate successive controlla le celle locali non ancora synced, così l'area esplorata cresce con il movimento. Il risultato è una mappa di occupazione costruita progressivamente, non una scansione completa della scena a ogni waypoint.

RPGGameScene::isEmpty(rect) usa _quadtree.queryObjects(rect) e considera occupata l'area solo se un StaticObject interseca davvero il rettangolo; intersectsRect() può arrivare fino al test SAT. Gli oggetti dinamici non rendono permanente un ostacolo nella griglia. L'inizializzazione di Pathfinding, però, legge scene()->objects() senza filtro per trovare gli statici: quella prima visita non è una query del quadtree.

Due BFS, due compiti

shortestPathNextTarget(dst) chiama update() e poi compie due ricerche con mosse nelle quattro direzioni cardinali:

1. nearestReachableCell(srcCell, dst) esegue una BFS dalla cella dell'actor. Tra le celle libere e sincronizzate esplorate sceglie quella il cui centro è più vicino al target reale. Se Link è oltre l'area locale esplorata, non pretende che la sua cella sia già raggiungibile: sceglie una tappa possibile.
2. Una seconda BFS parte dalla cella scelta e assegna distanze intere alle celle percorribili. Il metodo esamina i vicini della cella corrente dell'actor e restituisce il centro di quello con distanza minore: è il prossimo waypoint, non l'intero percorso.

Soldier::changeState(CHASING)
  -> Pathfinding::shortestPathNextTarget(Link)
       -> update della griglia; isEmpty() usa il quadtree
       -> BFS: cella raggiungibile vicina a Link
       -> BFS: distanze dalla destinazione scelta
       -> prossimo waypoint per Soldier::move()

Soldier richiede un nuovo waypoint quando raggiunge il precedente. Se il metodo restituisce PointF::invalid(), la state machine passa a SLEEP. Il pathfinding non muove direttamente il personaggio e non modifica il solver delle collisioni.

Confini e limiti

Il quadtree della GameScene copre anche un margine esterno alla mappa, necessario ai portali. La griglia di Pathfinding nasce invece da scene()->rect() (0..256 per asse in questo livello): non va assunta valida per inseguimenti nella casa a coordinate negative. Le celle già sincronizzate non vengono ricalcolate automaticamente quando cambia la geometria statica. Queste sono proprietà dell'implementazione corrente, non vincoli del core.

Per leggere il ruolo dell'indice spaziale in generale, vedi Quadtree; per i collider interrogati da isEmpty(), vedi Movimento e collisioni.

Sorgenti

• Soldier.cpp e Soldier.h
• Pathfinding.cpp e Pathfinding.h
• RPGGameScene.cpp e NPC.cpp

Prosegui con Link e gameplay.