Recherche de chemin basée sur une grille

Dans ce tutoriel, nous allons réaliser une simulation de recherche de chemin basée sur une grille de tableau à deux dimensions. Cela nous donnera une idée de base pour créer des activités de recherche de chemin dans nos jeux. Nous allons visualiser la grille en utilisant des objets carrés vides comme tuiles et un objet rond comme notre avatar qui peut se déplacer dans cette zone de grille à notre commande.

I. Configuration des objets

Nous n'utiliserons que quatre objets dans notre projet. Notre avatar vert, une tuile bleue, un bloc de blocage blanc et l'étiquette de grille pour configurer et visualiser notre grille.

Avatar

Notre avatar est un objet vide qui a une échelle x et y de 50 %. Réglez sa collision sur une forme ronde afin qu'il ressemble à l'image ci-dessous. Cet objet aura trois attributs prédéfinis : sur la tuile, tuile précédente et tuile cible. Réglez les valeurs par défaut de ces attributs à zéro afin qu'ils n'aient pas de valeur nulle lorsque nous essaierons de les récupérer plus tard.

Objet Tuile

Créez un autre objet vide qui sera utilisé pour visualiser les tuiles dans notre grille. Son échelle est également de 50 % et a seulement un attribut prédéfini : sur la tuile. Réglez également cette valeur à zéro.

Objet de blocage

Créez un autre objet vide qui servira de blocs de blocage dans notre grille. C'est un objet vide blanc avec une échelle de 40 %. Notre avatar ne pourra pas traverser une tuile qui a un blocage dessus.

Étiquette de Grille

Ceci est juste une étiquette qui aura les comportements qui permettront la configuration et la visualisation de notre grille. Elle a des attributs prédéfinis : start x avec une valeur de 4, et start y avec une valeur de 3. Ces valeurs sont des décalages qui seront utilisés comme références lors de la génération de nos tuiles afin de positionner notre grille proprement au centre.

Attributs prédéfinis Avatar/Tuile :

Nous définissons ici une tuile comme un tableau de taille 2 qui aura une valeur x et y en fonction de notre grille.

• sur la tuile - c'est la valeur de tuile sur laquelle notre objet se trouve actuellement dans notre grille
• tuile précédente - une tuile qui a été précédemment traversée par notre avatar
• tuile cible - la tuile que notre avatar va atteindre

II. Configuration de la grille

À l'intérieur de l'étiquette de grille, c'est là que nous définirons notre tableau 2D et la génération de notre grille. Il y a 2 points clés dans cet objet : la configuration du tableau et la visualisation du tableau. Commençons par le bundle de définition du tableau.

Définir le tableau - bundle

Tout d'abord, créez un tableau vide nommé 'Grille'. Ce tableau contiendra notre tableau à deux dimensions. Nous allons avoir un conteneur de boîte nommé 'compte de rangée x' qui a une valeur de 24 et un autre tableau vide nommé 'rangée y' qui a 18 valeurs vides.

Le premier comportement de notre ensemble est une boucle avec un nombre de répétitions égal à 'compte de rangée x'. Pour chaque étape de cette boucle, nous allons ajouter une rangée y vide au 'tableau Grille'. Cela créera un tableau dans un tableau avec une dimension de 24x18.

Remarquez que nous avons connecté un commentaire inactif au début de notre ensemble pour annuler l'exécution automatique de ce comportement racine. Un comportement racine est un comportement qui ne se déclenche pas en fonction d'un événement et est placé ouvertement dans l'interface.

Visualiser la grille - bundle

La principale chose que nous allons faire ici est de parcourir chaque valeur de notre 'tableau Grille' et de générer un objet tuile. Nous ajouterons également une condition dans notre boucle qui permettra la génération d'un blocage blanc sur le dessus de l'objet tuile.

Tout d'abord, obtenez le nombre d'éléments de notre 'tableau de rangée y', la valeur d'attribut 'start x' de cet objet et 'start y'.

