?

Log in

No account? Create an account
16 май, 2008 @ 21:51 границы в 2d
Товарищи, дайте плз наводочку на статью или простой исходник. после которого/которой я смог бы понять, как в 2d играх реализовывается механизм препятствий? То есть как определить, что вот в этой координате мой спрайт может двигаться, а вот здесь он упрётся в стенку. Ещё интересно, как определить, что в игрока попала пуля, что встретились два персонажа(которые объекты одного класса и друг про друга ничего не знают). Благодарю за помощь!
vitaljkapblog:
[User Picture Icon]
From:mic
Date:Май, 16, 2008 18:53 (UTC)
(Ссылка)
Жжоте, конечно )))
ну да ладно
http://noregret.org/tutor/n/collision/
(Ответить) (Ветвь дискуссии)
From:vitaljkapblog
Date:Май, 17, 2008 03:47 (UTC)
(Ссылка)
Не жгу, прост оникогда не сталкивался и даже терминов не знал ;)
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:unxp
Date:Май, 16, 2008 22:51 (UTC)
(Ссылка)
Про нахождение пути: http://www.policyalmanac.org/games/aStarTutorial.htm

Про коллизии - хороший урл посоветовать не могу, но обычно у игровых объектов должны быть outline-ы (контуры). Из точек аутлайна создается AABB (axis-aligned bounding box). Игровой мир делится на сетку (collision grid), в кажддой ячейке которой записывается информация о всех объектах с ней пересекающихся. Сам collision grid обычно организован в виде какого-нибудь дерева (quadtree, к примеру).
Для того чтобы найти пересечение, сначала находим ячейки на гриде которые содержат в себе наш объект и проверяем пересечение его бокс с боксами остальных объектов внутри ячейки. Если пересечение найдено - можно идти дальше и проверять пересекаются ли контуры. Для ускорения алгоритма (и если точное место пересечения не важно), сам контур объекта можно апроксимировать с помощью нескольких простых фигур (bounding shapes). Проще всего - bounding circle/sphere.
(Ответить) (Ветвь дискуссии)
From:vitaljkapblog
Date:Май, 17, 2008 03:48 (UTC)
(Ссылка)
Огромное спасибо!
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:iridix
Date:Май, 17, 2008 17:13 (UTC)
(Ссылка)
circle-то чем проще?
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:unxp
Date:Май, 17, 2008 21:13 (UTC)
(Ссылка)
Пересечение находить проще и быстрее всего. Необходимо всего лишь найти квадрат расстояния до центра и сравнить его с квадратом радиуса сферы.
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:iridix
Date:Май, 19, 2008 04:36 (UTC)
(Ссылка)
Это хорошо известно. Я к тому, что сравнение прямоугольников не содержит ничего кроме сложений и сравнений. Причем минимально при проверке одной координаты это будет пара сравнений и сложений. А вот сравнение окружностей потребует всегда 4 умножения. Что не есть гуд.
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:unxp
Date:Май, 17, 2008 23:49 (UTC)
(Ссылка)
Особенно жизнь упрощается когда надо считать пересечение объекта с линией.
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:iridix
Date:Май, 17, 2008 18:07 (UTC)
(Ссылка)
Вопрос не просто хороший, а очень хороший. И тема эта вовсе не раскрыта в google'ении "2D collision detection", как думают многие. Просто она гораздо глубже. Некоторое время назад я, для интереса, специально искал в google - ничерта полезного нет. Вернее может быть где-то на 150й ссылке и есть (должно быть), но хорошо погребено под тоннами мусора. Чаще всего банально раскрыта тема character-character, но не character-background и, например, не character-tiles collision.

Collision Detection делится в на два основных случая.
На character-character и на character-background detection.
В случае character-character все несложно. Чаще всего проверяется пересечение прямоугольников:

bool collide(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2) {
return x2 < x1 + w1 && x1 < x2 + w2 && y2 < y1 + h1 && y1 < y2 + h2;
}

Прямоугольники принято называть "Collision rectangles". Замечу что с прямоугольниками не все так просто как это может показаться на первый взгляд. Например, для некоторых персонажей задают их меньше, чтобы их было сложнее поразить. Или задается несколько прямоугольников, в особенности когда персонажи гигантские и имеют сложную форму (в некоторых играх есть колоссальные Final Boss'ы - например в Solaris это неимоверного размера "Трансформеры"). Плюс, иногда приходится задавать collision rectangles для каждого кадра анимации. Если спрайты вращаются, то все становится несколько интереснее.
Часто для определения столкновений можно сильно "загрублять" модель. К примеру спрайт вращается, а его collision rectangle - нет.
Проверку на основе столкновения окружностей можно применять на PC, но на 8,16-битах и handheld'ах этим ввиду отсутствия команд умножения не занимались.

В случае character-background дела обстоят существенно сложнее. Вариантов больше и все зависит от характера background'а и самой игры. Скроллируется ли back'? Один, или несколько? Используется тайловая техника? Итд..
Причем, ладно еще просто определить что character пересекся с тайлами, но самое интересное начинается, когда встречаются горки, лесенки (которые должны поднимать/задерживать/ускорять персонажа) и прочее, включая скролллинг фона в различных направлениях или перемещение отдельных частей уровня между собой. Некоторые решения мне чисто алгоритмически известны, но повторяю - не все тут так просто.

В некоторых старых игрушках я встречал эмпирические "трюки". Например я сталкивался с тем что толи Tanium, толи Chronos, толи Xecutor поступали так: очищал экран, рисовал звезды и ставил спрайт кораблика. Затем рисовал фон и тварей. И под конец игра вновь считывала спрайт кораблика с экрана и сверяла его - испорчен или нет? Если спрайт "испорчен", то это явно потому что что-то поверх него отрисовалось, он с чем-то столкнулся. Следовательно, кораблик должен был взорваться.

И последнее. В некоторых Framework'ах уже заложена необходимая функциональность.
Возьми Popcap Framework - там, явно должно быть что-то уже готовое для проверки столкновений спрайтов. Глянь, если интересуют тайлы редактор Tile Studio - обрати в примерах игровых карт внимание на некоторые атрибуты тайлов, которые используются для проверки столкновений.
(Ответить) (Ветвь дискуссии)
From:vitaljkapblog
Date:Май, 18, 2008 04:44 (UTC)
(Ссылка)
Ёлки, как всё оказывается усложнено.... Я до того как начал разбиратся считал, что в таких играх карту загружают в отдельный массив, каждый элемент которого - пиксель вроде свободный/несвободный, а объекты - просто добавляются в связанный список и при каждом движении, всё это между собой проверяется на столкновения, а тут оказывается...
Благодарю за развёрнутый комментарий.
(Ответить) (Уровень выше) (Ветвь дискуссии)
[User Picture Icon]
From:golergka
Date:Май, 18, 2008 09:33 (UTC)
(Ссылка)
Один из примеров оптимизированного алгоритма:
Разбиваешь игровой мир на квадраты так, что объекты из НЕ соседних квадратов в принципе пересекаться не могут. При проверке коллизий строишь пары объектов, которые находятся в одном или соседнем квадратах. Затем проверяешь расстояние между объектами, сравнивая с суммой радиусов, где радиус - расстояние от центар объекта до самой удалённой его точки. И только если расстояние меньше суммы радиусов, проверяешь коллизию по контуру :)

То есть такой алгоритм для самописного 2d-движка конечно нафиг нужен, потому что мощность подавляющего большинства современных компьютеров позволяет на счёт оптимизации в таких случаях не париться (не Crysis же пишешь?) - но на всякий случай.
(Ответить) (Ветвь дискуссии)