Algoritmo de processamento dinâmico para jogo de defesa

16

Estou fazendo uma defesa de torre e preciso de um bom algoritmo de correção.

Pensei em Dijkstra, mas preciso de um que seja dinâmico; ele deve poder se atualizar quando uma borda é removida ou adicionada sem um recálculo completo.

Estou codificando em c # se ajudar.

Dani
fonte

Respostas:

8

Geralmente, você deseja usar o A *, a menos que haja algo importante que esteja procurando.

John Haugeland
fonte
Se eu não estou tão familiarizado com A *, como eu lidaria com ambientes em mudança dinâmica? Recalcular em cada quadro? Em colisões?
Justin L.
1
Geralmente você reencaminharia cada quadro em um jogo simples como este. A grade do mapa provavelmente será muito pequena e o número de agentes na casa das centenas. Se acabou sendo um grande problema de desempenho, você poderá otimizá-lo mais tarde, não reconstruindo a árvore, exceto quando necessário.
Coderanger
6
Se for lento, minhas recomendações: não calcule o caminho para cada multidão. Provavelmente, todos estão seguindo o mesmo caminho. Recalco apenas o posicionamento da nova torre, e a torre está no caminho atual . Mesmo assim, faça um re-calc para monstros em pontos no caminho antes da quadra, não para mobs que já passaram e, portanto, não se importam. E então, para encurtar o caminho, você pode limitá-lo para encontrar o caminho para o quadrado após o quadrado bloqueado, já que você já conhece o caminho a partir daí.
Seanmonstar
4
Na verdade, "mob" é a linguagem da indústria (e jogador de MMO / MUD) para "objeto móvel".
3
Independentemente disso, é de longa data, remonta ao MUD1, e padrão o suficiente para ter aparecido em muitas publicações. en.wikipedia.org/wiki/Mob_%28computer_gaming%29
19

Eu precisava resolver um problema semelhante: encontrar caminhos em uma grande grade semelhante a um labirinto, com constantes "custos" e barreiras.

O problema é que, no jogo de defesa de torre, o número de entidades que precisam resolver o caminho para elas é geralmente muito maior que o número de nós no gráfico. A * não é o algoritmo mais apropriado para lidar com isso, porque você precisará resolvê-lo novamente sempre que algo for alterado. Bem, é apropriado se você precisar encontrar apenas um caminho, mas no meu caso eu precisava ser capaz de lidar com entidades que podem aparecer em locais diferentes e cada uma tem seu próprio caminho.

O algoritmo de Floyd-Warshall é muito mais apropriado, embora, para o meu caso, eu escrevi um algoritmo personalizado que, sempre que um nó é alterado, recalcula o custo desse nó de todos os seus vizinhos e, se os vizinhos foram alterados, ele é chamado recursivamente sobre eles.

Então, no início do jogo, eu apenas inicio esse algoritmo em todos os meus nós de "objetivo". Então, sempre que um único nó é alterado (por exemplo, torna-se impossível de passar), eu apenas o aciono nesse nó e a alteração é propagada para todos os nós que serão afetados e, em seguida, interrompida. Portanto, não há necessidade de recálculo global, e o algoritmo é completamente independente do número de entidades que exigirão a busca de caminhos.

Meu algoritmo era basicamente algo como (pseudo-código):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

Com a pontuação inicial, dependendo se o nó é um alvo ou algum tipo de barreira.

Carvalho
fonte
1
Também seria fácil espalhar isso dinamicamente nos quadros à medida que a carga da CPU muda.
22610 tenpn
+1 para A * não sendo o algoritmo certo a ser usado.
Ricket 18/08/10
5

O algoritmo de rota que usei no meu TD foi invertido do caminho A * normal devido ao número de entidades que eu tinha no jogo. Em vez de passar do gol para os bandidos, passei do gol para todos os quadrados vazios do tabuleiro.

Isso não leva muito tempo, você continua repetindo o quadro até encontrar seus "custos" e fornece um bom feedback para rotas bloqueadas (se você estiver fazendo isso). O uso do algoritmo de Floyd é rápido e fácil de armazenar em cache em comparação com o A *, pois não faz pesquisas dependentes de dados, é apenas carregar e operar dados em fluxos.

Comece com seu quadro definido como custo infinito, defina o quadrado da meta como zero e, em seguida, repita o quadro para verificar se uma célula vizinha custa menos que o custo atual mais o custo da viagem. O custo da viagem é onde você coloca sua heurística (no meu caso, o custo de viajar na diagonal era infinito, mas o custo de viajar através de uma torre era alto, então eles eram autorizados a comer através de torres, mas não o faziam, a menos que não tivessem escolha)

