Pathfinding avec serrure et clé?

22

Je travaille sur un jeu avec des cartes qui ressemblent à des puzzles de verrouillage et de clé . L'IA doit naviguer vers un objectif qui peut être derrière une porte rouge verrouillée, mais la clé rouge peut être derrière une porte bleue verrouillée, et ainsi de suite ...

Ce puzzle est similaire à un donjon de style Zelda, comme cette image:

Donjon de Zelda

Pour atteindre le but, vous devez vaincre le boss, ce qui nécessite d'aller au-dessus de la fosse, ce qui nécessite de récupérer la plume, ce qui nécessite de récupérer la clé

Les donjons Zelda ont tendance à être linéaires. Cependant, je dois résoudre le problème dans le cas général. Alors:

  • L'objectif pourrait nécessiter l'une d'un ensemble de clés. Alors peut-être que vous devez obtenir la clé rouge ou la clé bleue. Ou il pourrait y avoir une porte déverrouillée le long du chemin!
  • Il pourrait y avoir plusieurs portes et clés d'une même sorte. Par exemple, il pourrait y avoir plusieurs clés rouges sur la carte, et en collecter une vous donnera accès à toutes les portes rouges.
  • Le but peut être inaccessible car les bonnes touches sont derrière des portes verrouillées

Comment puis-je effectuer la recherche de chemin sur une telle carte? À quoi ressemblerait le graphique de recherche?

Remarque: le dernier point concernant la détection d'objectifs inaccessibles est important; Un *, par exemple, est extrêmement inefficace si l'objectif est inaccessible. Je voudrais traiter cela efficacement.

Supposons que l'IA sache où tout se trouve sur la carte.

congusbongus
la source
4
L'IA ne connaît-elle et découvre-t-elle les choses qu'une fois qu'elle les a déverrouillées? Par exemple, sait-il que la plume est derrière la porte verrouillée? L'IA comprend-elle des concepts comme «C'est une serrure, j'ai donc besoin d'une clé» ou quelque chose de plus simple comme «J'ai quelque chose qui bloque mon chemin, alors essayez toutes les choses que j'ai trouvées dessus. Plume sur la porte? Non. Clé sur la porte? Oui! "
Tim Holt
1
Il y a eu une discussion précédente de ce problème dans cette question sur la recherche de chemin vers l'avant vs vers l'arrière , qui pourrait vous être utile.
DMGregory
1
Donc, vous n'essayez pas de simuler un joueur, mais essayez de créer un parcours de donjon optimisé? Ma réponse était définitivement de simuler le comportement d'un joueur.
Tim Holt
4
Malheureusement, détecter un objectif inaccessible est assez difficile. La seule façon d'être sûr qu'il n'y a aucun moyen d'atteindre le but est d'explorer l'ensemble de l'espace accessible pour s'assurer qu'aucun ne contient un objectif - ce qui est exactement ce que fait A * qui le fait prendre autant d'étapes supplémentaires si le but est inaccessible. Tout algorithme qui recherche moins d'espace risque de manquer un chemin disponible vers l'objectif, car le chemin se cachait dans une partie de l'espace qu'il avait ignoré. Vous pouvez accélérer cela en travaillant à un niveau supérieur, en recherchant le graphique des connexions de pièce au lieu de chaque tuile ou polygone de navmesh.
DMGregory
1
Hors sujet, j'ai instinctivement pensé au Chip's Challenge au lieu de Zelda :)
Flater

Réponses:

22

La recherche de chemin standard est assez bonne - vos états sont votre emplacement actuel + votre inventaire actuel. «déménager», c'est soit changer de salle, soit changer d'inventaire. Pas couvert dans cette réponse, mais pas trop d'efforts supplémentaires, est d'écrire une bonne heuristique pour A * - il peut vraiment accélérer la recherche en préférant ramasser les choses plutôt que de s'en éloigner, préférant déverrouiller une porte près de la cible sur la recherche d'un long chemin, etc.

