История того, как задача на динамическое программирование стала идеей для игры и изменила отношение к работе

^{*Картинка для привлечения внимания}

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

Идея

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

Вот пример самой простой из них:

Даны N последовательных столбиков.
Кузнечик стоит на первом и умеет прыгать на 1 и 2 столба вперед.
Сколькими способами он может припрыгать к N-ому столбику?

Решение на вашем любимом языке программирования далось легко? Разумеется. Но как часто вы сами прибегали к счетной работе, используя вычислительные мощи собственного мозга ^[1]?

Давайте изменим условие:

Даны N последовательных столбиков.
Кузнечик стоит на первом и умеет прыгать на 1 и 2 столба вперед.

На каждом столбике кузнечик может получить золото или потерять его. Также, на некоторых столбиках сидят «кузнечикоеды», так что такие столбы нужно перепрыгивать.

Какое наибольшее количество золота он может иметь, допрыгав до N-ого столбика?

Думаю, читатель уже догадался о задумке, которая посетила меня однажды утром. Идея мне понравилась. Особенно потому, что я в последнее время плохо лажу с цифрами и хотелось немного это дело исправить. Однако идея очень нескоро начала движение к реализации…

Долгое время меня терзали вопросы:" Потяну ли? Или буду целый год тратить на написание такой простой игры?", «А оно мне вообще надо?», «А кто-нибудь, кроме меня, будет в нее играть?», «Я ведь не дизайнер и рисовать не умею, что делать с этим?», «А так ли хороша идея, как мне кажется?».
Т.к. я не отличаюсь спешностью мышления ^[1], эти вопросы оставались открытыми больше месяца, пока я не увидел рисунки одного своего знакомого. Я знал, что он неплохо разбирается в Photoshop'е, но никогда не видел его собственных рисунков (а не отретушированных фотографий). Практически сразу вслух выпалил мысль: «А может, ты хочешь попробовать себя в дизайне? У меня есть идея для игры на телефон...». Рассказал об идее, ему понравилось. Таким образом превратились мы в дуэт.

Начало

В тот же день создал проект в Android Studio (пользуюсь только ей. Объективных причин, почему она мне нравится больше Eclipse, назвать не могу. Скорее всего, имя Google являлось решающим фактором), почитал о разных движках(немного), пришел к выводу, что не хочу ими пользоваться, а написать небольшой свой, пусть и по туториалам «для чайников». Обзавелся книжкой Марио Цехнера (создатель libgdx), обрывками почитал — очень неплохо.
Структуру проекта я сделал почти идентичной с той, что предложил Марио (если не ошибаюсь, она же и пошла в основу libgdx), многие куски кода попросту «слизал» из книги. Когда основные интерфейсы, классы и их реализации были готовы, тут же сделал «скелет» игры, который вы увидели в изображении вверху.
Кузнечик уже прыгал при одиночном касании экрана на один столб вперед, а при двойном — на два. Дальнейшая разработка сводилась к «засовыванию» в скелет внутренних органов: очки(монеты), «генератора уровней» и т.п.; а так же к «натягиванию» кожи: спрайты, какая-нибудь анимация ну и т.д.
Мне казалось странным, что я до начала работы над игровой логикой, решил, что важнее сделать общий вид игры и реализовать что-то вроде анимации прыжка. Но такая стратегия себя оправдала — это действительно очень удобно, когда каждый аспект игры я реализовывал и сразу же видел его в действии. В другом случае мне бы пришлось делать игровую логику и отлаживать её с помощью консолек и т.п.
Приведу аналогию: либо я строю фундамент дома, а потом исходя из него начинаю делать оставшиеся строительные блоки, либо я сразу же делаю основные строительные блоки, потом пытаюсь сделать фундамент, чтобы как-то собрать их вместе.

Период «застоя»

Далее работа застопорилась, в виду отсутствия хороших идей для дизайна (в основном связанного с внешним видом игры).
Странно, но меня всегда они волнуют больше всего остального: «Главное — дизайн, а остальное я в состоянии сделать достаточно быстро и качественно».
После месяца раздумий и небольших дискуссий с моим новоиспеченным «дизайнером», он создал кузнечика, которого я назвал Грейс (вообще-то, это женское имя, но я дал его, т.к. кузнечик по-английский «grasshopper») и сразу же внес в игру:

Технический момент: анимация прыжка

Анимация прыжка весьма проста.
Во-первых следует помнить, что нам не нужно сдвигать кузнечика относительно оси X, т.к. нам нужно знать лишь то, сколько очков мы получим на следующих столбиках(я назвал их колоннами(columns)) => нам достаточно поднимать его вверх и опускать.
У кузнечика есть 3 позы, соотв. 3 картинки: standing (стоячее положение), landing(приземление) и jumping (выпрыгивание).
Поскольку изображения маленькие, а прыжок быстрый, то я пошел на такие упрощения:
1) Физика не нужна. Ради чего? Прыжка на 0.3 секунды?
2) Длительность прыжка на короткую и дальнюю дистанцию будет одинаков по времени => и анимация будет одинакова, просто будет меняться скорость «движения» колонн. Тут я сделал небольшой трюк: анимация для обоих прыжков действительно практически одинаковая, но высота, на которую поднимается кузнечик — разная. Делается одной строчкой кода, но при этом прыжок становится заметно натуральнее.

Метод класса Grasshopper

public void update(long deltaTime) {
	if (readyToJump) {
		return;
	}
	long currentTime = System.currentTimeMillis();
	if(currentTime - jumpStartTime >= CONST.GameScreen.FLYING_TIME ){
		currentPose = standing;
		readyToJump = true;
		landingTime = System.currentTimeMillis();
		y = destinationY();
	}
	else if(currentTime - jumpStartTime > UP_TIME) {
		currentPose = landing;
		y += (int)(downSpeed * (float)deltaTime);
	}
	else {
		y -= (int)(upSpeed * (float)deltaTime);
	}
}

Что за страшная штука CONST, я объясню позже.
Думаю, все достаточно ясно:
есть две скорости: скорость подъема и скорость снижения, причем они равны, просто знак разный. Не помню, зачем я выделил их в две переменные, скорее всего, ради читаемости, ну и для дальнейшей перспективы изменения анимации(спорный момент). Само время прыжка просто делим на две равные части: взлет и снижение.
destinationY() — метод, который возвращает точное число, на котором должен находиться кузнечик по оси Y уже после прыжка. Это сделано, т.к. вычисления происходят в дробном формате и приводятся к целочисленному => где-то возможны «сдвиги» координат. Потери эти незначительны на каждый отдельно взятый прыжок, поэтому это выравнивание проходит незаметно.

После появления кузнечика, работа опять застопорилась. На месяц.

Стартуем!

В один прекрасный момент до меня дошло (долго же оно шло, да?), что мой дизайнер «отвалился» и надеяться осталось только на себя. Определился, что оформление будет достаточно простое: пни; монетки; то, что их отбирает; какая-нибудь текстурка снизу. Фон я подсмотрел у какого-то фан-арта игры «Братья Марио» — просто синий линейный градиент (делается практически одной строчкой в Anroid-классе Canvas).
После пары часов перебора картинок в Гугле (живу на Камчатке, интернет здесь… в общем, об этом надо писать в темах для нытья на форумах), нашел один неплохой мультяшный пень, отфотошопил его (да-да, мне стыдно, я даже не посмотрел, откуда я его вытянул) и добавил в игру.
Также сделал «генератор уровней» (о нем чуть-чуть ниже), а т.к. монеток у меня еще не было, сделал просто вывод текста. Получилось вот так:

Симпатично, не правда ли?

Технический момент: «генератор уровней»

Уровни я изначально планировал делать вручную, но решил, что это неподъемная и слишком тяжелая задача для меня, поэтому сделал генерацию рандомной.

Класс привожу урезанный: некоторые методы пусты, а некоторые и вовсе не приведены, поскольку их реализация не очень важна:

private class GameLevel {
	private int[] cols;
	private boolean[] badCols;
	private int next;
	public static final int BAD_COLUMN = -10000;
	public static final int LAST_COLUMN = 5000;

