Пятнашки

Пятнашки - это классическая игра из серии перестановочных (комбинаторных) головоломок с полем 4 на 4 клетки, в которой установлены 15 фишек с номерами от 1 до 15. Задача игрока разместить все фишки в порядке возрастания номеров сверху вниз справа налево . Пустой должна остаться только нижняя правая клетка. За один ход фишку можно двигать только в соседнюю пустую клетку.

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

Всего у данной игры существует порядка 10 триллионов разрешенных комбинаций. Доказано, что самые сложные комбинации решаются максимум за 80 ходов (Число Бога)

Подготовительная часть

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

Если будете писать код самостоятельно то вам нужно будет решить ряд вопросов: как вы будете представлять (как хранить и что хранить) игровое поле, как вы будете проверять существует ли допустимый ход для фишки на которую кликнул игрок и так далее. Продумайте проверку условий победы. Как вы будете иницилизировать стартовое поле игры.

В первую очередь решите подводящую задачу, а именно: генерация поля со всеми установленными фишками на своих местах (1 в первой клетке, 2 во второй и так далее) и просто проверьте что перемещение фишек осуществляется правильно.

На этом этапе ваша программа должна выглядеть и работать примерно следующим образом:

Добавляем машину состояний

Введите машину состояний (флага bool gameOver будет достаточно)

Для проверки работоспособности сгенерируйте уровень в котором последняя фишка будет не на своем месте (чтобы игра сразу не перешла в состояние game over и вы успели проверить логику работы)

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

Добавим визуальное оформление (опционально)

Для улучшения внешнего вида, можно сделать наши блок псевдо-трехмерными, для этого можно скопировать код из урока тетрис анимация

Получим примерно такой результат

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

Инициализация уровня (поля)

Теперь рассмотрим генерацию игрового поля. Если мы будем генерировать стартовые позиции фишек случайным образом, то в половине случаев это будут не решаемые комбинации (infeasible state). Нужно либо генерировать фишки случайным образом накладывая на них проверку на решаемость, либо из решенного состояния делать ходы оставаясь все время в области допустимых состояний (feasible region).

Рассмотрим все эти способы более подробно.

Способ 1: Случайный набор ходов

Из финального положения можно произвести N допустимых ходов. Это будет гарантировать, что получаемое состояние доски на каждом шагу имеет решение.

Опишем функцию хода:

public void Turn(int col, int row)
{
    var val = board[col, row];
    //check 4 directions
    if (row > 0 && board[col, row - 1] == 0) // check up and move if empty
    {
        board[col, row] = 0;
        board[col, row - 1] = val;
    }
    else
    if (col > 0 && board[col - 1, row] == 0) // check left and move if empty
    {
        board[col, row] = 0;
        board[col - 1, row] = val;
    }
    else
    if (row < 3 && board[col, row + 1] == 0) // check down and move if empty
    {
        board[col, row] = 0;
        board[col, row + 1] = val;
    }
    else
    if (col < 3 && board[col + 1, row] == 0) // check right and move if empty
    {
        board[col, row] = 0;
        board[col + 1, row] = val;
    }
}

Теперь при каждой инициализации уровня будет осуществлять N случайных шагов

// функция осуществялютщая N случайных ходов
public void RandomMoves(int N)
{
    for (int i = 0; i < N; i++)
    {
// ищем позицию пустой клетки
        var empty = GetEmptyPoint(board).Value;

// расчтитывает координаты 4х соседних клеток
        var up = new Point(empty.X, empty.Y - 1);
        var down = new Point(empty.X, empty.Y + 1);
        var left = new Point(empty.X - 1, empty.Y);
        var right = new Point(empty.X + 1, empty.Y);

        Point[] moves = new[] { up, down, left, right };
// фильтруем ходы и оставляет только те которые лежат в пределах игоровго поля
        moves = moves.Where(z => z.X >= 0 && z.X <= board.GetUpperBound(0)
        && z.Y >= 0 && z.Y <= board.GetUpperBound(1)
        ).ToArray();
//выбирай случайным образом ход из списка допустимых
        var move = moves[rand.Next(moves.Length)];
//осуществляем ход (перемещение указанной фишки)
        Turn(move.X, move.Y);
    }
}

Преимущества: легкость реализации

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

Способ 2: Случайная генерация с проверкой на достижимость

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

Алгоритм следующий:

Для проверки является ли позиция фишек валидной или нет, нужно посчитать количество инверсий в одномерной версии нашего массива представляющего игровое поле (пройтись по нему сверху вниз справа налево и собрать все фишки в список игнорируя 0). Инверсией называется расположение числа a левее в массиве чем число b, при условии что a > b. Далее найти номер строки снизу в которой находится пустая ячейка, сложить эти два числа и проверить на четность. Если число окажется четное то данный набор фишек имеет решение.

static bool isSolvable(int[,] puzzle)
{
    List<int> puzzle1D = new List<int>();
    for (int i = 0; i < puzzle.GetLength(0); i++)
    {
        for (int j = 0; j < puzzle.GetLength(1); j++)
        {
            if (puzzle[i, j] == 0)
                continue;

            puzzle1D.Add(puzzle[i, j]);
        }
    }

    //calc inversions
    int invQty = 0;
    for (int i = 0; i < puzzle1D.Count; i++)
    {
        for (int j = i + 1; j < puzzle1D.Count; j++)
        {
            if (puzzle1D[i] > puzzle1D[j])
                invQty++;
        }
    }
    
    return (findEmptyRowIdx(puzzle) + invQty) % 2 == 0;            
}


static int findEmptyRowIdx(int[,] puzzle)
{            
    for (int i = puzzle.GetUpperBound(0); i >= 0; i--)
    {
        for (int j = puzzle.GetUpperBound(1); j >= 0; j--)
        {
            if (puzzle[i, j] == 0)
                return puzzle.GetUpperBound(0) - i;
        }
    }
    return -1;
}

Преимущества: позволяет получать сколько угодно сложные доски от самых простых до самых сложных (потому что генерация позиций случайная)

Недостатки: невозможно контроллировтаь сложность

Из возможных улучшений для контроля сложности, можно использовать эвристики вроде дистанций фишек от их целевых позиций (Манхетенское расстоние еще известное как taxicab), тем самым косвенно предсказывать сложность раскладки.

Способ 3: Поиск в пространстве вариантов

Этот способ хорош тем, что мы можем подсчитать количество необходимых ходов для завершения игры (подсчитано, что максимальное возможное количество ходов для решения этой игры равно 80). Тем самым (в будущем) мы сможем ввести уровни сложности игры (давать игроку право выбрать сложность игры). Для поиска стартового состояние обычно используют эвристичесвкие алгоритмы поиска в графе пространства вариантов (например, A*) с запоминанием посещенных состояний.

Проблема заключается в том, что поиск в графе с 10 триллионам узлов весьма сложная задача, для ее решения используются различные оптимизированные алгоритмы вроде IDA* и эвристики вроде WD (walk distance). Встраивать такие сложные вещи в простую игру нет смысла, лучше отдельно сгенерить наборы досок для разных уровней сложности (скажем по 20 штук на каждый уровень сложности) и прикрепить их как ресурс к нашей игре, а далее просто случайным образом выбирать из заранее сгенерированных уровней.

Для того чтобы сгенерировать уровни можно воспользоваться готовым солвером (https://github.com/hkociemba/FifteenPuzzle )

Всего существует 17 уровней требующих минимум 80 ходов для решения. Все эти уровни представлены на сайте здесь (https://kociemba.org/themen/fifteen/fifteensolver.html)

На самом деле, для игры пятнашки даже самые сложные уровни (80 ходов), не вызывают особой сложности когда их решает человек. Первые две верхние строки собираются всегда одинаково легко, а нижние две строки собираются тоже примерно всегда одинаково. Сложность расчетов игры пятнашки интересна в первую очередь академически, для компьютерных алгоритмов поиска. Поэтому уровни сложности в данной игре не очень наглядны. Но в следующих играх уровни сложности будут регулироваться гораздо проще и понятнее, более линейно (количество врагов и т.д.)

Пример решения раскладки на 80 ходов:

Полный код примера можете посмотреть здесь

Задания:

1. Добавить анимацию перемещения фишек

2. Реализуейте в игре первый способ генерации уровней

3. Реализуйте в игре второй способ генерации уровней

4. Реализуйте в игре третий способ генерации уровней (загружать из ресурсов заранее сгенерированные уровни)

5. Сделайте возможность переключать визуальное оформление (например, нажимая кнопку V на клавиатуре)