Système d'emploi et chemin de recherche

La carte

Dans un article précédent, j'ai examiné ce qu'est le nouveau système de travail , comment il fonctionne, comment créer des tâches, les remplir avec des données et effectuer des calculs multithread, et je n'ai expliqué que brièvement où vous pouvez utiliser ce système. Dans cet article, je vais essayer d'analyser un exemple spécifique de l'endroit où vous pouvez utiliser ce système pour obtenir plus de performances.

Étant donné que le système a été initialement développé dans le but de travailler avec des données, il est idéal pour résoudre les tâches de recherche de chemin.

Unity possède déjà un bon explorateur NavMesh , mais il ne fonctionne pas dans les projets 2D, bien qu'il existe de nombreuses solutions prêtes à l'emploi sur le même actif . Eh bien, et nous essaierons de créer non seulement un système qui cherchera des moyens sur la carte créée, mais rendra cette carte très dynamique, de sorte que chaque fois que quelque chose change, le système crée une nouvelle carte, et tout cela, bien sûr, nous calculerons en utilisant un nouveau système de tâches, afin de ne pas charger le thread principal.


Dans l'exemple, une grille est construite sur la carte, il y a un bot et un obstacle. La grille est reconstruite chaque fois que nous modifions les propriétés de la carte, que ce soit sa taille ou sa position.

Pour les avions, j'ai utilisé un simple SpriteRenderer , ce composant a une excellente propriété de limites avec laquelle vous pouvez facilement trouver la taille de la carte.

C'est essentiellement tout pour commencer, mais nous ne nous arrêterons pas et nous passerons immédiatement aux choses sérieuses.

Commençons par les scripts. Et le premier est le script d'obstruction Obstacle .


À l'intérieur de la classe Obstacle , nous verrons tous les changements dans les obstacles sur la carte, par exemple, en changeant la position ou la taille d'un objet.
Ensuite, vous pouvez créer la classe Map map, sur laquelle la grille sera construite, et l'hériter de la classe Obstacle .


La classe Map suivra également toutes les modifications sur la carte afin de reconstruire la grille si nécessaire.

Pour ce faire, remplissez la classe de base Obstacle avec toutes les variables et méthodes nécessaires pour suivre les modifications d'objets.


Ici, la variable de rendu aura une référence au composant SpriteRenderer , et les variables tempSize et tempPos seront utilisées pour suivre les changements de taille et de position de l'objet.

La méthode virtuelle Awake sera utilisée pour initialiser les variables, et la méthode virtuelle CheckChanges suivra les changements actuels dans la taille et la position de l'objet et retournera un résultat booléen .

Pour l'instant, laissons le script Obstacle et passons au script Map map lui-même, où nous le remplissons également avec les paramètres nécessaires pour le travail.


La variable nodeSize indiquera la taille des cellules sur la carte, ici j'ai limité sa taille de 0,1 à 1 pour que les cellules de la grille ne soient pas trop petites, mais aussi trop grandes. La variable de décalage sera utilisée pour indenter la carte lors de la construction de la grille afin que la grille ne se construise pas le long des bords de la carte.

Comme il y a maintenant deux nouvelles variables sur la carte, il s'avère que leurs changements devront également être suivis. Pour ce faire, ajoutez quelques variables et surchargez la méthode CheckChanges dans la classe Map .


C'est fait. Vous pouvez maintenant créer un sprite de carte sur la scène et lancer un script de carte dessus.



Nous ferons de même avec un obstacle - créez un simple sprite sur scène et lancez le script Obstacle dessus.



Nous avons maintenant des objets cartographiques et des obstacles sur scène.

Le script de carte sera responsable du suivi de toutes les modifications sur la carte, où dans la méthode de mise à jour , nous vérifierons chaque cadre pour les modifications.


Ainsi, dans la méthode UpdateChanges, la carte ne suivra que ses modifications jusqu'à présent. Vous pouvez même démarrer le jeu maintenant et essayer de modifier la taille de la carte ou le décalage de décalage pour vous assurer que tous les changements sont suivis.

Maintenant, vous devez en quelque sorte suivre les changements des obstacles eux-mêmes sur la carte. Pour ce faire, nous mettrons chaque obstacle dans une liste sur la carte, qui à son tour mettra à jour chaque cadre dans la méthode Update .

Dans la classe Map , créez une liste de tous les obstacles possibles sur la carte et quelques méthodes statiques pour les enregistrer.


Dans la méthode RegisterObstacle statique, nous allons enregistrer un nouvel obstacle Obstacle sur la carte et l'ajouter à la liste, mais tout d'abord, il est important de considérer que la carte elle-même est également héritée de la classe Obstacle et nous devons donc vérifier si nous essayons d'enregistrer la carte elle-même comme obstacle.

La méthode statique UnregisterObstacle , au contraire, élimine l'obstacle de la carte et le supprime de la liste lorsque nous permettons qu'il soit détruit.

Dans le même temps, chaque fois que nous ajoutons ou supprimons un obstacle de la carte, il est nécessaire de recréer la carte elle- même.Ainsi , après avoir exécuté ces méthodes statiques, définissez la variable requireRebuild sur true .

De plus, pour avoir un accès facile au script Map à partir de n'importe quel script, j'ai créé une propriété Instance statique qui me rendra cette instance même de Map .

Revenons maintenant au script Obstacle où nous allons enregistrer un obstacle sur la carte. Pour ce faire, ajoutez-y quelques méthodes OnEnable et OnDisable .


Chaque fois que nous créons un nouvel obstacle en jouant sur la carte, il s'enregistrera automatiquement dans la méthode OnEnable , où il sera pris en compte lors de la construction d'une nouvelle grille et nous supprimera de la carte dans la méthode OnDisable lorsqu'il sera détruit ou désactivé.

Il ne reste plus qu'à suivre les changements des obstacles eux-mêmes dans le script Map dans la méthode CheckChanges surchargée.


Nous avons maintenant une carte, des obstacles - en général, tout ce dont vous avez besoin pour construire une grille et maintenant vous pouvez passer à la chose la plus importante.

Maillage

La grille, dans sa forme la plus simple, est un tableau bidimensionnel de points. Pour le construire, vous devez connaître la taille de la carte et la taille des points dessus, après quelques calculs, nous obtenons le nombre de points horizontalement et verticalement, voici notre grille.

Il existe de nombreuses façons de trouver un chemin sur une grille. Dans cet article, cependant, l'essentiel est de comprendre comment utiliser correctement les capacités du système de tâches, donc ici je ne considérerai pas différentes options pour trouver le chemin, leurs avantages et leurs inconvénients, mais je prendrai l'option de recherche la plus simple A * .

Dans ce cas, tous les points de la grille doivent avoir, en plus de la position, les coordonnées et la propriété de perméabilité.

Avec perméabilité, je pense que tout est clair pourquoi il est nécessaire, mais les coordonnées indiqueront l'ordre du point sur la grille, ces coordonnées ne sont pas liées spécifiquement à la position du point dans l'espace. L'image ci-dessous montre une grille simple montrant les différences de coordonnées d'une position.


Pourquoi les coordonnées?
Le fait est que dans l'unité, pour indiquer la position d'un objet dans l'espace, un flottant simple est très inexact et peut être un nombre fractionnaire ou négatif, il sera donc difficile de l'utiliser pour implémenter une recherche de chemin sur la carte. Les coordonnées sont faites sous la forme d'un int clair qui sera toujours positif et avec lequel il est beaucoup plus facile de travailler lors de la recherche de points voisins.

Tout d'abord, définissons un objet point, ce sera une structure de nœud simple.


Cette structure contiendra la position position sous la forme de Vector2 , où avec cette variable nous dessinerons un point dans l'espace. La variable de coordonnées coords sous la forme de Vector2Int indiquera les coordonnées d'un point sur la carte, et la variable id , son numéro de compte numérique, en l'utilisant, nous comparerons différents points sur la grille et vérifierons l'existence d'un point.

La perméabilité du point sera indiquée sous la forme de sa propriété booléenne , mais comme nous ne pouvons pas utiliser les types de données convertibles dans le système de tâches, nous indiquerons sa perméabilité sous la forme d'un nombre entier , pour cela j'ai utilisé une énumération simple NodeType , où: 0 n'est pas un point passable, et 1 est passable.


De plus, pour la commodité de travailler avec un point, je surchargerai la méthode Equals pour faciliter la comparaison des points et compléter la méthode de vérification de l'existence d'un point.


Étant donné que le numéro d' identification du point sur la grille commencera par 1 unité, je vérifierai l'existence du point comme condition que son identifiant soit supérieur à 0.

Allez dans la classe Map où nous allons tout préparer pour créer une carte.
Nous avons déjà une vérification pour changer les paramètres de la carte, maintenant nous devons déterminer comment le processus de construction de la grille sera exécuté. Pour ce faire, créez une nouvelle variable et plusieurs méthodes.


La propriété de reconstruction indiquera si le processus de maillage est en cours. La méthode Rebuild collectera les données et les tâches pour la construction de la grille, puis la méthode OnRebuildStart démarrera le processus de construction de la grille et la méthode OnRebuildFinish collectera les données des tâches.

Modifions maintenant un peu la méthode UpdateChanges pour que l'état de la grille soit pris en compte.


Comme vous pouvez le voir maintenant dans la méthode UpdateChanges , il y a une condition que lors de la construction de l'ancien maillage ne commence pas à commencer à en créer un nouveau, et également dans la méthode Rebuild , la première action vérifie si le processus de maillage est déjà en cours.

Résolution de problèmes

Maintenant, un peu sur le processus de construction d'une carte.
Comme nous allons utiliser le système de tâches et construire la grille en parallèle pour construire la carte, j'ai utilisé le type de la tâche IJobParallelFor , qui sera exécutée un certain nombre de fois. Afin de ne pas charger le processus de construction avec une seule tâche distincte, nous utiliserons le pool de tâches regroupées dans un JobHandle .

Le plus souvent, pour construire une grille, utilisez deux cycles imbriqués l'un dans l'autre pour construire, par exemple, horizontalement et verticalement. Dans cet exemple, nous allons également construire la grille d'abord horizontalement puis verticalement. Pour ce faire, nous calculons le nombre de points horizontaux et verticaux dans la méthode Reconstruire , puis dans la méthode Reconstruire , nous parcourons le cycle le long des points verticaux, et nous construirons des points horizontaux en parallèle dans la tâche. Pour mieux imaginer le processus de construction, regardez l'animation ci-dessous.


Le nombre de points verticaux indiquera le nombre de tâches, à son tour, chaque tâche ne construira des points que horizontalement, après avoir terminé toutes les tâches, les points sont additionnés dans une liste. C'est pourquoi j'ai besoin d'utiliser une tâche comme IJobParallelFor pour passer horizontalement l'index du point sur la grille dans la méthode Execute .

Et donc nous avons la structure de points, maintenant vous pouvez créer la structure de la tâche Job et l'hériter de l'interface IJobParallelFor , tout est simple ici.


Nous revenons à la méthode de reconstruction de la classe Map , où nous effectuerons les calculs nécessaires pour la mesure de la grille.


Dans la méthode Rebuild , nous calculons la taille exacte de la carte mapSize , en tenant compte de l'indentation, puis dans les verticales nous écrivons le nombre de points verticalement, et en horizontal le nombre de points horizontalement. Si le nombre de points verticaux est égal à 0, nous arrêtons de construire la carte et appelons la méthode OnRebuildFinish pour terminer le processus. La variable d' origine indiquera l'endroit à partir duquel nous commencerons à construire la grille - dans l'exemple, il s'agit du point inférieur gauche sur la carte.

Vous pouvez maintenant accéder aux tâches elles-mêmes et les remplir de données.
Lors de la construction de la grille, la tâche aura besoin d'un tableau NativeArray où nous placerons les points, également puisque nous avons des obstacles sur la carte, nous devrons également les passer à la tâche, pour cela nous utiliserons un autre tableau NativeArray , puis nous aurons besoin de la taille des points dans le problème , la position initiale à partir de laquelle nous allons construire les points, ainsi que les coordonnées initiales de la série.


J'ai marqué le tableau de points avec l'attribut WriteOnly, car dans la tâche, il ne sera nécessaire que d '« écrire » les points reçus dans le tableau, au contraire, le tableau des limites d' obstacles est marqué avec l'attribut ReadOnly car dans la tâche, nous ne « lirons » que les données de ce tableau.

Eh bien, pour l'instant, procédons au calcul des points eux-mêmes plus tard.

Revenons maintenant à la classe Map , où nous désignons toutes les variables impliquées dans les tâches.
Ici, tout d'abord, nous avons besoin d'une poignée de tâche globale, d'un tableau d'obstacles sous la forme d'un tableau natif , d'une liste de tâches qui contiendra tous les points reçus sur la grille et du dictionnaire avec toutes les coordonnées et les points sur la carte, de sorte qu'il serait plus pratique de les rechercher plus tard.


Maintenant, nous revenons à la méthode Rebuild et continuons à construire la grille.
Tout d'abord, initialisez le tableau des limites des obstacles pour le passer à la tâche.


Ici, nous créons une instance de NativeArray via un nouveau constructeur avec trois paramètres. J'ai examiné les deux premiers paramètres dans un article précédent, mais le troisième paramètre nous aidera à gagner un peu de temps en créant un tableau. Le fait est que nous allons écrire des données dans le tableau immédiatement après sa création, ce qui signifie que nous n'avons pas besoin de nous assurer qu'elles sont effacées. Ce paramètre est utile pour NativeArray qui ne sera utilisé qu'en mode lecture dans la tâche.

Et donc, nous remplissons le tableau de limites avec des données.


Nous pouvons maintenant passer à la création de tâches, pour cela nous allons parcourir un cycle à travers toutes les lignes verticales de la grille.


Pour commencer, dans xPos et yPos, nous obtenons la position horizontale initiale de la série.


Ensuite, nous créons un tableau NativeArray simple où les points de la tâche seront placés, ici pour le tableau de tableau, vous devez spécifier le nombre de points qui seront créés horizontalement et le type d'allocation Persistant , car la tâche peut prendre plus d'une image.
Après cela, créez l'instance de tâche Job elle-même, placez les coordonnées initiales de la série startCoords , la position initiale de la série startPos , la taille des points nodeSize , le tableau de limites des obstacles et le tableau de points lui-même à la fin.
Il ne reste plus qu'à mettre la tâche en poignée et la liste globale des tâches.


C'est fait. Nous avons une liste de tâches et leur handle commun, maintenant nous pouvons exécuter ce handle en appelant sa méthode Complete dans la méthode OnRebuildStart .


Étant donné que la variable de reconstruction indiquera que le processus de maillage est en cours, la méthode UpdateChanges elle-même doit également spécifier la condition à laquelle ce processus se terminera à l'aide de handle et de sa propriété IsCompleted .


Après avoir terminé les tâches, la méthode OnRebuildFinish sera appelée où nous rassemblerons déjà les points reçus dans une liste de dictionnaires générale, et surtout, pour effacer les ressources occupées.


Tout d'abord, nous effaçons le dictionnaire de nœuds des points précédents, puis utilisons la boucle foreach pour trier tous les points que nous avons reçus des tâches et les mettons dans le dictionnaire de nœuds , où la clé est les coordonnées ( PAS la position !) Du point, et la valeur est le point lui-même. Avec l'aide de ce dictionnaire, il nous sera plus facile de rechercher des points voisins sur la carte. Après le remplissage, nous effaçons le tableau tableau à l'aide de la méthode Dispose et à la fin, nous effaçons la liste des tâches de travaux elle-même .

Vous devrez également effacer le tableau des limites des obstacles s'il a été créé précédemment.

Après toutes ces actions, nous obtenons une liste de tous les points sur la carte et maintenant vous pouvez les dessiner sur la scène.


Pour ce faire, dans la classe Map , créez la méthode OnDrawGizmos où nous allons dessiner les points.


Maintenant, dans la boucle, nous dessinons chaque point.


Après toutes ces actions, notre carte semble en quelque sorte ennuyeuse, afin d'avoir vraiment une grille, vous avez besoin que les points soient connectés les uns aux autres.


Pour rechercher des points voisins, nous avons juste besoin de trouver le point souhaité par ses coordonnées dans 8 directions, donc dans la classe Map , nous allons créer un simple tableau statique de directions Directions et une méthode de recherche de cellules par ses coordonnées GetNode .


La méthode GetNode renverra un point par coordonnées de la liste des nœuds , mais vous devez le faire avec précaution, car si les coordonnées Vector2Int sont incorrectes, une erreur se produira, nous utilisons donc ici le bloc try bypass exception , qui aidera à contourner l'exception et à ne pas " bloquer " l'application entière avec une erreur.

Ensuite, nous allons parcourir le cycle dans toutes les directions et essayer de trouver des points voisins dans la méthode OnDrawGizmos , et surtout, n'oubliez pas de considérer la perméabilité du point.


Vous pouvez maintenant démarrer le jeu en toute sécurité et voir ce qui s'est passé.


Dans cet exemple, nous avons construit uniquement le graphique lui-même à l'aide de tâches, mais c'est ce qui s'est produit après avoir vissé sur le système l'algorithme A * lui - même , qui utilise également le système Job pour trouver le chemin, la source à la fin de l'article .


Vous pouvez donc utiliser le nouveau système de tâches pour vos objectifs et créer des systèmes intéressants sans trop d'effort.

Comme dans l'article précédent, le système de tâches est utilisé sans ECS , mais si vous utilisez ce système en conjonction avec ECS , vous pouvez obtenir des résultats tout simplement incroyables en termes de gains de performances. Bonne chance !

Source du projet Path Finder