Struttura dati per gioco Punti e scatole

Question

Quale sarebbe una buona struttura dati per rappresentare lo stato del gioco Dots and Boxes?

mi si avvicinò con l'utilizzo di 2 matrici di booleana, per le linee orizzontali e verticali, ma forse c'è un modo più elegante di fare questo (e le operazioni: add linea, controllo di linea, controllo quadrato) .

Answer 1

L'utilizzo di un paio di matrici bidimensionali di booleani chiamate linesX e linesY ha senso per me. Ogni array avrà una riga/colonna in più rispetto al numero totale di quadrati sul tabellone in quella determinata direzione X/Y. Ecco un esempio di codice di piazzare controllo con tale soluzione:

bool isSquareComplete(int x, int y) { 
    return linesX[x][y] && linesX[x + 1][y] && linesY[x][y] && linesY[x][y + 1]; 
} 

Answer 2

avrei usato un singolo array bidimensionale che corrisponde alla dimensione area di gioco. Ogni elemento dell'array può quindi memorizzare un oggetto (o una struttura, a seconda della lingua utilizzata) che contiene 4 bool, uno per ciascun lato. Controllare per vedere se una scatola è completa diventa semplice come restituire gli ands logici dell'oggetto alle coordinate date.

Il singolo array bidimensionale semplifica notevolmente gli errori di manutenzione e risoluzione dei problemi.

Answer 3

L'ho fatto di recente e ho utilizzato una mappa di oggetti box. La mappa era una tupla e l'oggetto scatola. Ciò consente un accesso molto rapido ed è più semplice implementare gli algoritmi edge. È molto più facile controllare senza successo per < -1,0> anziché il caso speciale il bordo sinistro. Per evitare la duplicazione dei dati, c'era una matrice che rappresenta i bordi e gli oggetti box sapevano come accedervi.

Un vantaggio dell'utilizzo di oggetti box anziché di un array è che rende più semplici gli algoritmi di strategia. Spesso si desidera tenere traccia degli elenchi di caselle che sono quasi complete, ecc. Questo non può essere fatto facilmente in un array.

Answer 4

miei contatti di gioco giocabile, con W regolabile, H, e numPlayers, è qui: http://pconstrictor.github.io/cellsurround/

(Il codice sorgente è anche lì deve ancora essere riscritta nella sintassi del modulo ES6, e si spera riscritta usando FP Così.. se c'è un modello più semplice, mi piacerebbe saperlo.)

Per il modello di dati, ho utilizzato una singola matrice 2D di dimensione w per h. Ogni cella ha una lista di lati (quattro nel caso di questa griglia quadrata) e diventa "riempita" quando tutti i lati sono "riempiti". Nota che l'utente ottiene un turno extra. Inoltre, a volte una singola azione si traduce in due celle riempite contemporaneamente.

// MODEL 
exports.SquareGrid = function(width, height, players) { 

    // reset (also serves as init) 
    this.reset = function(w, h, players) { 
     this.players = players; 
     this.player = players.firstPlayer(); 
     var m = []; 
     this.matrix = m; // will be a 2D array (well, array of arrays) 
     this.height = h; 
     this.width = w; 

     // fill matrix 
     var toLeft = null, above = null; // these will be used for cells 
              // sharing sides 
     for (var row = 0; row < h; row++) { 
      m[row] = []; 
      for (var col = 0; col < w; col++) { 
       toLeft = col ? m[row][col - 1] : null; 
       above = row ? m[row - 1][col] : null; 
       m[row][col] = exports.createSquareCell(above, toLeft); 
      } 
     } 
    } 

... 
} 

Per effettivamente visualizzazione l'interfaccia utente, ho usato un singolo array 2D (di dimensione 2w + 1 per 2h + 1) come modello di vista, in cui punti, spigoli e le cellule sono tutti semplicemente rappresentati o pieno o vuoto. (I punti iniziano a essere riempiti e rimangono sempre tali). Questo si traduce in una tabella HTML, che può essere facilmente resa con due cicli e senza logica aggiuntiva. Ecco la matrice 7 per 9 che corrisponde a un modello 3x4. Si noti che queste pseudo colonne e righe dovrebbero idealmente essere visualizzate in dimensioni alternate, solo per ragioni visive.

(w = 3, h = 4) so (ww = 7, hh = 9) 
. ___ . ___ . ___ . 
|  |  |  | 
|  | p1 | p1 | 
.  . ___ . ___ . 
|  |  |  | 
|  | p1 | p2 | 
.  . ___ . ___ . 
|  |   | 
|  |   | 
.  . ___ .  . 
|     | 
|     | 
. ___ . ___ . ___ . 

Ecco il modello di visualizzazione effettivo.

// VIEW MODEL 

exports.SquareGridView = function(gameModel, appId, resetFuncString) { 

// prepare to render the latest of whatever is in the model 
this.refresh = function() { 
    var h = this.gridModel.height; 
    var w = this.gridModel.width; 

    // Initialize the UI table, whose dimensions are bigger than the 
    // model's. 
    var viewPm = []; 
    var hh = viewCoord(h); 
    var ww = viewCoord(w); 
    for (var i = 0; i < hh; i++) { 
     viewPm[i] = []; 
    } 

    // But loop over the model when actually filling it in. (Shared 
    // cells cause double writes to viewPm, but oh well.) 
    for (var row = 0; row < h; row++) { 
     for (var col = 0; col < w; col++) { 
      var cell = this.gridModel.matrix[row][col]; 
      var i = viewCoord(row), j = viewCoord(col); 
      viewPm[i][j] = cell.owner; 
      viewPm[i - 1][j] = cell.sides['top']; 
      viewPm[i + 1][j] = cell.sides['bottom']; 
      viewPm[i][j - 1] = cell.sides['left']; 
      viewPm[i][j + 1] = cell.sides['right']; 
      // Note: vertices can be either filled or left undefined here (and hard-coded as filled in the HTML). 
     } 
    } 
... 

Ed ecco l'effettivo passaggio rendering-as-html: è omesso

var t = []; // the html text 
// TODO: split the HTML bits out into a template file? Use React or Elm? 
... 

t.push('<table class="squaregrid">\n'); 
var tdClass, tdId; // 'vertex', '0.0'; 
for (var i = 0; i < hh; i++) { 
    t.push(" <tr> \n"); 
    for (var j = 0; j < ww; j++) { 
     t.push(this.tdHtml(viewPm, i, j)); 
    } 
    t.push(" </tr>\n"); 
} 
t.push("</table>\n"); 

... 

La funzione tdHtml() - genera un TD con ID corretto e classi.