Cette réponse a obtenu beaucoup de votes positifs depuis qu'elle est arrivée en premier et a une démo, mais pour une solution beaucoup plus optimisée et spécialisée, vous devriez également lire la réponse "Faire en arrière est beaucoup plus rapide" /gamedev/ / a / 150155/2624


Preuve de concept Javascript entièrement opérationnelle ci-dessous. Désolé pour la réponse sous forme de vidage de code - j'avais en fait implémenté cela avant d'être convaincu que c'était une bonne réponse, mais cela me semble assez flexible.

Pour commencer en pensant au pathfinding, rappelez-vous que la hiérarchie des algorithmes de pathfinding simples est

  • L'étendue de la première recherche est à peu près aussi simple que possible.
  • L'algorithme de Djikstra ressemble à la recherche en largeur mais avec des "distances" variables entre les états
  • Un * est Djikstras où vous avez un «sens général de la bonne direction» disponible comme une heuristique.

Dans notre cas, le simple encodage d'un «état» comme «emplacement + inventaire» et de «distances» comme «mouvement ou utilisation d'objets» nous permet d'utiliser Djikstra ou A * pour résoudre notre problème.

Voici du code réel illustrant votre niveau d'exemple. Le premier extrait est juste pour comparaison - passez à la deuxième partie si vous voulez voir la solution finale. Nous commençons avec une implémentation de Djikstra qui trouve le chemin correct, mais nous avons ignoré tous les obstacles et les clés. (Essayez-le, vous pouvez le voir juste avant l'arrivée, depuis la salle 0 -> 2 -> 3-> 4-> 6-> 5)

function Transition(cost, state) { this.cost = cost, this.state = state; }
// given a current room, return a room of next rooms we can go to. it costs 
// 1 action to move to another room.
function next(n) {
    var moves = []
    // simulate moving to a room
    var move = room => new Transition(1, room)
    if (n == 0) moves.push(move(2))
    else if ( n == 1) moves.push(move(2))
    else if ( n == 2) moves.push(move(0), move(1), move(3))
    else if ( n == 3) moves.push(move(2), move(4), move(6))
    else if ( n == 4) moves.push(move(3))
    else if ( n == 5) moves.push(move(6))
    else if ( n == 6) moves.push(move(5), move(3))
    return moves
}

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

    if (!nextStates.length) return ['did not find goal', history]

    var action = nextStates.pop()
    cost += action.cost
    var cur = action.state

    if (cur == goal) return ['found!', history.concat([cur])]
    if (history.length > 15) return ['we got lost', history]

    var notVisited = (visit) => {
        return visited.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
    };
    nextStates = nextStates.concat(next(cur).filter(notVisited))
    nextStates.sort()

    visited.push(cur)
    return calc_Djikstra(cost, goal, history.concat([cur]), nextStates, visited)
}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, 0)], []))

Alors, comment ajouter des éléments et des clés à ce code? Simple! au lieu de chaque "état" commencez juste le numéro de la chambre, c'est maintenant un tuple de la salle et notre état d'inventaire:

 // Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }

Les transitions passent désormais d'un tuple (coût, salle) à un tuple (coût, état).

// move(3) keeps inventory but sets the room to 3
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b))
// pickup("k") keeps room number but increments the key count
var pickup = (cost, item) => {
    var n = Object.assign({}, cur)
    n[item]++;
    return new Transition(cost, new State(cur.room, n.k, n.f, n.b));
};

enfin, nous apportons quelques modifications mineures liées au type à la fonction Djikstra (par exemple, elle correspond toujours à un numéro de salle d'objectif au lieu d'un état complet), et nous obtenons notre réponse complète! Notez que le résultat imprimé va d'abord dans la salle 4 pour récupérer la clé, puis dans la salle 1 pour récupérer la plume, puis dans la salle 6, tue le boss, puis dans la salle 5)

// Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }
function Transition(cost, state, msg) { this.cost = cost, this.state = state; this.msg = msg; }

