La mappa dei danni

> Programmazione

Con la valutazione dei movimenti e la gestione delle combinazioni di attacco, la mappa dei danni è un grande elemento essenziale in LeekWars. L'obiettivo principale è quello di poter valutare, a seconda dell'avversario, un livello di pericolosità di ogni casella in modo da potersi ritirare in una casella meno pericolosa alla fine del turno. Il modo più semplice è creare un array associativo: dangerMap=[ cell1:danger1 , cell2:danger2 , ... ], possibilmente limitato alle tue celle accessibili. A tale scopo, sono possibili diversi algoritmi

L'algoritmo "ingenuo".

Questa è di solito la prima idea che viene in mente quando si crea un algoritmo di valutazione del pericolo. L'idea è la seguente:

/* -per ognuna delle mie celle accessibili -per ogni avversario -per ogni cella accessibile dell'avversario -per ogni arma dell'avversario -se riesce a sparare al mio cellulare dalla sua cella aggiungi un "punteggio di pericolo" alla mia cella */

La scelta del punteggio è parte integrante del tuo algoritmo: puoi inserire "+1" o calcolare il danno potenzialmente inflitto, ... Ci sono tanti modi per affinare questa valutazione quanti sono i giocatori 😉

Il grosso problema con questo algoritmo è che è estremamente avido nelle operazioni! È quindi generalmente necessario ottimizzarlo molto rapidamente.

Tracce di ottimizzazione

La prima cosa da fare è impedire al tuo porro di "crash"... Quindi devi, da qualche parte nel codice, fare un test su getOperations() ed uscire dai cicli se il numero di operazioni si avvicina troppo a il limite: avrai solo una valutazione parziale del pericolo, ma il tuo porro potrà comunque muoversi un minimo 😉

Per l'ottimizzazione stessa, uno dei primi principi che dovrebbe guidare il vostro approccio è soprattutto quello di evitare di ripetere più volte le stesse operazioni nei loop: meglio in questo caso preparare le cose in tabelle e poi ricordare. Quindi, ad esempio, nel ciclo più interno che calcola il "punteggio di pericolo", se inserisci una chiamata a getStrength(Enemy), richiamerai quella funzione migliaia di volte. L'idea è quindi di calcolare la forza del nemico solo una volta e memorizzarla in una variabile prima di eseguire i cicli interni. Inizierai già a guadagnare qualche centinaio di migliaia di scambi! Quindi vai alla ricerca di elementi di loop "interni" che non dipendano dalla variabile loop, ma solo da un loop "esterno": puoi quindi risalire a questi elementi fino al loro loop.

Se il tuo algoritmo rimane costoso, un'altra strada piuttosto estetica per l'ottimizzazione è il downgrade della risoluzione di questa valutazione. Puoi, ad esempio, non testare tutte le caselle accessibili (tue e/o dell'avversario), ma, ad esempio, solo quelle che richiedono un numero pari di punti movimento. "Basta" poi riempire i gap ottenuti per interpolazione dei valori sui quadrati vicini (media dei vicini, massimo dei vicini, massimo della media tra due rette, ecc.). Questo approccio è meno accurato, ma, con l'esempio anche dei PM, consuma circa 4 volte meno del primo algoritmo.

Per continuare le ottimizzazioni, dovrai pensare al pre-calcolo delle cose, di solito al primo turno, memorizzando in grandi (o molti) array certe cose che devi ricalcolare e che non cambiano mai, o anche aggiornando aggiorna determinati valori ogni turno (nel nostro esempio, la forza dei porri nemici).

L'algoritmo "una volta per tutte".

Questo algoritmo pre-calcola una mappa del pericolo una volta all'inizio del combattimento. Economico, è molto meno preciso ma permette di avere velocemente l'elenco delle zone della mappa di combattimento generalmente pericolose. Consiste nel valutare, all'inizio del turno, per ogni casella della mappa di combattimento, tutte le caselle che permettono di sparargli con le armi che hanno il/i nemico/i: una casella raggiungibile solo da 5 altre caselle avranno poi un punteggio molto più basso di una casella raggiungibile da altre 200 caselle! Potrebbe essere saggio cercare di ritirarsi in aree "a basso pericolo" e indurre il nemico a rimanere in aree ad "alto pericolo".