Bienvenue dans l'équipe Graceful Algorithms!
À titre expérimental, nous avons décidé de tenir des «journaux» des développeurs dans lesquels nous partagerons notre expérience et soulignerons les résultats intéressants de nos expériences. Voici notre premier article sur le projet "Pathfinder 3D" - un atout pour le moteur de jeu Unity, qui vous permet de rechercher des chemins dans un espace tridimensionnel. Dans ce document, nous parlerons du chemin de l'origine de l'idée à un produit à part entière et de certains des problèmes que nous avons rencontrés. Ce matériel sera utile pour les personnes qui souhaitent démarrer leur projet et le soutenir à l'avenir, ainsi que pour celles qui souhaitent mettre en œuvre une recherche de chemin dans l'espace.
Une équipe de deux personnes a commencé à travailler sur l'actif. Le premier avait quelques développements permettant d'accélérer le processus de recherche du chemin le plus court sur des graphiques complexes suffisamment pour travailler en temps réel, et un désir de trouver une application pratique pour eux, le second avait une certaine expérience de travail avec Unity et cherchait une idée pour une startup. Puisqu'ils communiquaient souvent entre eux, il n'est pas surprenant qu'à un moment donné l'idée soit venue de la possibilité de créer un atout pour rechercher un chemin dans un espace tridimensionnel.
Lors de l'étude du catalogue d'actifs Unity, de nombreuses solutions ont été trouvées pour trouver le chemin dans l'espace bidimensionnel, mais pas un en trois dimensions. Il est devenu évident que c'était une excellente occasion d'entrer sur le marché des modules complémentaires de logiciels Unity, en particulier compte tenu de la visibilité et du divertissement du résultat attendu.
L'objectif était de mettre en œuvre directement la recherche d'un chemin dans un espace tridimensionnel et les capacités typiques des solutions existantes pour trouver un chemin dans un espace bidimensionnel. Nous avons commencé à travailler: l'un a développé directement le mécanisme de recherche de chemin, les deuxièmes classes et méthodes de gestion du processus de recherche de chemin, les interfaces de configuration, les scènes de test, la documentation, le site du projet, et a également été impliqué dans l'enregistrement et la configuration des comptes de service nécessaires à la vente de l'actif.
Peu de temps après le début des travaux, il est devenu clair qu'une sorte de ressource commune était nécessaire pour que l'équipe prenne des notes: une liste des tâches et des problèmes à résoudre, des informations sur les décisions prises, des idées intéressantes et des résultats de recherche à l'avenir. Après avoir analysé les solutions existantes, nous nous sommes arrêtés chez
Trello , pour sa fonctionnalité, sa simplicité, sa commodité et son aspect agréable. Comme la pratique l'a montré, ce service est très pratique pour les petites équipes. Si l'équipe compte plus de 5 personnes, nous vous recommandons d'utiliser un système de gestion de projet à part entière.
Ensuite, nous décrivons les décisions prises lors du développement de la première version de l'actif, et la logique que nous avons suivie lors de leur prise. Les personnes qui ont une expérience avec Unity et qui connaissent les algorithmes de recherche de chemin comprendront immédiatement où les problèmes se poseront à l'avenir. Dans ces endroits, nous avons utilisé une solution simple dans le but de réduire le temps de développement jusqu'à la réception de la première version de travail de l'actif, afin de ne pas s'enliser, car l'enthousiasme est limité et inconstant. Ainsi, nous avons traité l'une des raisons les plus courantes de la fermeture de telles startups, à cause de laquelle de nombreux projets meurent sans être nés. Tous les domaines problématiques ont été corrigés après la publication de l'actif.
Pour trouver le chemin, l'algorithme
A * (A star) a été choisi en raison de sa vitesse de fonctionnement élevée dans les grands espaces ouverts. La plupart des algorithmes de recherche de chemin fonctionnent sur des graphiques représentés par une matrice discrète. Il serait possible de construire cette matrice à l'avance, mais le processus ponctuel de sa construction dans un espace tridimensionnel avec des obstacles considérait cette époque comme une tâche plutôt difficile. En outre, il n'était pas clair comment procéder sans sacrifier les performances, car au moment du début des travaux sur l'actif, il n'y avait aucune expérience des processus d'arrière-plan et du multithreading dans Unity, ainsi que du multithreading en général. Le graphique a été formé en temps réel en sondant l'espace avec des rayons physiques (Physics.BoxCast) dans le sens de la recherche. Les trajectoires trouvées ont été réduites à des trajectoires brisées avec moins de points intermédiaires, puis lissées par des splines.
La principale difficulté était l'impossibilité d'utiliser les méthodes physiques du moteur de manière asynchrone, car elles peuvent fonctionner exclusivement dans le thread principal. Sur des scènes pas trop complexes, l'utilisation simultanée de la fonction de recherche par pas plus de vingt agents n'a pas significativement affecté la fréquence d'images. Pour se débarrasser des rares forts rabattements de FPS, la charge de calcul a été espacée dans le temps à l'aide de coroutines. Cela a ralenti la recherche, mais pas de manière significative.
Avant de soumettre un actif pour modération, vous devez mettre le code en ordre et rédiger une documentation détaillée, conformément aux
exigences , enregistrer et configurer le support mail. Il est également conseillé de créer un site Web de projet où les nouvelles de développement et les démos seront affichées de manière pratique. Ce sera un gros plus à la fois lors du passage de la modération, et lors de l'étude de votre bien par l'utilisateur avant de l'acheter. Les services d'hébergement et de courrier ont été commandés par nous auprès de
BeGet , car à cette époque, il offrait les offres les plus avantageuses et nous coûtait 1000r / an.
La modération des actifs a duré 22 jours et s'est écoulée la première fois, car nous avons abordé très attentivement la documentation et la conception de la page des actifs dans la boutique Unity. Après la publication, l'actif est immédiatement devenu la première place dans la catégorie Scripting / AI. À partir de ce moment, des lettres ont commencé à parvenir au courrier d'assistance pour demander de l'aide pour résoudre certains problèmes. Parfois quelques-uns par jour, parfois pas un mois. Si vous êtes en moyenne, alors pendant un mois, 2 personnes ont posé des questions, dont la correspondance a pris au total 2-3 heures. Pas tellement, mais il faut garder à l'esprit que quelle que soit votre charge de travail actuelle, vous devez répondre très rapidement afin que les utilisateurs en colère n'écrivent pas de mauvaises critiques sur le produit, mais, au contraire, enthousiastes à propos d'un support de qualité, laissent des commentaires positifs. De plus, un grand nombre de questions sont envoyées par la poste, comme «votre atout fonctionnera-t-il si ...». Ces lettres ne doivent pas non plus être ignorées, car il s'agit d'un acheteur potentiel qui peut partir.
Au fur et à mesure que des plaintes des premiers acheteurs ont été reçues, il est devenu clair que de nombreux utilisateurs utilisent des actifs sur des scènes complexes qui ont la configuration d'un labyrinthe ou d'une autre cavité connectée. Dans de tels projets, notre système de recherche de chemin, basé sur la vérification des collisions, et même dans le flux principal, n'était pas suffisamment efficace. Par conséquent, nous avons commencé à mettre en œuvre la première construction du graphique afin qu'il soit possible de rechercher le chemin dans le flux latéral sans utiliser la physique et sans accéder aux objets de la scène.
La discrétisation de l'espace tridimensionnel le décompose en cubes. Le stockage des informations sur tous les cubes de partition est redondant et très gourmand en mémoire. Par conséquent, il est logique de ne stocker que les coordonnées des cellules infranchissables, ce qui a été fait.
Les obstacles du jeu sont des figures polygonales et se composent de triangles. Pour tenir compte des obstacles dans le graphique de recherche, vous devez trouver tous les cubes de la partition qui coupent n'importe quel triangle de n'importe quel obstacle. Déjà à ce stade, la possibilité de supprimer et d'ajouter dynamiquement des obstacles à la scène était prévue, et non seulement les coordonnées des cubes occupés étaient enregistrées, mais aussi les identifiants des obstacles qui s'y trouvaient. Il est maintenant possible de construire un graphique de navigation avant le début du processus de jeu et, en raison de l'élimination d'un grand nombre de calculs complexes lors de la recherche d'un chemin, plus de deux cents agents pourraient le faire simultanément sans sacrifier les performances.
Un autre problème que nous connaissons s'est également fait sentir: l'algorithme A * et ses modifications fonctionnent extrêmement mal dans des espaces confinés sur des graphes de forte puissance. Étant donné que leur algorithme préfère la direction de l'itinéraire vers l'approche du point cible, tout blocage menant à la cible ralentit considérablement la recherche d'un chemin, car avant de choisir une direction différente de «germination», l'algorithme «remplit» d'abord tout l'espace à l'intérieur de l'impasse.
Dans de telles situations, l'
algorithme de recherche d'ondes (Lee Algorithm) s'avère très efficace en raison du
plus petit nombre d'opérations nécessaires pour «remplir» l'espace. Par conséquent, il a été ajouté à l'actif comme alternative. Lors des tests sur une scène qui est un labyrinthe, le temps de recherche du chemin a été réduit de plus de 30 fois.
Pour accélérer le traitement préliminaire de la scène et trouver le chemin vers l'actif, la possibilité d'exécution parallèle des processus a été ajoutée, mais l'efficacité du parallélisme était extrêmement faible, car lorsque vous travaillez avec un conteneur qui stocke les coordonnées des cellules occupées, il est nécessaire de synchroniser les flux, ce qui a été effectué à l'aide de mutexes, car les collections compétitives et de nombreux autres outils pour assurer une synchronisation efficace
ont été implémentés uniquement dans la norme .NET Framework 4.5, et dans Unity, la version .NE a été utilisée jusqu'à la version 2018. Cadre T 3.5. Nous avons essayé de résoudre ce problème en utilisant les outils disponibles, mais ils avaient des performances très médiocres, et nous n'avons obtenu le résultat souhaité qu'après le passage à la version 2018 de Unity. L'utilisation de collections compétitives a également ouvert la possibilité de réaliser le changement dynamique des obstacles dans la scène.
À un certain stade, des désaccords ont commencé à surgir dans l'équipe concernant la répartition des bénéfices, et une troisième personne a rejoint l'équipe, qui a introduit un système d'évaluation du temps investi par chaque membre de l'équipe, et a également commencé à procéder à l'inspection et aux tests du code, ce qui a considérablement amélioré la qualité du produit.
Le système d'estimation des coûts de temps pour le moment se présente sous la forme d'un tableau Excel et est un système automatisé dans lequel une fois par mois, il est nécessaire d'entrer des informations sur les ventes et les tâches terminées au cours du mois dernier. Les membres de l'équipe doivent évaluer le temps dont ils auraient besoin pour résoudre un problème particulier. Ainsi, lors de l'évaluation de la complexité temporelle des tâches, la vitesse de chaque participant est prise en compte. Une surestimation anormale ou une sous-estimation par l'un des participants devient immédiatement évidente à partir des statistiques accumulées de ses évaluations précédentes. Et, en l'absence d'explication satisfaisante, cette question est tranchée par toute l'équipe. Cette approche s'est avérée bonne pendant six mois d'utilisation et a permis de collecter des statistiques intéressantes. Nous n'avons pas trouvé de solution gratuite prête à l'emploi qui fournirait les fonctionnalités décrites. Par conséquent, pour le moment, pour les petites équipes, l'implémentation sous forme de tableaux Excel nous semble optimale. Pour les équipes relativement importantes, vous devrez très probablement concevoir votre base de données, développer la partie serveur et le client, ou implémenter une extension pour l'un des systèmes de gestion de projet existants.
Pour résumer. Un an s'est écoulé depuis le début du développement de la première version avec le minimum de fonctionnalités nécessaires et des performances suffisantes pour une utilisation dans des projets réels. Six mois supplémentaires ont été consacrés à l'amélioration des performances et à la mise en œuvre du travail multithread de l'actif. À l'heure actuelle, nous avons estimé les coûts de temps pour ce projet à 1065 heures-homme (il s'agit d'une estimation plutôt optimiste), et le bénéfice moyen pour le mois est de 9,5 t. Il est facile de calculer que le coût moyen d'une heure de travail en ce moment est d'environ 160 roubles, ce qui n'est pas tellement. Cependant, l'essentiel de cet événement est l'expérience acquise par chaque participant. Y compris une expérience de travail d'équipe et une expérience de support de produits logiciels. Le projet peut être considéré comme réussi.
Maintenant, notre équipe a commencé à mettre en œuvre des fonctionnalités utiles supplémentaires: vérification algorithmique de l'accessibilité; la possibilité d'assigner des objets de jeu à des portails; support d'obstacles dynamiques; Navigation locale entre les agents pour éviter les collisions et planifier les itinéraires locaux.
Nous espérons que ce matériel aidera quelqu'un à mener son projet à son terme.