Реализация сапёра в 100 строках чистого Ruby

в 13:00, , рубрики: ruby, ruvds_перевод, оптимизация кода, Программирование, сапёр

Реализация сапёра в 100 строках чистого Ruby - 1


Ruby — весьма экспрессивный язык, в котором очень многое зачастую можно реализовать буквально в ста строках кода. Именно поэтому мне так нравится искать способ создать то же самое, но в более сжатом виде.1

Сразу внесу ясность: я не говорю о код-гольфинге, хотя это занятие тоже бывает интересным. Я имею в виду сокращение количества строк кода без потери его читаемости. По факту одним из самых приятных аспектов Ruby является то, что уменьшение количества строк кода зачастую может повысить его читаемость.

В нашем случае мы проделаем это на примере старого доброго «Сапёра». Помню, как играл в него на Windows XP ещё пацаном. Если и вы разделяете аналогичные воспоминания, то приветствую вас, мои друзья-миллениалы!

Ради спортивного интереса я реализовал его в командной строке на чистом Ruby. Полноценная версия доступна здесь. Если хотите проделать это сами, то приостановитесь здесь и вернитесь позже, чтобы сравнить результат. Остальная часть статьи посвящена реализации, которая по чистой случайности составила ровно 100 строк (подсчитано в каталоге lib с помощью cloc). Причём я реально не мухлевал, чтобы округлить число. Я, конечно, планировал как-то под него всё подогнать, но в итоге этого делать не пришлось.

Попутно мы также освежим в памяти некоторые менее используемые возможности Ruby. Я не могу осваивать новые знания в вакууме. Мне больше нравится изучать что-либо в контексте мини-проекта, а не через просмотр журнала изменений.

▍ Генерация игрового поля

Первым делом нам нужен класс Board, который будет представлять поле. В качестве параметров поля выступают ширина, высота и расстановка мин.

	class Board < Data.define(:width, :height, :mines)
  # содержимое ...
end

Здесь мы используем функциональность, появившуюся в Ruby 3.2, класс Data. Он прекрасно подходит для определения иммутабельных объектов значений. Если вы уже его использовали, то наверняка зададитесь вопросом, почему я не задействовал типичный синтаксис Board = Data.define(...) do ... end, вместо этого выполнив наследование от него. Объясню чуть позже.

Мы создадим доску, случайным образом разместив на ней мины. При этом нельзя просто присвоить каждой мине случайную пару координат, поскольку тогда две мины могут оказаться в одной клетке. Вместо этого мы возьмём все возможные клетки доски и случайно выберем из них определённое количество.

К нашему удобству, в Ruby это можно выразить в близкой к простому английскому языку форме:

	class Board < Data.define(:width, :height, :mines)
    # ...
    def self.generate_random(width, height, mines_count)
      full_board = Enumerator.product(width.times, height.times)
        .map { |x, y| Coordinate.new(x, y) }
      self.new(width, height, full_board.sample(mines_count))
    end
    # ...
end

Enumerator.product получает два нумератора и возвращает их прямое произведение. На математическом языке это звучит так: «каждый элемент из первого списка, совмещённый с каждым элементом из второго списка». По сути, это даёт нам все возможные координаты. Далее мы вызываем sample, которая получает несколько случайных элементов из коллекции. Я мог бы встроить этот вызов, чтобы сэкономить сколько-то строк, но решил, что использование переменной full_board обеспечит приятный эффект самодокументирования.

Класс Coordinate начинается как ещё один простой объект Data:

	Coordinate = Data.define(:x, :y)

Board также должен определять, находится ли в конкретной клетке мина, или же эта клетка пуста. Если она пуста, нам нужно знать, сколько рядом с ней есть соседних заминированных клеток. Поскольку mines уже является просто массивом объектов Coordinate, можно использовать её напрямую:

	class Board < Data.define(:width, :height, :mines)
    # ...
    class Mine; end;
    Empty = Data.define(:neighbour_mines)

    def cell(coordinate)
      mines.include?(coordinate) ? Mine.new : Empty.new(count_neighbours(coordinate))
    end

    private

    def count_neighbours(coordinate)
      mines.count { |mine| mine.neighbour?(coordinate) }
    end
  end

