Что бы я предложил для ИИ pacman, вы используете алгоритм заливки, чтобы вычислить кратчайший путь и общее расстояние до КАЖДОГО тайла в сетке.Это гораздо более простой алгоритм, чем A *, и на самом деле в худшем случае, чем A *, в любом случае это означает, что если вы можете позволить A * каждый кадр, вы можете позволить заполнение флудом.
Чтобы объяснить производительностьсравните немного подробнее, представьте себе наихудший случай в A *: из-за тупиков вам придется исследовать каждую плитку в сетке, прежде чем вы достигнете конечного пункта назначения.Этот теоретический случай возможен, если у вас много тупиков на плате, но маловероятен в большинстве реальных игровых плат.Наихудший случай для заполнения наводнения такой же, как и в лучшем случае, вы посещаете каждую плитку на карте ровно один раз.Разница заключается в том, что итеративный шаг проще для заполнения флудом, чем для итерации A * (без эвристики, без кучи узлов и т. Д.), Поэтому посещение каждого узла быстрее при заполнении флудом, чем с A *.
Реализация довольно проста.Если вы представляете сетку в виде графика, где каждая плитка является узлом, а каждое ребро без стены между соседними плитками является ребром в графике, вы просто выполняете первый обход графика в ширину, отслеживая, какой узел вы пришлиот и сколько узлов вы исследовали, чтобы туда добраться.Вы отмечаете узел как посещенный, когда вы посещаете его, и никогда не посещаете узел дважды.
Вот некоторый псевдокод, чтобы начать работу:
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if not child.has_been_visited
child.has_been_visited = true
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
Чтобы выяснить, как заставить pacmanдвигаясь куда-то, вы начинаете с нужного вам узла и следите за указателями .previous до самого начала, а затем переворачиваете список.
Приятно то, что вы можете делать постоянные запросы времени остоимость достижения любой плитки на карте.Например, вы можете перебрать каждую из гранул силы и рассчитать, какая из них ближе всего, и как туда добраться.
Вы можете даже использовать это для призраков, чтобы узнать самый быстрый способ вернуться к pacman, когдаони находятся в режиме «атаки»!
Вы также можете рассмотреть заливку от каждого из призраков, сохраняя в каждой клетке, как далеко находится ближайший призрак.Вы можете ограничить максимальное расстояние, которое вы исследуете, не добавляя узлы в открытый список, если они превышают некоторую максимальную стоимость (8 квадратов?).Затем, если вы ДЕЙСТВИТЕЛЬНО сделали A * позже, вы могли бы сместить затраты для каждой плитки в зависимости от того, насколько близко призраки.Но это выходит за рамки того, о чем вы спрашивали в этом вопросе.
Это должно быть достаточно быстро, чтобы вы могли делать это в каждом кадре или многопоточно, если хотите.Я бы порекомендовал просто сделать это в своей основной ветке симуляции игры (заметьте, не в потоке пользовательского интерфейса) для простоты, поскольку она действительно должна быть довольно быстрой, когда все сказано и сделано.
Один совет по производительности: вместоПроходя и снимая флаг has_been_visited в каждом кадре, вы можете просто иметь счетчик поиска, который вы увеличиваете каждый кадр.Примерно так:
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if child.last_search_visit != FRAME_NUMBER
child.last_search_visit = FRAME_NUMBER
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
И тогда вы просто увеличиваете FRAME_NUMBER каждый кадр.
Удачи!