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.
ai
path-finding
Edwin Earl Ross
la source
la source
Réponses:
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.
la source
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.
la source
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.
la source
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é.
la source