PDA

Просмотр полной версии : Ландшафт произвольной формы (как в worms)



newart
17.04.2007, 00:32
Для одной игрушки пытаюсь подобрать сабжевый алгоритм.

И так, имеется ланшафт на подобие Worms (на много экранов), поэтому хранить его и маску проходимости нет возможности (много памяти и еще ряд причин).

Первый вариант, который пришел в голову и был реализован, это описать поверхность (ее периметр) в виде массива x,y координат. Минус этого способа в том, для проверки приходится перебирать весь массив. Для одной точки это еще примлемо, а для нескольких (расположеных в важных местах управляемого обьекта) будут тормоза.

А ведь нужно не только определить столкновение точки с контуром ланшафта, его еще нужно огибать. Если дискретность движения точки более 1 пикселя то цикл с проверки придется повторять несколько раз, что приведет к еще большим тормозам.

Кроме ланшафта в игре есть так называемые платформы, толщиной буквально несколько пикселов. Они также могут иметь произвольную форму. Так же некоторые платформы могут являться элеваторами, встав на которые точка (герой) начинает двигаться в определенную сторону.

Во время огибания поврехности нужно проверять ее угол по отношении к игроку. На картинке 1 показаны возможные ситуации.
Если угол слишком острый (на него не заехать) то отталкиваемся и едем обратно. Вот только как определить угол наклона отрезка ланшафта?

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

Третий вариант это совмещение первого и второго, но имхо это совсем изврат. :)

Хотелось бы услышать ваши варианты решения задачки.

NovaStorm
17.04.2007, 08:40
Ниндзя или гиш?
Реализация имхо - вектора и коллизии с деревьями 2-3х уровней.

newart
17.04.2007, 11:07
Ниндзя или гиш?
Реализация имхо - вектора и коллизии с деревьями 2-3х уровней.
Ниндзя не видел. А гиш, да можно сравнить с ним.
А что за деревья, можно поподробнее?

NovaStorm
17.04.2007, 14:24
Ниндзя представляет собой ландшафт+платформы+человеч ек с физикой, называлось просто n vX.X как-то.
А деревья, ну например quadtree(вроде=) ) - пространство бьётся на прямоугольники/квадраты, потом эти мелкие квады объединяются в более крупные и так несколько раз. Для проверки коллизии проверяем принадлежность наших координат одному из этих квадов, потом квадам этого квада и так до конца.
Это позволяет не просматривать на коллизии всё пространство, проводить определение всего за несколько сравнений , но возникают расходы на деревья-списки квадов.