Créez une boucle qui a une répétition de 'compte de rangée x' et pour chaque étape de cette boucle, nous allons ajouter la valeur d'index de cette boucle et la valeur d'attribut 'start x'. Cela mène à une position x absolue que nous allons utiliser pour positionner nos tuiles générées par la suite. Ensuite, voici la boucle de la rangée y qui a une répétition de 'compte de rangée y'. Pour chaque étape de cette boucle, nous ajouterons la valeur d'index de cette boucle et la valeur d'attribut 'start y', ce qui mènera maintenant à la position y absolue.

Après avoir ajouté les valeurs sous la boucle de rangée y, il faudra générer l'objet bleu. Réglez le nombre d'objets vivants sur 999 car nous en aurons besoin de nombreux pour notre grille, et aussi avec une durée de 0. Ensuite, déplacez cet objet généré à un point x avec une valeur provenant de la boucle x 'ajouter des valeurs', et au point y d'une valeur provenant de la boucle y 'ajouter des valeurs'.

Ensuite, ajoutez un tableau avec 2 valeurs vides nommé 'Sur la tuile' que nous n'utiliserons qu'en tant que placeholder de tableau. Après avoir déplacé l'objet tuile, il faudra modifier le tableau 'Sur la tuile' en remplaçant sa valeur à l'index 0 par la valeur de 'boucle de rangée x'. Ensuite, ajoutez une autre modification de tableau qui remplace la valeur à l'index 1 par 'index de rangée y'. Ce sont les coordonnées x et y de notre grille que l'objet aura comme attribut 'sur la tuile'.

Maintenant, réglez l'attribut de l'objet généré avec une clé dynamique, 'sur la tuile', et avec une valeur de 'Sur la tuile - tableau'.

Encore sous la boucle de rangée y, se trouve la condition de génération de l'objet de blocage blanc. Nous aurons une chance sur 5 d'exécuter ce bundle, ce qui ajoutera de la randomisation à notre grille. Ensuite, nous allons marquer une valeur de 1 sur les coordonnées x et y de cela dans notre 'Grille', ce qui nous indique que cette coordonnée a un blocage généré.

Tout d'abord, générez un nombre aléatoire de 1 à 5. Si ce nombre est inférieur ou égal à 2, nous allons générer le blocage. Réglez ses objets vivants sur 999 et déplacez cet objet au même point que la tuile bleue que nous avons générée auparavant, et également avec une durée de 0.

Ensuite, stockez les informations selon lesquelles cette coordonnée était occupée par un blocage, si elle a été générée. Nous faisons cela en marquant cette coordonnée avec une valeur de 1. Tout d'abord, obtenez la valeur à l'index 'boucle de rangée x' du tableau 'Grille'. Cette valeur nous donnera un tableau d'une 'rangée y'. Nous allons modifier cette 'rangée y' en remplaçant sa valeur à l'index 'boucle de rangée y' par la valeur 1, qui est la valeur marquée. Parce que cette modification de valeur s'applique uniquement à cette valeur, et non à la 'Grille elle-même', nous devons encore modifier le tableau 'Grille'. Remplacez la valeur à l'index 'boucle de rangée x' du tableau 'Grille' par la valeur de 'modifier rangée y - tableau'.

Une fois joué, cela devrait donner cette forme.

III. Sur Appuyer sur la Tuile

Pour pouvoir interagir avec la grille elle-même, nous aurons besoin d'un bundle de comportement chaque fois que nous appuyons sur une tuile bleue. La première pression entraînera l'apparition de notre avatar dans notre grille, et toute pression successive après cet événement commencera sa recherche de chemin.

À l'intérieur de l'objet bleu se trouve un bundle de comportement qui a 3 points principaux : réinitialiser la tuile précédente de notre avatar, définir sa tuile sur/son tuile cible, puis définir une animation de couleur pour visualiser l'événement de contact à l'écran.

Tout d'abord, obtenez l'attribut 'sur la tuile' de l'objet tuile. Réglez l'attribut 'tuile précédente' de notre avatar à 0. Notre avatar sera réglé pour éviter de revenir à une 'tuile précédente', c'est pourquoi nous réinitialisons la 'tuile précédente' à chaque pression de tuile.

