Je suis un débutant absolu dans le développement de jeux et tout ce que je sais sur l'évitement / résolution des collisions, je l'ai appris sur ou via ce site la semaine dernière ... alors n'hésitez pas à me corriger si ce que je demande ici est basé sur de fausses hypothèses / malentendus. J'ai fait de mon mieux pour être clair, mais cela dit, le sujet est encore nouveau pour moi.
Véhicules
Dans mon jeu, j'ai des véhicules qui se déplacent de manière autonome. Ils sont placés dans un espace 3D et leur mouvement est régi par un certain nombre de variables différentes pour chaque véhicule. Ceux qui nous intéressent ici sont principalement:
- Seulement mouvement vers l' avant .
- Une vitesse qui peut varier entre min et max, mais dont le min n'est pas (même proche de) zéro.
- Un rayon de braquage qui dépend de la vitesse (plus la vitesse est élevée, plus le rayon est grand)
- Deux accélérations maximales (pour diminuer et augmenter la vitesse)
Objectif
Mon objectif est de mettre en œuvre une sorte d'IA qui permettra une évitement de collision 100% précis (c'est-à-dire que je serai sûr que les véhicules n'entreront jamais en collision).
Conception
- Bien que je préfère davantage l'idée d'avoir l'IA "à bord" (c'est-à-dire que chaque véhicule possède sa propre "AI anti-collision", éventuellement en interrogeant et / ou en envoyant des messages à d'autres véhicules), il est également possible pour moi d'implémenter l'IA CA à un niveau central (envoi des commandes aux véhicules).
- Dans la plupart des cas, le véhicule devra simplement s'écarter les uns des autres dans toutes les directions, mais dans certaines circonstances, il devra éviter les collisions et se diriger vers la même cible
Ce que j'ai trouvé jusqu'à présent et où je suis resté coincé
Parmi les nombreux liens que j'ai trouvés dans d'autres questions sur ce site, j'ai trouvé particulièrement utiles ceux-ci:
Bien que ces trois liens "m'ont ouvert les yeux" de bien des manières, il n'est pas immédiatement clair pour moi comment utiliser ces informations dans mon cas. En particulier, l'article # 2 "essaie" de prévenir les collisions (mais les collisions se produisent de temps en temps). Alors que l'article # 3 doit parfois arrêter des véhicules pour éviter les collisions.
Ce que j'ai également remarqué, c'est que les algorithmes d'évitement de collision liés ci-dessus utilisent une "projection instantanée" de la vitesse linéaire pour vérifier si quelque chose se trouve sur le chemin du véhicule. Je me demandais si cela suffisait dans mon cas ou si je devais projeter ma position de manière plus réaliste (par exemple: si je suis à 60 ° dans une direction à 90 ° vers la droite, je devrais calculer ma position pour le reste de la 30 ° de la courbe, puis en supposant un mouvement linéaire).
Enfin, j'ai particulièrement peur des impasses . En d'autres termes: bien que la densité de véhicules dans le monde soit assez faible, je crains qu'étant donné un certain nombre de véhicules convergeant vers le même point, une fois qu'ils se rendront compte qu'ils sont sur une trajectoire de collision, toute manœuvre d'évitement sera impossible car cela amènerait le véhicule sur une trajectoire de collision avec d'autres.
Question
Comment puis-je atteindre mon "objectif"? Une explication approfondie est bien sûr très appréciée, mais les liens vers des ressources externes seraient également d'une grande utilité (je suis sûr que je ne suis pas le premier à résoudre ce problème, mais j'ai probablement utilisé les mauvais mots clés pour rechercher sur le Web? )
Merci d'avance pour votre aide!
Réponses:
Avez-vous étudié les algorithmes de flocage ? Quand je regarde votre description, c'est ce qui me vient à l'esprit. Il y a beaucoup d'articles à ce sujet, en voici un que j'aime . Vous n'utiliserez probablement pas tous les aspects du flocage, comme la cohésion. La plupart des aspects seraient utiles pour ce que vous essayez de faire, comme l'alignement et la séparation, qui aideraient à éviter les collisions. Vous vous retrouveriez avec quelque chose d'un peu différent du flocage, mais cela devrait vous aider à démarrer.
Bonne chance!
la source
Voici une approche: chaque véhicule a une courte trajectoire projetée où le véhicule à la fin ralentit et entre dans une boucle, ces trajectoires ne peuvent pas se chevaucher. Chaque fois qu'un véhicule arrive au point de ralentir, vous essayez de générer un nouveau chemin qui ne chevauche aucun de ceux existants. Si cela n'est pas possible, le véhicule continue sur sa trajectoire donnée et réessaye périodiquement de créer une nouvelle trajectoire.
La méthode pourrait être améliorée pour permettre un trafic plus serré en laissant les chemins menant à des boucles se chevaucher et des boucles où il peut être déterminé que cela ne provoquera pas de collision.
la source
Avoir une méthode dans chaque véhicule où il effectue une recherche radiale autour de lui, s'il y a d'autres véhicules dans ce rayon, éloignez-vous d'une manière qui vous convient: 1) Déplacez-vous dans le vecteur opposé, 2) ralentissez, 3) accélérer, etc.
Vous pouvez même faire des combinaisons: Si le vecteur de l'autre véhicule n'est pas droit devant ou directement derrière: éloignez-vous; sinon si c'est droit: ralentir; sinon: accélérer.
la source
Si cela avait été possible, il aurait déjà été installé dans tous les avions du monde.
Je suggère de détendre l'aspect «autonome» et d'avoir une fonction qui résout les collisions prévues entre 2 (ou plus) véhicules. Cela peut être aussi naïf que de choisir de nouvelles directions aléatoires pour voyager et voir si cela résout le problème, mais l'important est que la fonction ne revient que lorsqu'elle est parvenue à un accord qui convient aux deux véhicules.
Je suggère également que tout véhicule qui devrait entrer en collision dans un avenir proche réduit sa vitesse tout en conservant la même distance de vision d'avance - cela donnera à vos véhicules plus de possibilités d'éviter les collisions, tout comme dans la vie réelle.
la source
Il me semble que la simulation de foule pourrait être le sujet le plus pertinent pour ce que vous essayez de réaliser. Le groupe GAMMA de l'UNC dispose d'un vaste corpus de travaux sur le sujet qui mérite d'être examiné. Leur description:
http://gamma.cs.unc.edu/research/crowds/
la source
Je ne pense pas qu'il existe une méthode d'évitement à 100%, mais si vos véhicules possèdent des informations complètes sur le monde, vous pouvez enfermer chaque véhicule dans une boîte dont la longueur dépend de sa vitesse et effectuer un contrôle de collision sur ces boîtes. S'il y a bien une collision, éloignez-vous, avec une force en fonction de l'imminence de l'impact (ou de la zone de la collision entre les deux caisses), et ralentissez le Dow (mais gardez votre caisson de la même longueur lors de l'opération d'évitement).
Évidemment, cela ne fonctionnera pas si le véhicule ne possède pas d'informations complètes, mais dans ce cas, rien ne garantira un évitement de 100% (sauf, comme déjà dit, le mouvement parallèle)
certaines méthodes décrites ici seraient probablement utiles, notamment celle-ci: Comportement de direction pour éviter les collisions non alignées
Cordialement
la source