Conscience de la situation dans la recherche de chemin

Supposons que vous deviez trouver le chemin le plus court à travers un donjon, où certains passages ne vous sont ouverts qu'après la collecte de certains objets, comme des portes et des clés verrouillées, par exemple.

La réaction intestinale normale aux mots "chemin le plus court" serait évidemment A *. Mais A * échouerait dans un tel environnement, car je vois de nombreux problèmes pour définir une heuristique fiable et, en outre, il est très probable qu'un nœud doit être visité plusieurs fois, ce qui n'est également pas possible dans A * conventionnel et serait également rendre l'heuristique plus difficile.

Ce à quoi j'ai pensé, c'est simplement chercher un chemin du début du donjon à la fin, en ignorant toutes les portes bloquées. Après que ce chemin soit trouvé, pour chacune des portes bloquant notre chemin, un chemin supplémentaire recherchant la clé appropriée et revenant à la porte serait recherché et traversé avant même que la porte ne soit atteinte. Le même système serait utilisé pour gérer une situation où le chemin d'accès à une clé nécessaire pour ouvrir une porte est à nouveau bloqué par une autre porte, qui doit être ouverte en premier.

Un gros problème que je vois avec ma solution est qu'après avoir trouvé tous les chemins, y compris ceux pour l'acquisition d'objets, la distance totale parcourue par l'agent peut ne pas être la plus petite possible, car il peut y avoir d'autres portes bloquées plus éloignées de l'objectif mais ont leur clé appropriée beaucoup plus facilement disponible. A * aurait négligé ces portes lors du premier passage où les portes bloquées sont simplement ignorées.

Je suis sûr que je ne suis pas le premier à essayer de résoudre ce problème et j'apprécierais une contribution sur le problème.

La façon de gérer une telle situation de manière optimale en utilisant simplement A * est d'élargir l'espace de recherche. Autrement dit, imaginez qu'il existe une copie distincte du donjon pour chaque combinaison d'objets que votre personnage pourrait transporter.

Dans chaque copie du donjon, les portes qui sont praticables sont exactement celles qui peuvent être franchies en utilisant l'ensemble d'objets correspondant. La seule façon de passer d'une copie de donjon à une autre est de se tenir sur l'emplacement d'un objet et de le récupérer.

Vous pouvez étendre cette astuce pour inclure d'autres changements d'état, tels que des commutateurs qui peuvent ouvrir et / ou fermer des portes. Vous pouvez même autoriser le joueur à déposer des objets, bien que cela puisse devenir compliqué car l'état doit alors inclure l'emplacement de chaque objet abandonné, ce qui augmente considérablement l'espace de recherche potentiel.

Une optimisation très utile consiste à précalculer les chemins les plus courts depuis chaque porte (en fait, chaque côté de chaque porte) et chaque élément vers chaque autre porte / élément accessible, en supposant que toutes les portes sont verrouillées . Une fois que vous avez ces chemins, vous pouvez simplement traiter chacun d'eux comme un bord pondéré dans un graphique reliant ces emplacements importants les uns aux autres et ignorer tous les autres emplacements.

Par exemple, supposez que votre donjon a dix portes et cinq clés. Ensuite, il y aura 2 * 10 + 5 = 25 emplacements significatifs et 2 ^ 5 = 32 combinaisons d'éléments possibles, pour un total de 25 * 32 = 800 nœuds dans l'espace de recherche complet. Il s'agit d'un nombre très modeste, d'autant plus qu'une grande partie de l'espace de recherche est susceptible d'être inaccessible.

Du point de vue du monde réel: si vous vous dirigiez de A à B et trouviez une porte D sur votre chemin qui était verrouillée, vous vous rendriez compte que vous devez trouver la clé D. Donc, si votre IA est aussi inconnue que l'être humain typique , cela impliquerait de rechercher la clé, qui est un ensemble de minuscules étapes de recherche de chemin en soi. D'un autre côté, vous voudrez peut-être que votre IA sache, avant même de tenter un chemin, qu'il y ait une porte verrouillée sur cette route, et dans ce cas, elle saura probablement aussi où trouver la clé.

