遊戲點和框的數據結構

Question

什麼是一個很好的數據結構來表示遊戲的狀態Dots and Boxes？

我想出了使用2點矩陣布爾，水平和垂直線，但也許有這樣做的更優雅的方式（與操作：附加線，查線，檢查方） 。

Answer 1

使用一對稱爲linesX和linesY的布爾二維數組對我有意義。在給定的X/Y方向上，每個陣列都會有一個多於一個行/列的平方的總數。下面是檢查方與解決方案的代碼示例：

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

Answer 2

我會用對應的遊樂區大小的單個二維數組。然後，數組中的每個元素都可以存儲一個包含4個布爾值的對象（或結構，具體取決於所使用的語言），每個元素對應一個布爾值。檢查盒子是否完整變得像在給定的座標中返回對象的邏輯和一樣簡單。

單個二維陣列使維護和故障排除錯誤更容易。

Answer 3

我最近做了這個，並使用了盒子對象的地圖。該地圖是一個元組和盒子對象。這允許非常快速的訪問並且更容易實現邊緣算法。檢查< -1,0>不成功要容易得多，而不是特殊情況下的左邊緣。爲了避免數據重複，有一個數組表示邊界，並且框對象知道如何訪問它。

使用box對象而不僅僅是數組的一個優點是它使得策略算法更容易。你經常想跟蹤接近已滿的盒子列表等等。這在數組中很難做到。

Answer 4

我可玩的遊戲，帶可調W，H，和numPlayers，是在這裏： http://pconstrictor.github.io/cellsurround/

（源代碼也在那兒仍然需要重構到ES6模塊語法，並使用FP希望改寫左右。如果有更簡單的模型設計，我很想知道。）

對於數據模型，我使用了一個大小爲w的單個二維數組。每個單元格都有一個邊的列表（在這個正方形網格的情況下是四個），並且當所有邊都「填滿」時變爲「填充」。請注意，用戶然後獲得額外的回合。而且，有時一個動作會導致兩個單元格同時被填充。

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

... 
} 

對於實際顯示的UI中，我使用單個2D陣列（大小的2瓦特+ 1通過2H + 1）作爲視圖模式，其中的點，邊緣和細胞都簡單地表示爲無論是充滿還是空着。 （點開始填充並始終保持如此狀態）。這很好地轉化爲HTML表格，可以使用兩個循環輕鬆呈現HTML表格，而無需額外的邏輯。這是7x9陣列，對應於3x4模型。請注意，這些僞列和行理想情況下應以交替大小顯示，僅出於視覺原因。

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

這裏是實際的視圖模型。

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

而這裏的實際渲染爲HTML的步驟：省略

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

... 

的tdHtml()功能 - 它能夠生成具有正確的ID和類TD。