function next(cur) {
var moves = []
// simulate moving to a room
var n = cur.room
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b), "move to " + room)
var pickup = (cost, item) => {
	var n = Object.assign({}, cur)
	n[item]++;
	return new Transition(cost, new State(cur.room, n.k, n.f, n.b), {
		"k": "pick up key",
		"f": "pick up feather",
		"b": "SLAY BOSS!!!!"}[item]);
};

if (n == 0) moves.push(move(2))
else if ( n == 1) { }
else if ( n == 2) moves.push(move(0), move(3))
else if ( n == 3) moves.push(move(2), move(4))
else if ( n == 4) moves.push(move(3))
else if ( n == 5) { }
else if ( n == 6) { }

// if we have a key, then we can move between rooms 1 and 2
if (cur.k && n == 1) moves.push(move(2));
if (cur.k && n == 2) moves.push(move(1));

// if we have a feather, then we can move between rooms 3 and 6
if (cur.f && n == 3) moves.push(move(6));
if (cur.f && n == 6) moves.push(move(3));

// if killed the boss, then we can move between rooms 5 and 6
if (cur.b && n == 5) moves.push(move(6));
if (cur.b && n == 6) moves.push(move(5));

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))	
return moves
}

var notVisited = (visitedList) => (visit) => {
return visitedList.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
};

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

if (!nextStates.length) return ['No path exists', history]

var action = nextStates.pop()
cost += action.cost
var cur = action.state

if (cur.room == goal) return history.concat([action.msg])
if (history.length > 15) return ['we got lost', history]

nextStates = nextStates.concat(next(cur).filter(notVisited(visited)))
nextStates.sort()

visited.push(cur)
return calc_Djikstra(cost, goal, history.concat([action.msg]), nextStates, visited)
o}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, new State(0, 0, 0, 0), 'start')], []))

En théorie, cela fonctionne même avec BFS et nous n'avions pas besoin de la fonction de coût pour Djikstra, mais avoir le coût nous permet de dire "récupérer une clé est sans effort, mais combattre un boss est vraiment difficile, et nous préférerions revenir en arrière 100 pas plutôt que de combattre le boss, si on avait le choix ":

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))
Jimmy
la source
Oui, inclure l'inventaire / l'état des clés dans le graphique de recherche est une solution. Je suis préoccupé par l'augmentation de l'espace requis - une carte à 4 touches nécessite 16 fois l'espace d'un graphique sans clé.
congusbongus
8
@congusbongus bienvenue au problème des vendeurs itinérants NP-complete. Il n'y a pas de solution générale qui résoudra cela en temps polynomial.
Ratchet Freak
1
@congusbongus Je ne pense pas en général que votre graphique de recherche va être trop lourd, mais si vous êtes préoccupé par l'espace, il vous suffit de compresser vos données - vous pouvez utiliser 24 bits pour l'indicateur de pièce (16 millions de chambres devraient être suffisant pour n'importe qui) et un peu chacun pour les éléments que vous souhaitez utiliser comme portes (jusqu'à 8 uniques). Si vous voulez devenir sophistiqué, vous pouvez utiliser des dépendances pour regrouper des éléments en bits encore plus petits, c'est-à-dire utiliser le même bit pour "clé" et "boss" car il existe une dépendance transitive indirecte
Jimmy
@Jimmy Même si ce n'est pas personnel, j'apprécie la mention de ma réponse :)
Jibb Smart
13

En arrière A * fera l'affaire

Comme indiqué dans cette réponse à une question sur la recherche de chemin vers l' avant ou vers l'arrière , la recherche de chemin vers l'arrière est une solution relativement simple à ce problème. Cela fonctionne de manière très similaire à GOAP (Goal Oriented Action Planning), en planifiant des solutions efficaces tout en minimisant les interrogations sans but.

Au bas de cette réponse, j'ai une ventilation de la façon dont il gère l'exemple que vous avez donné.

En détail

