Рабочая эвристическая функция для A* тут была безумно простой — manhattan distance. Она испортилась (начала переоценивать), когда добавились трамплины, и поэтому A* перестал находить гарантированно лучшее короткое решение, но это в принципе не беда. Чуть более сложная эвристика, которую _adept_ описал: при помощи тупого A*, который в процессе продвижения по карте не меняет карту, найти путь до цели, и его длину использовать как оценку (это тот самый A* поверх A*).