Математика в геймдеві. Що таке діаграми Вороного та як їх використовують при розробці ігор

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

Ми розглядали досить багато тем для старту, аж поки в коментарях під топіком про процедурну генерацію на Unity один з членів нашої спільноти не згадав діаграми Вороного. Одразу стало зрозуміло, що це ідеальний приклад для початку нашого ознайомчого циклу.

Гравітація, теселяція та холера

Діаграми Вороного можна називати по-різному: математичним об’єктом, алгоритмом, методом, принципом, поділом. Пояснення цієї ідеї та того, як її використовують при розробці ігор, ми дамо трошки нижче, а зараз — невеличкий екскурс в історію.

Вважається, що цей принцип першим використав французький філософ і математик Рене Декарт. У 1644 році він написав і видав один з головних своїх творів — трактат «Засади філософії». Там Декарт запропонував ділити Всесвіт на зони гравітаційного впливу зірок, так звані вихори. Ці зони були виконані у вигляді діаграм Вороного, які, звісно, тоді ще так не називалися.

Кілька діаграм Вороного в «Засадах філософії»

Через двісті років німецький математик Йоганн Петер Густав Лежен Діріхле у своїй праці «Про скорочення додатних квадратичних форм з трьома невизначеними цілими числами» досліджував ці самі квадратичні форми. У ній він використав двовимірні та тривимірні діаграми Вороного. Зробив він це настільки ґрунтовно, що й досі діаграми іноді називають теселяцією (замощенням) Діріхле.

Ще один класичний приклад нашого алгоритму в історії пов’язаний з англійським лікарем Джоном Сноу. Його вважають одним з піонерів сучасної епідеміології, анестезіології та медичної гігієни. Так склалося, що у медицині XIX століття домінувала теорія міазмів — вчені вважали, що холеру та бубонну чуму викликала шкідлива форма повітря, а не мікроорганізми.

Але у 1854-55 роках Сноу щільно спілкувався з жителями лондонського району Сохо. З їхніх розповідей він зрозумів, що джерело спалаху холери — помпа комунального водопостачання неподалік. Використавши діаграму Вороного, Сноу довів: більшість тих, хто помер від епідемії холери в Сохо, перебували в осередку цієї водяної помпи.

Джон Сноу, англійський лікар XIX століття

«Працюючи над точковою мапою, я виявив, що майже всі смерті відбулись недалеко від помпи. У будинках, значно ближчих до іншої вуличної помпи, було лише десять смертей. У п’яти з цих випадків родини померлих повідомили мені, що завжди використовували воду з помпи на Брод-стріт, оскільки вода звідти їм подобалась більше порівняно з ближньою. У трьох інших випадках померли діти, які ходили до школи поряд з помпою на Брод-стріт».

Та ключовим в історії цих діаграм є видатний український математик, педагог та один з засновників геометрії чисел Георгій Феодосійович Вороний. На жаль, часто в іноземній літературі (англомовній, франкомовній і, звісно ж, російськомовній) він позначається суто як російський математик. Тому не зайвим буде наголосити ще раз — він саме український вчений.

Георгій Вороний народився 1868 року в селі Журавка. Зараз це територія Прилуцького району Чернігівської області, а тоді це була Полтавська губернія. Його хист та неабиякі здібності до математики проявилися ще в гімназії — першу наукову публікацію (статтю «Розклад многочленів на множники, що ґрунтується на властивостях коренів квадратного рівняння») Вороний видав у 16 років.

Після Прилуцької чоловічої гімназії він вступив до Санкт-Петербурзького університету та у 1894 році захистив магістерську дисертацію «Про цілі числа, залежні від кореня рівняння третього ступеня». Далі, вже в Варшавському університеті, вивчав ланцюгові дроби й захистив докторську дисертацію, що стосувалася узагальнення алгоритму неперервних дробів.

Довгий час Вороний мріяв про посаду професора математики Київського університету. Згодом його призначили деканом механічного факультету Донського політехнічного інституту, хоча стосунків з батьківщиною вчений не розривав — все життя під час відпусток він обов’язково повертався до Журавки, а разом з Михайлом Драгомановим ініціював у Києві безплатні недільні школи для молоді та був активним членом створеної при Київському університеті студентської громади.

Наукова спадщина Вороного налічує шість фундаментальних монографій та шість невеликих за обсягом праць. Вони стосуються аналітичної теорії чисел, геометрії чисел, теорії функцій тощо. Є серед них і робота 1908 року про примітивні паралелоедри. Саме звідти пішла назва діаграм Вороного. Але якщо Діріхле обмежився двовимірними та тривимірними діаграмами, то український вчений формалізував цей об’єкт для n-вимірних випадків.

Визначення, алгоритми та складність

Сьогодні діаграму Вороного широко використовують у різних сферах: в екології, космології, біології, моделюванні рельєфу; під час конструювання роботів, створення надміцних структур, експериментів з радіаційної фізики тощо. В комп’ютерній науці вона набула поширення у другій половині XX століття. Але що це, власне, таке?

Якщо говорити загалом, то діаграма Вороного описує просторове відношення між близько розташованими точками або їх найближчими сусідами на площині. Фактично, це безліч з’єднаних багатокутників, що мають спільні ребра. Самі ребра розміщені посередині між двома сусідніми точками. Проте це досить громіздке та не дуже зрозуміле для початківців визначення (особливо якщо його не підкріплювати візуальними матеріалами).

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

