Организация объектов для коллизий

[Asker13]

Привет всем. Давайте я вкратце опишу ситуацию. 2D игра, вид сбоку. Есть динамический массив объектов прямоугольной формы GObj: array of TGameObject;. Вся карта состоит из таких объектов. Есть функция для проверки столкновения двух прямоугольников.

Я бы хотел рассмотреть ситуацию, когда на карте находятся 1000+ объектов. Получается, что каждый такт (33 мс) таймера надо пройтись в цикле по всем 1000 объектам и проверить, что как минимум один прямоугольник с ними столкнулся, после этого соответственно выполнять действия какие-то. А если объектов, с которыми можно взаимодействовать, около 10000?

Похожая ситуация с рисованием этих объектов. Каждый такт нужно проходится по всем 1000 объектам, проверять, что объект находится в поле зрения игровой камеры, и в дальнейшем уже рисовать или не рисовать. И опять, если объектов будет 10000?

Можно ли и вообще нужно ли реорганизовать всё это, чтобы как-то оптимизировать работу?
P.S. Может я просто недооцениваю всю мощность современных ПК?

[RomiKon]

Во первых если делаете для себя и для современного компьютера то так пойдёт=)
А если уж желаете оптимизировать то я делал так. Бил всю карту на большие ячейки. Одна ячейка в среднем была размером с экран. Далее всю геометрию расфасовывал по этим ячейкам(один объект может находится сразу в нескольких ячейках). При проверке колизий сначала проверяем в каких ячейках находится объект а потом колизим его со всеми объектами в этих ячейках. Эта пожалуй самая простая оптимизация.

[phomm]

Сам давненько хотел накропать тему по организации игрового пространства и его интеракции, ну и тут хорошо ) хотел рассказать свои идеи по данному вопросу и послушать других людей

Да, поячеечная организация игрового пространства - самая простая и ненапряжная, дает хорошие результаты. В игре Герои3, например, так, карта приключений и поле боя разбито на ячейки.
Интеракция объектов с юзером (обычно воздействие от мышки) и друг с другом по сути заключается в проверке только целевой клетки, когда один объект пытается залезть на другую клетку, проверяем на занятость целевой клетки объектом (также и для мышки, коли занята клетка- можно взаимодействовать, а нет - так нет), само собой что это даже не при каждом такте будет !
получение координат клеток достаточно тривиально, и обычно игровые данные занесены в массивы(особенно 2д игры), что довольно просто совместить, надо просто хранить текущую крайнюю колонку и строку (аналог leftcol и toprow в гридах) и размер ячейки, при этом всегда можем узнать какая область "сетки" лежит в экране.

Однако, есть минус, может так случиться что изображения вылезает за пределы размеров логических клеток (в тех же героях есть высокие картинки объектов, а активна только 1 нижняя клетка), и естественность восприятия нарушается.
Ну и попиксельной коллизии никогда не добиться...

я как решаю данную задачу :

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

реализация : добавляем некий объект (его класс - потомок от элемента коллекции игрообъектов), он записывается в коллекцию, и коллекция впоследсвии уведомляет "пиксар" о местонахождении объекта на экране, пиксар пишет в себя ссылки на этот объект(на каждый пиксель ! ссылка).
при любых модификация в расположении элементов коллекция уведомляет пиксар.

ну и как это работает : клиентский код сообщает "пиксару" что мыша в конкретных координатах. пиксар смотрит в себя и выуживает ссылку на игрообъект (простой поиск в массиве, а это быстро) и передает тому нужные данные (нажатие там кнопок, и т.п.) "пиксар" также сам отслеживает, что мыша ушла с объекта и тоже его уведомляет.


на данный момент система написана в базовом виде и даже ещё не протестирована на 1000+ объектах (но на своём тестовом полигоне работает на отлично - исключительно попиксельно, и что более важно, практически непосредственная работа с пикселями , как напрямую адресуемыми объектами, специально нагородил там иерархию классов для последующего разрастания модели в область коллизий). Закончу тут пару проектов и с новой силой возьмусь за данную работу )


хотел бы услышать других бывалых игростроителей ))

[RomiKon]

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

[phomm]

у меня не совсем проверка пересечения по пикселям ) перечитайте повнимательнее )
у меня происходит лишь перераспределение ссылок на объекты по "массиву пикселей" , при "наложении" имеем коллизию
грубо говоря, у меня в памяти своеобразное представление экрана, где каждому пикселю соответствует конкретный объект, и любое движение объектов по данному "экрану в памяти" будет сопровождаться с учетом уже расположенных там объектов, и когда один объект хочет "занять" пиксель другого, то напрямую будет извещать того о коллизии