Depois de obter sua grade de custos, você pode criar rapidamente uma grade de "fluxo" testando o gradiente de custo mais alto nas células. Isso funciona muito bem para grandes quantidades de bandidos, porque nenhum deles precisa encontrar o caminho, apenas segue as placas virtuais.

Outro benefício é que, dessa forma, você só precisa executar essa tarefa toda vez que ajustar os obstáculos (ou no meu jogo, quando um rastejador come uma de suas torres). Nem toda vez que um creep / mob entra em campo (o que com milhares de monstros e dezenas de segundos seria uma dor de cabeça).

Richard Fabian
fonte
4

A busca de caminhos é rápida e, em algo do tamanho de um jogo de defesa de torre normal, você não terá problemas para executar um passe A * ou Dijkstra completo sempre que algo mudar. Estamos falando bem em um milissegundo para uma atualização completa. Qualquer tipo de busca de caminhos adaptativos acaba terrivelmente complicada. Faça da maneira mais simples, a menos que você esteja na maior grade de defesa de torre do mundo.

ZorbaTHut
fonte
1
Vale a pena notar que a Tower Defense é popular em telefones celulares, onde a busca de caminhos não é rápida. Especialmente em dispositivos um pouco mais antigos, como o Sidekick ou Android 1.6.
Seanmonstar
1
Os desenvolvedores usam algoritmos de busca de caminhos como A * e Dijkstra em hardware muito menos poderoso há décadas (pense em Game Boy). Qualquer telefone novo o suficiente para ter uma tela adequada para jogos não deve ter problema, desde que a implementação seja razoavelmente eficiente. Existem algumas otimizações bacanas discutidas aqui: harablog.files.wordpress.com/2009/06/beyondastar.pdf
Mike Strobel
+1. Cheguei à mesma conclusão quando estava desenvolvendo meu próprio clone DTD. Tentei atualizar os caminhos de forma incremental, mas o algoritmo se tornou muito complexo. Depois de passar um dia nisso, mudei para um recálculo completo em cada alteração. Isso funcionou e, com alguns ajustes, fui capaz de fazê-lo rápido o suficiente.
8114 finnw
2

Isso pode ser um exagero para a sua solução, mas pense em rotear para trás em vez de para a frente.

Em um jogo de TD, os inimigos geralmente estão tentando chegar a um objetivo específico. Rota para trás desse objetivo para o primeiro inimigo e, em seguida, armazene em cache esse caminho. Na geração do caminho para inimigos subsequentes, use o primeiro caminho como ponto de partida e assim por diante. Se você tiver vários pontos de entrada de inimigos, ou vários objetivos, tenha vários caminhos pré-armazenados em cache para começar.

tenpn
fonte
1

A busca de waypoints provavelmente seria a melhor para um jogo td, porque geralmente com base no nível em que o ai segue um caminho direto. Basicamente, você define seus nós ou waypoints, em seguida, tem o ponto "ai" em direção ao waypoiny e caminha até ele, uma vez que se aproxima o suficiente para que ele vá para o próximo waypoint, enfrenta-o e move-se em direção a ele.

Loktar
fonte
Isso funciona apenas para os jogos de TD, onde você só pode colocar torres ao lado do caminho - não para jogos que permitem a colocação de torres em qualquer lugar do tabuleiro.
Iain
Sim, inicialmente o autor não especificou qual o tipo que ele queria, então eu assumi que não era dinâmico.
Loktar 6/10/10
1

Como alguém perguntou, você aborda ambientes de mudança dinâmica recalculando o caminho toda vez que o jogador coloca ou remove uma torre, e você apenas armazena esse caminho na memória nesse meio tempo. O ambiente não muda em todos os quadros.

Observe que alguns jogos de TD têm um caminho definido e não permitem que você coloque torres nele, então eles resolvem encontrar o caminho da maneira mais fácil: codificando um caminho e não permitindo que você o bloqueie :)

Ian Schreiber
fonte
1

Uma solução simples é enganar.

Crie o mapa com antecedência para garantir que não haja becos sem saída. Em cada cruzamento, adicione um gatilho que faça o personagem escolher uma rota (exemplo: sempre vire à esquerda, sempre vire à direita ou aleatório).

MrValdez
fonte
1
Presumivelmente, ele está falando de algo como o Desktop TD, onde o usuário está criando o mapa rapidamente. Ainda para os inimigos "burros", que podem ser uma boa solução, para que você possa tornar inimigos com melhor IA um pouco de dificuldade.
Coderanger