Localização de caminho com fechadura e chave?

Estou trabalhando em um jogo com mapas que lembram quebra-cabeças de fechadura e chave . A IA precisa navegar para uma meta que pode estar atrás de uma porta vermelha trancada, mas a chave vermelha pode estar atrás de uma porta azul trancada, e assim por diante ...

Esse quebra-cabeça é semelhante a uma masmorra no estilo Zelda, como esta imagem:

Para chegar à meta, você deve derrotar o chefe, o que requer passar por cima do poço, o que exige a coleta da pena, o que exige a coleta da chave

As masmorras de Zelda tendem a ser lineares. No entanto, preciso resolver o problema no caso geral. Tão:

• O objetivo pode exigir um de um conjunto de chaves. Talvez você precise obter a tecla vermelha ou a tecla azul. Ou poderia haver uma porta destrancada a longa distância!
• Pode haver várias portas e chaves de um tipo. Por exemplo, pode haver várias chaves vermelhas no mapa, e a coleta de uma delas concederá acesso a todas as portas vermelhas.
• A meta pode estar inacessível porque as chaves certas estão atrás de portas trancadas

Como eu realizaria a busca de caminhos nesse mapa? Como seria o gráfico de pesquisa?

Nota: o último ponto sobre a detecção de objetivos inacessíveis é importante; A *, por exemplo, é extremamente ineficiente se a meta for inacessível. Eu gostaria de lidar com isso de forma eficiente.

Suponha que a IA saiba onde está tudo no mapa.

A busca de caminho padrão é boa o suficiente - seus estados são sua localização atual + seu inventário atual. "mudar" é vestiários ou troca de inventário. Não abordado nesta resposta, mas sem muito esforço adicional, está escrevendo uma boa heurística para A * - ele pode realmente acelerar a pesquisa, preferindo pegar as coisas em vez de se afastar, preferindo abrir uma porta perto do alvo sobre procurar um longo caminho, etc.

Esta resposta recebeu muitos upvotes desde que surgiu e tem uma demonstração, mas para uma solução muito mais otimizada e especializada, você também deve ler a resposta "Fazer isso ao contrário é muito mais rápido" /gamedev/ / a / 150155/2624

Prova de conceito Javascript totalmente operacional abaixo. Desculpe a resposta como um despejo de código - na verdade, eu implementei isso antes de me convencer de que era uma boa resposta, mas me parece bastante flexível.

Para começar ao pensar em busca de caminhos, lembre-se de que a hierarquia de algoritmos simples de busca de caminhos é:

• A Primeira Pesquisa de Largura é o mais simples possível.
• O algoritmo de Djikstra é como a primeira pesquisa de largura, mas com "distâncias" variáveis ​​entre estados
• A * é Djikstras, onde você tem um 'senso geral da direção certa' disponível como heurística.

No nosso caso, apenas codificar um "estado" como "local + inventário" e "distâncias" como "uso de movimento ou item" nos permite usar Djikstra ou A * para resolver nosso problema.

Aqui está um código real que demonstra seu nível de exemplo. O primeiro trecho é apenas para comparação - pule para a segunda parte, se você quiser ver a solução final. Começamos com a implementação de um Djikstra que encontra o caminho correto, mas ignoramos todos os obstáculos e chaves. (Experimente, você pode ver apenas linhas finais para o acabamento, da sala 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)], []))

Então, como adicionamos itens e chaves a esse código? Simples! em vez de cada "estado" começar apenas o número da sala, agora é uma tupla da sala e nosso estado de inventário:

 // 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 }

As transições agora mudam de uma tupla (custo, quarto) para uma tupla (custo, estado), para que você possa codificar "mover para outra sala" e "pegar um item"

// 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));
};

finalmente, fazemos algumas pequenas alterações relacionadas ao tipo na função Djikstra (por exemplo, ela ainda está apenas correspondendo a um número de sala de gol em vez de um estado completo) e obtemos nossa resposta completa! Observe que o resultado impresso primeiro vai para a sala 4 para pegar a chave, depois para a sala 1 para pegar a pena, depois para a sala 6, mata o chefe e depois para a sala 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')], []))

