Алгоритм генерации гирлянды для новогодней головоломки

в 5:49, , рубрики: android, Алгоритмы, Лабиринт, я пиарюсь

image Чтобы занять себя как-то бессонными ночами, опять засел за написание игрушек под Android. Так как скоро новый год, то решил, что игрушка должна быть новогодней. Для меня неотъемлемой частью нового года и новогодней ёлки является гирлянда, так что решение идея пришла сама — буду делать головоломку — собери гирлянду. В процессе разработки, для меня было два интересных момента:

1. Генерация гирлянды.
2. Работа с платежами в Google Play.

Вот об этом я и расскажу подробнее ниже…

Итак, задумка игры приведена на скриншоте:

image

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

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

Так как новый год всё ближе и ближе, то взял, на мой взгляд, самый простой и далеко не самый оптимальный алгоритм генерации лабиринтов, который был найден на Хабре.

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

Таким образом, каждой стороне клетки присвоено значение 1,2,4 или 8. Ну или чтобы было понятнее 0001, 0010, 0100, 1000.

image

Теперь алгоритм будет выглядеть следующим образом:

  1. Задаём начальную клетку и указываем с какой стороны на данную клетку пришли (например, пришли снизу);
  2. Делаем начальную клетку текущей и присваиваем клетке значение стороны, смежной с клеткой от куда пришли на текущую клетку (например, если пришли с нижней клетки, то начальное значение текущей клетки будет равно 4);
  3. Ищем свободны соседей у текущей клетки;
  4. Если есть свободные соседи, то:
  5. Если свободных соседей нет, то:
  6. Повторяем шаги со 2-го, пока есть клетки в стеке.

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

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

public void init() {

        clearGarland();  // заполняем массив гирлянды нулями
        FIFOStack.clear(); // очищаем переменную, содержащую FIFO стэк 

        Cell currentCell = new Cell(garlandWidth-1,garlandHeight-1,1); // задаём начальную клетку и начальное значание, от куда на данную клетку пришли

        boolean generationtree = true;

        int garlandLength = 0; // счётчик длины луча гирлянды
        int maxGarlandLength = 5; // максимальное значение длины луча гирлянды

        do {
            switch(currentCell.Position) {  // задаём начальное значение текущей клетки
                case 1: // пришли на клетку снизу
                    garland[currentCell.X][currentCell.Y][0] = 4;
                    break;
                case 2: // пришли на клетку слева
                    garland[currentCell.X][currentCell.Y][0] = 8;
                    break;
                case 4: // пришли на клетку сверху
                    garland[currentCell.X][currentCell.Y][0] = 1;
                    break;
                case 8: // пришли на клетку справа
                    garland[currentCell.X][currentCell.Y][0] = 2;
                    break;
                case 0: // взяли клетку из стека
                    break;
            }

            Cell[] neighbCells = searchNeighbours(currentCell); // Ищем свободных соседей, то есть клетки с нулевым значением;

            int neighbCount = 0;   // счётчик свободных соседей
            // Считаем сколько соседей нашли - если значение переменной X соседней клетки в строке массива больше 0, значит количество свободных соседей увеличиваем на 1
            for(int z=0;z<4;z++) {
                if (neighbCells[z].X >= 0) {
                    neighbCount++;
                }
            } // по результатам цикла имеем массив с клетками свободных соседей, и количество свободных соседей


            if ((neighbCount>0)&&(garlandLength < maxGarlandLength)) {  // проверяем, что есть свободные соседи и что текущее значение длины луча не превысило заданное максимальное значение 
                FIFOStack.push(currentCell); // помещаем в стек текущую клетку
                int randomCell = randomizer.nextInt(neighbCount); // выбираем случайного свободного соседа
                garland[currentCell.X][currentCell.Y][0] = garland[currentCell.X][currentCell.Y][0]+neighbCells[randomCell].Position; // увеличиваем значение текущей клетки на значение стороны, смежной с выбранным соседом
                currentCell = neighbCells[randomCell]; // делаем выбранную соседнюю клетку текущей
                garlandLength++; // увеличиваем счётчик длины луча гирлянды
            } else { // в случае если свободных соседей нет, или достигли максимальной длины луча гирлянды
                garlandLength = 0;  // обнуляем счётчик
                currentCell = FIFOStack.get(); // в качестве текущей клетки делаем первое значение из стека (обращаю внимание что стек - FIFO)
                currentCell.Position = 0;
                if (currentCell.X == -1) generationtree = false; // если стек кончился, то флагу генерации гирлянды присваиваем значение false
            }
        } while (generationtree); 

// гирлянда сгенерирована
// при отображении гирлянды, клетки со значениями 1,2,4,8 будут отображаться как лампы, а клетки с остальными значениям (3,5,6,7,9,10,11,12,13,14,15) отображаться как провода (элементы гирлянды) для лучшей наглядности привёл скриншот после раздела кода. 

        randomizeTree(); // теперь надо всё перемешать, то есть все элементы гирлянды будут повёрнуты в случайном порядке.
    }

image

Как оказалось, сгенерировать гирлянду очень просто.

Теперь немного о самой игре.

Правила очень простые:

1. Вращая элементы гирлянды необходимо зажечь все лампы, после чего загорится звезда на ёлке;
2. Должны быть задействованы ВСЕ элементы гирлянды;
3. Источник питания находится в правом нижнем углу. При подключении к источнику питания, провода светлеют, и если ток доходит по проводам до лампы, то она загорается;
4. В гирлянде не может быть петель, то есть путь до лампы всегда однозначен;
5. К лампочке должен подходить провод только с одной стороны.

А теперь ссылка на саму игрушку в Google Play

С Наступающим Новым Годом! и пусть он будет интереснее предыдущих!

P.S. Во второй части статьи про данную игрушку я расскажу, как работал с платежами в Google Play.

Автор: rlepricon

Источник

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


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