[Java] Giochino

[Enzo Font]

Vorrei fare un giochino in java senza interfaccia.
In pratica una griglia popolata randomicamente di spazi vuoti, bolle sgonfie, semigonfie e che stanno per esplodere.

L'utente può selezionare la bolla che vuole e questa passa allo stato successivo, se esplode propaga l'esposione. Qui ho i primi problemi di algoritmo se si verificasse una esplosione multipla, perché potenzialmente quella che esplode può farne esplodere altre quattro e via così.

L'altro problema è scrivere un algoritmo che trovi il minor numero di mosse possibile per liberare la griglia, cioè essendo la griglia di 5x6, avrei trenta modi per scegliere la prima, trenta/ventinove o meno la seconda e così via, mi pare molto complicato.

Grazie

[71106]

Domanda chiave, supponendo che la griglia sia ortogonale: ciascuna casella è circondata da altre 8 caselle, non 4, quindi come mai dici che "quella che esplode può farne esplodere altre quattro"?

Altra domanda chiarificatrice: quando una bolla che sta per esplodere è adiacente a un'altra che esplode, anche la prima naturalmente esplode; ma cosa succede quando una bolla sgonfia è adiacente a una che esplode? si gonfia di un "livello" o esplode direttamente?

[Enzo Font]

allora solo le bolle in direzione nord-sud-ovest-est vengono "toccate" dall'esplosione, quelle in diagonale no

si gonfia di un livello per quanto riguarda la seconda domanda

[71106]

L'algoritmo di base è facile. Supponiamo che tu abbia una matrice di naturali dove il valore 0 indica una casella vuota, 1 una bolla sgonfia, 2 una bolla semigonfia, e 3 una bolla che sta per esplodere.

Indichiamo con m la matrice, h il numero di righe e w il numero di colonne. L'utente clicca su una casella con coordinate (i, j) e questo è quello che succede:

void click(int i, int j) {
  if (i >= 0 && i < h && j >= 0 && j < w) {
    if (m[j][i] && ++m[j][i] > 3) {
      m[j][i] = 0;
      click(i - 1, j);
      click(i + 1, j);
      click(i, j - 1);
      click(i, j + 1);
    }
  }
}

Questo però comporta che in alcuni casi le bolle esplodano anche in diagonale. Prendi ad esempio la seguente matrice:

3 3
3 2

Se clicchi sulla prima casella in alto a sinistra, quella in alto a destra e in basso a sinistra esplodono assieme ad essa, tuttavia entrambe propagano l'esplosione a quella in basso a destra che sta già a livello 2 e ricevendo due propagazioni andrebbe a livello 4, quindi esplode anche quella. È corretto?

[Enzo Font]

Originariamente inviato da 71106

void click(int i, int j) {
  if (i >= 0 && i < h && j >= 0 && j < w) {
    if (m[j][i] && ++m[j][i] > 3) {
      m[j][i] = 0;
      click(i - 1, j);
      click(i + 1, j);
      click(i, j - 1);
      click(i, j + 1);
    }
  }
}

Questo però comporta che in alcuni casi le bolle esplodano anche in diagonale. Prendi ad esempio la seguente matrice:

3 3
3 2

Se clicchi sulla prima casella in alto a sinistra, quella in alto a destra e in basso a sinistra esplodono assieme ad essa, tuttavia entrambe propagano l'esplosione a quella in basso a destra che sta già a livello 2 e ricevendo due propagazioni andrebbe a livello 4, quindi esplode anche quella. È corretto?

corretto

ho un dubbio su quanto ho sottolineato: se il valore incrementato di 1? o incremento il valore di 1?

[71106]

Originariamente inviato da Enzo Font

corretto

ho un dubbio su quanto ho sottolineato: se il valore incrementato di 1? o incremento il valore di 1?

Quello è un preincremento, quindi incrementa il valore di 1 e restituisce il valore incrementato. Il valore restituito viene confrontato con 3, quindi quella parte va letta come: "se il valore incrementato è maggiore di 3, esplosione".

Ciò detto, il secondo problema che descrivi mi risulta non banale, io lo approccerei in due fasi:

1. rilevare le "isole" di bolle contigue non separate da spazi vuoti, ossia le aree che permettono la propagazione dell'esplosione;
2. determinare una strategia per eliminare ciascuna isola nel minor numero di mosse.

