Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Прочитання коду гри 2048

with 3 comments

От я їду в поїзді, інтернету нема, я забув скинути собі документацію з AngularJS, тому тепер не знаю чому не працює форма яку я написав по пам’яті. ng-value працює лише в одну сторону? Ах, точно, в іншу – ng-model. Тим не менш, я ще забув як визначити номер ітерації в ng-repeat, тому не можу зробити видалення зі списку. Але в мене є гра 2048 з кодом, от я й спробую її прочитати. Читати код корисно. Але ми звісно не намагатимемось розібрати все, а просто візьмемо собі за мету додати до гри штучний інтелект. 🙂

Код гри

Код взятий з https://github.com/gabrielecirulli/2048.git. Сommit: 6c12037b2a090ed0f1bd7ab1738637810f98da46.

Отож, гра складається з HTML5 веб-сторінки (на що вказує <!DOCTYPE html>), і завантажує наступні скрипти:

  <script src="js/animframe_polyfill.js"></script>
  <script src="js/keyboard_input_manager.js"></script>
  <script src="js/html_actuator.js"></script>
  <script src="js/grid.js"></script>
  <script src="js/tile.js"></script>
  <script src="js/local_score_manager.js"></script>
  <script src="js/game_manager.js"></script>
  <script src="js/application.js"></script>

Читати, очевидно варто починаючи з application.js. Його код короткий, тому вставимо тут повністю:

// Wait till the browser is ready to render the game (avoids glitches)
window.requestAnimationFrame(function () {
  window.game = new GameManager(4, KeyboardInputManager, HTMLActuator, LocalScoreManager);
});

Насправді window.game в оригінальній грі не створювалась, але я її записав щоб мати можливість подосліджувати цей об’єкт за допомогою Firebug.

Додаємо нову клавішу

Клас KeyboardInputManager зберігається в файлі keyboard_input_manager.js і відповідає за ввід (не тільки з клавіатури, а й всіма іншими можливими способами. В тому файлі також можна знайти цікавий словник, що відображає коди клавіш в напрями, і звідки ми можемо дізнатись що 0 – це вверх, 1 – вправо, 2 – вниз і 3 – вліво. Радує те що є також можливість командувати рухами за допомогою клавіш Vim:

  var map = {
    38: 0, // Up
    39: 1, // Right
    40: 2, // Down
    37: 3, // Left
    75: 0, // vim keybindings
    76: 1,
    74: 2,
    72: 3,
    87: 0, // W
    68: 1, // D
    83: 2, // S
    65: 3  // A
  };

Всередині класу GameManager (з файлу game_manager.js), KeyboardInputManager використовується наступним чином:

  this.inputManager = new InputManager;

  ...

  this.inputManager.on("move", this.move.bind(this));
  this.inputManager.on("restart", this.restart.bind(this));
  this.inputManager.on("keepPlaying", this.keepPlaying.bind(this));

Тобто є лише три події, які виконують три методи. Найцікавіший, звісно, метод move, тому що скоріш за все ним, ми змусимо наш штучний інтелект керувати грою. Давайте створимо для його ходу заглушку, і змусимо її виконуватись при натисненні Enter. В keyboard_input_manager.js є обробник натиснення клавіші з наступним кодом:

  document.addEventListener("keydown", function (event) {
      ...
      if (event.which === 32) self.restart.bind(self)(event);

Що означає “при натисненні прогалика – виконати self.restart()“. Додамо туди наступний рядок:

      if (event.which === 13) self.run_ai.bind(self)(event);

Тепер треба додати відповідну функцію:

KeyboardInputManager.prototype.run_ai = function (event) {
  event.preventDefault();
  this.emit("run_ai");
};

Тепер в нашому GameManager можна підписатись на подію:

  this.inputManager.on("run_ai", this.run_ai.bind(this));

Тепер давайте опишемо наш штучний інтелект в функції run_ai:

GameManager.prototype.run_ai = function () {
    this.move(this.random_choice([0, 1, 2, 3]));
};
GameManager.prototype.random_choice = function(items) {
    return items[Math.floor(Math.random() * items.length)];
};

Вона просто робить хід випадковим чином. Дуже непогана стратегія, можна дуже швидко скласти клітинку на 32, тепер можна було б подумати про вдосконалення стратегії.

Копіювання поля

Для цього просто треба вибирати хід хоч трохи кращий ніж випадковий. Давайте почнемо з того, що будемо обирати той хід, після якого на полі залишається менше чисел (тобто той, при якому найбільша кількість чисел об’єднуються). Для цього треба подивитись де то поле зберігається, зробити копію поля, спробувати ходи і оцінити ситуацію.

Переглядаючи код бачимо що щось схоже на поле створюється наступним кодом:

GameManager.prototype.setup = function () {
  this.grid        = new Grid(this.size);

Ліземо в grid.js.

function Grid(size) {
  this.size = size;
  this.cells = [];
  this.build();
}

// Build a grid of the specified size
Grid.prototype.build = function () {
  for (var x = 0; x < this.size; x++) {
    var row = this.cells[x] = [];

    for (var y = 0; y < this.size; y++) {
      row.push(null);
    }
  }
};

Бачимо що поле має розмір і клітинки. Клітинки це масив масивів null, де null напевне позначає порожні клітинки. І справді, якщо подивитись значення game.grid.cells в Firebug, можна побачити таку структуру:

[[Tile { x=0, y=0, value=2}, null, null, null], [null, null, null, null], [null, null, null, null], [Tile { x=3, y=0, value=2}, null, null, null]]

Якщо продивитись код grid.js трохи далі, можна помітити метод

Grid.prototype.availableCells = function () {
  var cells = [];

  this.eachCell(function (x, y, tile) {
    if (!tile) {
      cells.push({ x: x, y: y });
    }
  });

  return cells;
};

Він повертає нам масив всіх координат які ще не зайняті. Чим їх більше, тим краще, і це ми використаємо для оцінки позиції. Також це показує нам як користуватись методом eachCell, який ми використаємо для того щоб робити копію поля:

Grid.prototype.copy = function () {
    var grid = new Grid(this.size);

    this.eachCell(function (x, y, tile) {
        grid.cells[x][y] = tile;
    });
    return grid;
};

Тепер, функція яка перевіряє скільки буде доступно вільних клітинок на полі, при цьому самого поля не чіпаючи:

GameManager.prototype.try_direction = function(direction) {
        var grid_copy = this.grid.copy();
        this.move(direction);
        var cells_available = this.grid.availableCells().length;
        this.grid = grid_copy;
        return cells_available;
};

Правда при тестах виявляється, що поле вона все таки чіпає. Можливо тому що переміщення чисел по полю відбуваються асинхронно, і коли ми перевіряємо хід і потім відновлюємо початковий стан поля ще не всі числа перемістились? А може тому що треба робити глибшу копію об’єкту Grid, роблячи також копії всіх об’єктів Tile? Друге – простіше пояснення, і варто було б перевірити спершу його, але поїзд вже прибуває.

Advertisements

Written by bunyk

Червень 23, 2014 at 07:42

Оприлюднено в Кодерство

Tagged with

Відповідей: 3

Subscribe to comments with RSS.

  1. А що таке 2048 для не втаємничених?

    patlatus

    Червень 23, 2014 at 12:09


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: