Basic Ai pathfinding customization in Unreal

Ai per uno zombie in Unreal Engine 4, un approccio migliore di “AiGoTo” in Blueprint

Quando si tratta di preparare strumenti per giovani sviluppatori senza esperienza, Unreal Engine 4 eccelle, è possibile infatti anche senza nessuna conoscenza di pathfinding, posizionando un semplice NavMeshBound e chiamando la funzione predefinita AiGoTo, far muovere un Ai in modo dinamico, fargli automaticamente evitare gli ostacoli, e con pochi blocchi in più, addirittura inseguire il PlayerCharacter.

Però chi ha già testato questo sistema, sa che non è il massimo. Non solo il movimento delle Ai è meccanico, irrealistico, ma inoltre se utilizzato per creare un orda di nemici, essi non faranno altro che inseguire il Player in fila indiana, diventando estremamente prevedibili, facili da evitare, e particolarmente sgraziati.

Senza andare a codificare un complesso algoritmo di pathfinding, in grado di risolvere labirinti o trovare la strada migliore per raggiungere il target, si può comunque ottenere un risultato più efficace per questo caso specifico, utilizzando delle linee tracciate dal centro dell’agente verso diverse direzioni (LineTraceByChannel), controllando la distanza tra un Ai e eventuali ostacoli, ed effettuare scelte di conseguenza.

In questo modo se diversi agenti stanno inseguendo il Player, essi non solo cercheranno di evitare gli ostacoli, ma tratteranno gli altri agenti stessi come tali, cercando di distanziarsene, formando così un’orda ampia e minacciosa.

Abbiamo riportato qua sotto la nostra soluzione, ma ci sono diversi approcci per ottenere questo effetto.

Gli ingredienti per un Ai personalizzabile

Quello che ci serve per sviluppare e testare questo algoritmo è:

  • Un livello con un piano e degli ostacoli posti su di esso
  • Un player character che spawna all’inizio della partita
  • Il Pawn del livello impostato a DefaultPawn (indicazioni più precise a seguire)
  • Un nuovo Actor vuoto di classe Character

Ecco come impostare il Pawn a DefaultPawn:

Questo ci servirà per osservare il comportamento degli agenti dall’alto, e avere una migliore visuale di cosa sta accadendo.

Bene, ora rechiamoci nel Blueprint del nostro “zombie”, che d’ora in poi chiameremo Z, e prepariamoci all’azione.

L’agente Z

Dopo aver opportunamente creato un nuovo Actor di classe Character, aggiungiamo una serie di componenti che ci serviranno più avanti.

Queste frecce saranno il punto di partenza e la direzione da cui tracciare le linee che utilizzeremo per prevedere le collisioni con eventuali ostacoli.

Da notare che le frecce sono impostate come figli di “Scene”, un componente senza effetti sul mondo di gioco ma dallo scopo di raggruppare le varie Arrow per rotazione, traslazione e scala.

Event BeginPlay

Prima di tutto, dobbiamo preoccuparci di muovere Z in una direzione neutra, ovvero diritto contro il bersaglio, quando non si hanno ancora informazioni, o la direzione ottimale non è stata ancora calcolata.

Inoltre salviamo il primo attore che compare nella lista degli attori con tag “Target”. Questo può essere cambiato più tardi inserendo una qualche logica per scegliere il bersaglio preferito dalla lista.

Infine impostiamo che la funzione di calcolo della direzione “CalcoloDirezione” che creeremo successivamente si aggiorni ogni 0,1 secondi (è possibile inserire un delay migliore ma lo script diventa più pesante, più Ai si hanno maggiore deve essere il delay).

Event Tick

Ogni frame, dovremo aggiornare la direzione di movimento di Z con quella ottenuta dalla funzione

Come debug possiamo usare un LineTraceByChannel con visibility “Per duration” che abilitiamo solo quando vogliamo vedere dove effettivamente sta andando Z. Quando non dobbiamo verificare questo dato, la visibility deve essere settata a “None”. Questo anche perché siccome possiamo impostare che Z scivoli sul terreno invece che curvare in modo rigido, così diventa più chiaro capire dove sta puntando. Inoltre se ci fossero diversi agenti Z che si incastrano tra di loro, questa traccia ci indica come mai non si sbloccano.