Quoi qu'il en soit, le problème est celui de la connectivité à deux niveaux. Au niveau "sur le terrain", vous savez que vous pouvez toujours vous déplacer en toute sécurité dans une zone indivise ... indivisible par des portes verrouillées, c'est-à-dire. C'est ici que vous pouvez utiliser librement votre implémentation de pathfinding A * actuelle. (Dans un exemple simpliste, vous pourriez voir une zone comme une seule pièce. Vous ne pouvez pas accéder à une autre pièce sans déverrouiller une porte. En réalité, cela pourrait être une région entière de votre donjon.) Ceci est le fondement de votre mouvement d'entité, mais c'est un peu comme se promener les yeux baissés, au lieu d'examiner d'abord la zone autour de vous - vous risquez de marcher dans un lampadaire. Ou dans ce cas, une porte verrouillée. Ainsi, vos cartes au niveau du sol sur lesquelles votre A * fonctionne doivent limiter le joueur au mouvement uniquement dans la zone actuelle.

Ensuite, il y a une carte de niveau supérieur, qui est de nature plus topologique que topographique. Il ne se soucie pas vraiment des détails sur le terrain des obstacles et ainsi de suite, il ne se soucie que de la connectivité entre les zones. Cette carte topologique contient des connexions entre des zones paires qui ont actuellement une porte verrouillée entre elles, car elle montre la connectivité idéale de toutes les zones de votre donjon. Dans ses bords - chacun représentant une porte entre des zones - il stocke quelle clé est encore nécessaire, le cas échéant, pour ouvrir cette porte, sinon elle est considérée comme ouverte. Ainsi, lorsque vous recherchez dans ce graphique le chemin le plus court, il doit limiter ce chemin trouvé aux itinéraires déjà ouverts , en vérifiant les données dans les bords pendant l'exécution de la recherche. La connectivité ici n'implique pas l'ouverture, mais plutôt une ouverture potentielle.

Lorsque vous souhaitez vous déplacer vers un point qui se trouve dans une zone distincte, vous recherchez d'abord votre carte de niveau supérieur pour trouver un chemin. (Un * ou tout autre algorithme de chemin le plus court peut être utilisé à ce niveau.) Une fois que vous avez trouvé un chemin, cette carte de niveau supérieur devrait également fournir des informations sur la porte que vous devez utiliser pour passer de votre zone actuelle à l'autre zone. Maintenant, dans la zone locale, vous pouvez effectuer une IA au niveau du sol pour accéder à cette porte. Une fois la porte atteinte, votre personnage peut passer par cette porte / portail. Il est maintenant dans la zone B. S'il s'agit de la zone cible, il peut utiliser la navigation au niveau du sol pour accéder à la clé. Si ce n'est pas le cas, vous devez répéter la première étape jusqu'à ce que vous atteigniez la zone cible.

Il y a la possibilité qu'une clé recherchée soit elle-même derrière une porte verrouillée ... et que la clé de cette porte soit également ... et ainsi de suite ad nauseum. Il s'agit essentiellement d'un problème de résolution des dépendances, et il existe plusieurs façons de résoudre ce problème, dont Petri Nets. Voir cet excellent article.

PS. Si vous créez votre donjon de manière procédurale, vous pouvez alors stocker des informations sur l'ordre des dépendances, à condition que vous connaissiez déjà la position de départ du joueur.

La réaction intestinale normale aux mots "chemin le plus court" serait évidemment A *. Mais A * échouerait dans un tel environnement, car je vois de nombreux problèmes pour définir une heuristique fiable et, en outre, il est très probable qu'un nœud doit être visité plusieurs fois, ce qui n'est également pas possible dans A * conventionnel et serait également rendre l'heuristique plus difficile.

Premièrement, une heuristique admissible ne doit pas être parfaite. Il faut juste que ce soit une sous-estimation et ce doit être mieux que rien. Étant donné que vous travaillez avec des distances réelles, il semble probable que A * serait au moins d'une certaine aide, et même si l'heuristique n'améliorait pas beaucoup la recherche, elle serait probablement encore meilleure qu'une recherche standard en largeur ou similaire.

Deuxièmement, A * peut visiter un nœud autant de fois que vous le souhaitez. N'oubliez pas que A * n'est pas un algorithme de recherche de chemin mais un algorithme de recherche. Il recherche dans les états. Dans les jeux, nous assimilons souvent un état à une position, car peu importe comment vous avez atteint cet état - combien le chemin était court pour y arriver. Cependant, dans un problème comme celui-ci, l'état est une combinaison de la position et de tout autre état pertinent tel que les clés détenues.

