Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > разработка игр, графический дизайн и моделирование > Gamedev - cоздание игр: Unity, OpenGL, DirectX
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 14.12.2013, 21:51   #1
Shkolota
Пользователь
 
Регистрация: 02.04.2013
Сообщений: 51
Восклицание Столкновения в 2D-игре

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

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

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

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

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

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

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

Что вы можете сказать в отношении всего вышесказанного?
Shkolota вне форума Ответить с цитированием
Старый 14.12.2013, 23:21   #2
Selestis
Форумчанин
 
Аватар для Selestis
 
Регистрация: 21.01.2009
Сообщений: 719
По умолчанию

По поводу большого количества объектов - можно пробовать mark&sweep. Сортируете объекты по левой и правой границе по каждой оси - в итоге получается намного меньше необходимых проверок. Применял данный способ как расстояние от точки (0,0) - то бишь радиус, и на каждый объект приходилось чрезвычайно мало проверок. Также стоит посмотреть BSP Tree и QuadTree - разбиваете пространство на 2 или 4 части рекурсивно, и столкновения проверяете только внутри текущей части. Ну это в двух словах. К слову, эти методы не решают правильно упомянутую вами проблему скорости. Тут надо читать про continuous collision detection - с этим сложнее и боюсь соврать, так что не буду комментировать.
Изобретатель велосипедов
Selestis вне форума Ответить с цитированием
Старый 14.12.2013, 23:24   #3
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

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

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

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

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

Последний раз редактировалось phomm; 14.12.2013 в 23:28.
phomm вне форума Ответить с цитированием
Старый 15.12.2013, 00:41   #4
Shkolota
Пользователь
 
Регистрация: 02.04.2013
Сообщений: 51
По умолчанию

phomm, если есть пример, и он не является тайной, можно было бы его увидеть? Или хотя бы узнать об основных методах реализации такой системы.
Shkolota вне форума Ответить с цитированием
Старый 15.12.2013, 09:37   #5
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Просчет столкновения DimaLyao Общие вопросы C/C++ 0 04.12.2011 14:16
столкновения в GLScene beygul Gamedev - cоздание игр: Unity, OpenGL, DirectX 9 18.11.2011 22:12
Сложно ли реализовать столкновения? MaratZahidyl Gamedev - cоздание игр: Unity, OpenGL, DirectX 3 11.11.2011 16:12
Столкновения 3D моделей Zver1993 Gamedev - cоздание игр: Unity, OpenGL, DirectX 2 09.10.2010 13:19
Расчет столкновения шариков. belomorinka Общие вопросы Delphi 3 02.06.2009 18:54