Коротко об алгоритмах поиска пути в играх
реклама
Поиск в ширину
Поиск в ширину - равномерное исследование во всех направлениях.
Используют этот алгоритм при решении задач теории графов, при поиске пути, процедурной генерации миров, при проектировке печатных плат и многие другие, но сегодня нам понадобится именно поиск кратчайшего пути в графе.
Создавая режим для еще не вышедшей игры S&Box (Преемник Garry`s mod) мы процедурно генерируем карту из комнат, каждая из комнат получает индекс в формате [x, y, z]. Где x,y могут иметь значения от -32 768 до 32 767, а z изменяется от 0 до 2, поскольку сейчас мы подразумеваем, что этажей будет всего 3.
Наш режим должен будет стать кооперативным побегом причем игроки не всегда находятся в 1 месте. Следовательно противники - ИИ. Они ищут ближайшего игрока и двигаются к нему. Чтобы найти действительно ближайшего игрока нельзя сравнивать их координаты. Поскольку комнаты могут быть расположены вот так:
реклама
Скажу сразу, картинка немного не точная. Расстояния между комнатами всегда одинаковое, а комнаты ровные.
Координатно красная точка в 0:0 ближе к фиолетовой внутри -1:0, но идти до нее намного дольше чем до фиолетовой точки 1:1. Именно тут, мы можем применить поиск в ширину.
В красной точке вызывается метод поиска ближайшего игрока который принимает индекс текущей комнаты - [0,0,z] Помечает эту комнату как посещенную. Далее он обращается к словарю в котором хранятся комнаты (Они же vertexes в теории графов) с этими индексами и узнает у комнаты какие есть проходы (Они же edges в теории графов), Далее проверяет какие индексы из них уже посещены и если не посещенных вертексов более 1, он добавляет эту комнату в очередь (Branch - разветвление) с указанием количества не посещенных сторон. Поскольку 1 поток может выполнять только 1 операцию за раз, мы не можем сразу двигаться из 0:1 в 1:1 и -1:1 поэтому двигаемся сначала в ту сторону, у которой угол между текущей позицией и следующей наименьший согласно тригонометрическому кругу. Когда мы находим игрока, мы отправляем список с индексами комнат, у нас он будет: ([0,0,z]; [0,1,z]; [1:1,z])
Скорость этого алгоритма = O(Vertexes + Edges)
Алгоритм Дейкстры
Алгоритм Дейкстры - он же алгоритм поиска с равномерной стоимостью. Используется для поиска оптимальных маршрутов
Бывает так, что проход между комнатами разный. Например, чтобы попасть в комнату, у которой нет двери стоимость прохода 1 очко, а где есть дверь, 1.2 очка, поскольку нужно потратить время на ее открытие. Соответственно мы можем выбирать путь из наиболее дешевого пути. Мы этот алгоритм использовать не стали, поскольку у нас проходы между комнатами всегда равны, а скорость движения внутри комнаты не зависит от чего-либо. Более того, этот алгоритм подразумевает нахождение наиболее "дешевых" путей для всех узлов. Реализация алгоритма Дейкстры похожа на поиск в ширину, но появляется список стоимости перехода между клетками и его учет при выборе пути.
Скорость этого алгоритма = O(N2) - при линейном поиске
Скорость этого алгоритма = O(M Log N) - при бинарном поиске
Визуализация работы алгоритма:
реклама
UPD: Тут нет A* поскольку информация о нем довольно объемная, но если вам понравилась статья, то в следующий раз я могу рассказать про алгоритм A*
реклама
Лента материалов
Соблюдение Правил конференции строго обязательно!
Флуд, флейм и оффтоп преследуются по всей строгости закона!
Комментарии, содержащие оскорбления, нецензурные выражения (в т.ч. замаскированный мат), экстремистские высказывания, рекламу и спам, удаляются независимо от содержимого, а к их авторам могут применяться меры вплоть до запрета написания комментариев и, в случае написания комментария через социальные сети, жалобы в администрацию данной сети.
Комментарии Правила