	public int countMaximum() {

	}

	public void generateRandom() {
		cols = new int[40 + random.nextInt(15) + 1]; // 1 => end
		badCols = new boolean[cols.length];
		for(int i = 0; i < cols.length - 1; i++) {
			if(i > 0 && !badCols[i-1])
				badCols[i] = random.nextInt(100) < 15; // 15%
			else
				badCols[i] = false;

			if(!badCols[i]) {
				cols[i] = -100 + random.nextInt(160);
				if(cols[i] > 0) {
					if(cols[i] < 20)
						cols[i] = 10;
					else if(cols[i] < 40)
						cols[i] = 25;
					else
						cols[i] = 50;
				}
			}
		}

		badCols[badCols.length - 1] = false;
		cols[cols.length - 1] = LAST_COLUMN;
		next = 0;
	}


	public boolean end() {
		return next >= cols.length;
	}

	public int next() { 
		if(end() || badCols[next]){
			next++; // overflow?
			return BAD_COLUMN;
		}
		else
			return cols[next++];
	}
}

*Разумеется, это уже последняя версия кода (только что скопировал из IDE), ранняя была попроще, поэтому некоторые моменты, о которых я расскажу сейчас, на момент времени, в который сделан скриншот выше, отсутствовали вовсе.

Тут есть некоторые спорные моменты, такие как использование констант BAD_COLUMN и LAST_COLUMN, но сам по себе класс достаточно простой, и я не хотел терять много времени на его реализацию и допиливание.
Как вы уже могли заметить, это не совсем генератор. Это класс самого уровня, в котором есть метод-генератор.

Комментарии:
1) Возможно, вас смущают magic-numbers в рандомах. Меня, если честно, тоже. Чуть-чуть. В целом, такое немного корявенькое использование рандома позволяет добиться появления на колоннах положительных и отрицательных очков с какой-то вероятностью.
Так же следует отметить, что «положительные» очки у меня бывают всего-лишь в трех проявлениях: 10, 25, 50. Это связано с тем, что для игры не важны положительные очки, они играют скорее «украшательскую» роль. Сами подумайте, при игре, пользователь будет собирать все монетки, которые ему будут попадаться. Задумываться он будет только над местами, где подряд стоят отрицательные очки. Обратите внимание, с какой вероятностью появляются положительные, а с какой отрицательные очки. Это немаловажно и еще будет изменяться в будущем (мне кажется, в игре слишком много золота).
2) Для чего нужен метод next()? О, это оказалось весьма удобным решением. Когда мы прыгаем на следующий столб, предыдущий пропадает из виду, а из-за «кулис» приходит новый. Вот тут-то и включаются классы GameLevel и Pool (подсмотрел его у Цехнера. Создан ради того, чтобы не инстанцировать каждый раз новые классы, а использовать уже созданные). Из пула выдергивается пень, а очки (я их назвал loot) дает нам уровень. Кстати, при достижении последнего пня, уровень следующими выдает нам пропасть. Т.е. пней как бы нет, но они как бы есть. Это позволяет не писать дополнительных условий в методе, который добавляет пень на экран (вместо проверок на нуль и т.п. просто добавляем пень).
3) countMaximum() просто с помощью всем (кто это читает) известного метода динамического программирования находит максимальное кол-во очков, которые можно набрать на уровне. Можно было даже оптимизацию не проводить, лишь бы работало.

Далее мой мозг ^[1] пытался придумать, на что будет тратиться кузнечик во время путешествия по пням (отрицательные очки). Изначально я хотел поставить какие-нибудь ларьки и сказать: «Грейс обожает конфеты и никогда не проходит мимо ларька с ними», но решил, что это слишком.
Потом меня просто осенило: «Почему бы другим жадным насекомым не отбирать их у него?».
Читатель, наверное, уже догадался, кто именно стал этим алчущим насекомым:

