Tk

« Tk: applicazioni di esempio: clock: un orologio digitale/analogicoAppunti di Tcl/TkDescrizione di un demo Tk: ixset »

il gioco del 15

Questa applicazione è una versione leggermente modificata di uno dei demo che vengono forniti con Tk. È molto istruttivo andarsi a studiare il codice di questi demo come abbiamo fatto qui per questo gioco, così ben noto (per lo meno nella sua versione hardware) a tutti quelli che abbiano avuto occasione di annoiarsi a scuola da non aver affatto bisogno di spiegazioni :)

Il codice completo della prima versione si trova nel file 15.

Di seguito viene fornita qualche spiegazione linea per linea.

wm title . {15-Puzzle Game}
wm iconname . 15-Puzzle

Impostiamo un titolo per la finestra (altrimenti verrebbe impostato col nome dell'eseguibile) e uno breve che compare sotto l'icona (altrimenti vi compare il titolo della finestra, che è un po' troppo lungo).

scrollbar .s

Questo widget scrollbar serve solo per conoscere il colore che useremo per la casella vuota della scacchiera di gioco e non verrà mai pacchettato.

if {[string equal [tk windowingsystem] aqua]} {
    set frameSize 160
} else {
    set frameSize 120
}

Qualora siamo su un Macintosh con la nuova interfaccia Mac OS X Aqua o in breve detta acqua, piuttosto che quella classica, dobbiamo fissara una dimensione maggiore per il lato del quadrato della scacchiera (bastano 40 pixel in più), in quanto i tasti sono un po' più grossi che sotto Unix o Windows.

frame .frame -width $frameSize -height $frameSize -borderwidth 2 \
  -relief sunken -bg [.s cget -troughcolor]
pack .frame -pady 1c -padx 1c

Crea un frame che rappresenta la scacchiera, con dimensione laterale pari a $frameSize, un bordo 3-D largo 2 pixel, un effetto 3-D di incavo e usa lo stesso colore che ha l'incavo di una scrollbar. Pacchetta il frame lasciando 1 cm di spazio rispetto ai bordi della finestra da tutti e quattro i lati. Il risultato è rappresentato nella figura seguente:

il frame che rappresenta la tavola di gioco
destroy .s

Distrugge la scrollbar .s prematuramente, visto che l'abbiamo creata solo per conoscere il suo colore di sfondo e ora non serve più.

set order {3 1 6 2 5 7 15 13 4 11 8 9 14 10 12}

Questa lista di 15 elementi rappresenta la situazione di gioco iniziale.

for {set i 0} {$i < 15} {incr i} {
  set num [lindex $order $i]
  set xpos($num) [expr {($i % 4) * .25}]
  set ypos($num) [expr {($i / 4) * .25}]

  button .frame.$num -relief raised -text $num -highlightthickness 0 \
    -command "puzzleSwitch $num"
  place .frame.$num -relx $xpos($num) -rely $ypos($num) \
    -relwidth .25 -relheight .25
}

Questo ciclo effettua il packing dei 15 tasti. Utilizza il geometry manager place(n). Scandisce la lista order e per ciascun elemento di indice lineare $i calcola le sue coordinate cartesiane nella forma (colonna, riga), che sono date dalle semplici formule ($i%4, $i/4). Ogni bottone avrà una dimensione laterale relativa alla tavola di gioco pari a .25; infatti i bottoni sono 4 per lato e 1./4 fa .25. La posizione relativa di ogni tasto è individuata dalle coordinate (pure esse relative) (($i%4)*.25, ($i/4)*.25).

Per evitare che appaia ulteriore spazio tra i tasti, viene impostata a 0 la larghezza del rettangolo disegnato all'esterno del widget che lo mette in evidenza quando ha il focus. In questo modo non viene lasciato alcuno spazio esterno al widget, ovvero il rettangolo di evidenziazione non viene proprio disegnato. Per vedere cosa intendo, provate ad aumentare questo valore (ricordate che i tasti Tab e Alt-Tab spostano il focus).

Da notare che utilizziamo due array globali xpos e ypos per memorizzare rispettivamente le coordinate orizzontali e verticali relative di ciascuna pedina. Entrambi gli array sono indicizzati tramite il numero stampato sulla pedina.

Il risultato è come appare nella figura seguente:

la situazione di gioco iniziale
set xpos(space) .75
set ypos(space) .75

Con queste istruzioni memorizziamo la posizione iniziale della casella vuota (che è nell'angolo inferiore destro, come vedete dalla figura precedente), utilizzando una chiave space negli array xpos e ypos (avremmo potuto usare anche la chiave numerica 0, o una qualsiasi altra chiave numerica non già usata, ma poiché in Tcl gli array sono associativi, abbiamo preferito usare un nome di elemento più significativo).

Notate che l'aver usato il posizionamento relativo con place(n) fa sì che rimpicciolendo la finestra, le dimensioni della tavola di gioco si adattano di conseguenza:

la finestra di gioco è stata ora ristretta un po'
proc puzzleSwitch {num} {
  global xpos ypos

  if {(($ypos($num) >= ($ypos(space) - .01))
    && ($ypos($num) <= ($ypos(space) + .01))
    && ($xpos($num) >= ($xpos(space) - .26))
    && ($xpos($num) <= ($xpos(space) + .26)))
    || (($xpos($num) >= ($xpos(space) - .01))
    && ($xpos($num) <= ($xpos(space) + .01))
    && ($ypos($num) >= ($ypos(space) - .26))
    && ($ypos($num) <= ($ypos(space) + .26)))} {
      set tmp $xpos(space)
      set xpos(space) $xpos($num)
      set xpos($num) $tmp

      set tmp $ypos(space)
      set ypos(space) $ypos($num)
      set ypos($num) $tmp

      place .frame.$num -relx $xpos($num) -rely $ypos($num)
  }
}

Questa procedura viene richiamata ogni volta che si clicca su un tasto e gli viene passata l'etichetta del tasto $num. Essa verifica se il tasto su cui il giocatore ha cliccato è adiacente ad una casella vuota. In caso affermativo sposta il tasto nella casella vuota, effettuando lo scambio tra le coordinate relative della pedina numero $num e di quella chiamata space e riposizionando la pedina marcata $num dopo lo scambio, altrimenti non fa nulla in quanto la mossa non è valida.

Qualche piccola difficoltà pone la verifica se il tasto $num è adiacente allo spazio libero. Questa viene condotta confrontando le coordinate cartesiane relative dello spazio e della pedina, che sono rispettivamente ($xpos(space), $ypos(space)) e ($xpos($num), $ypos($num)) e sono dei dati direttamente disponibili.

Idealmente la casella $num è adiacente alla casella vuota se hanno lo stesso numero di colonna e un numero di riga che differisce di uno, vale a dire che la casella num si trova sopra o sotto la casella vuota; oppure se hanno lo stesso numero di riga, ma numero di colonna che differisce di uno (in questo caso la casella num è adiacente destra oppure adiacente sinistra lo spazio vuoto). Noi non abbiamo in memoria i numeri di riga e di colonna, ma li abbiamo moltiplicati per .25, perché così li vuole pack(n) e perché così avevamo deciso di memorizzarli negli array xpos e ypos. In prima stesura potremmo pensare che questo non cambia molto e scrivere la condizione di adiacenza così (avendo moltiplicato tutto per .25):

($ypos($num)==$ypos(space)) &&
(($xpos($num)==$xpos(space)-0.25) || ($xpos($num)==$xpos(space)+0.25))
||
($xpos($num)==$xpos(space)) &&
(($ypos($num)==$ypos(space)-0.25) || ($ypos($num)==$ypos(space)+0.25))

Nella realtà però capita che i calcoli tra numeri a virgola mobile sono approssimati e, a causa degli errori di calcolo, potrebbe non verificarsi l'uguaglianza tra numeri decimali, introducendo un subdolo baco. Occorre trasformare un'uguaglianza del tipo x==y tra numeri decimali in una condizione di disuguaglianza del tipo abs(x-y)<=e, vale a dire (x-y>=-e && x-y<=e), dove e rappresenta la precisione entro cui si vuole verificare l'uguaglianza.

Nel nostro caso, è facile verificare che fissato e pari a .01 si ottiene la condizione come è stata scritta nel codice.

Esercizi

  1. Proporre una soluzione alternativa per la verifica della adiacenza, che produca una condizione di verifica più semplice e quindi più leggibile
  2. Partendo dal risultato dell'esercizio 1, aggiungere del codice che faccia partire il tavolo di gioco da una permutazione casuale ogni volta diversa anziché dalla permutazione fissa {3 1 6 2 5 7 15 13 4 11 8 9 14 10 12}
  3. Modificare ulteriormente il programma di cui all'esercizio 2 per implementare la rilevazione di vittoria da parte del giocatore. Quando il giocatore vince, si apre un box con il messaggio "Congratulations, you won with # moves! Would you like to play again?". # rappresenta il numero di mosse, che il programma deve contare. Rispondendo yes si avvia un nuovo gioco diverso dal precedente, rispondendo no si esce dall'applicazione.
  4. Discutere se il programma ottenuto al punto 2 o 3 sia sempre corretto. In particolare è possibile che si verifichi il caso in cui il gioco sia già risolto in partenza? Come risolvereste il problema se per specifica questa situazione viene ritenuta non accettabile?
  5. Scrivere una versione del puzzle che lavori con i pezzi di una immagine anziché con caselle numerate.

Soluzioni

  1. Una soluzione con una condizione di verifica della adiacenza più semplice si ottiene memorizzando negli array xpos e ypos le coordinate intere, senza moltiplicarle per .25. Questo mostra come la scelta del formato di rappresentazione deve essere fatta nell'ottica di una semplificazione delle elaborazioni che si rendono necessarie. Il file 15-1 contiene il programma modificato.
  2. Una soluzione molto semplice (file 15-2) consiste nel partire dalla permutazione ordinata e generare dei numeri casuali compresi tra 1 e 15 (estremi inclusi) e provare a spostare la pedina con quel numero. Si ripete l'operazione un certo numero di volte, ad esempio 100:
    for {set i 0} {$i < 15} {incr i} {
      set num [expr {$i+1}]
      ...
    }
    
    for {set i 0} {$i < 100} {incr i} {
      set num [expr {1 + int(rand() * 15)}]
      puzzleSwitch $num
    }
    

    Anche se facile da implementare, questa soluzione non è soddisfacente in quanto vengono inutilmente tentate anche delle mosse non valide. In alcuni casi, delle 100 mosse fatte, solo poche unità sono valide. Una soluzione migliore consiste nel calcolare una delle mosse valide casualmente, ripetendo l'operazione un certo numero di volte e costruendo così un'animazione del mescolamento. Calcolare una mossa valida è relativamente facile: si tratta di spostare una delle pedine adiacenti allo spazio, ma occorre stare attenti che queste a volte sono 4 a volte sono 3 o persino 2. Inoltre sarebbe inutile fare due mosse in sequenza che si annullano, quindi questo va evitato. Una soluzione di questo tipo è nel file 15-2bis.

    Questa soluzione utilizza una tabella di lookup inversa chiamata number. Notate che si potrebbe evitare l'uso di number a costo di usare una tabella di lookup diretta pos al posto dei due array xpos e ypos (ossia pos è un array di liste di due elementi che sono le coordinate x e y) e fare una ricerca lineare dentro questa tabella pos per trovare il numero di casella corrispondente alla posizione x,y determinata come mossa valida. Per esercizio provate a codificare anche in questo modo. Per converso si potrebbe evitare l'uso di pos o xpos e ypos e usare solo l'array number.

    In generale in pratica capita che più informazioni di book-keeping si tengono, maggiore è la velocità e la semplicità di un algoritmo, ma maggiore è la memoria richiesta e occorre trovare un trade-off, un bilanciamento tra le due buone proprietà di un algoritmo (di essere veloce e richiedere poca memoria), che sono spesso contrastanti.

  3. Vedere la soluzione nel file 15-3
  4. Anche se molto poco probabile, è possibile che la fase di mescolamento produca un gioco banalmente già risolto. La probabilità che questo si verifichi può essere ridotta a zero modificando opportunamente la procedura puzzleShake, in modo che il mescolamento venga ripetuto finché i numeri non sono in ordine. Si potrebbe anche usare una chiamata ricorsiva in puzzleShake invece di un ciclo. Vedere la soluzione col ciclo nel file 15-4
  5. La soluzione più semplice, che non fa pieno uso della potenza del comando photo(n) consiste nel dividere un'immagine in 16 parti con un programma di grafica (ad es. gimp(1)). Come esempio ho preso una suggestiva immagine della terra earth.gif a tutto tondo di dimensioni 220x200 e l'ho divisa in 16 parti di dimensione 55x50 ciascuno. La ragione per cui non ho potuto fare un'immagine quadrata a tutto tondo è che, a causa del moto di rotazione, la terra non è sferica, bensì è visibilmente un ellissoide. Le dimensioni di ciascun pezzo non sono uguali (larghezza 55 e altezza 50), ma il programma 15-5 supporta senza problemi anche i pezzi rettangolari. Notate che le dimensioni del frame sono 224x204, quel 4 in più è stato aggiunto in quanto le dimensioni tengono conto anche dei bordi del frame (che sono larghi 2 pixel per ciascun lato), mentre il bordo dei pulsanti è stato ridotto a 0.

    Naturalmente una soluzione migliore non dovrebbe richiedere la preparazione dei pezzi in file separati, ma dovrebbe caricare un'immagine in memoria e fare da sè la divisione in 16 parti uguali. Qualora le dimensioni dell'immagine non siano esattamente divisibili per 4, non imponiamo alcun vincolo; la soluzione più semplice è di considerare la sottoimmagine superiore sinistra con dimensioni multiple di 4. Quando il giocatore vince occorre aggiungere il pezzo mancante all'immagine (che è sempre il 16-esimo), in modo da mostrare l'immagine completa, per poi toglierlo ad ogni nuova partita. Tutte queste modifiche sono implementate nella versione 15-5bis

« Tk: applicazioni di esempio: clock: un orologio digitale/analogicoAppunti di Tcl/TkDescrizione di un demo Tk: ixset »