Estructura de datos para el juego Puntos y cuadros

Question

¿Cuál sería una buena estructura de datos para representar el estado del juego Dots and Boxes?

me ocurrió con el uso de 2 matrices de booleano, para las líneas horizontales y verticales, pero tal vez hay una forma más elegante de hacer esto (y las operaciones: Añadir una línea de, verificación en línea, cuadrado cheque) .

Answer 1

El uso de un par de matrices bidimensionales de booleanos llamados linesX y linesY tiene sentido para mí. Cada matriz tendría una fila/columna más que el número total de cuadrados en la placa en esa dirección X/Y dada. Aquí está un ejemplo de código de cuadrado cheque con esa solución:

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

Answer 2

me gustaría utilizar una única matriz de dos dimensiones que corresponde al tamaño área de juego. Cada elemento de la matriz puede almacenar un objeto (o estructura, según el idioma utilizado) que contenga 4 bools, uno para cada lado. Verificando si una caja está completa se vuelve tan simple como devolver los ys lógicos del objeto en las coordenadas dadas.

La única matriz bidimensional hace que los errores de mantenimiento y solución de problemas sean mucho más fáciles.

Answer 3

Hace poco hice esto y usé un mapa de objetos de caja. El mapa era una tupla y el objeto de la caja. Esto permite un acceso muy rápido y es más sencillo implementar los algoritmos de borde. Es mucho más fácil comprobar sin éxito < -1,0> en lugar de un caso especial el borde izquierdo. Para evitar la duplicación de datos, había una matriz que representaba los bordes y los objetos de la caja sabían cómo acceder a ella.

Una ventaja del uso de objetos de caja en lugar de solo una matriz es que hace que los algoritmos de estrategia sean más fáciles. A menudo desea realizar un seguimiento de las listas de cajas que están casi llenas, etc. Esto no se puede hacer fácilmente en una matriz.

Answer 4

Mi juego jugable, con W regulable, H y numPlayers, es aquí: http://pconstrictor.github.io/cellsurround/

(El código fuente está allí también todavía tiene que ser reprogramado para utilizar la sintaxis módulo ES6, y es de esperar volver a escribir utilizando FP Así que.. si hay un diseño de modelo más simple, me gustaría saberlo).

Para el modelo de datos, utilicé una sola matriz 2D de tamaño w por h. Cada celda tiene una lista de lados (cuatro en el caso de esta cuadrícula) y se 'llena' cuando todos los lados están 'llenos'. Tenga en cuenta que el usuario obtiene un turno extra. Además, a veces una sola acción da como resultado que dos celdas se llenen simultáneamente.

// 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); 
      } 
     } 
    } 

... 
} 

Para realmente presentan la interfaz de usuario, que utiliza una sola matriz 2D (de tamaño 2w + 1 por 2h + 1) como el modelo de vista, en el que puntos, bordes y células son todos simplemente representados como ya sea lleno o vacío. (Los puntos comienzan llenos y siempre permanecen así). Esto se traduce muy bien en, por ejemplo, una tabla HTML que se puede representar fácilmente con dos bucles y sin lógica adicional. Aquí está la matriz de 7 por 9 que corresponde a un modelo de 3x4. Tenga en cuenta que estas pseudo columnas y filas idealmente deberían mostrarse en tamaños alternos, solo por razones visuales.

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

Aquí está el modelo de vista real.

// 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). 
     } 
    } 
... 

Y aquí está el paso de hacer-como-html real: se omite

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 función tdHtml() - se genera un TD con correcta identificación y clases.