La prima parte è in realtà facile, è un classico nonchè basilare problema di backtracking + programmazione dinamica.

Ho provato a fare qualche riflessione sulla seconda parte, penso che per ciascuna bolla bisognerebbe determinare quali eventuali altre bolle sono più "convenienti" da cliccare per farla esplodere. Prendi l'esempio di prima, avendo questa configurazione:

33
32

cliccare la bolla in alto a sinistra è più conveniente che cliccare quella in basso a destra se lo scopo è quello di far esplodere quella in basso a destra, perchè nel primo caso bisogna cliccare una volta sola mentre nel secondo bisognerebbe cliccare due volte.

Quindi in sostanza per ciascuna "isola" bisognerebbe costruire un grafo in cui ciascuna bolla dice "clicca lui, non me!", e a quel punto probabilmente nel grafo si verrebbero a formare degli "hub", ossia dei nodi per i quali molti altri nodi dicono "clicca lui". E a quel punto andrei a cliccare i nodi uno per uno in ordine di grado entrante dal più alto al più basso.

Questa idea è solo un vago abbozzo e lascia molti problemi aperti, primo fra tutti se sia necessario o no aggiornare il grafo ogni volta che causo un'esplosione (è necessario aggiornarlo se l'ordinamento dei nodi per grado entrante può cambiare ad ogni esplosione, altrimenti no).

Questo intanto è il codice per il backtracking:

void blowAll() {
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      ArrayList<Node> island = new ArrayList<Node>();
      detectIsland(i, j, island);
      // TODO: blow island
    }
  }
}

void detectIsland(int i, int j, ArrayList<Node> island) {
  if (i >= 0 && i < h && j >= 0 && j < w) {
    if (!a[j][i] && m[j][i] > 0) {
      a[j][i] = true;
      island.add(new Node(i, j));
      detectIsland(i - 1, j, island);
      detectIsland(i + 1, j, island);
      detectIsland(i, j - 1, island);
      detectIsland(i, j + 1, island);
    }
  }
}

Node è una classe che rappresenterebbe i nodi del grafo e "a" è una matrice ausiliare di booleani delle stesse dimensioni di "m" e inizializzata interamente a false.

[71106]

Riflettendo meglio sull'idea per risolvere il problema della cancellazione totale, il backtracking per rilevare le isole non è necessario, la seconda fase dell'algoritmo funzionerebbe anche se dovesse ripulire un'area non contigua.

Riformulo la mia idea di massima: la soluzione proposta è un algoritmo greedy che come soluzione locale sceglie di far esplodere la bolla con la massima propagazione.

Ergo, anche il grafo non è più necessario in quanto per sapere la propagazione di ciascuna bolla sarebbe sufficiente simulare l'esplosione in una matrice ausiliaria, molto più facile da implementare.

Quindi in pratica dimentica il post precedente.

Poi che questo approccio greedy sia ottimo è tutto da dimostrare, ma altri approcci non mi vengono in mente.

[Enzo Font]

r e c sono le coordinate inserite dall'utente
ho inserito il metodo che hai scritto sopra in una propria classe

     package C.JAVA.BB;
     import java.util.*;
     
     public class Selezione
     {
         public void clic (int r, int c, int [ ][ ] griglia) 
         {
             if (r >= 0 && r < 5 && c >= 0 && c < 6)
                if ((griglia[r][c] > 3) && (++griglia[r][c] > 3))
                {
                    griglia[r][c] = 0;
                    clic (r - 1, c, griglia);
                    clic (r + 1, c, griglia);
                    clic (r, c - 1, griglia);
                    clic (r, c + 1, griglia);
                }
         }
     }

nella classe principale

  
     import C.JAVA.BB.Selezione;
     import java.util.*;
     //...altro codice...
     Selezione o1 = new Selezione();
     o1.clic (r, c, griglia [r] [c]);

errori (sottolineati)

C:\JAVA\BB\BubbleBlast.java:46: error: cannot find symbol
o1.clic(r, c, griglia [r] [c]);

symbol: variable r
location: class BubbleBlast
C:\JAVA\BB\BubbleBlast.java:46: error: cannot find symbol
o1.clic(r, c, griglia [r] [c]);

symbol: variable c
location: class BubbleBlast
C:\JAVA\BB\BubbleBlast.java:46: error: cannot find symbol
o1.clic(r, c, griglia [r] [c]);

