Квадратные или шестигранные сетки лучше для поиска пути?

Есть ли существенная разница между использованием квадратной или гексагональной сетки для области поиска алгоритмом поиска пути? Другими словами, лучше квадрат или шестиугольник, и если да, то почему.

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

Скорее, это проблема игрового процесса, которую должны учитывать разработчики игр. Квадратные сетки более доступны для массового рынка (шестигранные доски имеют тенденцию выглядеть «вызывающе»), и в мире элементов управления вверх / вниз / влево / вправо гораздо удобнее перемещаться по квадратам, чем гексам с точки зрения пользовательского интерфейса. Квадратные сетки также имеют тенденцию немного ограничивать движение; предполагая ортогональное движение (а не диагональное), нужно пройти 4 шага, чтобы обойти препятствие площадью в один квадрат, по сравнению с 3 шагами в шестигранной сетке. С точки зрения программирования, гексы также немного легче реализовать, но речь идет не об алгоритмах поиска, а о том, что квадратная сетка равна двумерному массиву, но гекс-сетка на самом деле не отображается на стандартную структуру данных.

Недостатком квадратных сеток является то, что движение никогда не кажется правильным. Движение по диагонали должно брать sqrt (2) очков движения, но на практике это либо 1 движение (что дает ощущение, что ходьба по диагонали быстрая, и редко бывает причина ходить ортогонально), либо 2 движения (что делает движение по диагонали слишком медленным ). С гекс-сетками расстояние перемещения намного более интуитивно понятно, так как оно всегда одинаково от одного гекса до другого, независимо от того, какой путь вы выберете.

Я ни в коем случае не эксперт ИИ, но разница должна быть незначительной. Квадратные сетки немного быстрее (4 соединения на узел вместо 6), но это не является ограничивающим фактором в алгоритмическом времени выполнения. В зависимости от того, какой алгоритм вы планируете использовать, код может быть немного сложнее для шестнадцатеричной сетки, так как вычислить координаты немного сложнее, и сложнее использовать тот тип ярлыков квадри / октре, которые, я считаю, часто используется в поиске пути.

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

Есть одно практическое различие, которое я могу обдумать в отношении планирования пути. Перемещение от центра шестнадцатеричной ячейки до одного из ее соседей всегда на одном и том же расстоянии, тогда как, если вы разрешаете диагональное перемещение, это не верно для квадратов.

Это руководство по шестиугольникам удивительно. Часть о поиске пути содержит интерактивный пример и некоторую информацию о том, как адаптировать поиск по квадрату.

Если вы используете основанный на графике поиск путей, такой как алгоритм A * или Дейкстры или Флойд-Варшалл, поиск путей в гекс-сетках не отличается от поиска путей в квадратных сетках.

• Соседи. Пример кода, который я предоставляю в руководстве по нахождению пути, вызывает graph.neighbors для получения соседей местоположения. Для этого используйте функцию в разделе соседей. Отфильтруйте соседей, которые непроходимы.
• Эвристический. Пример кода для A * использует эвристическую функцию, которая дает расстояние между двумя местоположениями. Используйте формулу расстояния, масштабированную в соответствии с затратами на перемещение. Например, если ваша стоимость передвижения равна 5 за гекс, умножьте расстояние на 5.