ВИЗНАЧЕННЯ ЗІТКНЕНЬ І ПРЕДСТАВЛЕННЯ ОБ’ЄКТІВ В 2D – РОЗРОБКА ІГОР ДЛЯ ОС ANDROID

&nbsp

Оскільки в нашому світі є рухомі обєкти, існують і взаємодії між ними Одним з видів таких взаємодій є зіткнення Два обєкти вважаються зіткнулися, коли вони будь-яким чином перетинаються Ми вже зустрічалися із зіткненнями, коли перевіряли, що поглинає містер Ном – себе або чорнильна пляма Визначення зіткнень звичайно супроводжується відповіддю на зіткнення: після того як ми визначили, що два обєкти зіткнулися, ми повинні відреагувати на зіткнення коригуванням положення та / або руху наших обєктів належним чином Наприклад, коли Маріо стрибає на гриб Гумба, Гумба вирушає у свій грибний рай, а Маріо виконує ще один маленький стрибок Більш точний приклад – зіткнення і реакція на зіткнення двох і більше більярдних куль Ми не будемо заглиблюватися в розбір цього виду реакції на зіткнення, оскільки це не потрібно для наших цілей Наша реакція на зіткнення зазвичай складатиметься у зміні стану обєкта (наприклад, обєкт може вибухнути, померти, забрати монетку і т д) Тип реакції залежить від гри, тому ми не будемо говорити про неї в цьому розділі Отже, як же ми визначаємо, що два обєкти зіткнулися У першу чергу треба подумати, коли перевіряти, чи є зіткнення Якщо наші обєкти відповідають небудь простим фізичним моделям, про що говорилося в попередньому розділі, ми можемо виробляти перевірку на зіткнення після того, як перемістили всі наші обєкти на поточний кадр і крок за часом вперед

Обмежують фігури

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

Рис 88 Різні обмежують фігури навколо Боба

Це три типи обмежують фігур Кожна, відповідно, має такі властивості

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

Обмежуючий прямокутник з привязкою до осей координат Обмежує обєкт допомогою прямокутника, який привязаний до осей координат, тобто його верхня і нижня сторони завжди збігаються з віссю х, а права й ліва сторони – з віссю у Така фігура забезпечує легкість перевірок, але точність буде нижче, ніж у трикутної мережі Обмежуюча рамка зазвичай зберігається у вигляді координати її нижнього лівого кута і її ширини і довжини (при роботі з 2D фігури також можуть називатися обмежуючими прямокутниками)

Обмежуючий коло Обмежує обєкт найменшою окружністю, яка може вмістити обєкт Вона дуже швидко тестується, але результати найменш точні з усіх обмежують фігур Коло зазвичай зберігається у вигляді координати центру та діаметру

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

Звичайно, ми повинні встановити координати, масштаб і положення обмежує фігури відповідно до координатами, масштабом і положенням обєкта, коли переміщаємо обєкт, скажімо, на етапі інтегрування фізики

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

Масштабування обмежує фігури трохи складніше Спочатку потрібно задати точку, навколо якої ми будемо масштабувати Зазвичай це позиція обєкта, яка визначається по центру обєкта З урахуванням цього масштабування теж буде нескладним Для трикутної мережі масштабується координати кожної вершини, для би прямокутника – ширину, довжину і нижній лівий кут, а для обмежує кола – радіус (центр кола дорівнює центру обєкта)

Обертання обмежує фігури також залежить від визначення точки обертання При згаданому вище умови (обертання відбувається навколо центру обєкта), обертання не складе труднощів У випадку з трикутної мережею ми просто вращаем всі вершини навколо центру обєкта З обмежуючим колом взагалі нічого не доведеться робити, так як його радіус не зміниться, як би ми не обертали обєкт З обмежуючим прямокутником доведеться повозитися довше Нам треба буде побудувати всі 4 вершини, обертати їх, а потім знайти привязаний до осей координат обмежує прямокутник, який включатиме всі 4 точки На рис 89 показані всі три обмежують фігури після обертання