Обратите внимание, что пни стали ниже и появились кнопки (неужели, кто-то не заметил их?). Это важный момент, о нем чуть ниже.
Сами картинки были слизаны с какой-то школьной олимпиады по биологии. Думаю, они несильно обидятся. Таблички генерируются достаточно просто: в Paint.NET нарисовал табличку, взял ее координаты относительно изображения, сделал атлас с цифрами от 0 до 9-ти и просто поциферно справа-налево вывожу.

Гейм-дизайн: кнопки

Изначально метод управления был таков: 1 тап — прыжок на один, 2 тапа — прыжок на два.
Почему же я решил сменить его на кнопки, хотя это не модно, да и упрощает игру? Ответ прост: я не хочу, чтобы пользователь ошибался. «Но в чем же тогда сложность игры?!» — спросите вы, но и тут ответ несложный: я хотел сделать игру достаточно простой и чтобы вся нагрузка была на «вычислительный центр» мозга ^[1] игрока. Кнопки — это просто и удобно и также снижает вероятность глупой ошибки.
Вот такие мысли я считаю очень важными в любом учебном проекте. Таким образом, до меня стало доходить, что дизайн — это не только красивое оформление, но и общее юзабилити (да и мало ли что еще?).

Технический момент: организация работы

Очень удобно оказалось записывать фичи, которые хотелось бы увидеть, а потом их выборочно реализовывать. Я пользовался Evernote на своем телефоне. Вот старый скрин:

На самом деле, я не очень часто туда заглядывал, но само по себе его написание навело порядок в моей голове. Многие задачи от туда до сих пор не выполнены, а некоторые попросту отбракованы, например, под записью про сейвы появился такой комментарий: "upd. нафига?".

Гейм-дизайн: добавление сложности

Хоть я и писал выше, что хотел сделать игру очень простой, но согласитесь, что сама по себе эта задачка с нахождением оптимального пути довольно простая. Поэтому мне потребовался ограничивающий время на раздумья фактор.
Изначально я думал, что это будет некий бульдозер/комбайн, который будет вырубать лес (хотелось поднять еще и экологическую проблему), но тут на меня снизошло озарение: у меня кузнечик размером с пень, собирает монетки, а жадные муравьи с табличками, отбирают их у него. Наркомания.
Плюнул и решил сделать временное решение, чтобы сам принцип игры попробовать. Накидал «врага» за 5 минут в Paint.NET:

^{Запустив и узрев дело рук своих, я долго и истерично ржал}

Играть стало заметно тяжелее, оставалось только «подогнать» его под игру.
Что меня конкретно не устраивало:
он двигался либо слишком медленно, что за пару прыжков можно было уйти в сильный отрыв и сидеть тупить, либо слишком быстро, тогда при появлении его морды в «кадре» практически сразу игра завершалась.

Как решать? Можно посидеть и подобрать оптимальную скорость.
Но тогда есть проблема: люди разные, поэтому для кого-то скорость может оказаться слишком большой, а для кого-то слишком маленькой.

Как решать эту проблему?
Я думал вести статистику и увеличивать/уменьшать скорость в зависимости от нее. Но мне было лень.
Тогда на ум пришло гениальное (да-да, я нескромно считаю его гениальным) решение:
Зачем вообще ему пытаться сделать так, чтобы игрок проиграл? Почему бы просто не держать его в постоянном напряжении?
Тогда я взял и увеличил скорость «за кадром» в десять раз. Тогда он появляется очень часто, но при этом умереть от него достаточно сложно, ибо он весьма медлителен. Т.е. его появление заставляет игрока решать текущую ситуацию на экране быстрее, но при этом не дает ему проиграть (грубо говоря).

Финишная прямая

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

Как видите, я корректировал множество вещей:
Цветовую яркость муравьев, подкрасил кузнечика, изменил размер муравьев и их табличек, даже рамку на табличках пришлось сделать толще!

Кстати, вы заметили, что я так и не убрал черное чудище? Просто я к нему привязался. Пусть он и не вписывается в картинку, но выглядит он комично. Я даже имя ему дал: «мистер Чозанафиг»:) При написании «хелпа» его имя превратилось в «mr Whathell» (мистер Вотхелл). Игра букв — фамилия создана из известного ругательства, в котором «склеены» одинаковые буквы. Помогали мне мои хорошие знакомые, ибо я не любитель английского языка. (но до подобного «перевода» фамилии я додумался сам и очень этим горжусь(не знаю, почему))