Для практичного використання діаграм наш приклад треба трошки ускладнити — збільшити кількість початкових точок. Але перед цим згадаймо, що таке опуклий багатокутник. Якщо просто, то це така геометрична фігура, в якій продовження сторін не перетинають інших сторін. Трикутник, куб, п’ятикутник — опуклий багатокутник; зірка — ні (вона належить до увігнутих багатокутників).

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

Так виглядає діаграма Вороного для 40 довільних точок

Власне, є декілька алгоритмів побудови діаграми Вороного, і кожен з них відрізняється своєю складністю. Наприклад, для двох точок ми використали, напевно, найпростіший. Його ідея в тому, щоб будувати серединні перпендикуляри відрізків, що з’єднують кожну точку з усіма іншими на площині. Складність такого алгоритму становить O(n^4).

Один з найбільш відомих алгоритмів побудови діаграм Вороного — алгоритм Форчуна. Його описав 1986 року математик Стів Форчун у своїй статті «Алгоритм лінійної розгортки для діаграми Вороного». Для розуміння цього інструменту потрібно знати деякі визначення (фокус параболи, її директриса) та розуміти, що складність алгоритму становить O(n*log(n)). Це працює так:

  • Є пряма, що рухається, наприклад, зліва направо — від однієї точки до іншої. Коли вона «потрапляє» на чергову точку, то створює параболу. Її фокусом є саме ця точка, а директрисою — пряма, що рухається (вона називається sweep line). Нова парабола ділить площину на дві частини та змінюється залежно від положення sweep line;
  • Парабола розширюється та створює дві контрольні точки, які є точками її перетину з іншими параболами. Ці точки перетину рухаються якраз по ребрах локусів діаграм Вороного;
  • Коли дві контрольні точки з різних парабол «зустрічаються», то зливаються в одну. Ця точка злиття є вершиною локусу.

Більш докладно про алгоритм Форчуна та його застосування в діаграмах Вороного можна почитати на сайті The American Mathematical Society, або ж на Khan Academy.

Процедурне генерування та штучний інтелект

Як ми вже згадували, у діаграм Вороного безліч застосувань загалом. Геймдев — не виняток. По-перше, їх використовують для процедурного генерування мап і рівнів. При чому для вирішення як креативних, так технічних завдань. Щодо креативних, то у діаграм природний розподіл осередків, їхню структуру можна розглядати як графи (кожен локус є окремим вузлом, а кожне ребро — зв’язком між ними), і оскільки це вже достатньо вивчений інструмент, можна знайти багато готових застосувань.

Можна спочатку створити саму діаграму як приблизний контур мапи, а вже потім заповнювати його за логікою гри. З одних локусів чи груп локусів робити море або ж океан; з других — гори; з третіх — міські квартали. Останній варіант взагалі має непоганий вигляд, якщо вважати, що початкова точка то, наприклад, дерево в центрі окремого подвір’я, а ребра локуса — будівлі навколо. Таким чином, згенерувавши певну кількість точок та застосувавши до них той самий алгоритм Форчуна, можна отримати повноцінне місто для стратегії.

Для технічного застосування потрібно знати про тріангуляцію Делоне — це такий обернений до діаграм Вороного інструмент. Кожна лінія Делоне відповідає одному й лише одному ребру Вороного. Завдяки цій тріангуляції ми отримуємо замість багатокутників трикутники, які можна рендерити.

По-друге, не варто забувати одну важливу проблему з обчислювальної геометрії — задачу про поштову скриньку. Її формулюють так:

Уявіть туриста, який потрапив до цікавого міста, накупив гарних поштових листівок та планує надіслати їх друзям якомога швидше. Для цього йому потрібно знайти найближчу поштову скриньку. Власне, розв’язання цієї проблеми — одне із застосувань діаграми Вороного.

Методи розв’язання проблеми поштової скриньки гарно застосовуються до, наприклад, пошуку найближчого чекпоінту. Припустимо, що кожна точка позначає чекпоінт, або ж скриньку з коштовностями, або ж аптечку. Досить легко визначити, де розташована найближча до нас точка, якщо ми знаємо, в якому локусі перебуває гравець. І навіть якщо в цій ділянці вже немає аптечки, легко зрозуміти, де її шукати у сусідній комірці.

По-третє, все вищеперераховане ми можемо використати для керування штучним інтелектом в грі. Наприклад, знайти найбезпечніший шлях через ворожу місцевість. Все, що треба — провести ШІ такими ребрами, відстань до яких від базових точок найбільша.

Звісно, лише цими прикладами не обмежується застосування діаграм Вороного. Як і не обмежуються їхня побудова тими алгоритмами, які ми навели в статті. Але розуміння цього математичного об’єкта та його використання при створенні ваших ігор може значно поліпшити досвід гравця, а також спростити життя розробники. То чи використовуєте ви діаграми Вороного у своїй роботі? Можливо, не тільки їх? Якщо так — діліться досвідом у коментарях.

Підписуйтеся на Telegram-канал @gamedev_dou, щоб не пропустити найважливіші статті і новини

👍ПодобаєтьсяСподобалось15
До обраногоВ обраному9
LinkedIn


Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Тут:

знайти найнебезпечніший

Малось на увазі «найбезпечніший»

Підписатись на коментарі