Рис 89 Обмежують фігури після обертання при центрі обєкта як точці обертання

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

Створення обмежують фігур

У цьому прикладі я просто побудував обмежують фігури від руки, взявши за основу зображення Боба Але зображення Боба зроблено в пікселах, а відстані в нашому світі можуть вимірюватися метрами Для вирішення цієї проблеми буде потрібно нормалізація і застосування простору моделі Уявіть собі два трикутника, які ми можемо використовувати для Боба в просторі моделі, коли будемо візуалізувати його при допомоги OpenGL Прямокутник знаходиться по центру на початку координат простору моделі і має таке ж співвідношення ширини і висоти, як і текстурне зображення Боба (наприклад, 32 х 32 пікселя на текстурної карті і 2 х 2 м в просторі моделі) Тепер ми можемо застосувати растрове зображення Боба і зясувати, де в просторі моделі будуть знаходитися точки обмежують фігур На рис 810 показано, як ми створюємо обмежують фігури навколо Боба в просторі моделі

Рис 810 Обмежують фігури навколо Боба в просторі моделі

Цей процес може здатися дещо трудомістким, хоча насправді вживаються кроки не так і складні У першу чергу ми повинні памятати, як працює обробка текстур Ми задаємо текстурні координати для кожної вершини прямокутника Боба (який складається з двох трикутників) в текстурному просторі Верхній лівий кут растрового зображення в текстурному просторі знаходиться в (0, 0), а нижній лівий кут – в (1 1) незалежно від ширини і висоти зображення у пікселях Щоб перейти з пиксельного простору в текстурне, ми можемо використовувати таке нескладне перетворення:

де u і у – текстурні координати пікселя, що знаходиться під координатами хну в просторі зображення ImageWi dth і i mageHei ght встановлюються за розмірами зображення у пікселях (у разі Боба – 32 х 32) На рис 811 зображено, як центр зображення Боба переноситься в текстурне простір

Текстура застосовується до прямокутника, який ми задаємо в просторі моделі На рис 810 був показаний приклад, де верхній лівий кут знаходився в точці (-1 1), а нижній правий – в (1 -1) Для вимірювань в нашому світі використовуємо метри, тому ширина і довжина прямокутника рівні 2 м кожна Крім того, ми знаємо, що верхній правий кут має текстурні координати (0, 0), а нижній правий кут – (1 1), і таким чином ми наносимо повну текстуру Боба Проте в одному з наступних розділів ви побачите, що це не завжди працює подібним чином

Рис 811 Перенесення пікселя з простору зображення в текстуроване простір

Розглянемо універсальний спосіб асоціювання текстурного простору з простором моделі Ми можемо спростити собі завдання, обмежуючи обробку тільки привязаними до осей координат прямокутниками в текстурному просторі і просторі моделі Це означає, що ми допускаємо, що привязана до осей координат прямокутна область в текстурному просторі переноситься в привязаний до осей координат прямокутник в просторі моделі Для перетворення нам потрібно знати ширину і довжину прямокутника в просторі моделі і ширину і довжину прямокутника в текстурному просторі У нашому прикладі з Бобом у нас є прямокутник 2 х 2 в просторі моделі і прямокутник 1 х 1 в текстурному просторі (оскільки ми переносимо повну текстуру в прямокутник) Нам також необхідно знати координати верхнього лівого кута кожного прямокутника у відповідному просторі Для прямокутника в просторі моделі це (-1 1), а для прямокутника в текстурному просторі – (0, 0) (знову ж, оскільки ми переносимо всю текстуру, а не її частина) З цими даними і координатами і я у пікселя, який ми хочемо перенести в простір моделі, ми можемо зробити перетворення за допомогою наступних двох рівнянь:

Змінні і і v – це координати, які ми вирахували в останньому перетворенні з пиксельного в текстурне простір Змінні min U і min V – це координати верхнього лівого кута області, яку ми переносимо з текстурного простору Змінні tWidth і tHeight – ширина і довжина нашої області текстурного простору Змінні mWidth і mHeight – ширина і довжина прямокутника нашого простору моделі Змінні minx і minY, як ви здогадалися, – координати верхнього лівого кута прямокутника в просторової моделі І нарешті, х і у є перетвореними координатами в просторі моделі

Ці рівняння приймають координати асоціюють їх з діапазоном від 0 до 1, потім масштабують і поміщають в простір моделі На рис 812 зображений тексел в текстурному просторі і те, як він перенесений в прямокутник в просторі моделі З боків ви бачите tWi dth, tHeight, mWidth і mHeight відповідно Верхній лівий кут кожного прямокутника відповідає координатам (mi пі minV) в текстурному просторі і (min X minY) в просторі моделі

Рис 812 Перенесення з текстурного простору в простір моделі

Замінивши перші два рівняння, ми можемо прямо перейти від пиксельного простору до простору моделі:

Ми можемо використовувати ці два рівняння для обчислення обмежують фігур наших обєктів, побудованих на основі зображення, яке ми перемістили в їх прямокутники за допомогою обробки текстури У випадку трикутної мережі це може бути дещо складним обмежує прямокутник і обмежує коло набагато простіше Зазвичай ми не йдемо цим складним шляхом, а намагаємося створити текстури таким чином, щоб хоча б обмежують прямокутники мали таке ж співвідношення сторін, як і прямокутник, який ми визуализируем для обєкта за допомогою OpenGL ES Таким чином ми можемо будувати обмежує прямокутник прямо за розмірами зображення обєкта Це ж буде вірним і для обмежує кола Я просто хотів показати, як ви можете створити яку-небудь обмежуючу фігуру навколо зображення, яке переноситься в простір моделі

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

&nbsp

Атрибути ігрових обєктів

Тепер наш Боб став товщі Крім мережі, яку ми використовуємо для візуалізації (відображення прямокутника в текстурі зображення Боба), у нас також є вторинна структура даних, яка зберігає його кордону в якійсь формі Важливо розуміти що поки ми моделюємо кордону по перенесеної версії Боба в просторі, самі ці межі незалежні від того ділянки текстури, куди ми переносимо прямокутник Боба Звичайно, створюючи обмежує фігуру, ми намагаємося надати їй максимальну відповідність контуру Боба в текстурі Втім, неважливо, чи має текстуроване зображення розміри 32 х 32 або 128 х 128 пікселів В обєкта в нашому ігровому світі, таким чином, є три групи атрибутів

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

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

Графічне представлення Як показано на рис 812, ми всі так само використовуємо два трикутника, щоб створити один прямокутник для Боба, і переносимо його зображення на прямокутник Прямокутник визначається в просторі моделі, однак він необовязково дорівнює обмежує фігурі, як показано на рис 810 Графічний прямокутник Боба, який ми посилаємо в OpenGL ES, трохи більше, ніж його обмежує прямокутник

Такий поділ атрибутів дозволяє нам знову застосувати патерн Модель – вид – контролер (MVC)

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

Вид приймає графічне представлення Боба (наприклад, два текстурних трикутника, визначених у просторі моделі) і відображає їх на відповідних позиціях в ігровому світі, залежно від позиції, обертання і масштабу Боба Тут ми можемо використовувати матричні операції OpenGL ES, як робили раніше

Контролер відповідає за оновлення фізичних атрибутів Боба відповідно з вводяться користувачем даними (наприклад, натискання клавіші Вліво посуне його вліво), а також відповідно з такими фізичними силами, як прискорення вільного падіння (як ті, які ми застосовували до гарматного ядра в попередньому розділі)

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

