PacMan: какие виды эвристики в основном используются?

Помимо A*, BFS, DFS и т.п., какие другие хорошие алгоритмы/эвристики поиска пути широко используются в Пакман? Я не думаю, что те, которые я упомянул, будут работать, если pacman сможет найти более одного фрукта.

Мне нужны хорошие алгоритмы поиска пути, которые PacMan может использовать для прохождения лабиринта с наименьшим количеством шагов. Я пытался найти руководство, но пока безуспешно. A* с манхэттенским расстоянием упоминается везде, но он будет работать только с лабиринтами с одним (или двумя? или, может быть, несколькими?) фруктами.

Кстати, для простоты предположим, что призраков поблизости нет.

Несколько примеров из исходных задач PacMan: Первый, Второйи Третий