Проблема с поиском пути на основе сетки с ограниченными поворотами

Question

Я нахожусь в процессе создания двумерной игры на основе сетки и остановился из-за сложного кода. Мне нужно перемещаться от одной ячейки в сетке к другой, если это возможно, но не более 2 раз.

Красный шар - это цель, а зеленые пути - те, которые являются действительными, «повороты» выделены синим кружком.

Как это можно сделать без грубой форсировки проблемы и проверки всех возможных путей? Я экспериментировал с несколькими идеями наряду с реализацией *, но пока не повезло. Любые идеи, использующие API единства или что-либо еще высоко ценится.

Answer 1

Эту проблему можно решить с помощью обычного A *, создав специально разработанный ориентированный взвешенный граф из исходной сетки.

Хитрость в том, чтобы создать график с несколькими «слоями». Слой 0 представляет 0 оборотов, которые были сделаны до сих пор, слой 1 представляет 1 обороты, а слой 2 - 2 оборота. Узел соединяется со своими соседями на том же уровне, если они могут быть достигнуты без поворота, и со своими соседями на следующем уровне, если им требуется поворот.

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

1. Создать 6 копий графика, Layer_0_Horizontal, Layer_0_Vertical, Layer_1_Horizontal, Layer_1_Vertical, Layer_2_Horizontal, Layer_2_Vertical.
2. Для каждого узла в слое Horizontal удалите его ребра к его вертикальным соседям и замените их ребрами на узлы в следующем слое вниз, например. Layer_1_Vertical ниже Layer_0_Horizontal. Края в Layer_2 не будут заменены. Сделайте то же самое для Vertical слоев / горизонтальных краев.
3. Создайте поддельный «начальный» узел и подключите его к двум Layer_0 узлам, которые представляют тот же квадрат сетки с ребрами с нулевым весом. Если ваша реализация A * поддерживает только один целевой узел, проделайте то же самое с целью.

Если вы хотите предпочесть более длинные пути с меньшим количеством поворотов, чем более короткие пути с большим количеством поворотов (возможно ли это только с двумя поворотами ??) , придавайте ребрам между слоями чрезвычайно большой вес.