Принцип работы непроходимости через объекты

Всем доброго дня, решил попробовать сделать 2D игру с открытым миром. ВАЖНО: он рандомно генерируется. Вроде всё норм, но никак не могу сделать нормальную непроходимость через деревья. Я делал так, перед прорисовкой нового кадра при движении проверяются следующие пиксели, которые мой персонаж займёт, не принадлежат ли они никакому объекту в игре. Но тут два существенных минуса 1) объекты я проверяю с помощью 4 углов каждого объекта, т.е. если объект сложный с разными проходами, то этот способ категорически не подходит, т.к. эти проходы для меня будут также непроходимы, т.к объект формально будет не сложным, а просто четырёхугольным 2) ужасно с точки зрения оптимизации, ведь это просто ужасно, каждый следующий ход проверять на то, что впереди нету никакого объекта, а если объектов 1000, то это 1000 проверок за одно перемещение по карте! В общем мне нужна хорошая идея как всё это дело можно было бы сделать избежав этих 2-х минусов.

0

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

0

Fulcrum_013, спасибо, буду пробовать с тайлами)

0

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

0