Ensuite, obtenez l'attribut 'sur la tuile' de notre avatar. La première condition si est de savoir si la valeur 'sur la tuile' est égale à zéro. Cela signifie que si l'avatar n'est pas encore apparu, cela sera vrai. Si c'est vrai, nous définissons son attribut 'sur la tuile' avec la valeur de l'attribut 'sur la tuile' de l'objet tuile. Ensuite, déplacez la position de notre avatar en récupérant la position de l'objet tuile, en pointant ses valeurs x et y vers ce point avec une durée de 0.

Si la valeur 'sur la tuile' n'est pas égale à zéro, nous allons définir l'attribut 'tuile cible' de notre avatar avec la valeur de l'attribut 'sur la tuile' de l'objet tuile. Cela signifie que notre avatar est déjà dans notre grille, et ensuite, nous pourrons exécuter le bundle de comportement, 'trouver le chemin'. Nous n'avons pas encore ce comportement mais nous le corrigerons à nouveau après avoir réalisé la partie suivante de ce tutoriel pour le bundle 'trouver le chemin'.

Maintenant que nous avons correctement positionné notre avatar dans notre grille, nous allons simplement visualiser cet événement de pression. Tout d'abord, avoir un comportement racine 'obtenir la couleur' pour obtenir sa couleur d'origine. Ensuite, après l'événement de pression, nous changerons la couleur de l'objet tuile en noir avec une durée de 0, puis remettrons sa couleur d'origine avec une durée de 0.2.

Appuyer sur une tuile bleue devrait donner ce résultat.

IV. Exécuter le Bundle Trouver le Chemin

Pour cette dernière partie de notre tutoriel, nous allons réaliser l'algorithme qui nous permet de trouver la tuile la plus proche que notre avatar peut emprunter pour atteindre sa destination. Ce bundle sera exécuté à plusieurs reprises pour chaque étape de tuile que notre avatar se déplace dans notre grille.

Nous allons configurer l'algorithme à l'intérieur de notre objet avatar et cela aura trois points principaux : trouver les tuiles adjacentes, trouver la tuile adjacente la plus proche, et le mouvement vers cette tuile adjacente.

Trouver les tuiles adjacentes

Dans cette partie, nous allons collecter toutes les tuiles adjacentes que notre avatar pourrait traverser. Nous vérifierons les quatre tuiles adjacentes directionnelles et verrons si ces tuiles ont un blocage dessus ou si elles ont déjà été foulées.

Tout d'abord, ajoutez notre tableau 'Tuiles adjacentes'. Un tableau 'Direction' avec 2 valeurs vides, et les quatre tableaux directionnels ayant 2 valeurs chacun : N (0,1), S (0,-1), E (1,0), W( -1,0).

Le premier comportement de notre ensemble est de vider nos tuiles adjacentes. Parce que nous allons faire ce bundle plusieurs fois, nous devons réinitialiser nos 'tuiles adjacentes' collectées à chaque fois. Les quatre comportements suivants sont des modifications au tableau 'Direction'. Nous définissons le tableau de 'Direction' quatre fois avec les quatre tableaux directionnels, puis exécutons le bundle ci-dessous. Nous faisons cela pour créer une boucle avec différentes valeurs de tableau 'Direction' à chaque fois.

Maintenant que nous avons la direction, nous devons simplement combiner leurs valeurs x et y avec l'attribut 'sur la tuile' de notre avatar. Ensuite, nous pourrons obtenir notre valeur cible dans le tableau 'Grille' pour savoir si cette tuile était marquée par un blocage.

'Direction x' est la valeur du tableau 'Direction' à l'index 0, 'obtenir sur la tuile' x est la valeur de 'obtenir sur la tuile' à l'index 0. Cible x est la valeur additive de 'direction x' et 'obtenir sur la tuile x'. Idem pour les valeurs y, mais avec un index cible de 1.

'Cible y rangée' est la valeur du tableau 'Grille' à l'index 'Cible x'. Puis l'index cible dans 'rangée y' sera la valeur du tableau 'Cible y rangée' à l'index 'Cible y'. Cela nous dit quelles coordonnées dans notre grille nous allons voir si elle a été marquée avec un blocage.

