Consciência situacional na busca de caminhos

Suponha que você tenha que encontrar o caminho mais curto através de uma masmorra, onde certas passagens só são abertas para você depois que certos itens são coletados, como portas e chaves trancadas, por exemplo.

A reação intestinal normal às palavras "caminho mais curto" seria obviamente A *. Mas o A * falharia nesse ambiente, pois vejo muitos problemas ao definir uma heurística confiável e, além disso, é muito provável que um nó precise ser visitado várias vezes, o que também não é possível no A * convencional e também dificultar a heurística.

O que pensei foi simplesmente procurar um caminho desde o início da masmorra até o fim, ignorando as portas bloqueadas. Depois que esse caminho é encontrado, para cada uma das portas que bloqueiam nosso caminho, um caminho adicional procurando a chave apropriada e de volta à porta seria procurado e percorrido antes mesmo que a porta fosse alcançada. O mesmo sistema seria usado para lidar com uma situação em que o caminho para uma chave necessária para abrir uma porta é novamente bloqueado por outra porta, que precisa ser aberta primeiro.

Um grande problema que vejo com minha solução é que, depois que todos os caminhos, incluindo os de aquisição de itens, são encontrados, a distância total percorrida pelo agente pode não ser a menor possível, pois pode haver outras portas bloqueadas mais distantes da meta mas tenha a chave apropriada muito mais facilmente disponível. A * teria negligenciado essas portas na primeira passagem, onde as portas bloqueadas são simplesmente ignoradas.

Tenho certeza de que não sou o primeiro a tentar resolver isso e gostaria de receber algumas sugestões sobre o problema.

A maneira de lidar com essa situação de maneira otimizada usando o A * direto é expandir o espaço de pesquisa. Ou seja, imagine que exista uma cópia separada da masmorra para cada combinação de itens que seu personagem possa estar carregando.

Em cada cópia da masmorra, as portas que são passáveis ​​são exatamente aquelas que podem ser passadas usando o conjunto de itens correspondente. A única maneira de passar de uma cópia da masmorra para outra é ficar na localização de um item e buscá-lo.

Você pode estender esse truque para incluir outras alterações de estado, como interruptores que podem abrir e / ou fechar portas. Você pode até permitir que o jogador descarte itens, embora isso possa ser complicado, pois o estado deve incluir a localização de cada item descartado, aumentando enormemente o espaço potencial de pesquisa.

Uma otimização muito útil é pré-calcular os caminhos mais curtos de cada porta (na verdade, cada lado de cada porta) e item para qualquer outra porta / item acessível, assumindo que todas as portas estejam trancadas . Depois de ter esses caminhos, você pode apenas tratar cada um deles como uma aresta ponderada em um gráfico conectando esses locais significativos entre si e ignorar todos os outros locais.

Por exemplo, suponha que sua masmorra tenha dez portas e cinco chaves. Em seguida, haverá 2 * 10 + 5 = 25 locais significativos e 2 ^ 5 = 32 combinações de itens possíveis, para um total de 25 * 32 = 800 nós no espaço de pesquisa completo. Esse é um número muito modesto, principalmente porque é provável que grande parte do espaço de pesquisa seja inacessível.

Do ponto de vista do mundo real: se você fosse de A a B e encontrasse uma porta D no seu caminho trancada, perceberia que precisava encontrar a chave D. Portanto, se sua IA é tão desconhecida quanto o ser humano típico , isso envolveria a busca pela chave, que é um conjunto de pequenas etapas de busca de caminhos por si só. Por outro lado, você pode querer que sua IA saiba, antes mesmo de tentar um caminho, que existe uma porta trancada nessa rota e, nesse caso, provavelmente também saberá onde encontrar a chave.

De qualquer forma, o problema é de conectividade em dois níveis. No nível "no chão", você sabe que sempre pode se mover com segurança dentro de uma zona não dividida ... dividido por portas trancadas. É aqui que você pode usar sua implementação atual de localização de caminhos A * livremente. (Em um exemplo simplista, você pode ver uma zona como um quarto individual. Você não pode chegar a qualquer outro quarto sem abrir uma porta. Na realidade, pode ser uma região inteira do seu calabouço.) Esta é a base do seu movimento de entidade, mas é como andar com os olhos abatidos, em vez de examinar primeiro a área ao seu redor - é provável que você entre em um poste de luz. Ou, neste caso, uma porta trancada. Portanto, seus mapas no nível do solo nos quais seu A * é executado devem restringir o jogador ao movimento apenas dentro da zona atual.

A seguir, existe um mapa de nível superior, mais topológico do que topográfico. Realmente não se preocupa com os detalhes dos obstáculos no terreno e assim por diante, apenas se preocupa com a conectividade entre as zonas. Esse mapa topológico contém conexões entre zonas pares que atualmente têm uma porta trancada entre elas, pois mostra a conectividade ideal de todas as zonas em sua masmorra. Em suas bordas - cada uma representando uma porta entre zonas -, ela armazena qual chave ainda é necessária, se houver, para abrir a porta; caso contrário, é considerada aberta. Portanto, ao procurar o caminho mais curto nesse gráfico, ele deve limitar o caminho encontrado apenas às rotas que já estão abertas , verificando os dados nas bordas à medida que a pesquisa é executada. A conectividade aqui não implica abertura, mas implica abertura potencial.

Quando você deseja mover para um ponto que se enquadra em uma zona separada, primeiro você pesquisa no mapa de nível superior para encontrar um caminho. (Um * ou qualquer outro algoritmo de caminho mais curto pode ser usado nesse nível.) Depois de encontrar um caminho, esse mapa de nível superior também deve fornecer informações sobre qual porta você precisa usar para ir da sua zona atual para a outra zona. Agora, na zona local, você pode fazer IA no nível do solo para navegar até essa porta. Quando a porta for alcançada, seu personagem poderá passar por essa porta / portal. Ele agora está na zona B. Se esta é a zona de destino, ele pode usar a navegação no nível do solo para ir para a chave. Caso contrário, você precisa repetir a etapa um até chegar à zona de destino.

