Comment construire une «AI du trafic»?

Un projet sur lequel je travaille en ce moment présente beaucoup de "trafic" dans le sens de voitures se déplaçant le long des routes, d'avions se déplaçant autour d'un tablier, etc.

Désormais, les chemins disponibles sont précalculés, de sorte que les nœuds sont générés automatiquement pour les croisements qui sont eux-mêmes interconnectés par des arêtes. Lorsqu'un personnage / agent apparaît dans le monde, il commence à un nœud et trouve un chemin vers un nœud cible au moyen d'un algorithme simplement A *. L'agent suit le chemin et atteint finalement sa destination. Aucun problème jusqu'ici.

Maintenant, je dois permettre aux agents d'éviter les collisions et de gérer les situations de trafic complexes. Depuis que je suis nouveau dans le domaine de l'IA, j'ai recherché plusieurs articles / articles sur le comportement de pilotage, mais je les ai trouvés trop bas. Mon problème consiste moins à éviter réellement les collisions (ce qui est assez simple dans ce cas parce que les agents suivent des chemins strictement définis) mais à des situations comme un agent sortant d'une impasse tandis qu'un autre veut entrer exactement le même. Ou deux agents se rencontrant à un goulot d'étranglement qui permet à un seul agent de passer à la fois mais tous les deux doivent le passer (selon l'itinéraire optimal trouvé auparavant) et ils doivent trouver un moyen de laisser l'autre passer en premier. Donc, fondamentalement, l'aspect principal du problème serait de prévoir le mouvement du trafic pour éviter les blocages.

Difficile à décrire, mais je suppose que vous comprenez ce que je veux dire. Avez-vous des recommandations à me faire pour commencer à chercher? Des articles, des exemples de projets ou des choses similaires qui pourraient me permettre de démarrer?

J'apprécie ton aide!

Il y a tellement de façons de résoudre ce problème que j'aurais du mal à donner ici une réponse décente et complète. Mais voici quelques points de conception de haut niveau.

• Vous créez ici une simulation d'agent. La recherche de chemin n'est qu'une entrée dans le système - l'agent a un objectif et la recherche de chemin n'est qu'un moyen pour atteindre cet objectif. En fait, en y réfléchissant en termes réels, l'agent a deux objectifs: le premier objectif d'un conducteur est de "ne pas tomber en panne", ensuite "d'arriver là où je veux aller".

• Vos systèmes devraient s'appuyer sur des parallèles réels. La raison pour laquelle la plupart des routes ont deux voies ou plus est qu'il est beaucoup plus facile d'organiser la circulation avec ce système, personne ne doit y penser beaucoup. Dans un scénario à voie unique, les conducteurs doivent régler divers problèmes:

  détection - reconnaissant que vous et la voiture venant en sens inverse tomberont en panne à moins que vous vous évitiez

  réaction - ralentissement et entrée dans une phase de négociation.

  négociation - l'un des moteurs doit prendre les devants, l'autre doit céder. Les règles sur la façon de décider de cela sont vagues, mais fondamentalement, vous voulez quelque chose où un conducteur arbitrairement (ou basé sur une heuristique sur le nombre de voitures venant dans l'autre sens) décide de prendre la priorité. Par exemple, A est prioritaire au temps 1, B voit A prendre la priorité et cède (en s'éloignant et en s'arrêtant). Si A et B tentent tous les deux de prendre la priorité, ils doivent tous les deux s'arrêter, attendre un certain temps (ou se signaler) et réessayer. Finalement, l'un cédera à l'autre.

  La beauté de cette implémentation est qu'elle évite la nécessité de maintenir des files d'attente artificielles ou d'autres fausses constructions. La négociation se fait en termes de perceptions du monde réel - une fois que les deux parties sont dans la phase de négociation, toute avancée significative est facilement détectée comme une tentative de priorité. Il devrait également réagir de manière appropriée à l'utilisateur, qui ne respectera probablement pas les bonnes règles de conduite.

• Supposons le pire. Même dans un système parfait, des situations étranges peuvent survenir et vos acteurs doivent agir de manière sensée. Cela est encore plus probable si le joueur peut interférer (bloquer artificiellement des zones, etc.). Souvent, l'arrêt total est la seule réponse sensée (blocage!). Un arrêt total est au moins plausible en termes réels.

  Plus vous modélisez l'IA de votre acteur sur une logique simple du monde réel, plus il sera facile de créer une IA convaincante. Les vraies personnes ne s'arrêtent pas ni n'oscillent d'avant en arrière si elles ne peuvent pas atteindre leur objectif. Si la seule route vers la destination de l'IA est bloquée, ils devraient reconnaître cela et choisir une réponse (arrêtez-vous tout à fait, abandonnez et rentrez chez vous, abandonnez et conduisez ailleurs).

• Comportez les comportements pour obtenir ce que vous voulez. N'oubliez pas que le premier objectif n'est pas de planter. La logique d'évitement (direction) doit donc toujours dominer les actions du conducteur. Couchez en plus de cela la logique directionnelle qui provient de la recherche de chemin ('Je veux prendre à droite à la prochaine jonction'). Couche au-dessus de cette réévaluation occasionnelle des chemins, avec une logique de niveau supérieur («préférez aller de l'avant, mais si je ne peux pas progresser, autorisez un nouveau chemin qui implique un demi-tour»).

• La recherche de chemin provient de la mémoire, mais la conscience de la situation est basée sur la perception. N'essayez pas de rendre vos agents parfaits. Ils connaissent le chemin de leur domicile au bureau, donc ils savent quel virage faire. Mais ils ne savent pas que la rue à 3 km est bloquée. N'essayez pas de faire tracer un chemin parfait à vos agents, car il n'y en a pas - même s'il commence parfait, d'autres facteurs peuvent bloquer leur chemin. Les agents ne doivent planifier que quelques rues à l'avance où ils vont.

• Qualité de l'information. Vos comportements doivent être simples, mais pour y parvenir, vous avez besoin d'une bonne fonctionnalité de requête. Vous devez être en mesure de poser des questions sur votre environnement comme "est-ce que la voiture venant en sens inverse occupe ma voie?", "Combien de voitures arrivent?", "Y a-t-il des voitures derrière moi", "puis-je faire demi-tour" .

Après avoir vu d'horribles échecs dans les jeux sortis, j'ai quelques suggestions:

1) À moins qu'il n'y ait une bonne raison, faites deux voies et, à des fins d'intelligence artificielle, donnez-leur la priorité pour une direction d'écoulement normale - autorisez une circulation à deux vitesses, mais si quelque chose vient de l'autre côté, le gars du mauvais côté de la route est toujours cède.

