Trovare pattern nei giochi di puzzle

Question

Mi stavo chiedendo, quali sono gli algoritmi più comunemente usati per trovare schemi nei giochi di puzzle conformati da griglie di celle.

So che dipende da molti fattori, come il tipo di pattern che si desidera rilevare, o le regole del gioco ... ma volevo sapere quali sono gli algoritmi più comunemente usati in quel tipo di problemi ..

Ad esempio giochi come colonne, gioielli ingioiellati, persino tetris.

Voglio anche sapere se rilevare i pattern con "forza bruta" (come, scansionare tutta la griglia cercando di trovare tre celle adyacent dello stesso colore) è significativamente peggiore che usi particolari algoritmi in griglie molto piccole, come 4 X 4 per esempio (e ancora, so che dipende dal tipo di gioco e dalle regole ...)

Quali strutture sono comunemente utilizzate in questo tipo di giochi?

Answer 1

È sempre dipendente dal dominio. Ma ci sono anche due situazioni in cui faresti questo tipo di ricerche. Quella situazione è dopo una mossa (una modifica al campo di gioco fatta dal giocatore), e l'altra sarebbe se/quando l'intera scacchiera è cambiata.

In Tetris, non è necessario eseguire la scansione dell'intera scheda dopo che un pezzo è caduto. Dovresti solo cercare le righe che il pezzo sta toccando.

In giochi match-3 come Bejeweled, in cui si scambiano due pezzi adiacenti alla volta, per prima cosa si esegue una ricerca localizzata in ciascuna direzione attorno a ciascun riquadro che è cambiato, per vedere se alcuni pezzi si sono attivati. Quindi, se lo fanno, il gioco scaricherà alcuni nuovi pezzi casuali sul tabellone. Ora, è possibile eseguire la stessa ricerca localizzata su ogni quadrato che è cambiato, ma ciò potrebbe comportare un gran numero di dichiarazioni if e potrebbe essere effettivamente più lento semplicemente scansionare l'intera scheda da in alto a sinistra in basso a destra. Dipende dalla tua implementazione e richiederebbe la profilazione.

Come dice Adrian, è sufficiente un semplice array 2D. Spesso, tuttavia, è possibile aggiungere un "bordo" di pixel attorno a questo array, per semplificare l'aspetto della ricerca per i motivi. Senza un bordo, dovresti avere le affermazioni if lungo i quadrati che dicono "beh, se sei nella riga superiore, non cercare (e uscire dalla matrice)".Con un bordo intorno a esso, puoi tranquillamente cercare tra le cose: salvando te stesso le dichiarazioni if, risparmiandoti ramificazioni, risparmiando problemi di pipeline, cercando più velocemente.

Per Jon: questo genere di cose conta davvero nelle impostazioni ad alte prestazioni, anche su macchine moderne, se si sta eseguendo un algoritmo di ricerca per giocare/risolvere il gioco. Se lo sei, vuoi che la tua simulazione di fondo funzioni il più rapidamente possibile per cercare il più profondo possibile nel minor numero di cicli.

Answer 2

Per quanto riguarda gli algoritmi: Dipende certamente dal gioco. Ad esempio per tetris, dovresti solo scansionare ogni riga se ha lo stesso colore. Non riesco nemmeno a pensare a qualcosa che non sarebbe uguale all'approccio della forza bruta in questo caso. Ma per la maggior parte dei giochi casuali la forza bruta dovrebbe essere perfetta. Il riconoscimento dei pattern dovrebbe essere trascurabile rispetto alla grafica e all'elaborazione del suono.

Per quanto riguarda le strutture: un semplice array 2D dovrebbe essere sufficiente per rappresentare la scheda.

Answer 3

Data la velocità media del computer in questi giorni, se è in tempo reale mentre l'utente sta giocando, probabilmente non avrà importanza (MODIFICA: solo per schede di gioco molto piccole). Certamente, dipenderebbe dalla complessità della logica di gioco, ma anche dalla velocità con cui il codice verrà eseguito sulla macchina di destinazione (ad esempio, si tratta di un gioco di pagine Web JavaScript o di un'app di Windows scritto in C++).

Se questo è per qualcosa come simulare strategie di gioco, quindi utilizzare un algoritmo che è più efficiente.

Una strategia più efficiente potrebbe implicare il tenere traccia delle modifiche incrementali al tabellone di gioco, invece di riesaminare l'intera scheda ogni volta.