Existe a possibilidade de que uma chave sendo procurada esteja atrás de uma porta trancada ... e que a chave dessa porta seja da mesma forma ... e assim por diante ad nauseum. Este é essencialmente um problema de resolução de dependência, e existem algumas maneiras de resolver isso, uma das quais é a Rede de Petri. Veja este excelente artigo.

PS. Se você estiver criando sua masmorra proceduralmente, ao fazê-lo, poderá armazenar informações sobre pedidos de dependência, desde que você já saiba a posição inicial do jogador.

A reação intestinal normal às palavras "caminho mais curto" seria obviamente A *. Mas o A * falharia nesse ambiente, pois vejo muitos problemas ao definir uma heurística confiável e, além disso, é muito provável que um nó precise ser visitado várias vezes, o que também não é possível no A * convencional e também dificultar a heurística.

Em primeiro lugar, uma heurística admissível não precisa ser perfeita. Só tem que ser uma subestimação e tem que ser melhor que nada. Dado que você está trabalhando com distâncias reais, parece provável que A * seria de alguma ajuda, e mesmo que a heurística não tenha melhorado muito a pesquisa, provavelmente ainda seria melhor do que uma pesquisa padrão de primeira largura ou similar.

Em segundo lugar, A * pode visitar um nó quantas vezes quiser. Lembre-se de que A * não é um algoritmo de localização de caminho, mas um algoritmo de pesquisa. Ele pesquisa nos estados. Nos jogos, geralmente igualamos um estado com uma posição, porque não nos importamos como você alcançou esse estado - quão curto o caminho era para chegar lá. No entanto, em um problema como esse, o estado é uma combinação da posição mais qualquer outro estado relevante, como as chaves mantidas.

É verdade, no entanto, que essas complicações passarão A * dos reinos de 'muito eficiente' para 'terão sucesso, mas provavelmente não na escala de tempo que eu exijo'. Qual é a escala de tempo necessária? De fato, por que você precisa fazer isso - você realmente precisa do caminho mais curto ou seria suficiente?

O que pensei foi simplesmente procurar um caminho desde o início da masmorra até o fim, ignorando as portas bloqueadas. Depois que esse caminho é encontrado, para cada uma das portas que bloqueiam nosso caminho, um caminho adicional procurando a chave apropriada e de volta à porta seria procurado e percorrido antes mesmo que a porta fosse alcançada.

É fácil provar que esse sistema seria abaixo do ideal. De onde você começaria o caminho adicional? Se desde o início, você perdeu seu tempo traçando o caminho original para a porta. Se, a partir do final, colocar uma chave perto do início significa que o caminho percorre o mapa duas vezes quando uma vez é suficiente. Se você tentar calcular os pontos de mesclagem ideais para os caminhos de e para a porta e o caminho original, isso produzirá um resultado ideal, mas consumirá muitos recursos devido ao número de permutações e à dificuldade de formar uma heurística para simplificar a pesquisa. Se você adicionar várias chaves ao problema, terá o problema do Vendedor ambulante, que não é fácil de resolver com eficiência.

O que eu tentaria, se for possível relaxar o critério do 'caminho mais curto', é o seguinte:

• Crie um gráfico de alto nível que contenha apenas locais importantes - posições principais, posições da porta, posições em áreas bloqueadas e observe as distâncias retas entre elas. Se o seu mapa já se divide em salas ou outros locais distintos, isso é ótimo.
• Use A * para encontrar um caminho nesse gráfico, do início ao fim. A heurística cartesiana normal da distância deve ser suficiente para mantê-la gerenciável.
• Agora, com esse caminho simplificado entre esses pontos de referência, use A * novamente para plotar um caminho de baixo nível de um ponto de referência para o próximo.
• Junte esses caminhos de baixo nível para formar todo o seu caminho.

Depois que eu conseguisse isso, consideraria algumas otimizações menores - por exemplo. ponderar as áreas com chaves de maneira mais branda, para que o percurso de baixo nível tenha maior probabilidade de fazer pequenos desvios para coletar chaves.

com as informações que você forneceu, acho que você pode usar o A * com apenas uma pequena modificação. em um algoritmo A * normal, você marca todos os nós ao passar por cima deles para garantir que nunca mais os passará novamente. Essa é a parte exata que causa problemas com os itens. A principal mudança é lembrar quais eram seus itens quando você passou anteriormente de um nó. Aqui está um código sudo explicando o que quero dizer:

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

com esse algoritmo, você começa a verificar todos os nós sem nenhum item. existe uma grande possibilidade de que seu primeiro grupo de pesquisa acabe bloqueado por algumas portas. mas encontrará a chave dessa porta antes de procurar em todos os quartos. a partir dessa chave, você inicia uma nova pesquisa com essa chave específica. desta vez, quando você chegar à porta, poderá passar por ela. a mesma rotina continua até você sair da masmorra. o único problema pode ser o consumo de memória sempre que houver muitas portas e chaves. embora não seja um problema para pelo menos 10 ou 15 chaves.

Por que você simplesmente não usa A * e modela portas trancadas como regiões intransitáveis; depois de pegar a chave (andar no ladrilho da chave?), isso muda a porta trancada em uma região aceitável.

O que isso significa é que o localizador de caminho seguirá a rota mais curta sem chave e, se encontrar as chaves ao longo do caminho, incorporará isso ao caminho, se isso ajudar.

Isso me parece bastante razoável. Não é perfeito, mas é uma solução simples para o problema.