Il est vrai, cependant, que ces complications feront passer A * du domaine «très efficace» à «réussiront, mais probablement pas dans le délai dont j'ai besoin». Quel est le délai dont vous avez besoin? En fait, pourquoi avez-vous besoin de faire cela - avez-vous vraiment besoin du chemin le plus court, ou un chemin raisonnable suffirait-il?

Ce à quoi j'ai pensé, c'est simplement chercher un chemin du début du donjon à la fin, en ignorant toutes les portes bloquées. Après que ce chemin soit trouvé, pour chacune des portes bloquant notre chemin, un chemin supplémentaire recherchant la clé appropriée et revenant à la porte serait recherché et traversé avant même que la porte ne soit atteinte.

Il est facile de prouver qu'un tel système serait sous-optimal. D'où voudriez-vous commencer le chemin supplémentaire? Si depuis le début, vous avez perdu votre temps à tracer le chemin d'origine vers la porte. Si à partir de la fin, placer une clé près du début signifie que le chemin traverse la carte deux fois, une fois suffit. Si vous essayez de calculer des points de fusion optimaux pour les chemins vers et depuis la porte et le chemin d'origine, cela donnera un résultat optimal mais consommera beaucoup de ressources en raison du nombre de permutations et de la difficulté à former une heuristique pour simplifier la recherche. Si vous ajoutez plusieurs clés au problème, vous rencontrez le problème du voyageur de commerce qui n'est pas facile à résoudre efficacement.

Ce que j'essaierais, s'il est possible d'assouplir le critère du «chemin le plus court», est le suivant:

• Créez un graphique de haut niveau qui ne contient que des emplacements importants - positions clés, positions des portes, positions dans les zones verrouillées et notez les distances en ligne droite entre elles. Si votre carte se divise déjà en chambres ou autres emplacements discrets, c'est parfait.
• Utilisez A * pour trouver un chemin à travers ce graphique, du début à la fin. L'heuristique de distance cartésienne normale devrait être suffisante pour la maintenir gérable.
• Maintenant, avec ce chemin simplifié entre ces points de cheminement, utilisez à nouveau A * pour tracer un chemin de bas niveau d'un point de cheminement au suivant.
• Joignez ces chemins de bas niveau ensemble pour former votre chemin entier.

Une fois que j'aurais réussi, je considérerais quelques optimisations mineures - par exemple. pondérer les zones avec des clés de manière plus clémente de sorte que le cheminement de bas niveau soit plus susceptible de faire de petits détours pour récupérer les clés.

avec les informations que vous avez fournies, je pense que vous pouvez utiliser A * avec juste une petite modification. dans un algorithme A * normal, vous marquez chaque nœud au fur et à mesure que vous les passez pour vous assurer de ne plus jamais le passer. C'est la partie exacte qui pose problème avec les articles. Le changement clé consiste à se souvenir de ce qu'étaient vos articles lorsque vous êtes passé d'un nœud auparavant. voici un code sudo expliquant ce que je veux dire:

if (nodestoCheck.notempty())
    newNode = nodeToCheck.first;
    if (notpassed(newNode.pos, newNode.items))
        if (room(newNode).containItem)
            add NewNode + room(NewNode).items 
        else
            do normal A* algorithm for new Node

avec cet algorithme, vous commencez par vérifier tous les nœuds sans élément. il est fort possible que votre premier groupe de recherche soit bloqué par certaines portes. mais il trouvera une clé pour cette porte avant de fouiller toutes les pièces. à partir de cette clé, vous lancez une nouvelle recherche avec cette clé spécifique. cette fois, lorsque vous atteignez la porte, vous pouvez la passer. la même routine continue jusqu'à ce que vous trouviez votre moyen de sortir du donjon. le seul problème peut être la consommation de mémoire chaque fois qu'il y a beaucoup de portes et de clés. bien que ce ne soit pas un problème pour au moins 10 ou 15 clés.

Pourquoi ne pas simplement utiliser A * normal et modéliser les portes verrouillées comme des régions infranchissables; une fois que vous avez ramassé la clé (marcher sur la tuile clé?), cela transforme cette porte verrouillée particulière en une zone praticable.

Cela signifie que votre localisateur de chemin choisira l' itinéraire sans clé le plus court , et s'il trouve des clés en cours de route, il l'intégrera dans son chemin si cela vous aide.

Cela me semble assez raisonnable. Ce n'est pas parfait, mais c'est une solution simple au problème.