Широка і вузька фази визначення зіткнень

Ми все ще не знаємо, як перевіряти наявність зіткнень між нашими обєктами і їх обмежують фігурами Дві фази визначення зіткнення такі

Широка фаза На цьому етапі ми намагаємося визначити, які обєкти в принципі можуть зіткнутися Уявіть, що є 100 обєктів, кожен з яких може зіткнутися з іншими Якщо ми вирішимо спрощено перевірити кожну можливу пару обєктів, нам доведеться провести 100 х 100/2 перевірок на перетин Цей метод тестування на перетин має асимптотическую складність 0 (п2) це означає, що буде потрібно п2 кроків для завершення тесту (насправді ми закінчимо, виконавши лише половину операцій, але асимптотическая складність не враховує константи) При використанні більш розумного алгоритму для широкої фази ми намагаємося визначити, які пари обєктів мають ймовірні шанси на зіткнення Інші пари (наприклад, два обєкти, які розташовані дуже далеко один від одного, щоб зіткнутися), що не будуть перевірятися Таким чином ми зможемо зменшити обчислювальну навантаження на цьому етапі, так як у вузькій фазі тестування вимагає більше витрат

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

&nbsp

Вузька фаза

Після того як ми розібралися з далеким етапом, нам потрібно перевірити, чи перетинаються обмежують фігури обєктів, які потенційно можуть зіткнутися Я вже згадував раніше, що у нас є кілька видів обмежують фігур Трикутні мережі самі трудомісткі в плані обчислення і створення Звичайно в більшості 2D-nrp ми можемо обійтися обмежуючими прямокутниками і колами, тому сконцентруємося на них

Зіткнення кіл Обмежують кола – найменш складний інструмент для перевірки зіткнень Визначимо простий клас Circle (лістинг 84)

Лістинг 84 Circlejava, простий клас Circle

Ми зберігаємо центр як Vector2 і радіус як звичайне число з плаваючою крапкою Як перевірити, перекривають чи два кола один одного Дивимося на рис 813

Рис 813 Два кола, що перекривають один одного, і два кола, які не перекривають один одного

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

Спочатку вимірюємо відстань між центрами, а потім дізнаємося, перевищує цю відстань суму радіусів або дорівнює йому

Нам доведеться витягти квадратний корінь у методі Vector2 di st Це не дуже добре, оскільки витяг квадратного кореня – витратна операція Чи можемо ми зробити це швидше Можемо – достатньо тільки переформулювати наші умови:

Ми можемо позбутися квадратного кореня, звівши в ступінь обидві частини нерівності, з чого вийде:

Ми замінюємо квадратний корінь додатковими складанням і множенням в правій частині

Так вже краще Створимо функцію Vector2distSquared, яка поверне нам зведене в квадрат відстань між двома векторами:

Тоді метод over apCircles буде таким:

Зіткнення прямокутників Займемося прямокутниками Для початку нам знадобиться клас, який представлятиме прямокутник Раніше ми вже згадували, що збираємося визначати прямокутник його нижнім лівим кутом, шириною і довжиною Зробимо це, як в лістингу 85

Лістинг 85 RectangleJava, клас Rectangle

Ми зберігаємо координати нижнього лівого кута як Vector2, а ширину і довжину як два числа з плаваючою крапкою Як перевірити, перекриваються чи два прямокутники Подання про це можна отримати на рис 814

Рис 814 Перекриваються і неперекривающіеся прямокутники

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

Перевірка на перетин для прямокутників на перший погляд здається складною Однак трохи логіки – і ми можемо отримати досить простий тест Ось найпростіший метод перевірки на перетин між двома прямокутниками:

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

Зіткнення кола і прямокутника Чи можемо ми перевірити наявність зіткнення між колом і прямокутником Так, можемо, однак це буде складніше Розглянемо рис 815

Рис 815 Перевірка на перетин кола і прямокутника шляхом знаходження близькому до кола точки на / в прямокутнику