La funzione “Calcolo Direzione”

Partiamo dal calcolare nuovamente la direzione centrale, dopodiché controlliamo se Z è fermo

Se Z è fermo resettiamo la variabile WrongDirection, e resettiamo Direction. Questo vedremo fra poco che ci servirà per capire se Z è bloccato.

In ogni caso ruotiamo “Scene” (il componente a cui sono attaccate tutte le frecce che abbiamo aggiunto precedentemente), nella direzione di Target, in modo da effettuare i controlli a partire dalla direzione in cui desideriamo mandare Z.

Come ultimo passaggio in questa schermata, creiamo un array di tutte le frecce che useremo per verificare le collisioni nell’immediato futuro.

Per ogni freccia verifichiamo la collisione, e salviamo il risultato nella mappa “MovementDirection”.

Ok, ora dobbiamo solo scegliere la direzione migliore

Questo ultimo passaggio è un po’ complicato, ma in sostanza ci occupiamo di scegliere la direzione in cui andare prediligendo:

  • il centro, se non ci sono ostacoli
  • la direzione dove l’ostacolo non è presente più vicina al centro di Z
  • la direzione dove l’ostacolo è posto a distanza maggiore in caso ci siano ostacoli in tutte le direzioni
  • se abbiamo già una direzione salvata in memoria, e non siamo incastrati, e il centro ancora non è libero, continuiamo in quella direzione

Un piccolo video dimostrativo:

Come vedete non solo le Ai non si mettono in fila indiana per inseguire il Player, ma sono anche in grado di seguirlo mentre salta o è in volo, un’altra funzione che AiGoTo non supporta!

Da notare che per un risultato ancora migliore bisognerebbe evitare nel controllo degli ostacoli le Ai stesse quando la distanza dal Player è più alta di un certo limite (o non risultano visibili), per farli incastrare meno, arrivare più velocemente e salvare tempo di computazione.

Leonardo Bonadimani – Whatar – Filosoft

www.twitch.tv/whatartv

Preparare un immagine per il riconoscimento e categorizzazione tramite Ai

Quanto sarebbe divertente collegare una videocamera ad un arduino, e registrare una partita a poker, a dama, a scacchi…

Si potrebbe creare un arbitro computerizzato, sfruttando anche il Text-To-Speech per segnalare verbalmente i bari, creare un ai che calcola la mossa migliore e ti segnala quando la hai scelta, o fa un suono triste quando sbagli grossolanamente.

Per fare tutto questo, oltre naturalmente a creare un programma magari python (il nostro linguaggio di prima scelta) per collegarsi alla webcam e raccogliere il feed video, c’è bisogno di fare data pre-processing.

Data pre-processing

Purtroppo perché un ai sia in grado di riconoscere il campo da gioco, le carte e tutto il resto, non è sufficiente analizzare il feed video puro, bisogna togliere tutto ciò che rappresenta dati inutili, o che potrebbero facilmente confondere il nostro algoritmo.

 “Garbage in, garbage out”

Con dati sporchi, ricchi di errori, si ottengono risultati sporchi e ricchi di errori

Ecco che entra in azione il data pre-processing, ovvero una procedura di filtraggio intenta proprio ad ottenere questi risultati.

Image filtering con python

Prendiamo come esempio un immagine ottenuta da un ipotetica telecamera posta sopra ad una scacchiera e i pezzi per la dama.

(Scacchiera venduta dal negozio spagnolo www.brindesvisao.com.br, link non sponsorizzato)

Supponiamo di dover far riconoscere all’ai le caselle e le dame di entrambi i giocatori, per farlo bisogna usare l’image recognition IR, però se guardate attentamente, ci sono tre diversi problemi che potrebbero confondere un ipotetico algoritmo:

le ombre che l’illuminazione traccia sul campo confondono in parte le caselle

le pedine sia bianche ma soprattutto rosse non sono esattamente dello stesso colore e sulla superfice presentano granulosità

la videocamera non visualizza le pedine tutte dalla stessa angolazione

Due dei problemi che potremmo avere sono risolvibili filtrando l’immagine, però le ombre purtroppo essendo scure e essendo spesso tracciate su caselle nere, rimarranno un problema, anche se in misura minore, che potremo però aggirare in un altro modo.

