Як використовувати діаграми Вороного для управління штучним інтелектом


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

Просторові відношення

Просторове відношення — це будь-яка інформація, що описує, як пов’язаний один об’єкт в просторі з іншим. Приклади: відстань між ними, площа покривається кожним з них простору і перетин цих площ, кількість таких об’єктів, розташованих в одній області.

Такі відносини постійно використовуються у відеоіграх і можуть надавати дуже корисну інформацію ІІ, а також самому гравцеві.

У Вороного є відповідь

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

Щоб розібратися, поглянемо на картинку:


Як бачите, кожна лінія знаходиться рівно посередині між двома точками, і всі вони з’єднуються в центрі. Додамо в сцену ще декілька точок і подивимося, що відбудеться:


Картина стала цікавіше! У нас вже з’являються справжні області.

Про що ж нам говорить кожна з областей? Ми знаємо, що перебуваючи в області, гарантовано розташовані найближче до одній точці, яка теж знаходиться в області. Це багато що говорить нам про те, що знаходиться поблизу; таке фундаментальне просторове відношення до діаграми Вороного.

Вивертаємо Вороного навиворіт: тріангуляція Делоне

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


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


На малюнку зелена лінія Делоне відповідає рожевому ребру Вороного. Просто уявіть, що рожеве ребро йде далі, і ви побачите, що вони перетинаються.

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

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

Структура даних Вороного

Ми вже знаємо, як виглядає діаграма Вороного; тепер давайте подивимося, як буде виглядати її структура даних. Спочатку нам потрібно зберегти точки, які є основою діаграми Вороного:

class VoronoiPoint {
 float x
 float y
 VoronoiRegion* region
}

Кожна VoronoiPoint має локацію (x, y) і посилання на область, в якій вона знаходиться.

Далі нам потрібно описати VoronoiRegion:

class VoronoiRegion {
 VoronoiPoint* point
 Edge *edges[] // our list of edges
}

Область зберігає посилання на її VoronoiPoint, а також на список обмежують її ребер VoronoiEdges.

Подивимося, як виглядає VoronoiEdges:

class VoronoiEdge {
 VoronoiPoint* pointA
 VoronoiPoint* pointB
 float distance // distance between point A point and B
 float x1, z1, x2, z2 // to visualize start & end of the edge
}

Ребро знає які визначають її дві точки, а також відстань між ними. Для візуального відображення, а також для побудови форми багатокутної області нам потрібно зберігати початкову та кінцеву точки ребра.

Читайте також  Робимо 3D конфігуратор без програмування і верстки. Частина друга

І на цьому все. Маючи цю інформацію, ми можемо запросто побудувати діаграму Вороного. Нижче ми дізнаємося, як діаграма Вороного генерується. Але поки подивимося на парі прикладів, як можна використовувати ці дані.

Пошук найближчої аптечки

Знову поглянемо на діаграму Вороного для точок.


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

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

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

Пошук безпечного маршруту

Замінимо всі аптечки ворожими сторожовими вежами. Вам потрібно знайти найбільш безпечний маршрут між ними, щоб не бути спійманим. Стандартний спосіб обходу графа у відеоіграх — використання алгоритму A*. Так як діаграма Вороного — це граф, реалізувати пошук дуже легко. Нам лише потрібно алгоритм A*, підтримує спільні структури графів; плануйте все заздалегідь, і це допоможе вам у майбутньому.

Підготувавши граф, потрібно призначити кожному ребру вагу. Для нас значенням ваги буде відстань до цих сторожових вишок, і отримати його можна безпосередньо з структури даних: кожне VoronoiEdge вже знає своє відстань між двома точками. Зазвичай чим менше значення на ребрі A*, тим краще, але в нашому випадку краще буде більше значення, тому що воно позначає відстань до вежі.

Ось як виглядає початковий граф, якщо ми хочемо переміститися з точки A в точку B:


Приклавши до кожному ребру вага, ми побачимо, який маршрут краще буде вибрати:


Червоні ребра позначають найближчі контакти з вежами. Помаранчевим позначені більш далекі; жовтим ще більш далекі, і, нарешті, зелені — найбезпечніші. Після виконання A* з цими вагами ми отримаємо наступний шлях:


При такому використанні терезів буде обраний не найшвидший, а самий безпечний шлях, що нам і потрібно. ІЇ слід дотримуватися цього шляху і не відхилятися від нього!

Можна зробити ще один крок, щоб гарантувати безпечний шлях: усунути всі ребра, що знаходяться ближче, ніж мінімальну безпечну відстань. Наприклад, якщо кожна сторожова вежа має радіус видимості 30 одиниць, то всі ребра, відстань до точок яких менше, можна буде видалити з графа і не обходити їх.

Читайте також  Як зменшити розмір фото файлу

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

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

Пошук щільно розташований набір предметів

Припустимо, нам потрібно скинути з літака посилку з котячою м’ятою для купи сидять на землі котиків. Куди найкраще її скинути, щоб нею скористалося найбільшу кількість кішок? Це може виявитися надзвичайно витратними розрахунками. Але, на щастя, ми можемо зробити обґрунтоване припущення за допомогою тріангуляції Делоне.

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

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

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


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

Реалізація діаграм Вороного

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

Алгоритм Форчуна

Найшвидший спосіб називається алгоритмом Форчуна. Він виконується за O(n log(n)) і вимагає, щоб всі точки, які використовуються для генерації графа, були відомі на момент початку генерації. Якщо пізніше ви будете додавати нові точки, то доведеться заново генерувати весь граф. Якщо точок мало, то це може і не викликати проблем, але якщо їх у вас 100 тисяч, то це може зайняти багато часу!

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

Читайте також  Що таке UX/UI дизайн насправді?

Давайте подивимося, як він працює.

Алгоритм полягає в ковзанні лінії (вертикальної або горизонтальної) по області з точками. Коли він зустрічає точку, починає малювати з неї параболу, яка триває замітаючої лінією. Ось анімація цього процесу:


Пересічні параболи утворюють ребра Вороного. Але чому параболи?

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


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


Коли площина ковзає і відбувається перший контакт з конусом, отримана лінія буде такою:


При подальшому русі площині за конусам ми побачимо, як утворюються параболи:


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

Як сказано вище, це досить складно зрозуміти, тому ось посилання на реалізації з відкритим кодом, які можна використовувати і вивчати:

  • Java на GitHub. Автори: Benny Kjær Nielsen і Allan Odgaard https://github.com/sorbits/visual-fortune-algorithm/tree/master
  • Python на GitHub: https://github.com/MikkoJo/Voronoi. Автор: Mikko Johansson
  • Детальна реалізація алгоритму Форчуна: http://blog.ivank.net/fortunes-algorithm-and-implementation.html

 

Инкрементная вставка трикутників

Інший метод полягає в інкрементній вставці по одній точці, починаючи з базового трикутника з трьох точок за межами можливої області всіх інших точок. Цей метод виконується O(n^2) і не вимагає наявності всіх точок на момент генерації.

При вставці нової точки вона визначає існуючу область, в яку вона потрапляє. Ця область потім підрозділяється та створюються нові області.

Ось приклад з відкритим вихідним кодом для використання і вивчення:

  • Ісходник на Java. Автор: Paul Chew. Для вільного використання. Завантажити ZIP-файл. Джерело: http://www.cs.cornell.edu/home/chew/Delaunay.html

 

Висновок

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

Степан Лютий

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

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *