Envisagez A * de rechercher sur une carte basée sur des tuiles. Un code simple serait: s'il y a une unité à l'intérieur de cette cellule, alors elle est inaccessible, c'est ok.
Mais il y a un problème de résolution de carte. Quand je regarde Warcraft 3, les monstres et les structures ont un rayon différent, et vous pouvez marcher très près, ce qui ressemble plus à un vecteur, comment cela a-t-il été mis en œuvre?
De plus, quelle est la solution standard pour intégrer la détection de collision d'obstacles mobiles avec un algorithme de recherche de chemin, comme Warcraft 3?
Réponses:
Je ne peux pas dire avec certitude quel type d'approche a été utilisé par les développeurs WC3, mais cela ressemble à peu près à Hierarchical Annotated A *. Le rayon d'unité défini dans WC3Editor a été utilisé tel quel pour la mise à l'échelle du modèle 3D, mais la taille réelle de l'unité pour la recherche de chemin était discrète, peut-être quelque chose comme unitSize = (int) (unitRadius / 10). Ce n'était pas basé sur les vecteurs, c'est sûr.
Disons qu'il y a beaucoup de nœuds de chemin faisant une grille de nœuds haute résolution. Une unité simple comme une goule a une taille de 2, donc pour la placer quelque part dans une grille, nous avons besoin de 4 nœuds de libre parcours les uns à côté des autres. Un héros chevalier de la mort est légèrement plus grand avec une taille de 3, prenant 9 nœuds de chemin au total. Maintenant, nous plaçons 2 ziggourats ensemble en laissant un espace de 2 nœuds entre les deux, et envoyons une goule et un chevalier de la mort de l'autre côté. La goule pourra passer entre deux ziggourats, tandis que le chevalier de la mort devra se déplacer. Comment le déterminer?
Afin de voir si un nœud peut accueillir une unité de taille spécifique, attribuons une valeur de dégagement spéciale à chaque nœud définissant une taille d'unité maximale autorisée. Fondamentalement, cela signifie que plusieurs vérifications de délimitation ont été effectuées pour un nœud, et les limites les plus grandes possibles ont été mémorisées comme la clairance du nœud. Donc, lorsque nous voulons placer un chevalier de la mort sur un nœud, cela devient aussi simple que de comparer la clairance du nœud à la taille du chevalier de la mort. Bien sûr, les choses vont devenir beaucoup plus complexes lorsqu'il y a plusieurs unités qui se disputent les nœuds, mais c'est une autre histoire.
Pour plus de détails, vous pouvez consulter cet article:
http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
la source
Il utiliserait la tessellation pour créer des maillages de navigation AKA pour les régions de chemin. Cet article explique le concept avec des diagrammes complets.
Vous pouvez toujours conserver A * comme approche d'orientation, mais votre réseau n'est plus une grille (graphique à 4 connexions), mais un graphique représentant la connectivité arbitraire entre vos régions polygonales. Vous devrez donc adapter votre algorithme à votre convenance.
la source