Share
Pathfinding est omniprésent dans les jeux. Il est donc important de comprendre les implications de l'utilisation d'algorithmes tels que A *. Dans ce tutoriel, nous allons couvrir une méthode relativement nouvelle de recherche dans les mondes basés sur une grille: Recherche de points de saut, ce qui peut accélérer A * par ordre de grandeur.
Remarque: Bien que ce tutoriel ait été écrit avec AS3 et Flash, vous devriez pouvoir utiliser les mêmes techniques et concepts dans presque tous les environnements de développement de jeux..
Cette implémentation est basée sur le papier original et l'article sur JPS trouvés ici: Recherche de point de saut. le
L’implémentation basée sur Lua, Jumper, a été utilisée pour l’aide dans certaines parties de l’implémentation..
Cliquez sur le fichier SWF pour le mettre en évidence, puis déplacez votre souris sur les zones non bloquantes de la carte pour que les PNJ tentent de s'y rendre. Appuyez sur Espace pour basculer entre A *, Recherche de point de saut et les deux..
Pas de flash? Découvrez la vidéo YouTube à la place:
L'implémentation de démonstration ci-dessus utilise AS3 et Flash avec le rendu accéléré par le framework Starling Framework for et par la bibliothèque polygonale-ds pour les structures de données..
Pathfinding est souvent utilisé dans les jeux vidéo et vous êtes sûr de le rencontrer à un moment ou à un autre de votre carrière dans le développement de jeux. Son utilisation principale est de donner aux entités artificielles (NPC) un comportement de mouvement intelligent en regardant, afin d'éviter qu'elles ne se heurtent (souvent) à des objets..
Dans certains jeux, l'avatar du joueur est également sujet à des recherches (jeux de stratégie, de nombreux jeux de rôle à la troisième personne et jeux d'aventure). Vous pouvez donc supposer que le problème de l'orientation est résolu, mais malheureusement, ce n'est pas le cas. il n'y a pas de solution miracle que vous pouvez utiliser et juste en finir.
Et même dans les grands jeux AAA, vous trouverez toujours des choses amusantes comme celle-ci:
Il n’ya peut-être pas de solution miracle, mais une solution: l’algorithme A * (étoile). Dans ce tutoriel, nous allons voir un bref aperçu de A * et comment l'accélérer à l'aide d'un autre algorithme, Jump Point Search..
Tout d'abord, nous avons besoin d'un moyen de représenter notre monde de jeu de manière à ce qu'un algorithme de recherche de chemin puisse l'utiliser.
L’une des choses les plus importantes à prendre en compte lors de la réflexion sur la recherche de parcours pour votre jeu est représentation du monde. Comment les données des zones passables et des obstacles sont-elles organisées avec les structures de programmation en mémoire??
La représentation la plus simple que vous pouvez utiliser est une structure basée sur une grille, dans laquelle les nœuds de chemin d'accès sont organisés dans une grille et peuvent être représentés par un tableau 2D. Nous allons utiliser cette représentation dans ce tutoriel. Plus précisément, il s'agira d'une représentation en grille à huit voies: permettant un mouvement dans les directions droite et diagonale.
Vos besoins peuvent être différents, cette structure peut donc ne pas vous convenir. La bonne chose à faire est que, avec certains traitements (généralement effectués hors ligne), vous pouvez modifier les représentations de cheminement vers d'autres formats. Les alternatives à l'approche basée sur la grille incluraient des éléments tels que les polygones (obstacles représentés par des polygones) ou les maillages de navigation (zones de navigation représentées par des polygones); ceux-ci peuvent représenter les mêmes données avec moins de nœuds.
Les autres données pouvant être stockées dans la représentation cartographique sont: frais: combien coûte le trajet d’un nœud à un autre. Ceci peut être utilisé pour que l'IA détermine le chemin qui, par exemple, préfère les routes au-dessus d'un terrain normal (rendant le coût de la route inférieur au terrain)..
La recherche de point de saut est spécialement conçue pour la représentation cartographique sur une grille à huit voies, nous allons donc l'utiliser. En outre, sous sa forme vanille, il ne prend pas en charge les cartes pondérées. (Dans la dernière section, je discuterai d'un moyen de remédier à cela.)
Maintenant que nous avons une représentation mondiale, examinons rapidement la mise en œuvre de A *. C'est un algorithme de recherche de graphes pondérés qui utilise des heuristiques (petits "conseils") pour mieux rechercher dans la zone, du nœud de début au nœud de fin..
Je vous recommande vivement de consulter cette visualisation des algorithmes de recherche de chemin:
PathFinding.js - visuel. Jouer avec cela peut stimuler votre intuition de ce que l'algorithme est en train de faire - en plus c'est amusant!
Pour rechercher un chemin à l'aide de A * dans des grilles rectangulaires, procédez comme suit:
1. Recherchez le noeud le plus proche de votre position et déclarez-le noeud de départ et mettez-le sur la liste ouverte. 2. S'il y a des nœuds dans la liste ouverte: 3. Sélectionnez le nœud de la liste ouverte ayant le plus petit score F. Mettez-le sur la liste fermée (vous ne voulez pas y revenir). 4. Pour chaque voisin (cellule adjacente) qui ne figure pas dans la liste fermée: 5. Définissez son parent sur le nœud actuel. 6. Calculez le score G (distance entre le nœud de départ et ce voisin) et ajoutez-le à la liste ouverte. 7. Calculez le score F en ajoutant une méthode heuristique à la valeur G.Articles Similaires
L'heuristique suppose essentiellement que le nœud en cours d'évaluation mène au but. Les heuristiques peuvent faire une grande différence en termes d'efficacité des algorithmes de recherche de chemin car ils ont tendance à limiter le nombre de nœuds à visiter. Nous allons utiliser la distance de Manhattan pour nos besoins (ce qui signifie que les nœuds les plus proches du but auront un nombre inférieur):
fonction privée manhattanDistance (début: nœud, fin: nœud): int return Math.abs (end.x - start.x) + Math.abs (end.y - start.y);
C'est plus ou moins ça. Nous arrêtons l'algorithme lorsque nous trouvons le nœud de l'objectif, puis faisons un suivi en utilisant la variable parent du nœud pour construire le chemin..
Les algorithmes de recherche peuvent également être utilisés à d'autres fins. A * est un algorithme général de recherche de graphes pondérés, et peut être utilisé sur tout graphe de ce type. Cela peut couvrir d’autres domaines de l’intelligence artificielle, tels que la recherche des étapes optimales pour atteindre certains objectifs: lancer une bombe ou courir pour s’abriter et essayer de se faufiler derrière un ennemi.?
Dans le développement de jeux, nous devons faire vite, si chaque milliseconde compte, actualise nos jeux à 60 images par seconde. Même si A * fonctionne relativement bien pour certaines utilisations, il est nécessaire d'accélérer le processus ou d'utiliser moins de mémoire..
Le choix de la représentation est la première chose qui aura un impact sur les performances de recherche de chemin et sur le choix de l'algorithme de cheminement. La taille du graphique sur lequel vous effectuez une recherche aura une grande corrélation sur les performances de votre recherche de trajectoire (ce qui est logique; il est plus facile de trouver votre chemin dans votre pièce que dans une grande ville)..
Ensuite, vous pouvez envisager des optimisations de niveau supérieur qui impliquent généralement de regrouper des données dans des régions plus petites, puis de les rechercher tout en affinant ultérieurement les chemins dans des régions plus petites parcourues. Par exemple, si vous voulez aller dans un restaurant d'une ville voisine, vous devez d'abord déterminer comment vous rendre de votre ville à cette ville, et une fois dans cette ville, vous limitez votre "recherche" à la zone où se trouve le restaurant. , ignorant le reste. Cela inclurait des choses comme les marais, l'élimination des impasses et le HPA *.
Au niveau le plus bas, vous devez faire la recherche. Vous avez choisi votre représentation des données et vos abstractions possibles, puis vous les avez insérées dans un algorithme qui sélectionne les nœuds, se déplace ici et là à la recherche de l'objectif. Ces algorithmes sont généralement basés sur l'algorithme de recherche A * avec les modifications possibles. Dans les cas les plus simples, vous pouvez vous en tirer en utilisant le A droit qui vous offre la simplicité. J'ai fourni une implémentation basée sur une grille dans le téléchargement source.
Étant donné que ce didacticiel concerne la mise en œuvre de la recherche de point de saut, le graphe de cheminement sera représenté par une grille. Et il doit notamment s'agir d'une grille à huit voies puisque l'algorithme l'utilise directement..
La recherche de point de saut réellement consiste à éliminer un grand nombre de nœuds intermédiaires dans certains types de combinaisons de grilles. Il saute un tas de ceux que vous ajouteriez à la liste ouverte et à la liste fermée, ainsi que d'autres calculs, en faveur d'un traitement plus long lors de la sélection du prochain nœud..
Comme avec A *, nous sélectionnons dans la scène ouverte le nœud ayant le score F le plus bas. Mais c’est là que les choses commencent à devenir intéressantes. Au lieu de choisir des nœuds adjacents, nous appelons cette fonction pour le faire pour nous:
fonction identifierSuccesseurs (courant: noeud, début: noeud, fin: noeud): vecteur.success successeurs: Vector. = nouveau vecteur. (); Var voisins: vecteur. = nodeNeighbours (actuel); pour chaque (var vois: noeud dans les voisins) // Direction du noeud actuel au voisin: dX var: int = clamp (neighbour.x - current.x, -1, 1); var dY: int = clamp (neighbour.y - current.y, -1, 1); // Essayez de trouver un nœud vers lequel accéder: var jumpPoint: Node = jump (current.x, current.y, dX, dY, début, fin); // Si trouvé, ajoutez-le à la liste: if (jumpPoint) successors.push (jumpPoint); renvoyer les successeurs;
Ce que cela fait est d'éliminer les nœuds qui ne sont pas intéressants pour notre chemin. Pour cela, nous utilisons la directive du parent comme principale ligne directrice. Voici des exemples d'élagage des nœuds que nous ignorerons pour les directions horizontale et verticale:
Exemple de situation de taille horizontale.
Dans le code cela finira par une série de si déclarations vérifiant ces situations. Vous pouvez voir l'exemple ci-dessous, décrivant le cas correct de l'image:
if (directionY == 0) if (! _world.isBlocked (current.x + directionX, current.y)) if (_world.isBlocked (current.x, current.y + 1)) // créer un nœud avec la nouvelle position neighbours.push (Node.pooledNode (current.x + directionX, current.y + 1));
Après avoir sélectionné le voisin, nous essayons de trouver un point de saut, c’est un nœud qui peut être atteint à partir du point actuel, mais pas nécessairement de la même manière. Pour le dire de manière plus formelle, JPS élimine la symétrie entre les chemins - chacun a une permutation différente des mêmes mouvements:
Donc, pour les grands espaces ouverts, nous pouvons avoir d’énormes gains. Voici comment fonctionne la méthode de saut:
saut de fonction (cX: int, cY: int, dX: int, dY: int, début: nœud, fin: nœud): nœud // cX, cY - Position actuelle du nœud, dX, dY - Direction // Position du nouveau noeud que nous allons examiner: var nextX: int = cX + dX; var nextY: int = cY + dY; // S'il est bloqué, nous ne pouvons pas sauter ici si (_world.isBlocked (nextX, nextY)) return null; // Si le noeud est l'objectif, retournez-le si (nextX == end.x && nextY == end.y) renvoie new Node (nextX, nextY); // Diagonal Case if (dX! = 0 && dY! = 0) if (/ *… Vérification diagonale forcée du voisin… * /) return Node.pooledNode (nextX, nextY); // Vérifier les directions horizontale et verticale pour les voisins forcés // Ceci est un cas particulier pour la direction diagonale si (saut (nextX, nextY, dX, 0, début, fin))! = Null || jump (nextX, nextY, 0 , dY, début, fin)! = null) return Node.pooledNode (nextX, nextY); else // Cas horizontal if (dX! = 0) if (/ *… Vérification horizontale du voisin forcé… * /) return Node.pooledNode (nextX, nextY); /// Cas vertical else if (/ *… Contrôle de voisin forcé verticalement… * /) return Node.pooledNode (nextX, nextY); /// Si le voisin forcé n'a pas été trouvé, essayez le point de saut suivant. Saut de retour (nextX, nextY, dX, dY, début, fin);
J'ai supprimé les contrôles de voisins forcés des instructions if, car ils sont assez volumineux. Elles consistent essentiellement en des contrôles similaires à ceux de la première sélection de voisins pour un nouveau nœud (de nombreux contrôles pour voir si les cellules sont bloquées). Ils servent à détecter quand il nous est permis d’avoir nos hypothèses sur la symétrie.
Le cas de la diagonale est spécial et nous devons rechercher non seulement des voisins forcés dans les directions diagonales, mais également dans les directions horizontale et verticale, et si l'un de ceux-ci échoue, nous devons définir un nœud forcé comme point de saut. Nous devons également considérer un cas particulier du nœud de l'objectif, où la méthode de saut se termine.
Chaque fois que nous ne trouvons pas de nœud de recherche, nous appelons la fonction de saut de manière récursive dans la direction spécifiée. Dans la démo, j'ai effectivement déroulé cet appel récursif, car cet appel sera appelé beaucoup. (Lors de mes tests, les performances ont été multipliées par deux.)
C'est ce que fait JPS. le résultat final est de nouveaux nœuds à vérifier par A * et nous procédons avec l'algorithme. Lorsque le noeud de but est trouvé, nous reconstruisons le chemin et le retournons.
JPS peut ignorer de nombreux nœuds lors de la recherche, ce qui peut améliorer considérablement la vitesse (dans mon projet, il est environ 30 fois supérieur à A *), mais cela a un coût..
Cela fonctionne mieux sur une grille uniforme, mais peut être fait pour travailler avec des non uniformes en utilisant des ajustements supplémentaires, en marquant les voisins comme étant forcés lorsqu'il y a une transition vers un nœud de coûts différents (il est préférable d'utiliser des coûts discrets)..
Dans un jeu sur lequel je travaille, la grille est uniforme sauf pour les routes, qui coûtent beaucoup moins cher que de marcher sur un terrain ordinaire. (Cela semble beaucoup mieux quand le personnage respecte ça.) En fin de compte, j'ai résolu ce problème en calculant à l'avance certaines valeurs des positions sur la route. Lorsque le repérage de chemin est lancé, l'algorithme recherche les points les plus proches possibles du chemin depuis les nœuds de début et de but, puis recherche un graphique spécial de routes de haut niveau (qui est précalculé), puis utilise JPS pour rechercher des zones.
Une note rapide sur le débogage. Le débogage de ce type d'algorithmes peut être très difficile, et il est presque certain que la première implémentation aura un bogue difficile à trouver. Vous pouvez vous rendre service et construire une sorte de visualisation fonctionnelle et dessiner ce qui se passe lorsque l'algorithme s'exécute.
Si vous rencontrez un bogue, vous devez réduire le domaine (taille de la grille) au minimum, ce qui vous permet de reproduire votre problème et de le tester à partir de là. Comme vous pouvez probablement le deviner, ma première implémentation de JPS n'a pas fonctionné immédiatement!
Accentsconagua