Я все ще обожнюю програмування графіки

    
 
Приблизно рік тому я написав оповідання про один зі своїх велосипедів, який я назвав "Я обожнюю програмування графіки ". У тому оповіданні я намагався показати процес розробки "з романтичною сторони", трохи пожартувавши над собою, мовляв все так весело і забавно, коли програмуєш графіком. Я розповів історію тільки з боку "Ого! Полосатенький… ", а тепер, майже через рік, я вирішив поділитися з Вами розповіддю про те, як же це все працювало і чим закінчилося. Хочу відразу попередити, що це все ще розповідь про велосипедах. Це не розповідь про революційні технологіях або супер-мега розумних рішеннях. Це розповідь про те, як я, в своє задоволення, навмисне писав велосипед.
 
Розповідь знову трохи сумбурний і всіх, хто не любить 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 малював картинку (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). Трохи цікавіше питання з реалізацією рівня горизонту — горизонт повинен бути випадковим, але початкова та кінцева точки повинні сходитися, щоб не було такого ефекту:
 
 
 
Для вирішення завдання був написаний наступний алгоритм:
 
     
  • Випадковим чином вибираємо у координату початкової точки.
  •  
  • Наступна точка може мати одне з зсувів щодо попередньої точки: {-2, -1, 0, 1, 2}, для кожного з зміщень перевіряється, чи є можливість повернутися в початкову точку за залишився кількість переходів. Зсув, вибір якого не дозволить вийти в початкову точку, видаляється зі списку.
  •  
  • Вибирається випадкове значення зміщення зі списку.
  •  
  • Повторюємо з другого пункту, поки не прийшли в початок.
  •  
 
На практиці такий підхід дозволяє генерувати як плоскі поверхні ландшафту, так і "гори". По правді кажучи, я знаю, що алгоритм найоптимальніший і що слід було виходити з спотворень прямої лінії, але на той момент, рішення здалося достатнім.
 
 

Печери та інші елементи

Одним з основних завдань, була генерація печер, і різних блоків (вугілля, пісок, і т.д). Існує досить багато алгоритмів для вирішення даного завдання, але я вирішив писати все сам, як мені прийде в голову.
 
Реалізація була схожа на реалізацію алгоритму flood fill, тільки з деяким елементом випадковості:
 
     
  1. Вибрати випадкову точку, задати "вагу" для даної точки (випадкове число).
  2.  
  3. Перевірити доступність сусідніх точок (обробити кожну з сусідніх точок, зменшуючи "вагу" випадковим чином) — чи не знаходиться точка за межами екрану, немає чи була точка оброблена раніше.
  4.  
 
"Вага" сусідніх точок визначається випадковим числом в діапазоні від ("вага" батьківської точки / 2), до "ваги" батьківської точки. Додатково, в алгоритм генерації була додана можливість створювати більш випадкові регіони, додавши умова "додаткової випадковості", де з 20% ймовірністю не розглядаються дочірні точки.
 
Процес обходу точок досить наочно можна показати за допомогою анімації:
 
 
 
Трохи інша анімація, яка показує процес зменшення "ваги" від центру:
 
 
 
За своєю суттю, алгоритм рекурсівен, але для реалізації була використана чергу. Початкова точка додається в чергу обробки і цикл виконується до тих пір, поки в черзі є точки. Доступні сусідні точки, з вагою більше 0 додаються в чергу. В цілому тут все досить стандартно, з точки зору вирішення проблеми зайвої глибини стека викликів.
 
Даний алгоритм виконується в кілька проходів — створює кілька початкових точок з яких і обробляються дочірні точки. В результаті, регіони з'єднуються між собою випадковим чином, створюючи більш складні регіони. Ось приклад створення п'яти регіонів (точки кожного регіону відзначені цифрами від одного до п'яти, початкова точка регіону має червону рамку):
 
 
 
Цей алгоритм є основою для більшої частини ландшафту, змінюється тільки кількість початкових точок (точок з яких і створюються окремі регіони), початковий "вагу" для початкових точок, і положення початкових точок (це зроблено для того, щоб певні регіони створювалися тільки в рамках певної глибини, наприклад, тільки близько дна).
 
Початкові точки регіонів були використані і для розміщення елементів освітлення (факелів). У ранній версії факели перебували саме в початкових точках регіону, але потім я вирішив спустити їх "до землі" і якщо початкова точка регіону знаходиться вище, ніж у двох блоках від "статі", то факел ставилося саме в двох блоках від підлоги. Такий підхід зробив освітлення цікавіше (великі частини регіону могли залишатися слабо висвітлені).
 
 

Знову про продуктивність

Весь процес розробки я боровся з продуктивністю. Доводилося переробляти досить багато, коли на етапі тестування ставало зрозуміло, що промальовування вимагає занадто багато часу. Нічого особливо оригінального я не придумав, реалізував лише процес визначення змінених областей, щоб у промальовуванню брала участь тільки та область, яку реально потрібно перемалювати. Інша частина бралася з минулого зображення. Так, наприклад, при гортанні, більша частина залишалася незмінною, а лише той сегмент, який було необхідно додати, домальовують (на зображенні, блоки, які необхідно намалювати, відмічені червоним):
 
 
 
Алгоритм відповідав не тільки за зміщення, а й за області, висвітлення яких змінювалося при зміні часу:
 
 
 
 

Псевдо3д

"Псевдообьем" створювався також досить просто — положення блоку завжди фіксоване — крім передній грані, видно бічну грань (ліворуч) і верхню грань. Для кожного типу блоків, з текстур генерувалися 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 і без описаних збочень, але я знову сподіваюся, що це підштовхне ще когось на створення чого-небудь своїми руками, а не тільки використовуючи готові фреймворки та бібліотеки.
 
 Всім дякую за увагу!
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.