Pacman pathfinding heuristic

Question

Как я могу реализовать допустимую эвристическую функцию для игры pacman, чтобы найти самый короткий путь из данного места, включающий несколько целей (все остальные точки). В настоящее время я использую поиск A * с манхэттенскими расстояниями в качестве эвристики. Я беру сумму всех манхэттенских расстояний от узла до каждой оставшейся точки, которая еще не была съедена, и это мой H (n). Алгоритм занимает очень много времени, и я не совсем уверен в том, как сделать тай-брейк.

Answer 1

Ну, я предполагаю, что вы принимаете курс edX в искусственном интеллекте.

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

В зависимости от размера сетки и того, насколько она разрежена, вы можете запустить BFS из текущего местоположения вашего pacman, чтобы найти ближайший гранулы. Затем вы можете использовать это расстояние в качестве допустимой эвристики.