Загальна концепція перевірки на перетин кола і прямокутника виглядає приблизно так

Спочатку треба знайти найближчу до центру кола координату х на периметрі прямокутника або в самому прямокутнику Ця координата може бути точкою на лівій або правій стороні прямокутника, якщо тільки круг не знаходиться усередині прямокутника, тому що в цьому випадку найближчій х-координатою буде х-координата центру кола

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

Якщо точка, яка визначається найближчими х-і у-координатами, знаходиться в межах кола, коло і прямокутник перетинаються Хоча цей метод не зображений на рис 815, він також працює для кіл, повністю містять прямокутник Відобразимо метод в коді:

Опис виглядало страшніше, ніж виконання Ми визначаємо найближчу точку прямокутника щодо кола, а потім просто перевіряємо, чи знаходиться точка всередині кола Якщо це так, то коло і прямокутник перетинаються Зверніть увагу, що я додав перевантажений метод distSquared до Vector2, який бере дві змінні float замість ще одного Vector2 Я зробив те ж саме для функції diSt О

Всі разом

Перевірка, чи лежить точка всередині кола або прямокутника, теж може бути корисною Закодуємо ще два методи і відправимо в клас під назвою Overl apTester разом з трьома іншими методами, які ми вже визначили (лістинг 86)

Лістинг 86 OverlapTesterjava: перевірка на перетин кіл, прямокутників і точок

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

Широка фаза

Як же нам отримати від широкої фази максимум користі Подивіться на рис 816, на якому показана типова сцена з Супер Маріо

Рис 816 Супер Маріо і його вороги рамки навколо обєктів – обмежують прямокутники великі прямокутники створюють сітку, накладену на картинку

Здогадуєтеся, що ми можемо зробити, щоб уникнути деяких перевірок Сітка на рис 816 являє собою осередки, на які ми ділимо наш ігровий світ Кожна комірка має один і той же розмір осередки покривають весь світ Маріо в даний момент у двох з цих осередків Інші обєкти, з якими Маріо може зіткнутися, знаходяться в інших осередках Таким чином, нам не потрібно проводити жодних перевірок зіткнення, оскільки Маріо не може перебувати в тих же осередках, що й інші обєкти в кадрі Необхідно зробити наступне:

Оновити всі обєкти світу на основі застосовуваної фізики та управління

Оновити позицію кожної обмежує фігури кожного обєкта згідно з позицією обєкта Звичайно, ми також можемо включити сюди і оновлення орієнтації та масштабу

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

Перевірити на зіткнення, але тільки ті пари обєктів, які можуть зіткнутися (наприклад, гумбо не можуть зіткнутися з іншими гумбо) і які знаходяться в одній комірці На цьому етапі широкої фази застосовується просторова сітка (spatial hash grid), реалізація цього етапу не складає труднощів Перше, що нам необхідно визначити, – розмір кожного осередку Він багато в чому залежить від масштабу і компонентів, які ми використовуємо в ігровому світі

Ускладнений приклад

Продовжимо розглядати широку фазу з просторовою сіткою на нашому останньому прикладі з гарматним ядром Ми повністю переробимо цей приклад, включивши все, про що йшла мова в цьому розділі Крім гармати і ядра у нас повинні бути мішені для стрільби Не будемо ускладнювати собі життя і використовуємо в якості мішеней квадрати розміром 0,5 х 0,5 м Ці квадрати статичні і не рухаються Наша гармата також статична Єдине, що рухається, – це, власне, саме ядро В цілому ми можемо розділити обєкти в нашій грі на статичні (нерухомі) і динамічні (рухливі) Створимо клас для представлення таких обєктів

                                                                

Джерело: Mario Zechner / Маріо Цехнер, «Програмування ігор під Android», пров Єгор Сидорович, Євген зазноби, Видавництво «Пітер»

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*