Как я должен перепланировать A *?

10

У меня есть босс-враг, который ищет игрока, используя алгоритм A *. Это довольно сложная среда, и я делаю это во Flash, поэтому поиск может быть немного медленным, когда он ищет на больших расстояниях. Если бы плеер был неподвижен, я мог бы искать только один раз, но в данный момент я ищу каждый кадр. Это занимает достаточно много времени, чтобы моя частота кадров страдала.

Каково обычное решение этого? Есть ли способ «перепланировать» A *, не повторяя весь поиск? Должен ли я просто искать чуть реже (каждые полсекунды или секунды) и признавать, что на пути будет небольшая неточность?

Грегори Эйвери-Вейр
источник

Ответы:

13

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

PhilCK
источник
+1. Это также то, что Мэт Бакленд описывает в своей книге AI. Он называет это «Планирование пути с разделением по времени» ( books.google.ch/… ). Хорошая вещь.
bummzack
8

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

      Distance > 100, run A* every 2 seconds
100 > Distance >  50, run A* every 1 second
50  > Distance >  25, run A* every 10 frames
25  > Distance <  25, run A* every frame

Это предполагает, что есть расстояние, на котором при выполнении A * каждый кадр имеет производительность, которая все еще приемлема. Короче, я бы пошел на ваш второй вариант. Особенно, если то, что у вас есть, работает, я бы не стал реализовывать что-то еще, если бы я мог просто уменьшить то, что работает хорошо. Суть в том, что вам придется попробовать его, чтобы увидеть, работает ли он для вашей игры.

Nate
источник
8

Не совсем отвечая на ваш точный вопрос, но ... если вы хотите «обмануть», вы можете заставить игрока оставить «сухари» и заставить босса следовать за ними. Если путь крошек пересекает сам себя, следуйте по самому последнему пути (это заставляет босса избегать петель и других путей, которые могут быть слишком длинными, не говоря уже о том, что они не следуют точному пути игрока)

Это будет хорошо работать, если босс - это какое-то животное с хорошим обонянием. Это будет очень похоже на следование запаху игрока :)

ggambett
источник
5

Ваш случай - это почти то, что было изобретено HPA * . Однако, если это кажется излишним, я бы подумал, что поиск пути каждые полсекунды или около того должен работать очень хорошо.

хаос
источник
4

Если это статическая среда, то вы можете заранее рассчитать кратчайший путь для всех пар.

Питер Тейлор
источник
2
Если это небольшая статическая среда.
Зависит от платформы и доступной памяти.
Ноябрь
@ Джо, @Nate, правда.
Питер Тейлор
2

Я создал игру для соревнования на 48 игр, где персонаж A * следует за игроком на уровне. Поскольку моя реализация A * была медленной (она не могла запускать каждый кадр), я установил интервал с задержкой в ​​три секунды. Это привело к непреднамеренному результату, позволив игроку на несколько минут «обмануть» ИИ. Это на самом деле сделало игру веселее.

Позже я улучшил производительность реализации A * и попытался запустить ее на каждом кадре. Игра перестала быть веселой, потому что враг всегда будет отлично искать игрока.

Это было неожиданным и хорошим опытом обучения.

GloryFish
источник
1
Неплохо подмечено. Я помню, как читал о поиске пути в pac-man, где они сознательно использовали несовершенный алгоритм, позволяющий игроку перехитрить призраков. У каждого призрака было немного различное несовершенство, дающее им больше характера. Забрать здесь то, что в играх весело> все остальное.
Ник Ван Брант
0

Если вы абсолютно не хотите (или не нуждаетесь) использовать A *, вы также можете взглянуть на поведение рулевого управления . Поскольку нет полного планирования пути для каждого задействованного кадра, он должен быть намного легче при обработке.


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