Em teoria, isso funciona mesmo com o BFS e não precisávamos da função de custo para o Djikstra, mas ter o custo nos permite dizer "pegar uma chave é fácil, mas lutar com um chefe é muito difícil, e preferimos voltar atrás 100 passos em vez de lutar contra o chefe, se tivéssemos a escolha ":

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'))

Para trás A * fará o truque

Conforme discutido nesta resposta a uma pergunta sobre a busca de caminho para a frente e para trás , a busca de caminho para trás é uma solução relativamente simples para esse problema. Isso funciona de maneira muito semelhante ao GOAP (Planejamento de Ação Orientada a Objetivos), planejando soluções eficientes e minimizando o questionamento sem objetivo.

No final desta resposta, tenho uma descrição detalhada de como ela lida com o exemplo que você deu.

Em detalhe

Encontre o caminho do destino até o início. Se, em sua busca de caminho, você encontrar uma porta trancada, terá uma nova ramificação que continuará através da porta como se estivesse destrancada, com a ramificação principal continuando a procurar outro caminho. O ramo que continua pela porta como se estivesse destrancado não está mais procurando pelo agente de IA - agora está procurando uma chave que possa ser usada para passar pela porta. Com A *, sua nova heurística é a distância da chave + a distância do agente da IA, em vez de apenas a distância do agente da IA.

Se a ramificação da porta destrancada encontrar a chave, ela continuará procurando o agente de IA.

Essa solução é um pouco mais complicada quando há várias chaves viáveis ​​disponíveis, mas você pode ramificar de acordo. Como as ramificações têm um destino fixo, ele ainda permite que você use uma heurística para otimizar a localização de caminhos (A *), e esperamos que caminhos impossíveis sejam cortados rapidamente - se não houver maneira de contornar a porta trancada, a ramificação que não a passagem pela porta fica sem opções rapidamente e o galho que passa pela porta e procura a chave continua por conta própria.

Obviamente, onde há uma variedade de opções viáveis ​​disponíveis (várias chaves, outros itens para contornar a porta, caminho longo ao redor da porta), muitos galhos serão mantidos, afetando o desempenho. Mas você também encontrará a opção mais rápida e poderá usá-la.

Em ação

No seu exemplo específico, busca de caminhos da meta até o início:

1. Rapidamente encontramos uma porta do chefe. O ramo A continua pela porta, agora procurando um chefe para lutar. O ramo B permanece preso na sala e logo expirará quando descobrir que não há saída.

2. O ramo A encontra o chefe e agora está procurando o Start, mas encontra um buraco.

3. O ramo A continua sobre o poço, mas agora está procurando a pena, e fará uma linha de abelha em direção à pena de acordo. O ramo C é criado e tenta encontrar uma maneira de contornar o poço, mas expira assim que não é possível. Isso, ou é ignorado por um tempo, se sua heurística A * descobrir que o ramo A ainda parece mais promissor.

4. O ramo A encontra a porta trancada e continua pela porta trancada como se estivesse destrancada, mas agora está procurando a chave. O ramo D continua também pela porta trancada, ainda procurando a pena, mas depois procurará a chave. Isso ocorre porque não sabemos se precisamos encontrar a chave ou a pena primeiro e, no que diz respeito à busca de caminhos, o Start pode estar do outro lado desta porta. O ramo E tenta encontrar uma maneira de contornar a porta trancada e falha.

5. O ramo D encontra rapidamente a pena e continua procurando a chave. É permitido passar pela porta trancada novamente, pois ainda está procurando a chave (e está voltando no tempo). Mas uma vez que tenha a chave, não será possível passar pela porta trancada (já que ela não poderia passar pela porta trancada antes de encontrar a chave).

6. O ramo A e D continuam a competir, mas quando o ramo A alcança a chave, ele está procurando a pena, e não alcançará a pena porque precisa passar pela porta trancada novamente. O ramo D, por outro lado, ao alcançar a chave, volta sua atenção para o Start e a encontra sem complicações.

7. O ramo D vence. Ele encontrou o caminho inverso. O caminho final é: Iniciar -> Chave -> Pena -> Chefe -> Objetivo.

Editar : está escrito do ponto de vista de uma IA que está disposta a explorar e descobrir uma meta e não sabe a localização das chaves, bloqueios ou destinos antes do tempo.

Primeiro, suponha que a IA tenha algum tipo de objetivo geral. Por exemplo, "Encontre o chefe" no seu exemplo. Sim, você quer vencê-lo, mas realmente é sobre encontrá-lo. Suponha que não tenha idéia de como chegar à meta, apenas que ela existe. E saberá quando encontrar. Uma vez atingido o objetivo, a IA pode parar de trabalhar para resolver o problema.

Além disso, vou usar o termo genérico "lock" e "key" aqui, mesmo que possa ser um abismo e uma pena. Ou seja, a pena "destrava" o abismo "trava".

Abordagem da solução

Parece que você começaria primeiro com apenas uma IA que era basicamente um explorador de labirinto (se você pensar no seu mapa como um labirinto). Explorar e mapear todos os lugares aonde pode ir seria o foco principal da IA. Poderia se basear apenas em algo simples como: "Sempre vá para o caminho mais próximo que já vi, mas ainda não o visitei".

No entanto, algumas regras surgiriam ao explorar que poderiam mudar a prioridade ...

• Seria necessária qualquer chave encontrada, a menos que já tivesse a mesma chave
• Se encontrasse um cadeado que nunca tinha visto antes, tentaria todas as chaves encontradas naquele cadeado
• Se uma chave funcionasse em um novo tipo de bloqueio, lembraria o tipo de chave e o tipo de bloqueio
• Se encontrasse uma fechadura que tinha visto antes e tivesse a chave, usaria o tipo de chave lembrada (por exemplo, segundo bloqueio vermelho encontrado, a chave vermelha funcionou antes na fechadura vermelha, use apenas a chave vermelha)
• Lembraria a localização de qualquer bloqueio que não pudesse desbloquear
• Não seria necessário lembrar a localização dos bloqueios que havia desbloqueado
• Sempre que encontrava uma chave e conhecia os bloqueios anteriormente desbloqueáveis, ele visitava imediatamente cada um desses bloqueios e tentava desbloqueá-los com a nova chave encontrada
• Sempre que desbloqueava um caminho, ele simplesmente voltava à meta de exploração e mapeamento, priorizando entrar na nova área

Uma observação sobre esse último ponto. Se for necessário escolher entre verificar uma área inexplorada vista antes (mas não visitada) versus uma área inexplorada atrás de um caminho recém-desbloqueado, isso deve tornar o caminho recém-desbloqueado a prioridade. Provavelmente é aí que existem novas chaves (ou bloqueios) que serão úteis. Isso pressupõe que um caminho bloqueado provavelmente não será um beco sem saída.

Expandindo a ideia com chaves "bloqueáveis"

Você pode ter chaves que não podem ser obtidas sem outra chave. Ou chaves trancadas por assim dizer. Se você conhece suas antigas Cavernas Colossais, precisa da gaiola para pegá-lo - o que você precisa mais tarde para uma cobra. Então você "desbloqueia" o pássaro com a gaiola (que não bloqueia o caminho, mas não pode ser pego sem a gaiola) e depois "desbloqueia" a cobra (que bloqueia o caminho) com o pássaro.

Então, adicionando algumas regras ...

• Se não for possível pegar uma chave (ela está bloqueada), tente todas as chaves que você já possui.
• Se você encontrar uma chave que não pode desbloquear, lembre-se dela mais tarde
• Se você encontrar uma nova chave, experimente-a em todas as chaves bloqueadas conhecidas e também no caminho bloqueado

Eu nem vou entrar em detalhes sobre como carregar uma certa chave pode negar o efeito de outra chave (cavernas colossais, vara assusta o pássaro e deve ser descartada antes que o pássaro possa ser apanhado, mas é necessário mais tarde para criar uma ponte mágica) .