Come funziona il path-finding nei videogiochi RTS?

Question

In un gioco come Warcraft 3 o Age of Empires, i modi in cui un avversario di IA può muoversi sulla mappa sembrano quasi illimitati. Le mappe sono enormi e la posizione degli altri giocatori cambia continuamente.

Come funziona la ricerca del percorso dell'IA in giochi come questi? I metodi di ricerca grafici standard (come DFS, BFS o A *) sembrano impossibili in una tale configurazione.

Answer 1

Questo è un po 'un semplice esempio, ma dimostra che si può fare l'illusione di AI/Indepth Pathfinding da un insieme non-complesso di regole: Pac-Man Pathfinding

In sostanza, è possibile che l'IA a conoscere le informazioni locali (vicine) e prendere decisioni basate su tali conoscenze.

Answer 2

A* è un algoritmo di tracciamento comune. Questo è un argomento di sviluppo del gioco popolare: dovresti riuscire a trovare numerosi libri e siti Web che contengono informazioni.

Answer 3

Prendi quanto segue con un granello di sale, poiché non ho esperienza in prima persona con il pathfinding.

Detto questo, è probabile che esistano approcci diversi, ma penso che i metodi standard di ricerca del grafico, in particolare (varianti di) A * siano perfettamente ragionevoli per i giochi di strategia. La maggior parte dei giochi di strategia che conosco sembrano basati su un sistema di tessere, in cui la mappa è composta da piccoli quadrati, che sono facilmente mappati su un grafico. Un esempio potrebbe essere StarCraft II (Screenshot), che continuerò a utilizzare come esempio nel resto di questa risposta, perché mi è più familiare.

Mentre A * può essere usato per giochi di strategia in tempo reale, ci sono alcuni svantaggi che devono essere superati modifiche al algoritmo di base:

1. A * è troppo lento

   Dato che un RTS è definito come "tempo reale", attendere che il calcolo finisca frustrerà il giocatore, perché le unità saranno in ritardo. Questo può essere risolto in diversi modi. Uno è quello di utilizzare Multi-tiered A*, che calcola una rotta grezza prima di prendere in considerazione piccoli ostacoli. Un'altra ovvia ottimizzazione è raggruppare unità che si dirigono verso la stessa destinazione in un plotone e calcolare solo un percorso per tutte loro.

   Invece dell'approccio ingenuo di rendere ogni singola tessera un nodo nel grafico, si potrebbe anche costruire un navigation mesh, che ha meno nodi e potrebbe essere cercato più velocemente - questo richiede un po 'di regolazione dell'algoritmo di ricerca, ma sarebbe comunque essere A * al centro.

2. A * è statica

   A * funziona su un grafico statico, quindi cosa fare quando il paesaggio cambia? Non so come sia fatto nei giochi reali, ma immagino che il percorso sia ripetuto per affrontare nuovi ostacoli o rimuovere ostacoli. Forse stanno usando un incremental version of A* (PDF).

   Per visualizzare una dimostrazione di coping di StarCraft II, andare a 7:50 in this video.

3. A * ha informazioni perfetta

   Una parte di molti giochi RTS è terreno inesplorato. Dato che non puoi vedere il terreno, le tue unità non dovrebbero sapere neanche dove andare, ma spesso lo fanno comunque.Un approccio è quello di penalizzare la camminata attraverso un terreno inesplorato, quindi le unità sono più riluttanti a trarre vantaggio dalla loro onniscienza, un'altra è quella di allontanare l'onniscienza e semplicemente assumere un terreno inesplorato percorribile. Ciò può far sì che le unità incespicano in vicoli ciechi, a volte quelli che sono ovvi per il giocatore, fino a quando non esplorano finalmente un percorso verso il bersaglio.

   Nebbia di guerra è un altro aspetto di questo. Ad esempio, in StarCraft 2 ci sono ostacoli distruttibili sulla mappa. È stato dimostrato che puoi ordinare a un'unità di spostarsi nella base nemica e inizierà un altro percorso se l'ostacolo è già stato distrutto dal tuo avversario, dandoti così le informazioni che in realtà non dovresti avere.

Per riassumere: è possibile utilizzare algoritmi standard, ma potrebbe essere necessario utilizzarli in modo intelligente. E come ultimo bonus: ho trovato Amit’s Game Programming Information interessante per quanto riguarda il pathing. Ha anche collegamenti a ulteriori discussioni sul problema.

Answer 4

Controllare i grafici di visibilità. Credo che sia quello che usano per trovare il percorso.