symbol: variable r
location: class BubbleBlast
C:\JAVA\BB\BubbleBlast.java:46: error: cannot find symbol
o1.clic(r, c, griglia [r] [c]);

symbol: variable c
location: class BubbleBlast
4 errors

Process Terminated ... there were problems.

[71106]

Mi sembra che ti stia dicendo che a questa riga:

o1.clic (r, c, griglia [r] [c]);

r e c non sono dichiarati.

Inoltre hai introdotto un errore nel ricopiare il mio codice, a questa riga:

                if ((griglia[r][c] > 3) && (++griglia[r][c] > 3))

la parte sinistra dell'AND non deve essere un confronto con 3. La logica dell'if e': "se il valore non e' nullo E dopo averlo incrementato risulta maggiore di 3," eccetera.

Quindi cambia in:

                if (griglia[r][c] && (++griglia[r][c] > 3))

Se fa errore (e' molto che non uso Java) cambia in:

                if ((griglia[r][c] != 0) && (++griglia[r][c] > 3))

[Enzo Font]

stavo pensando per il secondo algoritmo di fare così:

int rnd = new Random().nextInt (griglia.length);

quindi, in pratica, di fare giocare il computer, per un numero di volte che devo ancora stabilire;
tre problemi:
1-posso ricavare l'indice di riga e colonna dell'elemento che sceglie il computer?
2-è possibile che il computer giocandolo più e più volte ripeta le stesse mosse, facendo in pratica due tentativi uguali; è possibile ovviare a questo problema?
3-numero di tentativi?

dubbi (in grassetto) anche sull'algoritmo che mi avevi presentato tu:

public int [ ] [ ] clic (int i, int j,  int nBolle, int [ ] [ ] griglia) 
         {
             if (i >= 0 && i < 5 && j >= 0 && j < 6)
             {
                 if ((griglia[i] [j] != 0) && (++griglia[i] [j] > 3))
                 {
                     nBolle--;
                     griglia[i][j] = 0;
                     clic (i - 1, j, nBolle, griglia);
                     clic (i + 1, j, nBolle, griglia);
                     clic (i, j - 1, nBolle, griglia);
                     clic (i, j + 1, nBolle, griglia);
                 }
                 if ((griglia [i] [j] > 0) && (griglia [i] [j] < 3))
                 {
                     ++griglia [i] [j];
                 }
                 if (griglia [i] [j] == 0)
                    //cosa faccio?
                 System.out.print(griglia [i] [j] + "\t");
             }
             else (/*fuori array*/)
                     //cosa faccio?
         }
         return griglia; //ER

mi stavo interrogando sulla chiamata ricorsiva di clic, correggimi se sbaglio, ma secondo la mia lettura funziona in questo caso ad esempio:

1 3 1
3 3 3 selezionando il 3 in mezzo
1 3 1

ma nel momento in cui avessi altri numeri intorno, gli altri 3 non propagherebbero l'esplosione, sbaglio?

[71106]

Vabbe' scusa, se devi farlo giocare a random diventa facilissimo. Fagli cercare le bolle col valore piu' alto, cioe' quelle piu' vicine a esplodere, e fagliene scegliere una a caso.

void click(int i, int j) {
  if (i >= 0 && i < h && j >= 0 && j < w) {
    if (m[j][i] && ++m[j][i] > 3) {
      m[j][i] = 0;
      click(i - 1, j);
      click(i + 1, j);
      click(i, j - 1);
      click(i, j + 1);
    }
  }
}

private final Random random = new Random();

int max() {
  int max = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      max = Math.max(max, m[i][j]);
    }
  }
  return max;
}

int count(int value) {
  int count = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (m[i][j] == value) {
        count++;
      }
    }
  }
  return count;
}

void play() {
  int index = random.nextInt(count(max()));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (m[i][j] == max) {
        if (--index == 0) {
          click(i, j);
          return;
        }
      }
    }
  }
}

Originariamente inviato da Enzo Font

2-è possibile che il computer giocandolo più e più volte ripeta le stesse mosse, facendo in pratica due tentativi uguali; è possibile ovviare a questo problema?

