Как написать бота для игры жанра "Три в ряд"

Что такое бот и зачем он нужен в таком жанре?

Перед тем как погрузиться в алгоритмы, объяснения и тёмную магию, мне бы хотелось немного поговорить о ботах и зачем мне он понадобился для такого жанра как "Три в ряд". Разберёмся со всем по порядку.

Бот – это набор алгоритмов, которые в совокупности имитируют поведение живого организма или предмета в реальном мире. Стоит сразу же отметить, что бот и искусственный интеллект, два несопоставимых образа, которые не в коем случае нельзя сравнивать. Искусственный интеллект нацелен на, чтобы развиваться, становиться более эффективнее, анализировать происходящее и т.д.

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

Принцип игры тот же. Необходимо складывать комбинации из фишек. Нововведениями является то, что в игре существует два игрока. Их задача уничтожить друг друга. У игрока имеются базовые характеристики, такие как жизненные показатели, количество энергии, урон по противнику, защита и прочее. Складывая комбинацию из черепков, вы отнимаете здоровье противника. Складывая комбинации из сердечек, восстанавливаете своё. Остальные типы фишек дают прирост к энергии персонажа.

Данный проект задумывался как мультиплеерный проект, без возможности играть одиночные игры. Однако, как и во всём мире, в процессе разработки было решено добавить «Одиночную игру», что и привело к написанию данной статьи.

На этом введение можно завершить и перейти к разбору, который состоит из нескольких частей:

Как устроен алгоритм работы системы игры
Написание логики поиска комбинаций
Написание алгоритмов для выбора лучшего хода

Как устроен алгоритм работы системы жанра «Три в ряд»?

Как я уже говорил пример написания алгоритма буден представлен на примере игры DarkCaves. Поэтому хотелось бы объяснить, как устроена логика в данной игре. У каждого игрока есть 30 секунд для того, чтобы совершить ход, т.е. переместить фишки местами.

Каждая из фишек на поле имеет свой собственный идентификатор. Всего их 64, но сразу хотелось бы отметить, что по сколько для хранения используются массивы, то 1 фишка будет 0 в массиве, и для того, чтобы получить любую другую, необходимо вычесть 1.

Вот идентификаторы всего поля:

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

На всём поле создаются рандомные типы фишек. Когда процесс создания закончен, запускается процесс поиска комбинаций, который будет описан в последующих статьях на сайте. Процесс поиска комбинаций, определяет все комбинации на поле, после чего уничтожает их, не засчитывая ни какому из игроков бонусы от этой комбинации. Следующим запускается процесс, движения фишек вниз. Как понятно из названия, он сдвигает все фишки вниз, для того, чтобы не образовывались пустые места, на месте удалённых комбинаций. После чего процесс запускается по новой: создание фишек, поиск комбинаций, движение вниз. Всё это продолжается до тех пор, пока на поле не окажется ни единой комбинации. Именно в этот момент мы и запускаем бота, который должен обнаружить все возможные комбинации и сделать наиболее сильный ход.

Пример как происходит создание игровой карты можно посмотреть в видеоролике который находиться в конце статьи.

Когда поле будет сформировано в этот момент нам необходимо запустить алгоритм бота.

Логика поиска комбинаций

Что ж, сейчас мы имеем поле, состоящее из фишек, на котором не существует ни одной комбинации. Нам нужно чтобы они появились. Я несколько часов думал, на счёт того, как это реализовать с наименьшим количеством перемещения фишек. В итоге, я пришёл к следующему алгоритму:

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

Переходим к коду.

Я создам отдельный скрипт, который назову «EnemyManager». Он будет отвечать за основную логику бота. За поиск комбинаций, и сам алгоритм лучшего хода. В скрипте, создадим функцию, которая будет отвечать за старт поиска комбинаций, у меня она будет вызываться из другого скрипта:

/// <summary> /// Функция старта поиска комбинаций /// </summary> 
public void StartAnalitic() {
    allCombinations.Clear (); // очищаем список комбинаций  
    StartCoroutine (NewAnalitic ()); // вызываем корутину поиска комбинаций 
}

Как можно заметить, данная функция очищает массив с комбинациями, и вызывает корутину (Coroutine) NewAnalitic();

Корутина – это потоки исполнения кода, которые организуются поверх аппаратных (системных) потоков.

Перейдём к вызываемой корутине:

/// <summary> /// Корутина поиска комбинаций /// </summary> /// <returns>The analitic.</returns> 
IEnumerator NewAnalitic()
{
    for (int i = 0; i < controller.points.Length; i++) { // перебираем все фишки на поле // перемещаем вправо
        if (i != 7 && i != 15 && i != 23 && i != 31 && i != 39 && i != 47 && i != 55 && i != 63) { // ограничиваем крайний правый ряд
            TransformPoint(i, i + 1); // перемещаем вправо 
        } // перемещение вних 
        if (i < 56) { // ограничиваем крайний нижний ряд 
            TransformPoint(i, i + 8); // вниз 
        } yield return null; // пропускаем кадр 
    } if (Complexity == level.random) { // если уровень сложности бота рандом 
        StartCoroutine (RandomCourse ()); // выбираем рандомную комбинацию 
    } else if (Complexity == level.easy) { // если уровень бота легко 
        StartCoroutine (EasyCourse ()); // выбираем лёгкую комбинацию 
    } else if (Complexity == level.normal) { // если уровень сложносит бота нормально 
        StartCoroutine (NormalCourse ()); // выбираем нормальную комбинацию 
    }
}

Разберёмся, что здесь происходит. В первую очередь мы перебираем все фишки, которые находятся на сцене, а именно в другом скрипте «controller»в массиве points. Данный массив содержит в себе 64 элемента типа int. В каждой ячейке данного массива храниться идентификатор типа фишки, на поле. Всего таких идентификаторов в игре пять:

Синие алмазы
Жёлтые алмазы
Красные алмазы
Сердечки
Скелетики

Следующая строка, это условие, при котором будут перемещены фишки, которые находятся не в последнем правом столбце. Это условие необходимо для того, чтобы не возникало ошибок в связи с перемещением последнего столбца, в ввиду того, что нам не нужно перемещать его в правую сторону. Ибо некуда. И так, если у нас фишка не в последнем правом столбце мы вызываем функцию, которая отвечает за перемещение фишек «TransformPoint(intold, intnew)». Функция «TransformPoint»включает в себя два int’овых параметра: старая и новая позиция. Поэтому мы передаём позицию фишки, которую мы хотим переместить (i)и позицию на которою мы хотим переместить (i + 1). Тоже самое мы делаем по вертикали. Ограничиваем перемещение по вертикали. И перемещаем позицию фишки iна позицию I + 8. 8 – потому что у нас восемь элементов в строке. В самом конце, в зависимости от выбранного уровня, мы выбираем алгоритм наилучшего хода, о котором поговорим позже.

Перейдём к функции «TransformPoint()».

/// <summary> /// Функция перемещения фишек /// </summary> /// <param name="OneID">Старая позиция.</param> /// <param name="TwoID">Новая позиция.</param> 
void TransformPoint(int OneID, int TwoID) { // меняем местами фишки 
    int copyID = controller.points [OneID]; // копируем идентификатор фишки которую перемещаем 
    controller.points [OneID] = controller.points [TwoID]; // присваиваем старому идентификатору фишшки, новый идетификатор фишки 
    controller.points [TwoID] = copyID; // присваиваем новому идентификатору фишки, копированный идентификатор // фишки изменены 
    List<int> destroyPoint = Inspection (); // получаем список всех появившихся комбинаций 
    if (destroyPoint.Count != 0) { // если существуют комбинации 
        Combination newCombination = new Combination (); // создаём комбинации 
        newCombination.id = controller.points [destroyPoint [0]]; // запоминаем идентификационый номер комбинации 
        newCombination.points = destroyPoint; // запоминаем фишки для удаления 
        newCombination.count = destroyPoint.Count; // запоминаем количество фишек 
        newCombination.OneID = OneID; // запоминаем позицию перемещения старой позиции фишки 
        newCombination.TwoID = TwoID; // запоминаем позицию перемещения новой позиции фишки 
        allCombinations.Add (newCombination); // добавляем комбинацию в список всех комбинаций
    } // меняем фишки местами обратно 
    copyID = controller.points [OneID]; // копируем идентификатор фишки которую перемещаем 
    controller.points [OneID] = controller.points [TwoID]; // присваиваем старому идентификатору фишки, новый идентификатор фишки 
    controller.points [TwoID] = copyID; // присваиваем новому идентификатору фишки, копированный идентификатор 
}

Что же, вероятнее всего данный код вам покажется странным, но не стоит, так оно и есть. Разберёмся, что мы здесь делаем:

В первую очередь мы меняем местами идентификаторы фишек старой позиции и новой.
После чего функций «Inspection()»возвращает нам список фишек которые нам нужно удалить. Если список пустой, значит комбинации на поле отсутствуют. Если список не пустой, значит у нас существуют комбинации.
И так, если список не оказался пустым, мы создаём комбинацию и записываем её.
После чего, меняем фишки обратно на свои же места.

Такой алгоритм происходит с 56 фишками, перемещая каждую из них вправо и вниз.

Осталось только вставить код функции «Inspection()».

List<int> Inspection()
{
    List<int> DestroyPoint = new List<int>();
    for (int i = 0; i < 64; i++) { // по вертикале 
        if (i < 48) {
            if (controller.points [i] == controller.points [i + 8]) {
                if (controller.points [i] == controller.points [i + 16]) {
                    if (i + 24 < 64 && controller.points [i] == controller.points [i + 24]) {
                        if (i + 32 < 64 && controller.points [i] == controller.points [i + 32]) {
                            DestroyPoint.Add (i);
                            DestroyPoint.Add (i + 8);
                            DestroyPoint.Add (i + 16);
                            DestroyPoint.Add (i + 24);
                            DestroyPoint.Add (i + 32);
                        } else {
                            DestroyPoint.Add (i);
                            DestroyPoint.Add (i + 8);
                            DestroyPoint.Add (i + 16);
                            DestroyPoint.Add (i + 24);
                        }
                    } else {
                        DestroyPoint.Add (i);
                        DestroyPoint.Add (i + 8);
                        DestroyPoint.Add (i + 16);
                    }
                }
            }
        } // горизонталь 
        if (i != 6 && i != 7 && i != 14 && i != 15 && i != 22 && i != 23 && i != 30 && i != 31 && i != 38 && i != 39 && i != 46 && i != 47 && i != 54 && i != 55 && i != 62 && i != 63) {
            if (controller.points [i] == controller.points [i + 1]) {
                if (controller.points [i] == controller.points [i + 2]) {
                    if (i + 3 < 63 && (i + 3 != 8 && i + 3 != 16 && i + 3 != 24 && i + 3 != 32 && i + 3 != 40 && i + 3 != 48 && i + 3 != 56) && controller.points [i] == controller.points [i + 3]) {
                        if (i + 4 < 63 && (i + 4 != 8 && i + 4 != 16 && i + 4 != 24 && i + 4 != 32 && i + 4 != 40 && i + 4 != 48 && i + 4 != 56) && controller.points [i] == controller.points [i + 4]) {
                            DestroyPoint.Add (i);
                            DestroyPoint.Add (i + 1);
                            DestroyPoint.Add (i + 2);
                            DestroyPoint.Add (i + 3);
                            DestroyPoint.Add (i + 4);
                        } else {
                            DestroyPoint.Add (i);
                            DestroyPoint.Add (i + 1);
                            DestroyPoint.Add (i + 2);
                            DestroyPoint.Add (i + 3);
                        }
                    } else {
                        DestroyPoint.Add (i);
                        DestroyPoint.Add (i + 1);
                        DestroyPoint.Add (i + 2);
                    }
                }
            }
        }
    }
    return
        DestroyPoint;
}

Я не оставлю ни каких комментариев к данному коду, поскольку он будет описан в последующих статьях на нашем сайте. Разве что, только это. Данный алгоритм берёт фишку на поле и проверяет существует ли комбинация с участием этой фишки. Если комбинация существует, он записывает позиции фишек, после чего возвращает список этих самых фишек. Функция подходит только для поля 8х8, на других полях она не будет работать.

Всё что осталось сделать, так это вставить некоторые переменные, которых не хватает.

[System.Serializable] // класс комбинаций 
public class Combination {
    public int id = 0; // идентификатор комбинаций    
    public List<int> points = new List<int>(); // список удаляемых точек  
    public int count = 0; // количество удаляемых точек   
    public int OneID = 0; // позиция фишки для перемещения  
    public int TwoID = 0; // позиция фишки для перемещения 
} public enum level {
    random,
    easy,
    normal,
    hard
}
public SingleGameController controller; // ссылка на скрипт контролера 
public level Complexity; // настройка уровня сложности
[Space(10)]
public List<Combination> allCombinations = new List<Combination>(); // все комбинацииy

Перейдём к разбору кода:

Класс Combination– это класс который содержит в себе данные о комбинации.
Enum – своего рода объект, который позволяет выбрать уровень бота.
SingleGameController – скрипт который отвечает за основную логику на сцене, именно там хранятся данные о местоположении фишек и прочее.
Последние переменные нужны для того, чтобы обратиться к созданным объектам.

На этом алгоритм работы с поиском комбинаций заканчивается и выглядит следующим образом.

Гиф анимация, как работает бот получает комбинации.

Алгоритм для лучшего хода

Здесь вы можете написать всё что угодно. Вы можете брать случайную комбинацию и использовать её. Или же вы можете найти комбинацию, где для удаление задействовано как можно больше фишек.

Для того, чтобы переместить фишки, вам нужно будет задействовать собственный алгоритм перемещения. Поскольку до создания бота в игре использовался мультиплеер, в моём случае это было уже реализовано и данный алгоритм не подойдёт для использования в вашем проекте.

Так же хотелось бы привести некоторый пример алгоритма лучшего хода. В данном примере используется несколько уровней сложности. В зависимости от того, что будет выбрано в редакторе или же установлено программным путём, будет выполняться та или иная функция.

Уровень сложности: рандом.

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

Уровень сложности: легко.

Здесь всё немного сложнее. Данный алгоритм выполняется в несколько этапов. Этап не может быть выполнен если уже был выполнен этап, находящийся выше.

И так,

Если жизненные показатели бота меньше чем 50%, используются случайная комбинация из все доступных комбинаций для восстановления здоровья.
Если предыдущий этап не был выполнен, то используется случайная комбинация из все доступных комбинаций для нанесения урона.
Если предыдущие этапы не были выполнены, то используется случайная комбинация из все доступных комбинаций для восстановления здоровья.
Если предыдущие этапы не были выполнены, то используется случайная комбинация из все доступных комбинаций.

Уровень сложности: нормально.

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

Что касается последнего уровня – сложно, так это то что он находится на этапе разработки.

Реализация бота игры жанра «Три в ряд» закончена.

Пример работы бота с уровнем сложности «нормально» можно посмотреть здесь:

Автор статьи: Александр Каримов.

4.25/5 (6)