Cấu trúc dữ liệu cho trò chơi Dấu chấm và Hộp

Question

Cấu trúc dữ liệu tốt để thể hiện trạng thái của trò chơi Dots and Boxes là gì?

tôi đã đưa ra sử dụng 2 ma trận của boolean, cho đường ngang và dọc, nhưng có lẽ có một cách thanh lịch hơn để làm điều này (và các hoạt động: add dòng, kiểm tra dòng, séc vuông) .

Answer 1

Sử dụng một cặp mảng hai chiều của các phép toán được gọi là linesX và linesY hợp lý với tôi. Mỗi mảng sẽ có thêm một hàng/cột so với tổng số ô vuông trên bảng theo hướng X/Y đã cho. Dưới đây là một mẫu mã của séc vuông với giải pháp mà:

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

Answer 2

Tôi sẽ sử dụng một mảng hai chiều đơn tương ứng với kích thước khu vui chơi. Mỗi phần tử trong mảng sau đó có thể lưu trữ hoặc một đối tượng (hoặc cấu trúc, tùy thuộc vào ngôn ngữ được sử dụng) có chứa 4 bool, một cho mỗi bên. Kiểm tra xem một hộp đã hoàn thành trở nên đơn giản như trả về các lôgic logic của đối tượng tại các tọa độ đã cho hay chưa.

Mảng hai chiều duy nhất giúp lỗi bảo trì và xử lý sự cố trở nên dễ dàng hơn nhiều.

Answer 3

Gần đây tôi đã làm điều này và sử dụng bản đồ các đối tượng hộp. Bản đồ là một tuple và đối tượng hộp. Điều này cho phép truy cập rất nhanh và đơn giản hơn để thực hiện các thuật toán cạnh. Nó dễ dàng hơn nhiều để kiểm tra không thành công cho < -1,0> hơn là trường hợp đặc biệt cạnh trái. Để tránh trùng lặp dữ liệu, có một mảng biểu diễn các cạnh và các đối tượng hộp biết cách truy cập nó.

Một lợi thế của việc sử dụng các đối tượng hộp thay vì chỉ là mảng là nó làm cho thuật toán chiến lược dễ dàng hơn. Bạn thường muốn theo dõi danh sách các hộp gần đầy, v.v. Điều này không thể thực hiện dễ dàng trong một mảng.

Answer 4

trò chơi có thể chơi được tôi, với W có thể điều chỉnh, H, và numPlayers, là ở đây: http://pconstrictor.github.io/cellsurround/

(Source code là có quá Tuy nhiên cần phải được refactored vào cú pháp mô-đun ES6, và hy vọng viết lại sử dụng FP Vì vậy,.. nếu có một thiết kế mô hình đơn giản hơn, tôi rất muốn biết.)

Đối với mô hình dữ liệu, tôi đã sử dụng một mảng 2D có kích thước w bằng h. Mỗi ô có một danh sách các cạnh (bốn trong trường hợp lưới vuông này) và trở thành 'đầy' khi tất cả các bên được 'lấp đầy'. Lưu ý rằng người dùng sẽ nhận thêm lượt. Ngoài ra, đôi khi một hành động đơn lẻ dẫn đến hai ô được điền đồng thời.

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

... 
} 

Đối với thực hiển thị UI, tôi sử dụng một mảng 2D đơn (kích thước 2W + 1 bởi 2h + 1) là mô hình điểm, trong đó dấu chấm, cạnh, và các tế bào đều chỉ đơn giản là thể hiện dưới dạng điền hoặc trống. (Dấu chấm bắt đầu được lấp đầy và luôn luôn giữ nguyên.) Điều này dịch độc đáo thành một bảng HTML có thể dễ dàng hiển thị với hai vòng lặp và không có logic phụ. Đây là mảng 7 x 9 tương ứng với mô hình 3x4. Lưu ý rằng các cột và hàng giả này lý tưởng nên hiển thị ở kích thước thay thế, chỉ vì lý do trực quan.

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

Đây là mô hình chế độ xem thực tế.

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

Và đây là các bước render-như-html thực tế:

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"); 

... 

Chức năng tdHtml() được bỏ qua - nó tạo ra một TD với đúng ID và các lớp học.