Si la valeur de 'index cible dans la rangée y' est 1, alors cette tuile cible a été marquée comme bloquée. Mais si la valeur n'est pas égale à 1, alors nous pouvons continuer dans notre bundle.

Parce que notre cible x et y a passé notre condition, nous avons ajouté une nouvelle tuile vide nommée 'Nouvelle tuile adjacente'. Cela stockera les valeurs cible x et y en tant que tableau de tuile. Nous allons définir la valeur de cible x à l'index 0 de 'Nouvelle tuile adjacente' et la cible y à son index 1.

Maintenant, obtenez l'attribut 'tuile précédente' de notre avatar. Si la 'tuile précédente' n'est pas égale à la 'nouvelle tuile adjacente', cela signifierait que la nouvelle tuile n'a pas été précédemment traversée. Ensuite, nous pouvons en toute sécurité ajouter la 'Nouvelle tuile adjacente' au tableau 'Tuiles adjacentes' en l'ajoutant. Nous définirons la valeur de 'tuile précédente' plus tard, après avoir réussi à déplacer notre avatar vers une autre tuile.

"Vous pouvez étendre ce bundle en créant des tableaux directionnels 8, ce qui permet à votre avatar de se déplacer dans des directions diagonales."

Trouver la tuile adjacente la plus proche

Maintenant que nous avons collecté nos tuiles adjacentes fiables, nous devons simplement obtenir la tuile adjacente la plus proche de la tuile cible de notre avatar. Nous ferons le calcul à l'aide d'une formule de distance fournie par les valeurs x et y de notre tuile cible et des tuiles adjacentes.

Il y a deux points clés dans ce bundle : l'initialisation des variables pour le calcul et le calcul des distances de tuile à l'intérieur d'une boucle.

a. Initialisation des variables

Tout d'abord, obtenez le nombre d'éléments de nos tuiles adjacentes. Ensuite, obtenez l'attribut 'tuile cible' de notre avatar et récupérez ses valeurs x et y. Nous allons ajouter 2 nouveaux conteneurs de boîte : la 'distance min' et l'index de tuile cible. Nous définissons la valeur initiale de 'distance min' à 9999, et la valeur de 'index de tuile cible' à 0. La distance min est fixée à un nombre élevé parce que nous avons besoin de la distance la plus faible depuis le départ. L'index de tuile cible est notre index de référence dans le tableau 'Tuiles adjacentes' qui a la distance la plus faible par rapport à notre 'tuile cible'.

Notre objectif principal ici est d'obtenir l'index de la tuile dans notre tableau 'Tuiles adjacentes' qui est la plus proche de notre 'tuile cible'.

b. Calcul des distances de tuiles

Dans ce bundle, nous allons effectuer le calcul à l'intérieur d'une boucle que nous allons réaliser pour chaque tuile adjacente. La boucle se répète selon 'nombre de tuiles adjacentes' et nous allons obtenir la valeur de tuile du tableau 'Tuiles adjacentes' en utilisant l'index de cette boucle.

Obtenez les valeurs x et y de cette tuile adjacente et ensuite nous allons obtenir la distance entre notre 'tuile cible' et la 'tuile adjacente' en utilisant cette formule :

distance = sqrt((x2 - x1)^2+(y2 - y1)^2)
x1 = Cible x
x2 = Adjacent x
y1 = Cible y
y2 = Adjacent y

Nous soustrayons d'abord leurs valeurs x et y, multiplions par elles-mêmes pour obtenir leurs valeurs exponentielles, ajoutons ces valeurs, puis faisons la racine carrée de la somme ajoutée, afin d'obtenir la valeur de distance.

Si la valeur de 'distance' est inférieure à la valeur du conteneur de distance 'min', nous allons alors définir la valeur de l'index de tuile cible à l'index actuel de la boucle, qui est l'index de notre tuile récupérée dans le tableau 'Tuiles adjacentes'. Nous définissons également la valeur du conteneur de distance 'min' avec la valeur 'distance' pour que nous puissions la comparer avec la tuile suivante de notre boucle.

Après la fin de la boucle, nous avons comparé chacune de nos tuiles adjacentes et nous avons obtenu la valeur d'index de la tuile adjacente qui est la plus proche de notre 'tuile cible'.

