Share
La recherche de cheminement basée sur une grille fonctionne bien pour les jeux dans lesquels les personnages peuvent se déplacer librement le long des axes x et y. Le problème avec cette application aux plateformes est que le mouvement sur l'axe des ordonnées est fortement limité, en raison des forces gravitationnelles simulées..
Dans ce didacticiel, je vais donner un aperçu général de la modification d'un algorithme A * standard afin qu'il fonctionne pour les développeurs de plates-formes en simulant ces restrictions gravitationnelles. (Dans la partie suivante, je vais vous expliquer comment coder l'algorithme.) L'algorithme adapté pourrait être utilisé pour créer un personnage IA qui suit le joueur ou pour montrer au joueur l'itinéraire vers son but, par exemple..
Je suppose ici que vous connaissez déjà A * pathfinding, mais si vous avez besoin d'une introduction, A * Pathfinding for Beginners de Patrick Lester est excellent..
Vous pouvez jouer à la démonstration Unity ou à la version WebGL (64 Mo) pour voir le résultat final en action. Utilisation WASD déplacer le personnage, click gauche sur un endroit pour trouver un chemin que vous pouvez suivre pour y arriver, et clic-droit une cellule pour basculer le sol à ce point.
À la fin de cette série, nous aurons également ajouté des plates-formes à sens unique, étendu le code afin de traiter différentes tailles de caractères et codé un bot capable de suivre automatiquement le chemin! Découvrez cette démo d'Unity ici (ou la version de 100 Mo + WebGL).
Avant de pouvoir adapter l’algorithme de recherche de chemin, nous devons définir clairement les formes que les chemins eux-mêmes peuvent prendre..
Disons que notre personnage prend une cellule, et peut sauter trois cellules haute.
Nous ne permettrons pas à notre personnage de se déplacer en diagonale à travers les cellules, car nous ne voulons pas qu'il traverse un terrain solide. (Autrement dit, nous ne lui permettons pas de se déplacer dans le coin d'une cellule, mais dans le haut, le bas, le côté gauche ou le côté droit.) Pour passer à une cellule adjacente en diagonale, le personnage doit déplacer une cellule vers le haut ou le bas. et une cellule à gauche ou à droite.
Comme la hauteur de saut du personnage est de trois cellules, il ne devrait pas pouvoir bouger après avoir sauté trois fois. en haut plus de cellules, mais il devrait toujours être en mesure de passer à la côté.
Sur la base de ces règles, voici un exemple du chemin que prendrait le personnage pendant son saut de distance maximum:
Bien sûr, le personnage peut sauter directement vers le haut, ou avec n'importe quelle combinaison de mouvements gauche et droite, mais cet exemple montre le type d'approximation que nous devons adopter pour calculer le chemin à l'aide de la grille..
Chacune des cellules du chemin doit conserver des données sur la hauteur du saut afin que notre algorithme puisse détecter que le joueur ne peut pas sauter plus haut et doit commencer à tomber..
Commençons par attribuer la valeur de saut de chaque cellule en l'augmentant d'un, chaque cellule, tant que le saut continue. Bien sûr, lorsque le personnage est au sol, la valeur de saut doit être 0.
Voici la règle appliquée au même chemin de saut de distance maximale que précédemment:
La cellule qui contient un 6 marque le point le plus élevé du chemin. Cela a du sens, car cela correspond à deux fois la valeur de la hauteur de saut maximale du personnage, et le personnage alterne en déplaçant une cellule vers le haut et une cellule sur le côté, dans cet exemple..
Notez que si le caractère saute droit et que nous continuons à augmenter la valeur de saut d'une cellule, cela ne fonctionne plus car dans ce cas, la cellule la plus haute aurait une valeur de saut 3.
Modifions notre règle pour augmenter la valeur de saut à la prochain numéro pair chaque fois que le personnage se déplace vers le haut. Ensuite, si la valeur du saut est paire, le personnage peut se déplacer à gauche, à droite ou vers le bas (ou vers le haut, s'il n'a pas atteint une valeur de saut de 6 encore) et si la valeur du saut est impair, le personnage ne monte ou ne descend que (selon qu’il a atteint le sommet du saut ou non).
Voici à quoi cela ressemble pour un saut droit vers le haut:
Et voici un cas plus compliqué:
Voici comment les valeurs de saut sont calculées:
Comme vous pouvez le constater, avec ce type de numérotation, nous savons exactement quand le personnage atteint sa hauteur de saut maximale: c’est la cellule avec la valeur de saut égale à deux fois la hauteur maximale de saut de caractère. Si la valeur du saut est inférieure à cela, le personnage peut toujours se déplacer vers le haut; sinon, nous devons ignorer le noeud directement au-dessus.
Maintenant que nous sommes conscients du type de mouvements que le personnage peut effectuer sur la grille, considérons la configuration suivante:
La cellule verte à la position (3, 1) est le personnage la cellule bleue à la position (2, 5) est le but. Dessine une route que l’algorithme A * peut choisir en premier pour tenter d’atteindre l’objectif @
Le chiffre jaune dans le coin supérieur droit d'une cellule est la valeur de saut de la cellule. Comme vous pouvez le constater, avec un saut direct, le personnage peut sauter trois tuiles, mais pas plus. Ce n'est pas bien.
Il est possible que nous trouvions plus de chance avec un autre itinéraire. Reprenons donc notre recherche et recommençons à partir de node (3, 2)..
Comme vous pouvez le constater, sauter sur le bloc à la droite du personnage lui a permis de sauter assez haut pour atteindre le but! Cependant, il y a un gros problème ici…
Selon toute vraisemblance, la première voie empruntée par l'algorithme est la première que nous avons examinée. Après l'avoir pris, l'algorithme n'ira pas très loin et finira par revenir au nœud (3, 2). Il peut ensuite rechercher à travers des nœuds (4, 2), (4, 3), (3, 3) (encore), (3, 4) (encore), (3, 5), et enfin la cellule de but, (2, 5).
Dans une version de base de l'algorithme A *, si un nœud a déjà été visité une fois, nous n'avons pas besoin de le traiter à nouveau. Dans cette version, cependant, nous le faisons. En effet, les nœuds ne se distinguent pas uniquement par les coordonnées x et y, mais aussi par les valeurs de saut..
Dans notre première tentative de trouver un chemin, la valeur de saut au noeud (3, 3) était 4; dans notre deuxième tentative, c’était 3. Étant donné que lors de la deuxième tentative, la valeur de saut dans cette cellule était inférieure, cela signifiait que nous pouvions potentiellement aller plus haut que lors de la première tentative..
Cela signifie essentiellement que le noeud (3, 3) avec une valeur de saut de 4 est un noeud différent que le noeud à (3, 3) avec une valeur de saut de 3. La grille doit essentiellement devenir tridimensionnelle à certaines coordonnées pour tenir compte de ces différences, comme suit:
Nous ne pouvons pas simplement changer la valeur de saut du noeud à (3, 3) de 4 à 3, parce que certains chemins utilisent le même nœud plusieurs fois; si nous faisions cela, nous remplacerions fondamentalement le noeud précédent et cela corromprait bien sûr le résultat final.
Nous aurions le même problème si le premier chemin avait atteint l'objectif malgré les valeurs de saut les plus élevées; si nous avions remplacé l'un des nœuds par un autre plus prometteur, nous n'aurions aucun moyen de récupérer le chemin d'origine..
Rappelez-vous, c'est le algorithme qui utilise une approche basée sur une grille; en théorie, votre jeu et ses niveaux ne doivent pas.
Il est important que le personnage ait au moins autant de liberté de mouvement que l'algorithme en attend, et de préférence un peu plus que cela.
Faire en sorte que le mouvement des caractères corresponde exactement aux contraintes de l'algorithme n'est pas une approche viable, en raison de la nature discrète de la grille et de la taille de la cellule de la grille. Il est possible de coder la physique de manière à ce que l’algorithme toujours trouver un moyen s'il en existe un, mais cela nécessite de construire la physique à cette fin.
L’approche que j’adopte dans ce tutoriel consiste à adapter l’algorithme à la physique du jeu, et non l’inverse..
Les problèmes principaux se produisent dans les cas où la liberté de mouvement attendue de l'algorithme ne correspond pas à la liberté de mouvement réelle du personnage dans le jeu..
Supposons que l'IA autorise des sauts de six cellules de long, mais que la physique du jeu autorise un saut de sept cellules. S'il existe un chemin qui nécessite le saut le plus long pour atteindre l'objectif dans les meilleurs délais, le bot l'ignorera et choisira le plus conservateur, pensant que le saut le plus long est impossible..
S'il y a un chemin qui nécessite un saut plus long et qu'il n'y a pas d'autre moyen d'atteindre l'objectif, alors le viseur conclura que l'objectif est inaccessible..
Si, à l'inverse, l'algorithme pense qu'il est possible de sauter sept cellules de suite, alors que la physique du jeu ne permet en réalité qu'un saut de six cellules, le bot peut alors suivre le mauvais chemin et tomber dans un endroit d'où il ne peut pas accéder. out, ou essayez de trouver un chemin à nouveau et recevez le même résultat incorrect, provoquant une boucle.
(En dehors de ces deux problèmes, il est préférable de laisser la physique du jeu permettre plus de liberté de mouvement que ne le prévoit l'algorithme.)
La première façon de s'assurer que l'algorithme est toujours correct consiste à avoir des niveaux que les joueurs ne peuvent pas modifier. Dans ce cas, vous devez simplement vous assurer que le terrain que vous concevez ou générez fonctionne bien avec l'IA pathfinding..
La deuxième solution à ces problèmes consiste à peaufiner l'algorithme, la physique ou les deux, afin de s'assurer qu'ils correspondent. Comme je l'ai mentionné plus tôt, cela ne signifie pas qu'ils doivent correspondre exactement; par exemple, si l'algorithme pense que le personnage peut sauter cinq cellules plus haut, il est correct de définir le saut maximal réel à 5.5 cellules élevées. (Contrairement à l'algorithme, la physique du jeu peut utiliser des valeurs fractionnaires.)
Selon le jeu, il peut également être vrai que le bot en intelligence artificielle ne pas trouver un chemin existant n’est pas une grosse affaire; il va tout simplement abandonner et retourner à son poste, ou simplement s'asseoir et attendre le joueur.
À ce stade, vous devriez avoir une compréhension conceptuelle décente de la manière dont A * pathfinding peut être adapté à un jeu de plateforme. Dans mon prochain tutoriel, nous concrétiserons cela en adaptant un algorithme de cheminement A * existant afin de l'implémenter dans un jeu.!
Accentsconagua