Разрешить алгоритм A-star, чтобы обойти x количество препятствий

Question

Прямо сейчас у меня есть этот лабиринт:

Узлы, отмеченные S и E , представляют начало и конец этого лабиринта.

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

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

Мой алгоритм A * в настоящее время перемещается по нему следующим образом:

.

Но я хочу, чтобы он двигался так, если я позволю обойти 1 препятствие:

и вот так, если я позволю обойти 2 препятствия:

Как я могу изменить алгоритм A * для достижения этой цели? Может быть, есть альтернативный алгоритм, который мог бы помочь мне с этой проблемой?

Answer 1

Вы можете дублировать узлы на вашем графике и генерировать экземпляры для каждого количества обходов. Т.е. вы создадите несколько слоев графика и начнете со слоя 0 (вы уже обошли 0 препятствий). Всякий раз, когда вы переходите к узлу препятствия, вы переключаетесь на следующий уровень (то есть имеются ребра для соседних узлов препятствий следующего слоя и ребра для соседних узлов без препятствий того же слоя). Создайте столько слоев, сколько вы хотите, чтобы препятствия были обойдены. Если вы достигли любого экземпляра целевой ячейки (на любом слое), все готово.