Блог

Я столкнулся со следующей проблемой. Я программировал игру, и она будет использовать алгоритм поиска пути, чтобы определить, как создавать туннели для лабиринта из комнат и туннелей. Но мне нужен алгоритм, который будет находить пути через полосы препятствий, в которых направление подхода имеет значение. Т.Е. Путь, проходящий горизонтально через препятствие, может быть в порядке, а путь, идущий вертикально, — нет.

Пример на диаграмме:

 . = free space
X = path
| = vertical-blocking obstacle
a = start point
b = end point
  

Если у нас есть

 .....
a.|.b
.....
  

тогда мы должны получить путь, подобный

 .....
XXXXX
.....
  

Но если у нас есть

 ..a..
..|..
..b..
  

тогда мы должны получить путь, подобный

 ..XX.
..|X.
..XX.
  

Какой алгоритм это сделает? Можно ли изменить «A *» для этого?

A * решит проблему без изменений.

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

Затем задача заключается в составлении графика из сетки. Неориентированный график сетки, который вы указали выше, будет выглядеть примерно так: