Я всё ещё обожаю программирование графики
Примерно год назад я написал рассказ про один из своих велосипедов, который я назвал «Я обожаю программирование графики». В том рассказе я старался показать процесс разработки «с романтичной стороны», немного пошутив над собой, мол всё так весело и забавно, когда программируешь графику. Я рассказал историю только со стороны «Ого! Полосатенько…», а теперь, почти год спустя, я решил поделиться с Вами рассказом о том, как же это всё работало и чем закончилось. Хочу сразу предупредить, что это всё ещё рассказ о велосипедах. Это не рассказ о революционных технологиях или супер-мега умных решениях. Это рассказ о том, как я, в своё удовольствие, умышленно писал велосипед.
Рассказ снова немного сумбурный и всех, кто не любит Android, С++, Live Wallpaper, Minecraft, велосипеды, поток сознания, который слабо привязан к теме и всё около того, хочу сразу предупредить что их может огорчить содержание этого поста, поэтому продолжайте чтение на свой страх и риск.
Прошлый рассказ? Для тех, кто не в курсе и не хочет читать предыдущую статью, расскажу в двух словах, о чём была речь. Я писал Live Wallpaper для Android, в стиле игры Minecraft. По сути просто изображение ландшафта в стиле игры Minecraft, которое можно листать пальцем и в которой есть смена дня и ночи.Немного про велосипеды
В прошлом своём рассказе я сделал лирическое отступление, чтобы рассказать об игре, которую я писал много лет назад из-за ностальгических чувств и в этом рассказе я решил не отличаться особой оригинальностью и начать с этого же.В 2006-ом году, я был счастливым обладателем КПК. VGA экран и все прочие плюшки данного устройства предоставляли довольно широкие возможности и в то время я написал несколько приложений под Windows Mobile.Одним из приложений, которое я написал, была игра, которую в моём детстве называли «Яйцеловкой» и на которую было потрачено немало детского времени и детских нервов. Не вдаваясь в детали, я взял набор изображений из эмулятора и сделал на их базе игру: 
Но рассказываю я это не для того, чтобы рекламировать КПК и не только из ностальгических чувств. Это рассказ про велосипеды — про велосипеды, которые создаются умышленно.
В то время у меня был достаточный опыт в области разработки ПО, для написания такой простой игры за неполный день. Как я уже говорил, рафика и звуковое сопровождение были взяты из эмулятора, логика проста до ужаса, а вывод на экран 10-и спрайтов уж точно не составлял никаких проблем. Пожалуй именно то, что реализация была слишком проста, было для меня основной проблемой. Ведь я решил написать эту игру для себя — не для продажи, не для кого-то, а просто для себя, а значит я должен получить из этого что-то большее, чем готовую игру. Процесс должен был доставлять удовольствие.
Тут на помощь и подоспели велосипеды… Свой формат изображений, для спрайтов, которые должны отображаться на экране (поверх фонового изображения). Свой процесс вывода этих спрайтов с эффектом белого шума. И всё реализовывалось через FrameBuffer, т.е. через массив пикселей. И вот задача уже заняла около 4-х дней и стала намного интереснее.
Процитирую себя из прошлой статьи:
Написал, работало именно так, как я запомнил, поиграл один раз, бросил, т.к. уже «наигрался» в процессе отладки.
Но для меня это стало своего рода традицией… Понимаете, каждый год 31 декабря мы с друзьями ходим в баню. Это у нас такая традиция.
Я стал время от времени, для себя, реализовывать вещи, чтобы, как говориться, «размять мозг». И этот процесс доставляет мне массу удовольствия, поэтому я сразу хочу дать ответ тем, кто любит кричать в комментах: «Фу-фу-фу, зачем так?! Да тут же нужен perlin noise и фрактальная генерация областей!». — Да, для всего, что я описываю в этом рассказе, есть свои методы и свои инструменты — я это отлично знаю. Моя реализация никак не связана с тем, что я не знаю о существовании готовых решений. Суть именно в реализации своих решений.Снова к теме
Было написано простое приложение Live wallpaper, которое просто закрашивало экран определённым цветом. Я не стану рассказывать, как это сделать, т.к. это та часть, которую можно легко найти в поисковиках. В приложении за прорисовку отвечал метод «draw», который делал примерно следующее: 
Тут и начались первые заморочки с производительностью…
Особенности SDK
Изначально, вопрос был в том, как же получить изображение от JNI и самым логичным решением показалось получать массив из int, который бы и представлял битмап с 32 битным представлением пикселя (32bpp). К такому подходу меня подталкивало и то, что Java предлагает метод для вывода такого массива на canvas: 
Я исходил из такой логики — массив пикселей можно получить и из объекта Bitmap, но это будет определённо дольше, чем просто передача массива и отрисовка массива методом, который специально для того сделан.
Тут меня ожидал сюрприз от Android: метод drawBitmap рисовал картинку (720×1280) примерно 21 мс, значит, если я хочу рисовать 30 кадров в секунду (пускай даже без задержек — занимая всё время процессора), то моя реализация должна была бы укладываться в 12 мс (и да, тут я даже не беру во внимание то, что сама прорисовка — это не единственная вещь, которая требует времени). Такое расположение дел меня определённо не устраивало, поэтому пришлось экспериментировать и искать другие варианты. Решением оказалась передача в JNI объекта Bitmap, который в методе прорисовки обрабатывался так:
Итак, передача объекта типа Bitmap, получение информации о нём (AndroidBitmap_getInfo), получение массива пикселей (AndroidBitmap_lockPixels / AndroidBitmap_unlockPixels) и собственно сам вызов JNI (без моей прорисовки), теперь занимал не более 1 мс. На этом этапе, проблема передачи изображение в JNI и обратно была решена. В документации я не нашёл ничего о том, почему использование метода drawBitmap с массивом пикселей работает так долго, но можно предположить, что в том случае просто перед прорисовкой создаётся объект Bitmap.
Накладные расходы так или иначе остались, т.к. получение и освобождение объекта Canvas при каждой прорисовке занимает примерно 1–2 мс. И сам вывод Bitmap при помощи метода drawBitmap занимает ещё 3–4 м:
В сумме, примерно 5–6 мс приходится отдавать на дополнительные операции, но тут я уже ничего поделать не мог и пришлось смириться.
Это пожалуй единственный интересный технический аспект, с которым пришлось столкнуться в Java, поэтому дальнейшее повествование уходит в JNI и в реализацию алгоритмов генерации ландшафта.
Линия горизонта и цикличность Сам ландшафт отображался циклично, т.е. изображение представляет собой замкнутую ленту, которую можно прокручивать бесконечно в любую сторону (по горизонтали). С точки зрения алгоритма, можно генерировать ландшафт любой длинны, но длинна ограничена, чтобы не занимать слишком много памяти.С точки зрения реализации тут всё очень просто: Если необходимо сгенерировать регион, точки которого уходят за пределы карты (по горизонтали), то эти точки просто переносятся на другую сторону карты (при x < 0, x += width и при x >= width, x -= width). Немного интереснее вопрос с реализацией уровня горизонта — горизонт должен быть случайным, но начальная и конечная точки должны сходиться, чтобы не было такого эффекта:
Для решения задачи был написан следующий алгоритм:
Случайным образом выбираем у координату начальной точки. Следующая точка может иметь одно из смещений относительно предыдущей точки: {-2, -1, 0, 1, 2}, для каждого из смещений проверяется, есть ли возможность вернуться в начальную точку за оставшееся количество переходов. Смещение, выбор которого не позволит выйти в начальную точку, удаляется из списка. Выбирается случайное значение смещения из списка. Повторяем со второго пункта, пока не пришли в начало. На практике такой подход позволяет генерировать как плоские поверхности ландшафта, так и «горы». По правде говоря, я знаю, что алгоритм самый оптимальный и что следовало исходить из искажений прямой линии, но на тот момент, решение показалось достаточным.
Пещеры и прочие элементы Одной из основных задач, была генерация пещер, и различных блоков (уголь, песок, и т.д). Существует довольно много алгоритмов для решения данной задачи, но я решил писать всё сам, как мне придёт в голову.Реализация была похожа на реализацию алгоритма flood fill, только с некоторым элементом случайности:
Выбрать случайную точку, задать «вес» для данной точки (случайное число). Проверить доступность соседних точек (обработать каждую из соседних точек, уменьшая «вес» случайным образом) — не находится ли точка за пределами экрана, нет была ли точка обработана ранее. «Вес» соседних точек определяется случайным числом в диапазоне от («вес» родительской точки / 2), до «веса» родительской точки. Дополнительно, в алгоритм генерации была добавлена возможность создавать более случайные регионы, добавив условие «дополнительной случайности», где с 20% вероятностью не рассматриваются дочерние точки.
Процесс обхода точек довольно наглядно можно показать при помощи анимации:
Немного другая анимация, которая показывает процесс уменьшения «веса» от центра:
По своей сути, алгоритм рекурсивен, но для реализации была использована очередь. Начальная точка добавляется в очередь обработки и цикл выполняется до тех пор, пока в очереди есть точки. Доступные соседние точки, с весом больше 0 добавляются в очередь. В целом тут всё довольно стандартно, с точки зрения решения проблемы излишней глубины стека вызовов.
Данный алгоритм выполняется в несколько проходов — создаёт несколько начальных точек из которых и обрабатываются дочерние точки. В результате, регионы соединяются между собой случайным образом, создавая более сложные регионы. Вот пример создания пяти регионов (точки каждого региона отмечены цифрами от одного до пяти, начальная точка региона имеет красную рамку):
Этот алгоритм является основой для большей части ландшафта, изменяется только количество начальных точек (точек из которых и создаются отдельные регионы), начальный «вес» для начальных точек, и положение начальных точек (это сделано для того, чтобы определённые регионы создавались только в рамках определённой глубины, например, только около дна).
Начальные точки регионов были использованы и для размещения элементов освещения (факелов). В ранней версии факелы находились именно в начальных точках региона, но потом я решил спустить их «к земле» и если начальная точка региона находится выше, чем в двух блоках от «пола», то факел ставился именно в двух блоках от пола. Такой подход сделал освещение интереснее (большие части региона могли оставаться слабо освещены).
Снова про производительность
Весь процесс разработки я боролся с производительностью. Приходилось переделывать довольно много, когда на этапе тестирования становилось понятно, что прорисовка требует слишком много времени. Ничего особо оригинального я не придумал, реализовал лишь процесс определения изменившихся областей, чтобы в прорисовке участвовала только та область, которую реально нужно перерисовать. Остальная часть бралась из прошлого изображения. Так, например, при перелистывании, большая часть оставалась неизменной, а лишь тот сегмент, который было необходимо добавить, дорисовывался (на изображении, блоки, которые необходимо нарисовать, отмечены красным): 
Алгоритм отвечал не только за смещение, но и за области, освещение которых менялось при смене времени:
Псевдо3д
«Псевдообьём» создавался также довольно просто — положение блока всегда фиксировано — помимо передней грани, видно боковую грань (слева) и верхнюю грань. Для каждого типа блоков, из текстур генерировались 5 изображений, которые вместе и создавали иллюзию объема: 
Всего можно выделить 5 различных вариантов расположения блоков (чёрным отмечен блок, который необходимо нарисовать, серым показаны соседние блоки, белым отмечено место, где нет соседнего блока):
В каждом из вариантов необходимо рисовать определённый набор изображений:1. a, b, c, d1, d22. a, c, d23. a, c…
Пример прорисовки, где сегменты блока отмечены разными цветами:
Значения видимых граней блока просчитывались на этапе генерации ландшафта, а значит при прорисовке было необходимо лишь нарисовать то, что необходимо.
Немного про случайные числа Для генерации «случайных» чисел был написан свой класс, который генерировал набор чисел, основываясь на заданной строке (seed) и дополнительном параметре. Так например, при генерации пещер, использовалась комбинация seed и «caves», для деревьев — seed и «trees». Такой подход обеспечил возможность отключить генерацию определённой области (например, не генерировать блоки угля или железа), но не затрагивать внешний вид остальных элементов, которые основаны на случайных числах.Алгоритм я построил на алгоритме вычисления контрольной суммы crc32, т.к. он одновременно позволял получать число из любых данных и у меня под рукой была его реализация.
Коротко про результаты
Установки приложения за год: 16553 (+ 81 (paid)): 
Общий доход от приложения составил 2794.91 рублей. В общем, если бы зарабатывал на жизнь написанием велосипедов, то я бы уже умер с голода.
О процессе разработки я могу сказать, что было очень интересно решать задачи, с которыми мы обычно не сталкиваемся в своей работе. Конечно, можно было взять один из готовых движков и на его основе сделать что-то похожее, с честным 3d и без описанных извращений, но я снова надеюсь, что это подтолкнёт ещё кого-то на создание чего-либо своими руками, а не только используя готовые фреймворки и библиотеки.
Всем спасибо за внимание!
