Блог

Было интересно, есть ли у кого-нибудь знания о реализации поиска пути, но с использованием запаха. Чем сильнее запах в окружающих узлах, тем ближе движется «враг».

Спасибо

Да, я делал свой выпускной проект в университете по этому предмету.

Одно из применений этой идеи заключается в поиске shortest path . Идея в том, что «запах», как вы выразились, со временем исчезнет. Но самый короткий путь между двумя точками будет иметь самый сильный запах.

Взгляните на эту статью.

Что именно вы хотели знать??

Не совсем понятно, в чем конкретно заключается вопрос, но это просто кажется другим способом описания проблемы оптимизации колонии муравьев:

В компьютерных науках и исследованиях операций алгоритм оптимизации муравьиной колонии (ACO) представляет собой вероятностный метод для решения вычислительных задач, который может быть сведен к нахождению хороших путей через графики.

Что ж, подумайте об этом минутку.

Моя идея заключалась бы в том, чтобы разделить игровое поле на секции размером 32×32 (или любого другого размера, который имеет ваш персонаж). Затем выполняйте несколько проверок каждые x секунд (так что, если они останутся неподвижными, плитки вокруг них будут иметь больше «запаха»), чтобы выяснить, насколько силен запах на любой данной плитке. Вот несколько примеров: 1) Если вы пересекаете плитку, добавьте 3; 2) если вы пересекли соседнюю плитку, добавьте 1.

Затем добавьте такие вещи, как ухудшение со временем, уменьшайте каждую плитку на 1 каждые x секунд, пока она не достигнет нуля.

Последнее, о чем вам нужно беспокоиться, — это использование искусственного интеллекта для отслеживания этого пути. Я бы рекомендовал просто поместить AI куда-нибудь и сказать ему, чтобы он нашел узел с запахом, а затем перейти к соседнему узлу с запахом большего / равного значения. Также беспокойтесь о том, чтобы вычеркивать пройденные пути. Если игрок идет вверх по пути, а затем возвращается по нему в другом направлении, убедитесь, что ИИ всегда просто выбирает закольцованный обратный путь.
Последнее, на что следует обратить внимание при использовании искусственного интеллекта, — это добавить немного ошибок. Заставляйте ИИ время от времени выбирать неверный путь. Или потерять след немного проще.

Это ключевые моменты, я уверен, что вы можете придумать больше, проведя еще несколько мозговых штурмов.

При каждом обновлении игры (или в какой-либо другой, менее частый период времени) увеличивайте значение запаха узлов рядом с тем местом, где находятся целевые объекты (красные капли).

Уменьшите все значения запаха узла на некоторую величину уменьшения до нуля.

В функции think / move желтого двоичного объекта найдите доступные узлы для перемещения. Двигайтесь к узлу с наибольшим значением запаха.

В зависимости от количества узлов «уменьшить все значения запаха узла» может потребоваться оптимизация, например, возможно, ведение списка ненулевых узлов, подлежащих уменьшению.

Я вижу большое противоречие между моделью запаха и поиском пути. Для охотника на природе найти путь по запаху означает найти именно тот путь, которым пользуется преследуемый объект. А в играх поиск пути означает нахождение самого быстрого пути между двумя точками. Это не одно и то же. 1. При моделировании запаха вы будете считать концентрацию запаха в точке как СУММУ окружающих концентраций, умноженных на различные коэффициенты. А поиск самого быстрого пути от точки означает использование МИНИМАЛЬНОГО количества времени, подсчитанного для окружающих точек, умноженного на различные параметры. 2. При подсчете запаха следует использовать рекурсивную модель — запах распространяется во всех направлениях, включая обратное. В случае поиска пути, если вы нашли кратчайшие пути для точек, окружающих цель, они не изменятся. 3 Уровень запаха может повышаться и понижаться. В поиске пути при поиске минимального значения результат никогда не может возрасти.

Итак, модель запаха действительно намного сложнее, чем ваша цель. Конечно, то, что я сказал, верно только для стандартной ситуации, и у вас может получиться что-то совершенно особенное…