As grades quadradas ou hexagonais são melhores para encontrar caminhos?

Existe alguma diferença significativa entre o uso de uma grade quadrada ou hexagonal para a área pesquisada por um algoritmo de localização de caminho. Em outras palavras, é quadrado ou hexagonal melhor e, em caso afirmativo, por quê.

A principal consideração para decidir se as grades quadradas e hexadecimais devem ser fáceis de implementar na IA - os algoritmos de busca em primeiro e segundo em profundidade são praticamente os mesmos, independentemente do tipo de gráfico que você possui.

Pelo contrário, esta é uma questão de jogabilidade que deve ser considerada pelos designers do jogo. As grades quadradas são mais acessíveis ao mercado de massa (placas hexadecimais tendem a parecer "nerds") e, em um mundo de controles para cima / baixo / esquerda / direita, é muito mais intuitivo navegar por quadrados do que hexágonos do ponto de vista da interface do usuário. As grades quadradas também tendem a restringir um pouco mais o movimento; assumindo movimento ortogonal (e não diagonal), são necessários 4 movimentos para contornar um obstáculo de um quadrado, em comparação com 3 movimentos em uma grade hexagonal. Do ponto de vista da programação, os hexágonos também são um pouco mais fáceis de implementar, mas não se trata de algoritmos de pesquisa, pois uma grade quadrada é igual a uma matriz bidimensional, mas uma grade hexadecimal não é realmente mapeada para uma estrutura de dados padrão.

O lado negativo das grades quadradas é que o movimento nunca parece certo. Mover na diagonal deve levar pontos de movimento sqrt (2), mas, na prática, é 1 movimento (o que faz parecer que andar nas diagonais é rápido e raramente há uma razão para caminhar ortogonalmente) ou 2 movimentos (o que faz o movimento diagonal parecer muito lento ) Com grades hexagonais, a distância do movimento é muito mais intuitiva, pois é sempre a mesma distância de um hexágono para outro, independentemente do caminho que você seguir.

Eu não sou um especialista em IA de forma alguma, mas a diferença deve ser insignificante. As grades quadradas são um pouco mais rápidas (4 conexões por nó em vez de 6), mas esse realmente não é o fator limitante no tempo de execução algorítmico. Dependendo do algoritmo que você planeja usar, o código pode ser um pouco mais complexo para uma grade hexadecimal, já que é um pouco mais complicado calcular coordenadas e é mais difícil usar o tipo de atalho quadtree / octree que acredito que sejam frequentemente usado na busca de caminhos.

Mas para um mundo simples como um nível de jogo baseado em turnos, a diferença entre os dois layouts não deve importar muito; uma grade quadrada será um pouco mais simples e mais rápida.

Há uma diferença prática em que posso pensar em relação ao planejamento de caminhos. Atravessar do centro de uma célula hexadecimal para uma de suas vizinhas é sempre a mesma distância, enquanto que, se você permitir um deslocamento diagonal, isso não se aplica aos quadrados.

Este guia sobre hexágonos é incrível. A parte sobre o pathfinding tem um exemplo interativo e algumas informações sobre como adaptar o square pathfinding.

Se você estiver usando o pathfinding baseado em gráfico, como o algoritmo A * ou Dijkstra ou o Floyd-Warshall, o pathfinding em grades hexagonais não é diferente do pathfinding em grades quadradas.

• Vizinhos. O código de exemplo que forneço no tutorial de busca de caminhos chama graph.neighbors para obter os vizinhos de um local. Use a função na seção vizinhos para isso. Filtrar os vizinhos que são intransitáveis.
• Heurística. O código de exemplo para A * usa uma função heurística que fornece uma distância entre dois locais. Use a fórmula da distância, dimensionada para corresponder aos custos de movimentação. Por exemplo, se seu custo de movimento for 5 por hexadecimal, multiplique a distância por 5.