Структура данных для игры Dots and Boxes - PullRequest
7 голосов
/ 22 января 2011

Какая будет хорошая структура данных для представления статуса игры Точки и ящики ?

Я придумал использовать 2 логические матрицы для горизонтальных и вертикальных линий, но, возможно, есть более элегантный способ сделать это (и операции: добавить строку , проверить строку , контрольный квадрат ).

Ответы [ 4 ]

2 голосов
/ 26 августа 2011

Я недавно сделал это и использовал карту коробочных объектов.Карта представляла собой кортеж и коробочный объект.Это обеспечивает очень быстрый доступ и упрощает реализацию граничных алгоритмов.Гораздо проще безуспешно проверить <-1,0>, чем в особом случае левый край.Чтобы избежать дублирования данных, существовал массив, представляющий ребра, и объекты-блоки знали, как получить к нему доступ.

Одним из преимуществ использования объектов-блоков вместо массива является то, что он упрощает алгоритмы стратегии.Вы часто хотите отслеживать списки ящиков, которые близки к полному, и т. Д. Это не может быть легко сделано в массиве.

2 голосов
/ 22 января 2011

Использование пары двумерных массивов логических значений с именами 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];
}
1 голос
/ 22 мая 2015

Моя играбельная игра с настраиваемыми параметрами W, H и numPlayers находится здесь: http://pconstrictor.github.io/cellsurround/

(Исходный код тоже есть. Все еще нужно реорганизовать его в синтаксис модуля ES6 и, надеюсь, переписать с использованием FP. Поэтому, если есть более простой дизайн модели, я бы хотел знать.)

Для модели данных я использовал один двумерный массив размером w на h. Каждая ячейка имеет список сторон (четыре в случае этой квадратной сетки) и становится «заполненной», когда все стороны «заполнены». Обратите внимание, что пользователь получает дополнительный ход. Кроме того, иногда одно действие приводит к заполнению двух ячеек одновременно.

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

...
}

Для фактического отображения пользовательского интерфейса я использовал один 2D-массив (размером 2w + 1 на 2h + 1) в качестве модели представления, в которой точки, ребра и ячейки просто представлены в виде либо заполнен, либо пуст. (Точки начинаются заполненными и всегда остаются таковыми.) Это хорошо переводится, скажем, в таблицу HTML, которую можно легко отобразить с помощью двух циклов и без дополнительной логики. Вот массив 7 на 9, который соответствует модели 3х4. Обратите внимание, что эти псевдостолбцы и строки в идеале должны отображаться в чередующихся размерах только для наглядности.

(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() опущена - она ​​генерирует TD с правильным ID и классами.

1 голос
/ 22 января 2011

Я бы использовал один двумерный массив, который соответствует размеру игровой площадки. Каждый элемент в массиве может затем хранить либо объект (или структуру, в зависимости от используемого языка), который содержит 4 bools, по одному для каждой стороны. Проверка того, завершена ли ячейка, становится такой же простой, как и возвращение логических значений объекта в заданных координатах.

Единый двумерный массив значительно облегчает ошибки обслуживания и устранения неполадок.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...