L’obbiettivo

Dobbiamo fondamentalmente rendere le superfici della dame perfettamente regolari, in questo modo potremmo riconoscerle semplicemente dando in pasto all’algoritmo di IR due cerchi, uno rosso e uno bianco, ed esso escluderà automaticamente le parti inclinate che ci davano fastidio.

Il codice

Partiamo dalle dipendenze di questo progetto:

from PIL import Image
import numpy as np
import time

Sia numpy e pil si possono installare lanciando pip3 install PIL e pip3 install numpy da terminale.

Per quanto riguarda time, non solo si tratta di una libreria già presente nell’installazione base di python3, ma è anche facoltativa, in quanto la useremo solamente per calcolare l’efficienza del nostro algoritmo.

Passiamo all’apertura della nostra foto:

image = Image.open("photo.jpg")
img_data = np.array(image)
h, w, t = img_data.shape

Ora la nostra immagine è salvata dentro image, i suoi dati in formato di array di numpy sono salvati dentro img_data, la altezza è h, la larghezza è w e il numero di componenti del singolo punto (3 con immagini RGB, 4 con immagini RGBA), sono salvati in t.

Possiamo fare un po’ di debug aggiungendo un print:

print(h, w, t)

Che ci restituirà in output:

>> 913 866, 3

Ottimo, quindi la nostra immagine è alta 913, larga 866 e non ha la trasparenza (si poteva già prevedere, considerando che si tratta di un jpg).

Ora prepariamo un nuovo array di numpy vuoto, pronto a raccogliere i pixel dell’immagine rielaborata.

new_img_data = np.zeros((h, w, t), dtype=np.uint8)

Quindi creiamo un iterazione in cui eseguiamo un ciclo per ogni pixel all’interno dell’immagine. Raccogliamo intanto la lista dei tre valori (R, G, B) che formano il pixel.

for x in range(w):
    for y in range(h):
        r_pixel = img_data[y][x][0]
        g_pixel = img_data[y][x][1]
        b_pixel = img_data[y][x][2]

Ora supponendo che non sia possibile posizionare perfettamente la videocamera, potrebbe essere necessario effettuare uno zoom sul soggetto, imponiamo dunque una regola che ci permetta di analizzare solo le zone interessanti.

if x in range(0, w) and y in range(0, h):

Per ora abbiamo inserito w e h come estremità del range per includere tutta l’immagine, se serve per esempio tagliare i bordi a sinistra e a destra di 200px basterebbe sostituire il primo range con range(200, w-200).

Siamo arrivati al filtro vero e proprio. Per la nostra immagine abbiamo trovato che per regolarizzare abbastanza i colori si può eseguire un’operazione di questo genere,

r = (255, 0)[r_pixel < 100]
g = (255, 0)[g_pixel < 100]
b = (255, 0)[b_pixel < 100]
new_img_data[y][x] = [r, g, b]

In sostanza salviamo 255 ovvero intensità massima per ogni colore, solo se il colore stesso parte da un intensità non troppo elevata.

Il programma completo, con l’aggiunta del caso in cui siamo fuori dal range interessante e la produzione effettiva dell’immagine risulta così.

from PIL import Image
import numpy as np
import time

image = Image.open("photo.jpg")
img_data = np.array(image)
h, w, t = img_data.shape

print(h, w, t)

new_img_data = np.zeros((h, w, t), dtype=np.uint8)

for x in range(w):
    for y in range(h):
        r_pixel = img_data[y][x][0]
        g_pixel = img_data[y][x][1]
        b_pixel = img_data[y][x][2]
        if x in range(0, w) and y in range(0, h):
            r = (255, 0)[r_pixel < 100]
            g = (255, 0)[g_pixel < 100]
            b = (255, 0)[b_pixel < 100]
            new_img_data[y][x] = [r, g, b]
        else:   #siamo fuori dal range
            new_img_data[y][x] = [255, 255, 255] # pixel bianco

print("Process time: " + str(time.process_time()) + "s")

new_img = Image.fromarray(new_img_data, 'RGB')
new_img.show()                # visualizza l'immagine a video
new_img.save("new_photo.jpg") #salva la nuova immagine

Che produce questo risultato:

Perfetto, adesso come preventivato con dei semplici cerchi rossi e bianchi possiamo riconoscere tutte le pedine.

E la scacchiera? La scacchiera in realtà non serve, una volta riconosciuta la pedina nella relativa posizione, basta controllare in che range di pixel rientra, per capire in che casella risiede.

Ancora non soddisfatti? Si può ottenere un immagine con ancora meno disturbo effettivamente, togliere completamente ombre e scacchiera, e tenere solo le pedine, quello che davvero ci interessa.

Per farlo è sufficiente modificare il filtro:

r = (255, 0)[r_pixel > 207]
g = (255, 0)[g_pixel > 207]
b = (255, 0)[b_pixel > 207]

Per ottenere il seguente risultato.

Ora è impossibile che l’algoritmo si confonda. Direste mai che questa foto è stata scattata ad una scacchiera di dama?

Avete notato un trend? Meno l’immagine è riconoscibile dall’umano, più è riconoscibile dalla macchina. Questo perché noi siamo in grado di dare molteplici significati con relativamente alta precisione, mentre una macchina non è in grado (ancora) di analizzare più di un dettaglio su un immagine senza applicare nessun filtro. Se si vogliono analizzare le ombre bisogna togliere tutto il resto, se si vuole capire quanti tasselli ha un puzzle bisogna togliere i colori, e così via. Dopo molti filtri e diverse analisi si ottiene il risultato che un umano in genere ricava con un solo sguardo.

Leonardo Bonadimani – Whatar – Filosoft

www.twitch.tv/whatartv

La migliore piattaforma di allenamento per le Ai euristiche: Codingame.com, osserviamo la Spring Challenge 2021

In questo articolo andremo a osservare e commentare la challenge proposta su https://www.codingame.com/multiplayer/bot-programming/spring-challenge-2021 e alcune interessanti strategie per risolverla.

Codingame è un sito estremamente affascinante, che raccoglie sfide di ogni genere che non solo possono risultare piuttosto dilettevoli, ma allenano la capacità di creare algoritmi e di codificare gli stessi in diversi linguaggi.

Da code golf all’ottimizzazione, su codingame.com ci si può cimentare nella risoluzione di problemi di diverso tipo, ma quelli che più ci interessano riguardano la scrittura di Ai.

Il sito presenta due volte all’anno una challenge di 10-11 giorni in cui i bot (programmi Ai) di due programmatori dovranno scontrarsi per scalare la classifica.

La challenge di quest’anno fa impersonare dai nostri codici uno spirito della foresta ispirato dall’iconico Totoro di Hayao Miyazaki, il suddetto spirito, istruito dai nostri comandi, dovrà gestire il ciclo naturale della semina, crescita e passaggio a miglior vita degli alberi della sua radura. In questo articolo andremo a parlare degli algoritmi a livello logico che permettono di superare le leghe “legno II”, “legno I” e “bronzo”, ma sarete voi a dovervi ingegnare per codificare queste strategie, poi per argento e oro vi serviranno idee tutte vostre.

Tutti gli esempi di codice, e le citazioni alle variabili riportate in questo articolo saranno in python3.

Le regole…

Qui riportiamo le regole che riteniamo più importanti per la risoluzione (quantomeno logica) del problema. C’è da sottolineare che man mano che il nostro algoritmo avanzerà di lega battendo i vari boss, il gioco si andrà a complicare sempre più, aggiungendo nuove regole.

Innanzitutto conviene scegliere uno Starter Kit scritto nel linguaggio di programmazione che si vuole adoperare, poi possiamo metterci all’opera.

…della lega legno II

  • Si possono completare alberi di grandezza = 3
  • Si possono fare infinite mosse all’interno di un giorno di gioco
  • Completare un albero costa 4 soli
  • Ogni albero ci da x punti sole ad inizio turno, dove x è la grandezza dell’albero stesso
  • Tutte le mosse legali sono elencate negli input
  • La partita dura un giorno
  • Si guadagna 1 punto per ogni 3 punti sole risparmiato a fine partita
  • Si guadagnano più punti al completamento di un albero se l’albero è piantata in una cella con cell.richness maggiore

La prima lega di una challenge su codingame.com in genere è molto semplice, qui vediamo che gli unici comandi che abbiamo a disposizione sono il completamento con

