Последние записи

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

17th
Дек

Столкновения в 2D-игре

Posted by maloy under Заметки, Общалка

Shkolota

Здравствуйте. Вот есть вопрос, который уже давно я обдумываю — какие существуют способы организации столкновений в 2D-играх с видом сверху (например, в стратегиях)? К примеру, камера расположена стандартно, как в Warcraft 2 (чтобы не усложнять).

У нас есть массив всех игровых объектов — стен, зданий, боевых единиц… Всего, на что хватит фантазии. Но игра чуть посложнее тех, что обычно разрабатываются на этом форуме, оттого, простые модели организации данных здесь вряд ли уместны. Прежде всего, модульность — разбиение игры на классы, модули — как это принято, чтобы один объект не знал о существовании другого. Не двумерный массив ячеек с записями, а самые что ни на есть настоящие классы. Допустим, у каждого объекта существует поле ‘Физическая модель’ — простой прямоугольник, настраиваемый внутри данного объекта.

Так вот, у нас имеется обычный массив всех игровых объектов, и у каждого из них есть своя физическая модель, представленная в виде прямоугольника. Допустим, в массиве 200 элементов. И вот, если проверять столкновения обычными способами, то есть, проходя в цикле по всем объектам и еще в одном таком же, только вложенном, проверять для них столкновения с каждым из остальных объектов на карте, то получим:

200 * 199 = 39 800 проходов по циклу только для обычной проверки столкновений. А мы знаем, что задачи даже самой простой игры намного шире, и помимо этого в цикле может выполняться еще очень много действий.

О, еще есть и такой параметр, как скорость. Скорость объекта должна быть ограничена какими-то значениями. А что, если скорость боевой единицы превысила минимальный размер объекта на карте? Вполне возможно наличие объекта с размером физической модели в 20 px, а скорость снаряда при этом вполне может превышать 20 px за шаг, и тогда наши снаряды — ракеты или пули, будут пролетать сквозь объекты.

Решение проблемы скорости я пока знаю только одно — при каждой проверке на столкновения разбивать скорость объекта на несколько отрезков, не превышающих минимальный размер объекта в игре и таким образом исключать возможность прохождения объектов друг сквозь друга. Но, разбей мы скорость объекта на 4 отрезка, и придется 39 800 умножить на 4, а в данной ситуации я боюсь это делать.

Что такое ‘Карта путей’? Если я не ошибаюсь, то, построив один раз подобную карту (всего 200 шагов по нашему массиву), мы сможем каждый объект сталкивать не с каждым объектом, а с этой самой картой путей. Вообще, представления о ней у меня размыты, и я даже не знаю, существует ли такое понятие программировании игр… Подобное предположение возникло при изучении редактора такой известной игры как Warcraft — там в меню есть галочка ‘Отображать карту путей’, и при ее активации карта разбивается на проходимые и непроходимые участки, закрашенные определенным цветом. Отсюда возникло и предположение о существовании подобной технологии, но интернеты мало о ней поведали.

Что вы можете сказать в отношении всего вышесказанного?

Selestis

По поводу большого количества объектов — можно пробовать mark&sweep. Сортируете объекты по левой и правой границе по каждой оси — в итоге получается намного меньше необходимых проверок. Применял данный способ как расстояние от точки (0,0) — то бишь радиус, и на каждый объект приходилось чрезвычайно мало проверок. Также стоит посмотреть BSP Tree и QuadTree — разбиваете пространство на 2 или 4 части рекурсивно, и столкновения проверяете только внутри текущей части. Ну это в двух словах. К слову, эти методы не решают правильно упомянутую вами проблему скорости. Тут надо читать про continuous collision detection — с этим сложнее и боюсь соврать, так что не буду комментировать.

phomm

Я могу много чего сказать.
То, что Вы описываете, ещё не сложная модель.
У неё , насколько я знаю, есть 3 метода решения, плюс я свой разработал, который можно отнести к развитию одного из этих 3.
Итак, первый, простой и эффективный способ. Физ движок. Минус только один — надо разобраться как с ним работать.
2. Деревья, это такая структура данных, которая разбивает пространство иерархично и поиск внутри такой структуры обычно производится за время log N (обычный перебор, как вы заметили N*N), объекты соотносятся с листьями в дереве и для проверок используются только соседние листья, есть вполне известный пример — чанки из майнкрафта. Конкретно вряд ли что подскажу, никогда с деревьями в гейм-областях не работал.