Pathfind de la destination au départ. Si, dans votre recherche de chemin, vous tombez sur une porte verrouillée, vous avez une nouvelle branche à votre chemin qui continue à travers la porte comme si elle était déverrouillée, la branche principale continuant de chercher un autre chemin. La branche qui continue à travers la porte comme si elle était déverrouillée ne cherche plus l'agent IA - elle cherche maintenant une clé qu'elle peut utiliser pour traverser la porte. Avec A *, sa nouvelle heuristique est la distance à la clé + la distance à l'agent AI, au lieu de simplement la distance à l'agent AI.

Si la branche porte déverrouillée trouve la clé, elle continue de chercher l'agent AI.

Cette solution est rendue un peu plus compliquée lorsque plusieurs clés viables sont disponibles, mais vous pouvez vous connecter en conséquence. Parce que les branches ont une destination fixe, il vous permet toujours d'utiliser une heuristique pour optimiser la recherche de chemin (A *), et les chemins impossibles seront, espérons-le, coupés rapidement - s'il n'y a pas de moyen de contourner la porte verrouillée, la branche qui ne fonctionne pas ne passez pas la porte à court d'options rapidement et la branche qui passe par la porte et cherche la clé continue d'elle-même.

Bien sûr, là où il existe une variété d'options viables disponibles (plusieurs clés, d'autres éléments pour contourner la porte, un long chemin autour de la porte), de nombreuses branches seront maintenues, affectant les performances. Mais vous trouverez également l'option la plus rapide et pourrez l'utiliser.


En action

Dans votre exemple spécifique, la recherche de chemin depuis l'objectif jusqu'au début:

  1. Nous rencontrons rapidement une porte de boss. La branche A continue à travers la porte, à la recherche d'un boss pour se battre. La branche B reste coincée dans la pièce et expirera bientôt lorsqu'elle découvrira qu'il n'y a pas d'issue.

  2. La branche A trouve le boss et cherche maintenant le départ, mais rencontre une fosse.

  3. La branche A continue au-dessus de la fosse, mais maintenant elle cherche la plume et fera une ligne d'abeille vers la plume en conséquence. La branche C est créée qui essaie de trouver un moyen de contourner la fosse, mais expire dès qu'elle ne peut pas. Cela, ou il est ignoré pendant un certain temps, si votre heuristique A * constate que la branche A semble toujours la plus prometteuse.

  4. La branche A rencontre la porte verrouillée et continue à travers la porte verrouillée comme si elle était déverrouillée, mais maintenant elle cherche la clé. La branche D continue également à travers la porte verrouillée, toujours à la recherche de la plume, mais elle cherchera ensuite la clé. C'est parce que nous ne savons pas si nous devons d'abord trouver la clé ou la plume, et en ce qui concerne la recherche de chemin, le Start pourrait être de l'autre côté de cette porte. La branche E essaie de trouver un moyen de contourner la porte verrouillée et échoue.

  5. La branche D trouve rapidement la plume et continue de chercher la clé. Il est autorisé à passer à nouveau par la porte verrouillée, car il cherche toujours la clé (et il recule dans le temps). Mais une fois qu'il a la clé, il ne pourra pas passer par la porte verrouillée (car il ne pouvait pas passer par la porte verrouillée avant d'avoir trouvé la clé).

  6. Les branches A et D continuent de rivaliser, mais lorsque la branche A atteint la clé, elle cherche la plume, et elle ne parviendra pas à atteindre la plume car elle doit repasser par la porte verrouillée. La branche D, d'autre part, en atteignant la clé, tourne son attention vers le départ et la trouve sans complication.

  7. La branche D gagne. Il a trouvé le chemin inverse. Le chemin final est: Démarrer -> Clé -> Plume -> Boss -> Objectif.

Jibb Smart
la source
6

Modifier : Ceci est écrit du point de vue d'une IA qui est prête à explorer et à découvrir un objectif, et qui ne connaît pas à l'avance l'emplacement des clés, des verrous ou des destinations.

Tout d'abord, supposons que l'IA ait une sorte d'objectif global. Par exemple, "Trouvez le patron" dans votre exemple. Oui, vous voulez le battre, mais il s'agit vraiment de le trouver. Supposons qu'il ne sache pas comment atteindre le but, juste qu'il existe. Et il le saura quand il le trouvera. Une fois l'objectif atteint, l'IA peut cesser de travailler pour résoudre le problème.