print("COMPLETE #indicecella")

Dove #indicecella sta per il numero della cella dove risiede l’albero da completare, e

print("WAIT")

Per concludere il proprio turno, quando entrambe le Ai avranno completato il proprio turno, il giorno diventerà il successivo, se game.day sarà uguale all’ultimo giorno della partita, la partita si concluderà.

Ad inizio partita, tutti gli alberi in questa lega saranno di dimensione tre, ovvero saranno completabili.

A questo punto dobbiamo porci la domanda, come facciamo a battere Totoboss?

L’algoritmo per uscire da legno è semplice, dobbiamo semplicemente completare gli alberi in ordine da quelli nella zona con cell.richness maggiore, a quelli nella zona con cell.richness minore.

Ps. in realtà anche eseguendo l’ultima azione disponibile in game.possible_actions, senza sapere ne leggere ne scrivere, siamo riusciti a raggiungere legno I senza sforzi, ma scegliere di completare l’albero migliore ci aiuterà in futuro.

…della lega legno I

  • Ci sono 6 giorni di gioco
  • Si possono far crescere gli alberi
  • Il sole ruota attorno alla radura (un giorno, uno spostamento)

Riportiamo le regole di crescita:

Grow action

  • Growing a size 1 tree into a size 2 tree costs 3 sun points + the number of size 2 trees you already own.
  • Growing a size 2 tree into a size 3 tree costs 7 sun points + the number of size 3 trees you already own.

Non preoccupiamoci del comportamento del sole per ora

Chiaramente anche qui come prima dobbiamo prediligere la crescita degli alberi su un terreno con cell.richness migliore, e poi completarne il più possibile.

…della lega Bronzo

  • Si possono piantare semi
  • il costo di piantare un seme equivale al numero di propri semi già presenti in campo
  • Gli alberi fanno ombra sulle zone circostanti in base alla propria grandezza.
  • Non otteniamo punti sole dagli alberi sotto l’influsso di un’ombra creata da un albero di grandezza uguale o maggiore
  • La partita consiste in 24 giornate
  • Si ottiene un bonus per ogni pianta completata che diminuisce mano a mano che più piante vengono completate

Il motivo per il quale il sole gira attorno alla radura vi sarà ormai chiaro. Qui il gioco si fa dura, per arrivare ad argento bisognerà fare in modo che:

  • I semi che si andranno a piantare copriranno uno spazio ampio, in modo che si eviti il rischio di fare ombra ai propri stessi alberi
  • Il costo delle varie azioni deve essere ottimizzato, per riuscire a piantare e completare il numero massimo di piante
  • Si completino la piante prima del proprio avversario, per sfruttare a meglio il bonus

Osservando la griglia di debug del campo di gioco, possiamo formulare matematicamente alcune condizioni per svolgere le varie azioni, in modo da adempire ai vari requisiti precedentemente discussi.

Per cominciare, un ottima strategia per evitare di ostacolarsi da soli tramite le ombre, è obbligare l’algoritmo a non piantare in celle che rispondono alla condizione action.target_cell_index in cell.neighbors dove la cella in esame è cell = action.origin_cell_index.

Un altra condizione interessante da implementare è quella che un seme non dovrebbe essere piantato in linea retta (per esempio 25, 11, 3) rispetto ad un altro albero di nostra proprietà, perché nei round futuri esso sarebbe posto all’ombra.

Inoltre siccome piantare un seme non costa punti sole solo se non ci sono altri nostri semi in gioco, conviene piantarne uno solo in questo particolare caso.

Infine riguardo alla tempistica, abbiamo scoperto che iniziare a completare alberi dal round 12 sembra proficuo, mentre fino all’ultimo round è conveniente avere sul terreno sempre almeno 3 alberi, per non rischiare di avere troppi pochi i punti sole generati ad inizio turno. Non eccedere invece mai invece il limite di 6/8 alberi piantati, oltre quel numero le ombre sul campo iniziano a diventare troppe e si rende impossibile tenerne traccia.

Se volete battere il sottoscritto dovete raggiungere le prime 150 posizioni della lega oro.

Buona fortuna per challenge.

Leonardo Bonadimani – Whatar – Filosoft

www.twitch.tv/whatartv