Divisione di un percorso * di molte unità in frame di gioco separati

Question

Quindi il mio problema è che, per grandi gruppi di unità, tentare di trovare path per tutti nello stesso frame sta causando un rallentamento piuttosto evidente. Quando si percorrono 1 o 2 unità, il rallentamento non è generalmente evidente ma per molti altri, a seconda della complessità del percorso, può essere molto lento.

Mentre il mio A * potrebbe probabilmente permettersi un po 'di messa a punto, so anche che un altro modo per accelerare il percorso è quello di dividere il path path su più frame di gioco. Qual è un buon metodo per realizzare questo?

Mi scuso se questa è una domanda ovvia o facilmente ricercabile, non potevo davvero pensare a come metterlo in una stringa di parole ricercabile.

Altre informazioni: Questo è A * su una griglia rettilinea e programmato utilizzando C# e il framework XNA. Ho intenzione di avere potenzialmente fino a 50-75 unità che necessitano di pathing.

Grazie.

Answer 1

scalabilità

Ci sono diversi modi per ottimizzare per questa situazione. Per uno, potresti non dover dividere in più frame di gioco. In una certa misura, sembra che la scalabilità sia il problema. 100 unità è almeno 100 volte più costose di 1 unità.

Quindi, come possiamo rendere il percorso più ottimizzato per la scalabilità? Beh, questo dipende dal tuo design di gioco. Vado (forse erroneamente) ad assumere un tipico scenario RTS. Diversi gruppi di unità, in cui ciascun gruppo è relativamente vicino in prossimità. La soluzione di pathing per molte unità nelle immediate vicinanze sarà piuttosto simile. Le unità potrebbero richiedere il pathing da qualche tipo di risolutore di percorsi. Questo risolutore di percorsi potrebbe mantenere una tabella delle richieste di percorsi recenti e delle relative soluzioni ed evitare di calcolare lo stesso output dallo stesso input più volte. Questo è chiamato memoization.

Un'altra aggiunta a questo potrebbe comportare la creazione di una gerarchia dalla griglia o dal grafico. Risolvi prima il grafico più semplice, quindi passa a un grafico più dettagliato. Le unità multiple possono utilizzare lo stesso percorso a bassa risoluzione, sfruttando la memoizzazione, ma ognuna calcola il proprio percorso ad alta risoluzione individualmente se i percorsi ad alta risoluzione sono troppo numerosi per essere ragionevolmente memo- rizzati.

Calcoli Multi-Frame

Per quanto riguarda il tentativo di dividere i calcoli tra i fotogrammi, ci sono alcuni approcci che posso pensare fuori mano.

Se si desidera utilizzare il percorso multi-thread, è possibile utilizzare un modello di pool di thread di lavoro. Ogni volta che un'unità richiede un percorso, viene accodata per una soluzione. Quando un thread di lavoro è gratuito, viene assegnato un compito da risolvere. Quando il thread risolve l'attività, è possibile avere una richiamata per informare l'unità o si potrebbe richiedere l'interrogazione dell'unità se l'attività è stata completata in qualche modo, molto probabilmente si è interrogato su ogni frame.

Se non ci sono ostacoli dinamici o vengono gestiti separatamente, è possibile avere uno stato costante utilizzato dal risolutore di percorsi. In caso contrario, ci sarà una quantità non trascurabile di complessità e forse persino di aver sentito che questi thread bloccano le informazioni mutabili dello stato di gioco. I percorsi potrebbero essere resi non validi da un fotogramma all'altro e richiedono una nuova convalida per ciascun fotogramma. Il multithreading può essere un extra-overhead inutile in cui, a causa del blocco e della sincronizzazione, i thread raramente funzionano in parallelo. È solo una possibilità.

In alternativa, è possibile progettare gli algoritmi di individuazione dei percorsi da eseguire in passaggi discreti. Dopo n numero di passaggi, controllare la quantità di tempo trascorso dall'inizio dell'algoritmo. Se supera una certa quantità di tempo, l'algoritmo di pathing salva i suoi progressi e ritorna. Il codice chiamante potrebbe quindi verificare se l'algoritmo è completato o meno. Nel frame successivo, riprendi l'algoritmo di pathing da dove era. Ripeti fino a soluzione.

Anche con l'approccio volontario a thread singolo, per risolvere i percorsi, se le modifiche nello stato del gioco influenzano la validità di un percorso da un frame all'altro, ci si ritroverà a dover convalidare nuovamente le soluzioni correnti su un frame per inquadrare

utilizzare le soluzioni parziali

Con uno dei due approcci di cui sopra, si potrebbe incorrere in l'emissione di quote comandato di andare da qualche parte al minimo per più fotogrammi prima di avere una soluzione completa pathing. Questo può essere accettabile e praticamente non rilevabile in circostanze tipiche. Se non lo è, puoi provare a utilizzare la soluzione incompleta così com'è. Se ciascuna soluzione incompleta differisce troppo, tuttavia le unità si comporteranno in modo piuttosto indeciso. In pratica, questa "indecisione" potrebbe anche non accadere abbastanza spesso da causare preoccupazione.

Answer 2

Se le tue unità sono tutte in viaggio verso la stessa destinazione, questa risposta potrebbe essere applicabile, altrimenti sarà solo uno spunto di riflessione.

Uso un algoritmo di distanza di ampiezza in unità di percorso. Inizia a destinazione e segna la distanza da esso come 0. Qualsiasi cella adiacente è 1, le celle adiacenti a quelle sono 2, ecc. Non attraversare ostacoli e percorrere l'intera scacchiera. Solitamente la complessità temporale O (A) in cui A è l'area delle schede.

Quindi, ogni volta che si desidera determinare la direzione in cui un'unità deve andare, è sufficiente trovare il quadrato con la distanza minima dalla destinazione. O (1) complessità temporale.

Userò questo algoritmo di pathing per i giochi di tower defense abbastanza spesso perché la sua complessità temporale dipende interamente dalla dimensione della scheda (solitamente piuttosto piccola nei giochi TD) piuttosto che dal numero di unità (di solito abbastanza grandi). Permette al giocatore di definire il proprio percorso (una bella caratteristica), e ho solo bisogno di eseguirlo una volta al round a causa della natura del gioco.