OpenCV e Bejeweled

Ultimamente abbiamo giocato molto a Artusi:Cooking time. Con la scusa di scaricare le ricette dell’Artusi abbiamo giocato per mesi, in bagno e per strada, a questo clone di Bejeweled, ma con dei simpatici twist.
Oltre che essere molto soddisfacente come gameplay, quando si preparano piatti su piatti, il gioco ha, alla fine di ogni quadro, un livello da risolvere con una mossa sola: in una mossa si devono raccogliere più ingredienti possibile, fino al numero fissato. In genere quasi tutti, e in genere devono sparire quasi tutti iquadratini.

Dopo vari tentativi, abbiamo capito che alcuni quadri erano difficilissimi da risolvere di botto, o con prove su prove.. dopo poco infatti sarebbero finite le “foglie d’oro” che sono la moneta del gioco. Allora abbiamo scritto prima un programmino python che, a partire da una matrice inserita a mano e con un semplice algoritmo di forza bruta, prova tutti gli scambi di tessere leciti, esegue le regole di cancellazione delle triplette e altre combo, e arriva fino alla fine e prova tutte le combinazioni fino a trovare quella che lascia meno ingredienti pregiati sul campo di gioco. E questo, in qualche ora, si fa.

Ora però diventava impensabile, ad ogni quadro, dover ocmpilare a mano un file di 8x8 caratteri, con simboli per i vari quadrati ecc ecc.. serviva un riconoscitore automatico a partire dall’immagine: ecco che entra OpenCV.

I primi tentativi sono stati beceri: cercare di capire quale è, tra le tessere “inutili” (le posate) l’ingrediente da raccogliere, e che varia di quadro in quadro

Abbiamo provato vari algoritmi di riconoscimento delle posate, basati su logica, apprendimento, ecc.. alla fine il migliore è stato il pattern matching fornendo dei quadrati di prova, tanto le posate possibili sono 4.
Poi rimaneva da distinguere tra i quadrati “di sfondo” e quello di ingrediente. Anche qui vari tentativi, non sempre felici.. ad esempio cercando colori o forme.. la cosa più semplice è stata operare per differenza: prima riconsocere lo sfondo e poi, di default, tutto il resto che non è posate, e neanche sfondo, è per forza l’ingrediente da raccogliere.

Con un po’ di operazioni abbiamo schiarito l’immagine (si opera praticamente sempre in BN per il riconoscimento di immagini e forme) e poi barato cercando quali sono i quadrati più bianchi.. con un semplice metodo montecarlo che randomizza dei punti di test, e conta quanti sono quelli “bianchi” in un quadrato. Impostando la soglia ad 80 su 100 campioni, si ottengno in genere i quadrati di sfondo.
Il pattern matching qui non andava bene perché gli sfondi sono vari.

Il tutto poi lo abbiamo wrappato in un semplice server web (python) che gira su un nostro sito clandestino, pronto ad essere usato quando, dal bagno, serve risolvere in fretta un livello per guadagnare le agognate tre foglioline d’oro :)