Non ho capito che intendi. Ogni volta che il computer fa una mossa la griglia viene aggiornata, quindi alla mossa successiva quella appena fatta non puo' piu' essere considerata una mossa valida (se la bolla e' esplosa).

mi stavo interrogando sulla chiamata ricorsiva di clic, correggimi se sbaglio, ma secondo la mia lettura funziona in questo caso ad esempio:

1 3 1
3 3 3 selezionando il 3 in mezzo
1 3 1

ma nel momento in cui avessi altri numeri intorno, gli altri 3 non propagherebbero l'esplosione, sbaglio?

Sbagli, l'algoritmo e' fatto in modo da propagarla senza problemi. La profondita' della ricorsione e' arbitraria.

[Enzo Font]

Allora faccio un po' d'ordine.

L'utente gioca e clic è il metodo con cui si realizza il gioco.

Poi, prima di far giocare l'utente, il pc deve stabilire il numero di mosse minimo in cui è risolvibile la griglia data.

In un primo momento avevo pensato anch'io di far esplodere prima le bolle più vicine allo stato di esplosione e via via le altre, però non è assolutamente detto che sia il procedimento migliore, per cui ho deciso di ripiegare su di un altro procedimento, ossia: far giocare il pc lasciandogli la scelta di quali bolle selezionare, quindi a random, e una volta completata la griglia, fargliela rigiocare ancora, e ancora, e ancora ... in questo senso gli farei fare delle ripetizioni/tentativi di risoluzione.

             //trova numero minimo mosse
             while (true/*TROVA MASSIMO MINIMO: CASO PEGGIORE: NUMERO DI RIPETIZIONI*/ )
             {
                 while ((nBolle > 0) && (min <= minimo))
                 {
                     //int rnd = new Random().nextInt (griglia.length);
                     //DEVO SAPERE COORDINATE ELEMENTO
                     //HO RISOLTO COME DI SEGUITO PER LE COORDINATE
                     i = (int) (Math.random()*5);
                     j = (int) (Math.random()*6);
                     //fine coordinate
                     if (griglia [i] [j] != 0)
                        min++;
                     griglia = o2.clic(i, j, nBolle, griglia); //ER
                 }
                 if (min <= minimo)
                    minimo = min;
                 nBolle = nB; //ripristino contatore numero bolle iniziale
                 System.arraycopy (gri, 0, griglia , 0, griglia.length); //ripristino griglia originaria
             }

minimo è impostato ad un valore alto per far sì che il ciclo while interno parta e arrivi fino al completamento della griglia la prima volta.
Al posto di quel true devo stabilire un numero di ripetizioni, anche qui un numero altissimo, per aumentare le probabilità di trovare l'effettivo numero minimo di mosse necessario.

Ti riporto anche la consegna che mi è stata data: ... un algoritmo che ripete il gioco scegliendo tutte le possibili combinazioni di mosse in modo automatico per trovare il minimo. ...

Volevo sapere come ricavare le coordinate di riga e colonna di rnd. -Risolto vedi codice-

E se è possibile ovviare al problema di ripetizione di due risoluzioni di griglia identiche da parte del pc, che non so quanto possa essere probabile ma credo sia possibile; avevo pensato di salvare gli indici delle mosse in sequenza in altri array ma considerato che il numero di ripetizioni sarà altissimo probabilmente meglio evitare questa strada e credo non ce ne siano altre; quindi alla fine credo non si possa ovviare.

----------------------------------------------------------------------------------------

Poi a proposito del metodo clic

         public int [ ] [ ] clic (int i, int j,  int nBolle, int [ ] [ ] griglia) 
         {
             if (i >= 0 && i < 5 && j >= 0 && j < 6)
             {
                 if ((griglia[i] [j] != 0) && (++griglia[i] [j] > 3))
                 {
                     nBolle--;
                     griglia[i][j] = 0;
                     clic (i - 1, j, nBolle, griglia);
                     clic (i + 1, j, nBolle, griglia);
                     clic (i, j - 1, nBolle, griglia);
                     clic (i, j + 1, nBolle, griglia);
                 }
                 if ((griglia [i] [j] > 0) && (griglia [i] [j] < 3))
                 {
                     ++griglia [i] [j];
                 }
                 if (griglia [i] [j] == 0)
                    //cosa faccio?
                 System.out.print(griglia [i] [j] + "\t");
             }
             else (/*fuori array*/)
                     //cosa faccio?
         }
         return griglia; //ER

Che istruzioni potrei dargli nel momento in cui la bolla è 0, oppure nel momento in cui è fuori dalla griglia?