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

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.

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

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.

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.

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.

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.