Как обращаться с объектами разных размеров в ситуации поиска пути (A *, A-star)

Question

Я работаю над игрой, которая использует A-звезду (A *) для поиска пути, но я дошел до того, что у меня есть некоторые объекты, которые больше, чем один квадрат сетки.

Я работаю на сетке 16 * 16 пикселей. сегменты стен 16 * 16 и поэтому делают один квадрат непроходимым. Некоторые из моих злодеев - 32 * 32, поэтому им нужно проверить, что зазор имеет ширину не менее 2 квадратов сетки, чтобы можно было его преодолеть.

Я не могу просто сделать сетку 32 * 32, так как дизайн требует тонких стен (в 16 пикселей), и есть пара маленьких злодеев, которые занимают только один квадрат 16 * 16.

Как мне реализовать эту среду с множественным разрешением? Является ли A-star правильным инструментом для использования?

Answer 1

http://aigamedev.com/open/article/clearance-based-pathfinding/

Answer 2

Для относительно простого решения я бы придерживался того же алгоритма A *, что и для объектов размером 16x16, но с немного другим способом оценки, можно ли пройти квадрат или нет.

• Объект размером 16x16 может ходить по квадрату, если по нему можно пройти.
• Объект размером 32x32 может ходить по квадрату, если этот квадрат и все его соседи доступны для прохождения.