2) Une sorte de logique pour dérouler un embouteillage s'il se produit. J'ai observé des situations où la gestion des embouteillages ne s'appliquait qu'aux véhicules qui essayaient de se croiser, mais échouait complètement face à un schéma -> -> <- <-. Je me souviens d'une carte qui était sujette à cela - c'était un point d'étranglement destiné à rendre la base de l'IA plus difficile à attaquer, mais tôt ou tard deux moissonneurs de ressources entreraient pendant qu'un groupe d'attaque se dirigeait et c'était tout. Les unités en contact tournaient autour pour essayer de trouver une route mais elles n'avaient aucun mouvement légal. Il n'a pas fait marche arrière et n'a pas compris qu'une autre unité devait d'abord se déplacer, et donc l'IA n'a pris aucune mesure utile jusqu'à ce que le barrage routier soit supprimé. (Vous pourriez regarder les unités en contact tourner et rien d'autre ne faire quoi que ce soit.)

Je crois que cela pourrait être résolu en obligeant une unité bloquée à dire aux unités voisines de s'écarter - cela se propagerait jusqu'à ce qu'elle atteigne une unité non bloquée qui pourrait reculer. Cela devrait impliquer une sorte de logique pour les éloigner jusqu'à ce que le problème soit résolu.

Notez que la simple recherche d'un chemin alternatif est souvent une mauvaise réponse. J'ai observé une situation de vivelock de ce type - l'unité A note que B bloque la route et qu'elle se retourne pour emprunter un itinéraire différent. Cela bloque maintenant la route pour B qui se retourne - maintenant la route est débloquée, donc les deux se retournent à nouveau. À chaque tour, ils alternent entre avancer et reculer.

Le même jeu, j'en ai vu une version différente, également à cause du brouillard de guerre. Il y avait une unité ennemie à un point d'étranglement. En mouvement automatique, la recherche de chemin ne combattrait que si elle était ciblée sur l'unité ennemie. Il avancerait et verrait la route bloquée. Il a ensuite reculé, il ne pouvait plus voir le bloqueur et il allait de nouveau avancer. Répétez jusqu'à ce que l'humain se rende compte qu'il n'ira pas là où il était censé aller.

Je ne suis pas trop expérimenté avec les simulations de trafic, mais quelques choses me viennent à l'esprit.

Premièrement, pour éviter les goulets d'étranglement, j'aurais d'abord deux voies qui permettent aux véhicules de se déplacer dans des directions opposées. sur la même "route".

Deuxièmement, pour les collisions qui peuvent se produire, vous devriez avoir un comportement de direction anti-collision pour éviter un amoncellement massif. Les comportements de pilotage peuvent être de bas niveau, mais ils sont très utiles pour créer un comportement émergent d'apparence réaliste.

Si vous ne voulez pas avoir plus d'une voie, vous devrez stocker plus d'informations dans le graphique. Par exemple, si l'agent A est sur une route (représentée comme un bord de graphique) et que l'agent B est sur la même route se déplaçant dans la direction opposée à A, alors ils entreront en collision / bloqueront / tout ce que vous aurez codé pour faire face à ce comportement.

Cependant, si l'agent A est sur une route, il pourrait demander la propriété de cette route. Posséder la route signifierait qu'aucun autre agent ne peut voyager le long de ce bord (vous pouvez le faire tout simplement en changeant le coût du bord en un nombre massif pour vous assurer qu'A * ne choisit pas la route lors du calcul d'un chemin). Ensuite, lorsque l'agent A est libre de cette route, il abandonne la propriété.

Honnêtement, c'est une solution hacky que je n'aime pas particulièrement et la plupart des simulations de trafic (sinon toutes?) Que j'ai vues utiliser une approche à plusieurs voies.

Vous avez dit que vous avez consulté plusieurs articles sur le comportement de direction, mais juste au cas où, avez-vous consulté le suivant?

http://www.red3d.com/cwr/steer/

Sinon, il peut vous fournir des réponses, car il couvre certains des problèmes que vous avez nommés, par exemple le problème des goulots d'étranglement (file d'attente).

Je pense que ce que vous devez faire est d'implémenter un algorithme de recherche de chemin.

Décomposez votre carte en morceaux aussi petits que possible (par exemple des carrés), mais uniquement pour les endroits valides pour le trafic. Vous pourriez alors déterminer où se trouve le véhicule et où il va et trouver un chemin, le plus court ou le plus direct peut-être. Le chemin sera un tableau de carrés, chaque étape du chemin vers la destimation. Ce que vous voudriez alors est de calculer non seulement la position actuelle de tous les véhicules, mais aussi les positions futures des véhicules pour quelques étapes à l'avenir. Si deux véhicules doivent être dans le même carré à l'avenir, vous devez modifier la vitesse de l'un ou des deux.

A * (Une étoile) est un algorithme de recherche de chemin très simple que vous pouvez probablement traduire facilement le code pseudo dans wikipedia dans la langue de votre choix et cela fonctionnera: http://en.wikipedia.org/wiki/A*_search_algorithm

Lorsque j'ai implémenté Enemy Nations, mon dernier repli était que si un véhicule était coincé pendant plus de 2 secondes, je le sautais en avant sur son chemin. Donc, quand ils se sont retrouvés coincés, une unité a été transportée. Personne ne s'est jamais plaint, alors je pense que les rares fois où cela s'est produit, personne ne l'a regardé et ne l'a pas vu.