Planification de patrouille de territoire

Je développe un jeu / simulation où les agents se battent pour la terre. J'ai la situation montrée dans l'image ci-dessous:

Ces créatures se promènent et occupent des parcelles de terrain sur lesquelles elles marchent si elles sont libres. Pour rendre cela plus intéressant, je veux introduire un comportement de "patrouille", de sorte que les agents se promènent réellement sur leur territoire pour patrouiller contre tout intrus qui voudrait le prendre.

Côté technique, chaque carré est représenté comme une x,yposition ainsi qu'une dimension représentant sa longueur latérale. Il contient également des informations sur qui occupe la place. Tous les carrés sont stockés dans un ArrayList.

Comment puis-je introduire un comportement de patrouille? Ce que je veux, c'est que chaque agent patrouille une certaine partie de la zone (ils se divisent entre eux les zones qu'ils vont patrouiller). Le principal problème que j'ai trouvé est le suivant:

• La superficie du terrain est très aléatoire, comme on le voit sur la photo. Il est assez difficile de comprendre où se situent les limites dans chaque direction.
• Comment les agents devraient-ils répartir les régions pour patrouiller?
• Les zones de terrain peuvent être disjointes, puisque l'équipe adverse peut prendre le territoire du milieu.

J'ai eu l'idée de prendre le carré le plus éloigné dans chaque direction, de les traiter comme les limites de la zone et de diviser les régions en fonction de ces limites, mais cela pourrait inclure beaucoup de terres non pertinentes.

Comment dois-je aborder ce problème?

Question fascinante. Je pense que l'un des premiers problèmes que vous devez résoudre est de savoir si vous voulez que le comportement de patrouille soit une patrouille «optimale» ou une patrouille «réaliste». Je fais juste ces mots, mais ce que je veux dire c'est:

Optimum : Les agents se déplacent d'une manière qui répartit parfaitement leur zone de couverture pour le système dans son ensemble.

Réaliste : Les agents se déplacent et tentent de se répartir le plus équitablement possible, mais chacun n'a accès qu'aux données locales selon son point de vue.

Je vais me concentrer sur la deuxième approche, que je pense que vous pouvez résoudre en utilisant un mélange pondéré de divers modèles de direction à partir des comportements de direction de Craig Reynolds pour les personnages autonomes . L'idée de base des comportements de pilotage est d'utiliser des forces simples qui se combinent pour produire une navigation improvisée autour d'un environnement. Dans votre cas, je pense que vous voudriez combiner les comportements de pilotage suivants:

• Évitement (hors territoire) - Les agents tentent de rester sur leur territoire et évitent de se déplacer à l'extérieur de celui-ci. Pour certains réalisme cependant, l'influence de «sortir du territoire» n'a pas besoin d'être à 100% ici. Un peu de "coins coupés" pour sortir de la zone rendrait probablement le mouvement plus réaliste.

• Errant - Les agents essaient de continuer à se déplacer et à explorer. Celui-ci, vous allez vouloir peser lourdement sinon les agents vont essayer de trouver un point de séparation optimal les uns des autres et ensuite "rester sur place".

• Séparation (autres agents) - Les agents tentent de garder une distance par rapport aux autres agents (afin qu'ils couvrent le maximum de terrain et ne se regroupent pas).

• Recherche (envahisseurs) - Les agents tentent de se rapprocher des envahisseurs qu'ils détectent.

Je pense que vous voudriez jouer avec la pondération relative de manière dynamique. Par exemple, si un agent détecte un envahisseur, la pondération de séparation doit baisser. (En d'autres termes, ils n'ont qu'à s'étaler lorsqu'ils chassent, pas lorsqu'ils trouvent quelqu'un.) Je pense que si vous jouiez avec les poids des quatre modèles ci-dessus, vous auriez quelque chose d'assez proche de ce que vous '' re cherche.

Il existe de nombreuses ressources en ligne sur la façon d'implémenter des "boids" qui suivent les modèles de comportement décrits. Je recommande l'implémentation open-source opensteer .

Une approche consiste à enregistrer, pour chaque cellule, quand elle a été visitée pour la dernière fois par un "gardien", et à faire en sorte que les gardes se déplacent continuellement vers la cellule voisine qui a été la plus longtemps non visitée.

Bien sûr, cela suppose que le territoire est connecté.

Ce n'est pas une solution parfaite, mais facile à coder, adaptable aux circonstances changeantes et efficace. J'ai utilisé avec succès cet algorithme pour les attaques de dépistage et de harcèlement dans un rts ai que j'ai écrit il y a quelque temps.