newart
17.04.2007, 00:32
Для одной игрушки пытаюсь подобрать сабжевый алгоритм.
И так, имеется ланшафт на подобие Worms (на много экранов), поэтому хранить его и маску проходимости нет возможности (много памяти и еще ряд причин).
Первый вариант, который пришел в голову и был реализован, это описать поверхность (ее периметр) в виде массива x,y координат. Минус этого способа в том, для проверки приходится перебирать весь массив. Для одной точки это еще примлемо, а для нескольких (расположеных в важных местах управляемого обьекта) будут тормоза.
А ведь нужно не только определить столкновение точки с контуром ланшафта, его еще нужно огибать. Если дискретность движения точки более 1 пикселя то цикл с проверки придется повторять несколько раз, что приведет к еще большим тормозам.
Кроме ланшафта в игре есть так называемые платформы, толщиной буквально несколько пикселов. Они также могут иметь произвольную форму. Так же некоторые платформы могут являться элеваторами, встав на которые точка (герой) начинает двигаться в определенную сторону.
Во время огибания поврехности нужно проверять ее угол по отношении к игроку. На картинке 1 показаны возможные ситуации.
Если угол слишком острый (на него не заехать) то отталкиваемся и едем обратно. Вот только как определить угол наклона отрезка ланшафта?
Кроме буфера с координатами вижу еще 1 вариант. Разбить поверхность на неболшие отрезки и в буфере хранить не весь ландшафт, а только точки отрезков. При этом коллизии проверяются в 2 этапа. Каждый отрезок как бы вписан в прямоуголник согласно коордианатм его точек, если точка (герой) входит в этот прямоуголник тогда уже проверем точку на принадлежность отрезку. Это вариант в целом быстрее но на в некоторые моменты (если квадраты пересекаются и проиходит проверка на принадлежность отрезку) это вариант может оказаться медленее первого.
Третий вариант это совмещение первого и второго, но имхо это совсем изврат. :)
Хотелось бы услышать ваши варианты решения задачки.
И так, имеется ланшафт на подобие Worms (на много экранов), поэтому хранить его и маску проходимости нет возможности (много памяти и еще ряд причин).
Первый вариант, который пришел в голову и был реализован, это описать поверхность (ее периметр) в виде массива x,y координат. Минус этого способа в том, для проверки приходится перебирать весь массив. Для одной точки это еще примлемо, а для нескольких (расположеных в важных местах управляемого обьекта) будут тормоза.
А ведь нужно не только определить столкновение точки с контуром ланшафта, его еще нужно огибать. Если дискретность движения точки более 1 пикселя то цикл с проверки придется повторять несколько раз, что приведет к еще большим тормозам.
Кроме ланшафта в игре есть так называемые платформы, толщиной буквально несколько пикселов. Они также могут иметь произвольную форму. Так же некоторые платформы могут являться элеваторами, встав на которые точка (герой) начинает двигаться в определенную сторону.
Во время огибания поврехности нужно проверять ее угол по отношении к игроку. На картинке 1 показаны возможные ситуации.
Если угол слишком острый (на него не заехать) то отталкиваемся и едем обратно. Вот только как определить угол наклона отрезка ланшафта?
Кроме буфера с координатами вижу еще 1 вариант. Разбить поверхность на неболшие отрезки и в буфере хранить не весь ландшафт, а только точки отрезков. При этом коллизии проверяются в 2 этапа. Каждый отрезок как бы вписан в прямоуголник согласно коордианатм его точек, если точка (герой) входит в этот прямоуголник тогда уже проверем точку на принадлежность отрезку. Это вариант в целом быстрее но на в некоторые моменты (если квадраты пересекаются и проиходит проверка на принадлежность отрезку) это вариант может оказаться медленее первого.
Третий вариант это совмещение первого и второго, но имхо это совсем изврат. :)
Хотелось бы услышать ваши варианты решения задачки.