Mouvement vers la tuile adjacente

Dans ce dernier bundle de notre tutoriel, nous allons déplacer notre avatar vers la tuile adjacente la plus proche et refaire tout le bundle 'Trouver le chemin' si nous ne nous sommes pas encore déplacés vers notre 'tuile cible'.

La première chose est de vérifier si notre 'nombre de tuiles adjacentes' est supérieur à 0. Cela pour s'assurer que nous ne nous déplacerons que si nous avons récupéré au moins une tuile adjacente fiable.

Ensuite, nous 'Obtenons la tuile la plus proche' en utilisant notre valeur d'index de tuile cible de l'ensemble précédent pour obtenir la valeur du tableau de 'Tuiles adjacentes'.

Pour obtenir le point exact où notre avatar se déplacera, nous aurons besoin des valeurs de tuile x et y de cette tuile, et également des valeurs d'attribut 'start x' et 'start y' de notre étiquette 'Grille'. Nous ajoutons alors la valeur x de notre 'tuile la plus proche' et la valeur 'start x', et également la même chose avec les valeurs y. Ces valeurs ajoutées sont nos points cibles x et y où notre avatar se déplacera.

Avant de nous déplacer vers ce point, nous définissons la 'tuile précédente' de notre avatar avec sa valeur d'attribut 'sur la tuile' actuelle. Nous pouvons obtenir cette valeur 'sur la tuile' à partir des ensembles précédents. Ensuite, déplacez notre avatar vers nos points cibles, avec une durée de 0.2.

Après la fin du comportement 'Déplacer vers le point', nous définissons maintenant la valeur de l'attribut 'sur la tuile' de notre avatar avec la valeur du tableau 'Obtenir la tuile la plus proche'. Si la valeur de ce tableau 'Obtenir la tuile la plus proche' n'est pas égale à notre 'tuile cible', nous allons ensuite exécuter le bundle 'Trouver le chemin', relançant ainsi tout le bundle encore une fois. La valeur d'attribut 'tuile cible' peut être obtenue à partir de l'ensemble précédent.

En appuyant sur n'importe quelle tuile bleue, et après l'apparition de notre avatar sur la grille, le bundle 'Trouver le chemin' sera exécuté. Cela déclenchera le mouvement de l'avatar d'une tuile à l'autre.

Conclusion

Dans ce tutoriel, nous avons appris à créer une activité de recherche de chemin d'objet en utilisant un tableau que nous avons appelé 'Grille', qui est utilisé pour stocker des informations sur le fait qu'une tuile était occupée ou non. Vous pouvez étendre cette idée, en utilisant des identifiants d'objet comme stockage d'information au lieu de simples nombres pour notre tableau 'Grille'. Cela nous donnera des informations plus fiables que nous pouvons utiliser lors de la recherche de chemin. Par exemple, nous pouvons obtenir les attributs de cet identifiant d'objet pour savoir s'il est vivant ou non, ou s'il nous permet de fouler sa tuile ou non.

Ce tutoriel n'a donné qu'une idée de base sur la recherche de chemin. Un inconvénient à cela est qu'il ne crée pas le chemin le plus court possible vers une tuile cible, et ne vérifie que les tuiles adjacentes actuelles. Cela peut entraîner une boucle de mouvement qui n'atteint nulle part.

Cependant, cela peut être résolu en élargissant notre algorithme de recherche de chemin. Nous pouvons faire cela en répétant nos tuiles adjacentes récupérées pour obtenir également leurs tuiles adjacentes jusqu'à ce que nous trouvions notre tuile cible. Chaque tuile adjacente trouvée sera ajoutée à une liste. Pour éviter une boucle infinie, ajoutez une condition que si cette tuile adjacente a déjà été vérifiée, cette tuile ne sera pas ajoutée à notre liste. De plus, ajoutez une limite max sur le compte d'itérations pour éviter une boucle infinie causée par la tuile cible si elle est trop éloignée ou impossible à trouver. Une fois que cette itération trouve la tuile cible, nous quittons cette itération et commençons à déplacer l'avatar d'une tuile à l'autre en utilisant la liste de tuiles.