Обнаружение пути между препятствиями, которые находятся на вершине пешеходной плитки

Question

Возьмите приведенную ниже картинку в качестве примера. Рассмотрим следующее -

• Голубой квадрат - игрок
• Оранжевый квадрат - первый пункт назначения
• Розовый квадрат - второй пункт назначения
• Зеленые квадраты являются проходными плитками
• Черные квадраты - это стены / препятствия на вершине проходной плитки
• Каждая плитка имеет размер 4x4

Предполагаемое поведение здесь -

1. Прогулка до оранжевого квадрата приводит к прямой линии вниз
2. Прогулка до розового квадрата (от синего квадрата) обходит черные квадраты в непосредственной близости

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

При этом текущая реализация приводит к этому, как нет другого выбора, кроме как придерживаться сетки плиток 4х4, и, не помечая всю плитку как неприступную, она будет проходить сквозь объекты. Красные плитки не ходят.

, которая обеспечивает очень дрянную систему поиска пути, поскольку она пропускает идеально мелкие плитки (обозначены красным). Мой вопрос: как мне сделать так, чтобы стены не были обрезаны, но плитка, на которой они сидят, все еще проходима?

Answer 1

Идея решения:

Первое решение, очевидно, состоит в том, чтобы повысить точность A *, используя каждую ячейку 1x1.

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

Я не могу дать вам более подробные ответы, поскольку вы ничего не показали в своей реализации.

I надеюсь, что я был полезным