Также был добавлен звук, но подобрать что-то хорошее так и не получилось. Скорее всего, в финальном релизе выпилю его.

Итак, какие же проблемы оставались? Сугубо технические.
Я проверял всё на своем телефоне Samsung Galaxy S4 Active с разрешением 1920x1080. На других экранах всё выглядело совсем печально (да и сейчас не фонтан, если честно, я буду исправлять это со временем).
После ночи размышлений пришел к такому соглашению:
1) резать изображение под разные соотношения сторон не будем, ибо небольшое растяжение по оси y не сильно портит картинку. Кому-то растянутое нравится даже больше. А кнопки я предусмотрительно сделал прямоугольными, а не круглыми, как изначально.
2) сделаем картинки под 3 разрешения: 1920x1080, 960x540, 640x360 и будем молиться, чтоб в меня не сильно плевались люди.

Еще была такая проблема: при блокировке экрана игра начиналась заново: активити уничтожается, а потом создается заново (onCreate). Решение нашлось быстро: сохранять игру в Bundle.

Самая важная часть

Решая проблему «блокировки экрана», я весь день провел за компьютером: много часов кодинга, тупого и беспощадного.
Суть сохранения в Bundle очень проста: просто переопределяем событие и сохраняем, что нужно. А потом восстанавливаем. За всё время работы я задумался дольше, чем на минуту только один раз: придумывал имя для переменной.
С экранами я поступил, наверное, странно. Сделал класс Const, в котором были внутренние классы под каждый игровой экран (меню, игра, пауза и т.д.), в каждом из классов еще внутренние классы — обозначающие внутренние классы экрана. (я же обещал рассказать позже, что такое CONST? Это экземпляр класса Const, который создается при запуске на основе разрешения экрана)
Пример:
У меня есть класс GameScreen, в нем есть класс Grasshopper.

Тогда в Const имеем класс gamescreen и его экземпляр с именем GameScreen, а внутри класс grasshopper с экземпляром Grasshopper.

Для чего это? Я храню там игровые константы для каждого изображения экрана в виде открытых переменных (глупо, да, но я точно знаю, что нигде не буду изменять их содержимое).
Допустим, мне нужно узнать положение таблички муравья в картинке:

//CONST - экземлпяр класса Const. Общий для всего приложения
int x = CONST.GameScreen.Column.BLANK_X;
int y = CONST.GameScreen.Column.BLANK_Y;

На мой взгляд, достаточно удобно. Сами значения устанавливаются при инициализации Const. Там есть 3 функции: large(), middle(), small(). В зависимости от разрешения экрана, он выбирает наиболее близкие значения из этих трех и вызывает соотв. функцию, которая в свою очередь и проставляет значения.

После этого код-марафона я понял, что не хочу быть программистом (в данный момент я 11-классник и готовлюсь к поступлению на программистское направление), хотя я уже лет 5 мечтаю об этом. Почему? Я люблю программирование и не хочу, чтобы любимое дело превращалось в подобную рутину. Лучше я буду заниматься им изредка ради себя любимого. Чем я собираюсь заниматься? Поступать буду так же: на направление, связанное с программированием. Но становиться собираюсь преподавателем (пойти в аспирантуру, защитить кандидатскую). Да, это тоже рутина, но с моральной точки зрения преподавание — это круто. Я буду тут же видеть результаты своих трудов в виде студентов, которых научу чему-нибудь важному и полезному.
Разумеется, всё может поменяться, но план я избрал такой.

Послесловие

Игры пока нет в открытом доступе, выложу её на Play market, скорее всего, в конце этой недели. Потом постараюсь написать пост о том, как её восприняла публика и принесла ли она мне хоть сколько-нибудь денег.

Спасибо, если вы дочитали.
Комментарии весьма приветствуются.

Автор: Sna1L

Источник ^[2]