- PVSM.RU - https://www.pvsm.ru -
Примерно год назад я написал рассказ про один из своих велосипедов, который я назвал “Я обожаю программирование графики [1]”. В том рассказе я старался показать процесс разработки “с романтичной стороны”, немного пошутив над собой, мол всё так весело и забавно, когда программируешь графику. Я рассказал историю только со стороны “Ого! Полосатенько...”, а теперь, почти год спустя, я решил поделиться с Вами рассказом о том, как же это всё работало и чем закончилось. Хочу сразу предупредить, что это всё ещё рассказ о велосипедах. Это не рассказ о революционных технологиях или супер-мега умных решениях. Это рассказ о том, как я, в своё удовольствие, умышленно писал велосипед.
Рассказ снова немного сумбурный и всех, кто не любит Android, С++, Live Wallpaper, Minecraft, велосипеды, поток сознания, который слабо привязан к теме и всё около того, хочу сразу предупредить что их может огорчить содержание этого поста, поэтому продолжайте чтение на свой страх и риск.
Для тех, кто не в курсе и не хочет читать предыдущую статью, расскажу в двух словах, о чём была речь. Я писал Live Wallpaper для Android, в стиле игры Minecraft. По сути просто изображение ландшафта в стиле игры Minecraft, которое можно листать пальцем и в которой есть смена дня и ночи.
В прошлом своём рассказе я сделал лирическое отступление, чтобы рассказать об игре, которую я писал много лет назад из-за ностальгических чувств и в этом рассказе я решил не отличаться особой оригинальностью и начать с этого же.
В 2006-ом году, я был счастливым обладателем КПК. VGA экран и все прочие плюшки данного устройства предоставляли довольно широкие возможности и в то время я написал несколько приложений под Windows Mobile.
Одним из приложений, которое я написал, была игра, которую в моём детстве называли “Яйцеловкой” и на которую было потрачено немало детского времени и детских нервов. Не вдаваясь в детали, я взял набор изображений из эмулятора и сделал на их базе игру:
Но рассказываю я это не для того, чтобы рекламировать КПК и не только из ностальгических чувств. Это рассказ про велосипеды — про велосипеды, которые создаются умышленно.
В то время у меня был достаточный опыт в области разработки ПО, для написания такой простой игры за неполный день. Как я уже говорил, рафика и звуковое сопровождение были взяты из эмулятора, логика проста до ужаса, а вывод на экран 10-и спрайтов уж точно не составлял никаких проблем. Пожалуй именно то, что реализация была слишком проста, было для меня основной проблемой. Ведь я решил написать эту игру для себя — не для продажи, не для кого-то, а просто для себя, а значит я должен получить из этого что-то большее, чем готовую игру. Процесс должен был доставлять удовольствие.
Тут на помощь и подоспели велосипеды… Свой формат изображений, для спрайтов, которые должны отображаться на экране (поверх фонового изображения). Свой процесс вывода этих спрайтов с эффектом белого шума. И всё реализовывалось через FrameBuffer, т.е. через массив пикселей. И вот задача уже заняла около 4-х дней и стала намного интереснее.
Процитирую себя из прошлой статьи:
Написал, работало именно так, как я запомнил, поиграл один раз, бросил, т.к. уже “наигрался” в процессе отладки.
Но для меня это стало своего рода традицией…
Понимаете, каждый год 31 декабря мы с друзьями ходим в баню. Это у нас такая традиция.
Я стал время от времени, для себя, реализовывать вещи, чтобы, как говориться, “размять мозг”. И этот процесс доставляет мне массу удовольствия, поэтому я сразу хочу дать ответ тем, кто любит кричать в комментах: “Фу-фу-фу, зачем так?! Да тут же нужен perlin noise и фрактальная генерация областей!”. — Да, для всего, что я описываю в этом рассказе, есть свои методы и свои инструменты — я это отлично знаю. Моя реализация никак не связана с тем, что я не знаю о существовании готовых решений. Суть именно в реализации своих решений.
Было написано простое приложение Live wallpaper, которое просто закрашивало экран определённым цветом. Я не стану рассказывать, как это сделать, т.к. это та часть, которую можно легко найти в поисковиках. В приложении за прорисовку отвечал метод “draw”, который делал примерно следующее:
Тут и начались первые заморочки с производительностью…
Изначально, вопрос был в том, как же получить изображение от JNI и самым логичным решением показалось получать массив из int, который бы и представлял битмап с 32 битным представлением пикселя (32bpp). К такому подходу меня подталкивало и то, что Java предлагает метод для вывода такого массива на canvas:
Я исходил из такой логики — массив пикселей можно получить и из объекта Bitmap, но это будет определённо дольше, чем просто передача массива и отрисовка массива методом, который специально для того сделан.
Тут меня ожидал сюрприз от Android: метод drawBitmap рисовал картинку (720x1280) примерно 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 ). Немного интереснее вопрос с реализацией уровня горизонта — горизонт должен быть случайным, но начальная и конечная точки должны сходиться, чтобы не было такого эффекта:
Для решения задачи был написан следующий алгоритм:
На практике такой подход позволяет генерировать как плоские поверхности ландшафта, так и “горы”. По правде говоря, я знаю, что алгоритм самый оптимальный и что следовало исходить из искажений прямой линии, но на тот момент, решение показалось достаточным.
Одной из основных задач, была генерация пещер, и различных блоков (уголь, песок, и т.д). Существует довольно много алгоритмов для решения данной задачи, но я решил писать всё сам, как мне придёт в голову.
Реализация была похожа на реализацию алгоритма flood fill, только с некоторым элементом случайности:
“Вес” соседних точек определяется случайным числом в диапазоне от (“вес” родительской точки / 2), до “веса” родительской точки. Дополнительно, в алгоритм генерации была добавлена возможность создавать более случайные регионы, добавив условие “дополнительной случайности”, где с 20% вероятностью не рассматриваются дочерние точки.
Процесс обхода точек довольно наглядно можно показать при помощи анимации:
Немного другая анимация, которая показывает процесс уменьшения “веса” от центра:
По своей сути, алгоритм рекурсивен, но для реализации была использована очередь. Начальная точка добавляется в очередь обработки и цикл выполняется до тех пор, пока в очереди есть точки. Доступные соседние точки, с весом больше 0 добавляются в очередь. В целом тут всё довольно стандартно, с точки зрения решения проблемы излишней глубины стека вызовов.
Данный алгоритм выполняется в несколько проходов — создаёт несколько начальных точек из которых и обрабатываются дочерние точки. В результате, регионы соединяются между собой случайным образом, создавая более сложные регионы. Вот пример создания пяти регионов (точки каждого региона отмечены цифрами от одного до пяти, начальная точка региона имеет красную рамку):
Этот алгоритм является основой для большей части ландшафта, изменяется только количество начальных точек (точек из которых и создаются отдельные регионы), начальный “вес” для начальных точек, и положение начальных точек (это сделано для того, чтобы определённые регионы создавались только в рамках определённой глубины, например, только около дна).
Начальные точки регионов были использованы и для размещения элементов освещения (факелов). В ранней версии факелы находились именно в начальных точках региона, но потом я решил спустить их “к земле” и если начальная точка региона находится выше, чем в двух блоках от “пола”, то факел ставился именно в двух блоках от пола. Такой подход сделал освещение интереснее (большие части региона могли оставаться слабо освещены).
Весь процесс разработки я боролся с производительностью. Приходилось переделывать довольно много, когда на этапе тестирования становилось понятно, что прорисовка требует слишком много времени. Ничего особо оригинального я не придумал, реализовал лишь процесс определения изменившихся областей, чтобы в прорисовке участвовала только та область, которую реально нужно перерисовать. Остальная часть бралась из прошлого изображения. Так, например, при перелистывании, большая часть оставалась неизменной, а лишь тот сегмент, который было необходимо добавить, дорисовывался (на изображении, блоки, которые необходимо нарисовать, отмечены красным):
Алгоритм отвечал не только за смещение, но и за области, освещение которых менялось при смене времени:
“Псевдообьём” создавался также довольно просто — положение блока всегда фиксировано — помимо передней грани, видно боковую грань (слева) и верхнюю грань. Для каждого типа блоков, из текстур генерировались 5 изображений, которые вместе и создавали иллюзию объема:
Всего можно выделить 5 различных вариантов расположения блоков (чёрным отмечен блок, который необходимо нарисовать, серым показаны соседние блоки, белым отмечено место, где нет соседнего блока):
В каждом из вариантов необходимо рисовать определённый набор изображений:
1. a, b, c, d1, d2
2. a, c, d2
3. a, c
…
Пример прорисовки, где сегменты блока отмечены разными цветами:
Значения видимых граней блока просчитывались на этапе генерации ландшафта, а значит при прорисовке было необходимо лишь нарисовать то, что необходимо.
Для генерации “случайных” чисел был написан свой класс, который генерировал набор чисел, основываясь на заданной строке (seed) и дополнительном параметре. Так например, при генерации пещер, использовалась комбинация seed и “caves”, для деревьев — seed и “trees”. Такой подход обеспечил возможность отключить генерацию определённой области (например, не генерировать блоки угля или железа), но не затрагивать внешний вид остальных элементов, которые основаны на случайных числах.
Алгоритм я построил на алгоритме вычисления контрольной суммы crc32, т.к. он одновременно позволял получать число из любых данных и у меня под рукой была его реализация.
Установки приложения за год: 16553 (+ 81 (paid)):
Общий доход от приложения составил 2794.91 рублей. В общем, если бы зарабатывал на жизнь написанием велосипедов, то я бы уже умер с голода.
О процессе разработки я могу сказать, что было очень интересно решать задачи, с которыми мы обычно не сталкиваемся в своей работе. Конечно, можно было взять один из готовых движков и на его основе сделать что-то похожее, с честным 3d и без описанных извращений, но я снова надеюсь, что это подтолкнёт ещё кого-то на создание чего-либо своими руками, а не только используя готовые фреймворки и библиотеки.
Всем спасибо за внимание!
Автор: simbiod
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/66430
Ссылки в тексте:
[1] Я обожаю программирование графики: http://habrahabr.ru/post/190458/
[2] Источник: http://habrahabr.ru/post/231787/
Нажмите здесь для печати.