|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
14.12.2013, 21:51 | #1 |
Пользователь
Регистрация: 02.04.2013
Сообщений: 51
|
Столкновения в 2D-игре
Здравствуйте. Вот есть вопрос, который уже давно я обдумываю - какие существуют способы организации столкновений в 2D-играх с видом сверху (например, в стратегиях)? К примеру, камера расположена стандартно, как в Warcraft 2 (чтобы не усложнять).
У нас есть массив всех игровых объектов - стен, зданий, боевых единиц... Всего, на что хватит фантазии. Но игра чуть посложнее тех, что обычно разрабатываются на этом форуме, оттого, простые модели организации данных здесь вряд ли уместны. Прежде всего, модульность - разбиение игры на классы, модули - как это принято, чтобы один объект не знал о существовании другого. Не двумерный массив ячеек с записями, а самые что ни на есть настоящие классы. Допустим, у каждого объекта существует поле 'Физическая модель' - простой прямоугольник, настраиваемый внутри данного объекта. Так вот, у нас имеется обычный массив всех игровых объектов, и у каждого из них есть своя физическая модель, представленная в виде прямоугольника. Допустим, в массиве 200 элементов. И вот, если проверять столкновения обычными способами, то есть, проходя в цикле по всем объектам и еще в одном таком же, только вложенном, проверять для них столкновения с каждым из остальных объектов на карте, то получим: 200 * 199 = 39 800 проходов по циклу только для обычной проверки столкновений. А мы знаем, что задачи даже самой простой игры намного шире, и помимо этого в цикле может выполняться еще очень много действий. О, еще есть и такой параметр, как скорость. Скорость объекта должна быть ограничена какими-то значениями. А что, если скорость боевой единицы превысила минимальный размер объекта на карте? Вполне возможно наличие объекта с размером физической модели в 20 px, а скорость снаряда при этом вполне может превышать 20 px за шаг, и тогда наши снаряды - ракеты или пули, будут пролетать сквозь объекты. Решение проблемы скорости я пока знаю только одно - при каждой проверке на столкновения разбивать скорость объекта на несколько отрезков, не превышающих минимальный размер объекта в игре и таким образом исключать возможность прохождения объектов друг сквозь друга. Но, разбей мы скорость объекта на 4 отрезка, и придется 39 800 умножить на 4, а в данной ситуации я боюсь это делать. Что такое 'Карта путей'? Если я не ошибаюсь, то, построив один раз подобную карту (всего 200 шагов по нашему массиву), мы сможем каждый объект сталкивать не с каждым объектом, а с этой самой картой путей. Вообще, представления о ней у меня размыты, и я даже не знаю, существует ли такое понятие программировании игр... Подобное предположение возникло при изучении редактора такой известной игры как Warcraft - там в меню есть галочка 'Отображать карту путей', и при ее активации карта разбивается на проходимые и непроходимые участки, закрашенные определенным цветом. Отсюда возникло и предположение о существовании подобной технологии, но интернеты мало о ней поведали. Что вы можете сказать в отношении всего вышесказанного? |
14.12.2013, 23:21 | #2 |
Форумчанин
Регистрация: 21.01.2009
Сообщений: 719
|
По поводу большого количества объектов - можно пробовать mark&sweep. Сортируете объекты по левой и правой границе по каждой оси - в итоге получается намного меньше необходимых проверок. Применял данный способ как расстояние от точки (0,0) - то бишь радиус, и на каждый объект приходилось чрезвычайно мало проверок. Также стоит посмотреть BSP Tree и QuadTree - разбиваете пространство на 2 или 4 части рекурсивно, и столкновения проверяете только внутри текущей части. Ну это в двух словах. К слову, эти методы не решают правильно упомянутую вами проблему скорости. Тут надо читать про continuous collision detection - с этим сложнее и боюсь соврать, так что не буду комментировать.
Изобретатель велосипедов
|
14.12.2013, 23:24 | #3 |
personality
Старожил
Регистрация: 28.04.2009
Сообщений: 2,886
|
Я могу много чего сказать.
То, что Вы описываете, ещё не сложная модель. У неё , насколько я знаю, есть 3 метода решения, плюс я свой разработал, который можно отнести к развитию одного из этих 3. Итак, первый, простой и эффективный способ. Физ движок. Минус только один - надо разобраться как с ним работать. 2. Деревья, это такая структура данных, которая разбивает пространство иерархично и поиск внутри такой структуры обычно производится за время log N (обычный перебор, как вы заметили N*N), объекты соотносятся с листьями в дереве и для проверок используются только соседние листья, есть вполне известный пример - чанки из майнкрафта. Конкретно вряд ли что подскажу, никогда с деревьями в гейм-областях не работал. 3. Клеточное разбиение. Самое простое что может быть, но , правда зависит от реализации. Самая существенная часть реализации это соотнесение размеров объектов размерам клеток. Если объект и клетка соотносятся 1 к 1 одному то получается самая простая схема - типа сокобана. Есть вариация с дробными размерами клетки - танчики, где можно исхитряться находиться между клетками, но в целом всё всё равно ориентируется по ним. Когда объект больше 1 клетки и занимает их много и даже нерегулярно - то начинаются сложности в некоторых вещах, но , в принципе проверку столкновений сделать несложно, просто проверить все объекты в радиусе макс размера объектов. Но проверять не перебором, а через клетки, которые содержат ссылки на тех кто на них находится. Если объект занимает допустим 3*3 клетки, то во всех клетках прописана ссылка на существо. Если существо движется, то на каждом шаге оно обнуляет ссылки в тех клетках где оно было и выставляет на те клетки куда оно идёт (с проверкой на занятость ессно). Проверка на столкновения чисто математически - перебор только ближних клеток. Проверка на столкновение для летящих объектов также возможна через клеточное разбиение, когда летящий объект не просто приращивает свои координаты , а "трейсит" путь по которому он пройдёт (например алгоритмом брезенхема) и по всем этим клеточкам тоже проверяет ссылочки на другие объекты. Карта путей, по сути нет такого понятия, скорее всего в данном случае было клеточное разбиение, где часть клеток непроходима, а совокупность проходимых и была картой путей, вот и всё. Лично мой способ - специальная система, которая знает каждый пиксель на экране, таким образом, что каждый пиксель это "клетка". И все описанные операции с клетками как в 3 способе, производятся автоматически в этой системе, любое столкновение объектов своими пикселями приводит к их оповещению. Плюс метода в том, что не надо знать и рассчитывать никаких математических попаданий, если пиксель на экране "столкнулся" с другим пикселем - система сразу это видит, и если на то есть необходимость - производятся игровые действия. Есть и пример этой системы (правда, недоработаный во многом). Последний раз редактировалось phomm; 14.12.2013 в 23:28. |
15.12.2013, 00:41 | #4 |
Пользователь
Регистрация: 02.04.2013
Сообщений: 51
|
phomm, если есть пример, и он не является тайной, можно было бы его увидеть? Или хотя бы узнать об основных методах реализации такой системы.
|
15.12.2013, 09:37 | #5 |
personality
Старожил
Регистрация: 28.04.2009
Сообщений: 2,886
|
Пример вот http://programmersforum.ru/showpost....&postcount=169
Там же некоторое описание к нему. Написано на дельфи + GDI + Canvas. Нет компонентов вообще (голая форма с методами, которые вызывают движок, и таймер, управляемым движком), не используются никакие сторонние вещи, кроме библиотек (в виде юнитов) для загрузки графических форматов. Реализация несложная сама по себе, но у меня она сквозь всё приложение протянута, все элементы работают на ней, и в итоге получилось довольно прилично (3 кстрок сама реализация) и 1 кстрока клиентский код (+1 кстрока игрового кода, который по сути не используется в той демке). Суть™ : Каждый объект в игре состоит из 2 компонент - программная сущность и графическая сущность. Программная сущность отвечает за взаимодействие со всем(она главнее), графическая - за отрисовку и пиксельчек (она подчинённая). Глобально есть класс пиксельного движка, он содержит данные и методы для работы с пиксельным буфером экрана. Все графические сущности регистрируются в его коллекции. Он на каждой итерации спрашивает все графические сущности - куда они хотят себя "поставить" и производит "ремап" пиксельных буферов. Пиксельный буфер это грубо говоря 2дмассив размером с графическое представление сущности (картинку), где просто выставлено true/false - занят пиксель или это пустота. Движковый же класс имеет пиксельбуфер размером с игровое окно, каждая ячейка соответствует пикселю на экране, а хранит ссылку на графическую сущность, таким образом, при операциях ремапа если в конкретном пикселе уже записана чья-то ссылка, то попытка другой сущности встать туда (путём обычного обхода массива смотрится, занят ли пиксель, если true в пиксельбуфере сущности, то ссылка на сущность попадёт в пиксельбуфер движка) приведёт к оповещению обоих столкнувшихся сущностей. Также это используется для хиттеста мыши - если в движковом пиксельбуфере ячейка по координатам курсора мыши имеет ссылку на сущность - то ей сообщается что мышь на ней. Работает на удивление быстро, хотя я ещё знаю куда можно ужаться в плане скорости. Буферайз всего и вся рулит. А в планах вообще было перейти на какую-то специальную библиотеку графическую (но процессорную, типа FastLib, а мб даже и видюшную), через код-адаптер, эта работа была начата. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Просчет столкновения | 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 |