Desempenho lento em uma implementação A * em um jogo de defesa de torre

9

Estou fazendo um jogo de Tower Defense em Flash sem caminho predefinido.

Embora minha grade seja 40x40 (pequena?), A * está tendo dificuldades ao recalcular todas as vezes. Então, eu fiz minha própria modificação para facilitar o recálculo e a contagem de células tocadas caiu para cerca de 900 (ao modificar perto da raiz). Ainda congela por um período muito curto, mas detectável, quando uma nova torre é colocada.

Isso é um problema de implementação ou 40x40 é demais?

Editar:

A estrutura do meu código:

  • Todos os dados são salvos na 2ª matriz de células.
  • Cada célula contém seu pai na direção do caminho (1-8 no sentido horário) e a matriz codificada em bits dos seus filhos no caminho (cada bit representa um filho).
  • A busca é realizada por A * com a estimativa da distância euclidiana.
Dani
fonte
Você precisará ser muito mais específico aqui. Não temos idéia de como é o seu código, de como está estruturado etc., e, portanto, não podemos tirar conclusões sobre o que o torna lento.
Sean James
11
Quando implementei o A * pela última vez, lembro-me de rodar em uma grade de 64x64 em no máximo 1ms. Então, sim, parece haver um problema com sua implementação. Sugiro que você publique seu código ou a essência dele para que possamos ajudá-lo ainda mais.
Marc Müller
Veja a edição que adicionei
Dani
11
Se 40x40 for muito lento, é provável que você esteja fazendo algo muito errado. Publique o seu código ou crie um perfil. Como alternativa, aumente a escala e veja o que acontece - se uma grade de 80x80 demorar mais de quatro vezes mais, você terá algo extremamente danificado.
ZorbaTHut
O título pode ser um pouco mais informativo, por favor?
22410 dezpn

Respostas:

4

Não posso comentar, mas primeiro perfil no Flex, todo o resto é conjectura.

Jonathan Fischoff
fonte
Como posso criar um perfil do projeto flash no flex?
Dani
Sim e não. Não acho que você carregue o projeto flash diretamente. Eu acho que você pode ser capaz de criar um perfil do swf sem fonte e ainda obter informações sobre o nível da função. Eu faria uma pesquisa no google por "criar um perfil de um projeto em flash no flex" ou algo parecido. Eu fiz e consegui: flexblog.edchipman.ca/… que parece promissor.
Jonathan Fischoff
Obrigado, realmente me ajudou a encontrar a parte problemática (não estava no algoritmo, veja o comentário em questão)
Dani
13

Estou assumindo que TD é 'Tower Defense'

Eu acho que A * está exagerando nisso.

No início do jogo, preencha a área do jogo a partir dos pontos de saída para criar um mapa de movimento:

 |---------|
 |5|4|3|3|3|
 |5|4|3|2|2|
->5|4|3|2|1->
 |5|4|3|2|2|
 |5|4|3|3|3|
 |---------|

e o movimento é sempre em direção a um quadrado com um valor menor.

Quando o jogador coloca uma torre, atualize cada um dos oito quadrados adjacentes: para cada quadrado, defina seu valor de movimento como um a mais que o menor valor adjacente. Se o valor mudar, repita o processo centralizado no quadrado atualizado. Em seguida, para verificar se a rota para a saída não está bloqueada, verifique se todos os quadrados estão adjacentes a um quadrado de valor mais baixo.

Quando o jogador remover uma torre, defina o valor do movimento como um a mais que o quadrado adjacente mais baixo e repita o processo acima.

Uma abordagem mais simples seria refazer o preenchimento da inundação.

Skizz
fonte
6
Refazer o preenchimento é mais caro do que fazer A * para um pequeno número de unidades - aproximadamente o comprimento da placa - pelo menos em termos algorítmicos (e como esse é o Flash, constantes não algorítmicas como o layout da memória provavelmente podem ' t ser usado com muita eficácia). No entanto, esse é um modelo muito bom para muitas unidades de comunicação e é chamado de difusão colaborativa - scalablegamedesign.cs.colorado.edu/wiki/Collaborative_Diffusion .
@ Joe Wreschnig: uau link legal. Eu usei essa técnica antes, mas nunca soube como ela era chamada. Obrigado.
22810 dezpn
@ Joe, desde que haja pelo menos algumas barreiras no mapa, não acho que isso seria mais ineficiente do que chamar A *. Ou seja, acredito que apenas para um mapa aberto, quase sem barreiras e com poucas unidades, pode ser pior.
EdA-qa mort-ora-y
@edA: Por definição, um preenchimento de inundação deve eventualmente tocar em todos os pontos acessíveis no mapa; A * fornece limites superiores comprovados para quantos pontos ele deve tocar, que é no máximo todos os pontos acessíveis no mapa e geralmente muito menos. O preenchimento de inundação é um algoritmo mais simples para otimizar coisas como layout de memória, mas, como eu disse, no Flash, isso provavelmente não importa.
@ Joe, é o que estou argumentando é que, mesmo com apenas algumas torres, o A * provavelmente tocará em quase todos os espaços. Mas para N monstros, é necessário apenas exceder total_squares / N para ser menos eficiente que o preenchimento de inundação.
EdA-qa mort-ora-y
2

Estranho, pensei ter respondido a isso, mas a resposta parece ter sumido. Faça seu algoritmo de busca de forma que possa ser atualizado em várias etapas, para que, quando você posicione uma torre e reproduza uma animação, faça um pouco de cada quadro e tenha entre meio segundo e um segundo para atualizar seu A * sem uma pausa perceptível. É latência - se você não pode acelerar, encontre uma maneira de escondê-lo. Reproduzir uma animação ao colocar uma torre seria natural para um jogo e seria um bom lugar para escondê-lo.

Kaj
fonte
Essa é uma boa ideia em geral, mas é ruim para essa questão específica. Um * em uma grade tão pequena deve ser quase instantâneo, não demorando muito tempo.
davr
Justo. É a única resposta que eu poderia dar que resolveria o problema sem conhecer os detalhes da implementação que causariam a desaceleração.
Kaj
0

Para começar, você pode alterar sua matriz para um vetor - deve fornecer algumas melhorias de velocidade. Poste o código e poderemos sugerir mais otimizações.

Iain
fonte
0

Eu acho que o seu abrandamento é porque você está calculando um caminho para todos os caracteres simultaneamente. O cálculo de um caminho para um personagem é rápido, mas se houver duas dúzias de caracteres na cena, isso poderá ocorrer.

Em vez disso, você deve distribuir a carga por alguns quadros. Escale suas atualizações de IA para que personagens diferentes atualizem seu caminho em quadros diferentes. Seria realmente perceptível se um personagem não reagisse até um segundo depois, mas apenas um quadro não causaria reações ruins.

jhocking
fonte
Isso foi respondido quase um ano atrás e só foi prejudicado por causa do trabalho de edição de Grace. (Não tinha nada a ver com muitos caracteres.)
Obrigado por me avisar. Não notei as datas.
jhocking