Вложенные подклассы Mine и Empty и являются той причиной, по которой здесь я произвёл наследование от класса Data. Они потребуются вне данного контекста. Эти подклассы не будут видимы изнутри блока Data.define do; end.

Да, метод, который подсчитывает соседей, не оптимален, так как считает все мины. Пока что мы оставим эту его легко читаемую версию и оптимизируем её позднее при необходимости.

В последнем методе mine — это просто coordinate, и мы используем метод neighbour?, который ещё не определили. Определим мы его путём проверки того, является ли расстояние в одной из координат меньше либо равным 1:

	Coordinate = Data.define(:x, :y) do
    def neighbour?(other)
      [(self.x - other.x).abs, (self.y - other.y).abs].max <= 1
    end
end

На этом с классом Board мы закончили.

▍ Игровой процесс

Реализацию игрового процесса мы поручим новому классу с шокирующим названием Game. Ему потребуется экземпляр объекта доски и карта открытых к текущему моменту клеток:

	class Game
    def initialize(board)
      @cells = Array.new(board.height * board.width, nil)
      @board = board
    end
    # ...
end

Изначально ещё ничего не открыто, поэтому мы инициализируем массив, соответствующий размеру доски. По умолчанию он инициализируется со всеми nil.

Мы сократим интерфейс до одного метода reveal, который будет выполняться при «клике» по ячейке для её открытия. Единственная хитрость здесь в том, что при открытии клетки, рядом с которой нет мин, игра должна автоматически рекурсивно открывать все соседние клетки, проявляя за раз целую область. Именно этот момент так радует в процессе игры. Соответствующую логику мы реализуем, как я уже и сказал, рекурсивно открывая все соседние клетки:

	class Game
  # ...
  CELL_WITH_NO_ADJACENT_MINES = Board::Empty.new(0)

  def reveal(coordinate)
    index = cell_index(coordinate)
    return :play if @cells[index]

    (@cells[index] = @board.cell(coordinate)).tap do |cell|
      return :lose if cell.is_a?(Board::Mine)
      reveal_neighbours(coordinate) if cell == CELL_WITH_NO_ADJACENT_MINES
    end
    @cells.count(&:nil?) == @board.mines.size ? :win : :play
  end

  private

  def cell_index(coordinate)= coordinate.y * @board.width + coordinate.x

  def reveal_neighbours(coordinate)
    coordinate.neighbours(width, height).each { |n| reveal(n) }
  end
end

По сути, когда открывается клетка, рядом с которой нет мин, этот код выполняет по доске поиск в ширину. В основе его работы лежит два ключевых момента:

  1. Ранний выход из метода, когда клетка уже была открыта.
  2. Присваивание открытого значения до перехода к рекурсивному вызову reveal для соседних клеток. Это исключает вхождение в бесконечную рекурсию, когда только что открытый сосед пытался бы следом открыть изначальную клетку.

Наконец, если мы натыкаемся на мину, то выполняем ранний выход с помощью :lose. В противном случае мы проверяем, все ли оставшиеся клетки являются заминированными, и если да, возвращаем :win. Во всех остальных случаях возвращается :play.

Единственное, чего здесь не хватает — это метода neighbours для координат. Для его реализации мы сначала создадим список смещений для всех 8 соседей:

	Coordinate = Data.define(:x, :y) do
  NEIGHBOURS = (Enumerator.product([-1, 0, 1], [-1, 0, 1]).to_a - [0, 0]).map { |x, y| self.new(x, y) }
  # ...
end

Мы снова используем product, только здесь он также будет включать centre, который мы удалим посредством исключения из списка [0, 0].

После этого список фактических координат соседей формируется путём добавления всех их смещений в Coordinate и удаления тех, которые выходят за пределы доски:

	Coordinate = Data.define(:x, :y) do
  # ...
  def +(other)
    self.class.new(self.x + other.x, self.y + other.y)
  end

  def neighbours(board_width, board_height)
    NEIGHBOURS
      .map { |n| self + n }
      .reject { |n| n.x < 0 || n.x >= board_width || n.y < 0 || n.y >= board_height }
  end
end

▍ Отображение доски в формате ASCII

Для вывода доски в командной строке мы будем перебирать сетку, преобразуя клетки в символы ASCII:

	AsciiRenderer = Data.define(:grid) do
  def render(output = $stdout)
    grid.height.times do |y|
      grid.width.times do |x|
        output.print case cell = grid.cell(Coordinate.new(x, y))
                      when nil then "#"
                      when Board::Mine then "*"
                      else cell.neighbour_mines.zero? ? "_" : cell.neighbour_mines
                      end
      end
      output.puts
    end
  end
end

В итоге мы получим что-то вроде следующего:

	___1#1_______1#1___1#1__1#1___
___111_______111___1#1__1#1___
11_________________111__1#211_
#21111_______111111_____1###1_
#####1_______1####311___12#21_
###211__111__111####1____111__
###1____2#2____1#2211_______11
###1____2#2____1#1__________1#

Заметьте, что код ожидает методы width, height и cell, которые мы определили в Board, но не в Game. А по факту нам нужно выводить именно экземпляры Game. Так что определим их:

	class Game
  # ...
  def width = @board.width
  def height = @board.height
  def cell(coordinate) = @cells[cell_index(coordinate)]
  # ...
end

Здесь мы используем бесконечные методы. Да, каждый из них сократил по 2 строки кода, поспособствовав тому, чтобы игра уместилась в 100 строк, но использовал я их не для этого. Единственное требование к бесконечным методам — это то, что тело такого метода должно представлять всего одно выражение, сколько бы строк оно ни включало. Заметьте, что в Coordinate и Board есть несколько методов, которые также могут быть бесконечными. Я не использовал их здесь, потому что результат получался не особо читаемым. Всё же эстетика важна.

▍ Совмещаем всё воедино

Наконец, мы собираем все компоненты в жизнеспособную игру в командной строке.
Нам нужна возможность запустить её с помощью ruby lib/play.rb 20, 10, 20 и параметрами, определяющими ширину, высоту и количество мин. Для этого мы спарсим аргументы командной строки:

	if ARGV.size == 3
  Minesweeper.play(*ARGV.map(&:to_i))
else
  puts "Usage: ruby lib/play.rb width, height, mines_count (e.g. 'play.rb 12 6 6')"
end

Теперь мы просто определим метод игры в качестве функции модуля. Мы используем модуль ReadLine для вывода в командной строке запроса ввести координаты открываемой клетки и построчного считывания. Интерактивная консоль Ruby (IRB) внутренне использует аналогичный механизм.

	module Minesweeper
  module_function def play(...)
    game = Game.new(Board.generate_random(...))
    renderer = AsciiRenderer.new(game)
    renderer.render

    while input = Readline.readline("Type click coordinate as 'x, y' (0 based)> ")
      result = game.reveal(Coordinate.new(*input.split(",").map(&:to_i)))
      renderer.render
      if [:win, :lose].include?(result)
        puts "You #{result == :win ? "win" : "lose"}!"
        return
      end
    end
  end
end

Заметьте, что мы используем здесь def play(...). Этот синтаксис был добавлен в Ruby 2.7 для случаев, когда все параметры нужно просто перенаправить. В нашем случае параметры необходимо полностью перенаправить в Board.generate_random, после чего мы уже окружим их игровой логикой.

▍ Что дальше?

Полная версия игры доступна здесь. Если вы написали свою в качестве практики, то поделитесь ей в комментариях.

Сейчас это технически полноценная реализация «Сапёра», но пока играть в неё не особо весело. Всё же командная строка — не лучшая платформа для этой игры. В связи с этим следующий пост будет про её упаковку в приложение на Rails + Hotwire. И просто ради фана мы дополнительно сделаем игру многопользовательской, почему нет?

▍ Сноска

1. Если согласиться с утверждением, что количество багов коррелирует с количеством строк кода, то это получится уже не просто некая практика. Реализация функциональности с помощью меньшего объёма кода несёт реальную бизнес-ценность.

Автор: Дмитрий Брайт

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js