Алгоритм генерации гирлянды для новогодней головоломки
Чтобы занять себя как-то бессонными ночами, опять засел за написание игрушек под Android. Так как скоро новый год, то решил, что игрушка должна быть новогодней. Для меня неотъемлемой частью нового года и новогодней ёлки является гирлянда, так что решение идея пришла сама — буду делать головоломку — собери гирлянду. В процессе разработки, для меня было два интересных момента:
1. Генерация гирлянды.
2. Работа с платежами в Google Play.
Вот об этом я и расскажу подробнее ниже…
Итак, задумка игры приведена на скриншоте:
Точнее это скриншот того, что получилось, но собственно, именно это и задумывалось изначально.
Основная задача была придумать алгоритм генерации гирлянды, чтобы каждый раз она была новая, и играть было интересно.
Немного почитав про различные алгоритмы генерации различных графических структур, пришёл к выводу, что наиболее близким к моей задаче является алгоритм генерации лабиринтов.
Так как новый год всё ближе и ближе, то взял, на мой взгляд, самый простой и далеко не самый оптимальный алгоритм генерации лабиринтов, который был найден на Хабре.
Но его пришлось немного дополнить — пришлось добавить в каждую клетку информацию о соединении со смежными клетками, или если клетка тупиковая, то необходимо знать с какой стороны в эту клетку пришли.
Таким образом, каждой стороне клетки присвоено значение 1,2,4 или 8. Ну или чтобы было понятнее 0001, 0010, 0100, 1000.
Теперь алгоритм будет выглядеть следующим образом:
- Задаём начальную клетку и указываем с какой стороны на данную клетку пришли (например, пришли снизу);
- Делаем начальную клетку текущей и присваиваем клетке значение стороны, смежной с клеткой от куда пришли на текущую клетку (например, если пришли с нижней клетки, то начальное значение текущей клетки будет равно 4);
- Ищем свободны соседей у текущей клетки;
- Если есть свободные соседи, то:
- Если свободных соседей нет, то:
- Повторяем шаги со 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(); // теперь надо всё перемешать, то есть все элементы гирлянды будут повёрнуты в случайном порядке.
}
Как оказалось, сгенерировать гирлянду очень просто.
Теперь немного о самой игре.
Правила очень простые:
1. Вращая элементы гирлянды необходимо зажечь все лампы, после чего загорится звезда на ёлке;
2. Должны быть задействованы ВСЕ элементы гирлянды;
3. Источник питания находится в правом нижнем углу. При подключении к источнику питания, провода светлеют, и если ток доходит по проводам до лампы, то она загорается;
4. В гирлянде не может быть петель, то есть путь до лампы всегда однозначен;
5. К лампочке должен подходить провод только с одной стороны.
А теперь ссылка на саму игрушку в Google Play
С Наступающим Новым Годом! и пусть он будет интереснее предыдущих!
P.S. Во второй части статьи про данную игрушку я расскажу, как работал с платежами в Google Play.
