Les grilles carrées ou hexagonales sont-elles meilleures pour la recherche de chemin?

17

Existe-t-il une différence significative entre l'utilisation d'une grille carrée ou hexagonale pour la zone recherchée par un algorithme de recherche de chemin. En d'autres termes, est mieux carré ou hexagonal, et si oui pourquoi.

Edwin Earl Ross
la source
4
Il me semble que vous devriez utiliser ce qui convient à votre gameplay;)
Andrew Russell

Réponses:

19

La principale considération pour décider d'utiliser des grilles carrées ou hexagonales ne devrait pas être la facilité de mise en œuvre de l'IA - les algorithmes de recherche en largeur et en profondeur sont à peu près les mêmes quel que soit le type de graphique que vous avez.

Il s'agit plutôt d'un problème de gameplay qui devrait être pris en compte par les concepteurs de jeux. Les grilles carrées sont plus accessibles au marché de masse (les cartes hexagonales ont tendance à avoir l'air "geek"), et dans un monde de contrôles haut / bas / gauche / droite, il est beaucoup plus intuitif de naviguer autour des carrés que des hexagones du point de vue de l'interface utilisateur. Les grilles carrées ont également tendance à restreindre un peu plus le mouvement; en supposant un mouvement orthogonal (et non diagonal), il faut 4 mouvements pour contourner un obstacle d'un carré, contre 3 mouvements dans une grille hexagonale. Du point de vue de la programmation, les hexs sont également un peu plus faciles à implémenter, mais il ne s'agit pas autant d'algorithmes de recherche qu'une grille carrée équivaut à un tableau à deux dimensions, mais une grille hexadécimale ne correspond pas vraiment à une structure de données standard.

L'inconvénient des grilles carrées est que le mouvement ne se sent jamais bien. Le déplacement en diagonale devrait prendre des points de mouvement sqrt (2), mais en pratique c'est soit 1 mouvement (ce qui donne l'impression que marcher sur les diagonales est rapide et il y a rarement une raison de marcher orthogonalement) ou c'est 2 mouvements (ce qui rend le mouvement diagonal trop lent ). Avec les grilles hexagonales, la distance de déplacement est beaucoup plus intuitive, car c'est toujours la même distance d'un hex à l'autre, quel que soit le chemin que vous empruntez.

Ian Schreiber
la source
4
+1. C'est une décision de conception, pas une décision d'IA. Si vous voulez des grilles hexagonales, une grille carrée décalée comme www-cs-students.stanford.edu/~amitp/game-programming/grids/… peut être moins intimidante pour les joueurs occasionnels, et elle est mathématiquement équivalente aux hexagones. C'est également une représentation pratique en mémoire.
2
+1 pour la phrase "Les grilles carrées sont plus accessibles au marché de masse (les planches hexagonales ont tendance à avoir l'air" geek ")": D
Kornel Kisielewicz
Edwin ne demande pas ce qui est mieux sur un jeu basé sur une grille. Il demande ce qui est mieux pour l'IA d'utiliser des carrés ou des hexagones. Le monde et le gameplay lui-même ne doivent pas être limités à ceux-ci, mais uniquement sur les nœuds sur lesquels l'IA recherche.
AttackingHobo
J'ai implémenté des jeux de stratégie au tour par tour avec des grilles hexagonales et carrées, et il n'y a absolument aucune différence nécessaire en termes de complexité de détermination de chemin. J'ai même changé un jeu d'une carte hexadécimale à une carte carrée, et (à part le rendu) le seul changement que j'ai dû apporter était une méthode MapLocation :: GetDistance () qui calculait la distance entre deux secteurs. J'ai simplement dû ajuster les calculs pour que chaque ligne soit légèrement décalée. Dans les deux cas, vous pouvez utiliser la même représentation en mémoire. Donc, comme les autres l'ont dit, c'est vraiment un problème de conception.
Mike Strobel
4
Juste un côté, les hexs peuvent être mappés à un tableau à 2 dimensions. Imaginez une grille carrée, puis déplacez chaque colonne paire d'un demi-pas vers le bas. Vous avez maintenant une grille carrée décalée, qui est isomorphe à une grille hexadécimale.
Asmor
3

Je ne suis en aucun cas un expert en IA, mais la différence devrait être négligeable. Les grilles carrées sont un peu plus rapides (4 connexions par nœud au lieu de 6), mais ce n'est vraiment pas le facteur limitant dans l'exécution algorithmique. Selon l'algorithme que vous prévoyez d'utiliser, le code peut être un peu plus complexe pour une grille hexadécimale, car il est un peu plus compliqué de calculer des coordonnées, et il est plus difficile d'utiliser le type de raccourcis quadtree / octree que je crois être souvent utilisé dans la recherche de chemins.

Mais pour un monde simple comme un niveau de jeu de stratégie au tour par tour, la différence entre les deux dispositions ne devrait pas avoir beaucoup d'importance; une grille carrée sera légèrement plus simple et plus rapide.

Gregory Avery-Weir
la source
5
"Les grilles carrées sont un peu plus rapides (4 connexions par nœud au lieu de 6)" - à moins que vous ne puissiez voyager le long des diagonales, auquel cas c'est 8 connexions contre 6.
Ian Schreiber
Touche. Vous avez tout à fait raison; bien sûr, des connexions diagonales seraient probables.
Gregory Avery-Weir
3

Il y a une différence pratique à laquelle je peux penser en ce qui concerne la planification de parcours. Traverser du centre d'une cellule hexadécimale à l'un de ses voisins est toujours la même distance alors que, si vous autorisez un déplacement diagonal, ce n'est pas vrai pour les carrés.

Clodéric
la source
0

Ce guide sur les hexagones est génial. La partie sur le pathfinding a un exemple interactif et quelques informations sur la façon d'adapter le pathfinding carré.

Si vous utilisez le pathfinding basé sur un graphique tel que A * ou l'algorithme de Dijkstra ou Floyd-Warshall, le pathfinding sur les grilles hexadécimales n'est pas différent du pathfinding sur les grilles carrées.

  • Voisins. L'exemple de code que je fournis dans le didacticiel de recherche de chemin appelle graph.neighbors pour obtenir les voisins d'un emplacement. Utilisez la fonction dans la section voisins pour cela. Filtrer les voisins infranchissables.
  • Heuristique. L'exemple de code pour A * utilise une fonction heuristique qui donne une distance entre deux emplacements. Utilisez la formule de distance, mise à l'échelle pour correspondre aux coûts de mouvement. Par exemple, si votre coût de déplacement est de 5 par hex, multipliez la distance par 5.
marque
la source