3. Клеточное разбиение. Самое простое что может быть, но , правда зависит от реализации. Самая существенная часть реализации это соотнесение размеров объектов размерам клеток. Если объект и клетка соотносятся 1 к 1 одному то получается самая простая схема — типа сокобана. Есть вариация с дробными размерами клетки — танчики, где можно исхитряться находиться между клетками, но в целом всё всё равно ориентируется по ним. Когда объект больше 1 клетки и занимает их много и даже нерегулярно — то начинаются сложности в некоторых вещах, но , в принципе проверку столкновений сделать несложно, просто проверить все объекты в радиусе макс размера объектов. Но проверять не перебором, а через клетки, которые содержат ссылки на тех кто на них находится. Если объект занимает допустим 3*3 клетки, то во всех клетках прописана ссылка на существо. Если существо движется, то на каждом шаге оно обнуляет ссылки в тех клетках где оно было и выставляет на те клетки куда оно идёт (с проверкой на занятость ессно). Проверка на столкновения чисто математически — перебор только ближних клеток.
Проверка на столкновение для летящих объектов также возможна через клеточное разбиение, когда летящий объект не просто приращивает свои координаты , а «трейсит» путь по которому он пройдёт (например алгоритмом брезенхема) и по всем этим клеточкам тоже проверяет ссылочки на другие объекты.

Карта путей, по сути нет такого понятия, скорее всего в данном случае было клеточное разбиение, где часть клеток непроходима, а совокупность проходимых и была картой путей, вот и всё.

Лично мой способ — специальная система, которая знает каждый пиксель на экране, таким образом, что каждый пиксель это «клетка». И все описанные операции с клетками как в 3 способе, производятся автоматически в этой системе, любое столкновение объектов своими пикселями приводит к их оповещению. Плюс метода в том, что не надо знать и рассчитывать никаких математических попаданий, если пиксель на экране «столкнулся» с другим пикселем — система сразу это видит, и если на то есть необходимость — производятся игровые действия.
Есть и пример этой системы (правда, недоработаный во многом).

Пример вот http://programmersforum.ru/showpost….&postcount=169
Там же некоторое описание к нему. Написано на дельфи + GDI + Canvas. Нет компонентов вообще (голая форма с методами, которые вызывают движок, и таймер, управляемым движком), не используются никакие сторонние вещи, кроме библиотек (в виде юнитов) для загрузки графических форматов.
Реализация несложная сама по себе, но у меня она сквозь всё приложение протянута, все элементы работают на ней, и в итоге получилось довольно прилично (3 кстрок сама реализация) и 1 кстрока клиентский код (+1 кстрока игрового кода, который по сути не используется в той демке).
Суть™ : Каждый объект в игре состоит из 2 компонент — программная сущность и графическая сущность. Программная сущность отвечает за взаимодействие со всем(она главнее), графическая — за отрисовку и пиксельчек (она подчинённая). Глобально есть класс пиксельного движка, он содержит данные и методы для работы с пиксельным буфером экрана. Все графические сущности регистрируются в его коллекции. Он на каждой итерации спрашивает все графические сущности — куда они хотят себя «поставить» и производит «ремап» пиксельных буферов. Пиксельный буфер это грубо говоря 2дмассив размером с графическое представление сущности (картинку), где просто выставлено true/false — занят пиксель или это пустота. Движковый же класс имеет пиксельбуфер размером с игровое окно, каждая ячейка соответствует пикселю на экране, а хранит ссылку на графическую сущность, таким образом, при операциях ремапа если в конкретном пикселе уже записана чья-то ссылка, то попытка другой сущности встать туда (путём обычного обхода массива смотрится, занят ли пиксель, если true в пиксельбуфере сущности, то ссылка на сущность попадёт в пиксельбуфер движка) приведёт к оповещению обоих столкнувшихся сущностей.
Также это используется для хиттеста мыши — если в движковом пиксельбуфере ячейка по координатам курсора мыши имеет ссылку на сущность — то ей сообщается что мышь на ней.
Работает на удивление быстро, хотя я ещё знаю куда можно ужаться в плане скорости. Буферайз всего и вся рулит. А в планах вообще было перейти на какую-то специальную библиотеку графическую (но процессорную, типа FastLib, а мб даже и видюшную), через код-адаптер, эта работа была начата.

тема на форуме