De plus, je vais utiliser ici le terme générique "verrou" et "clé", même s'il peut s'agir d'un gouffre et d'une plume. C'est-à-dire que la plume "déverrouille" le gouffre "verrouille".

Approche de solution

Il semble que vous commenciez d'abord avec une IA qui était essentiellement un explorateur de labyrinthe (si vous considérez votre carte comme un labyrinthe). Explorer et cartographier tous les endroits où il peut aller serait le principal objectif de l'IA. Cela pourrait être basé uniquement sur quelque chose de simple comme, "Allez toujours vers le chemin le plus proche que j'ai vu mais pas encore visité."

Cependant, quelques règles entreraient en jeu tout en explorant cela pourrait changer la priorité ...

  • Il faudrait n'importe quelle clé trouvée, à moins qu'il n'ait déjà la même clé
  • S'il trouvait un verrou qu'il n'avait jamais vu auparavant, il essaierait chaque clé qu'il avait trouvée sur ce verrou
  • Si une clé fonctionnait sur un nouveau type de verrou, elle se souviendrait du type de clé et du type de verrou
  • S'il trouvait un verrou qu'il avait vu auparavant et qu'il avait la clé, il utiliserait le type de clé mémorisé (par exemple, le deuxième verrou rouge trouvé, la clé rouge fonctionnait auparavant sur le verrou rouge, il suffit donc d'utiliser la clé rouge)
  • Il se souviendrait de l'emplacement de tout verrou qu'il ne pouvait pas déverrouiller
  • Il n'aurait pas besoin de se souvenir de l'emplacement des verrous qu'il avait déverrouillés
  • Chaque fois qu'il trouve une clé et connaît des verrous précédemment déverrouillables, il visite immédiatement chacun de ces verrous et essaie de les déverrouiller avec la nouvelle clé trouvée
  • Chaque fois qu'il ouvrait un chemin, il revenait simplement à l'objectif d'exploration et de cartographie, donnant la priorité à l'entrée dans la nouvelle zone

Une note sur ce dernier point. S'il doit choisir entre aller vérifier une zone inexplorée qu'il a vue avant (mais non visitée) par rapport à une zone inexplorée derrière un chemin nouvellement déverrouillé, il devrait faire de ce chemin nouvellement déverrouillé la priorité. C'est probablement là qu'il y a de nouvelles clés (ou verrous) qui seront utiles. Cela suppose qu'un chemin verrouillé ne sera probablement pas une impasse inutile.

Élargir l'idée avec des touches "verrouillables"

Vous pourriez potentiellement avoir des clés qui ne peuvent pas être prises sans une autre clé. Ou des clés verrouillées pour ainsi dire. Si vous connaissez vos anciennes grottes colossales, vous devez avoir la cage à oiseaux pour attraper l'oiseau - dont vous aurez besoin plus tard pour un serpent. Donc vous "déverrouillez" l'oiseau avec la cage (qui ne bloque pas le chemin mais ne peut pas être ramassé sans la cage), puis "déverrouillez" le serpent (qui bloque votre chemin) avec l'oiseau.

Donc, ajouter quelques règles ...

  • Si une clé ne peut pas être prise (elle est verrouillée), essayez toutes les clés que vous avez déjà dessus
  • Si vous trouvez une clé que vous ne pouvez pas déverrouiller, souvenez-vous-en pour plus tard
  • Si vous trouvez une nouvelle clé, essayez-la sur toutes les clés verrouillées connues ainsi que sur le chemin verrouillé

Je n'entrerai même pas dans le détail de la façon dont le port d'une certaine clé pourrait annuler l'effet d'une autre clé (Grottes colossales, la tige fait peur aux oiseaux et doit être lâchée avant que l'oiseau puisse être ramassé, mais est nécessaire plus tard pour créer un pont magique) .

Tim Holt
la source