Devo compartilhar a mesma estrutura de blocos para exibição e localização de caminhos?

8

Eu sei como exibir um mapa 2D com peças.

Eu sei como criar um algoritmo de busca de caminhos usando A *.

Essas duas coisas exigem uma estrutura ou uma classe. Minha pergunta é: você usa a mesma estrutura para exibição e computação de caminho? A estrutura do nó para a busca de caminhos exige a adição de alguns dados: posição x, posição y, F, G, H mais o nó pai. A estrutura do bloco para exibição pode ser otimizada para quase apenas uma informação: o valor do bloco.

Você usa uma classe grande para seus blocos, que lidam com exibição e busca de caminhos, ou você usa um método diferente? Obrigado por seus conselhos!

path-finding tiles data-structure Raveline
fonte
Ótima pergunta, eu realmente precisava aprender isso, mas não sabia o que perguntar.
DFectuoso

Respostas:

6

Minha pergunta é: você usa a mesma estrutura para exibição e computação de caminho?

Não eu não. Você pode obter alguma otimização do cálculo do seu A * diretamente no mapa de blocos, mas não pode usar facilmente seu algoritmo A * para coisas que não são mapeadas diretamente para os blocos. Além disso, significa que você não pode executar o algoritmo A * simultaneamente em vários threads, pois eles acabam compartilhando os dados do mapa. Finalmente, certos métodos de movimentação não permitem a otimização tile = node; um veículo que precise de espaço para dar a volta pode chegar ao mesmo lado de diferentes direções e ter opções diferentes em cada caso - eles não podem ser mesclados em uma pontuação.

Então, sugiro manter os dados separados.

Kylotan
fonte
Embora seja interessante mantê-los separados, você não precisa usar um gráfico explícito para encontrar o caminho, você pode ter um "mapa de peças" com apenas as informações de colisão / custo, totalmente separado da renderização e do modelo lógico. Por exemplo, se você adicionar um objeto ao mundo que não está armazenado no mapa de mosaicos, mas apenas usando as cordas (x, y), ainda poderá colocá-lo no mapa de colisão e usá-lo para a localização de caminhos com base em grade.
Trinidad
3

Do ponto de vista do desenvolvimento de software, é sempre bom manter coisas diferentes separadas .

Para uma solução rápida e suja, junte tudo e comece a trabalhar nas especificidades do jogo.

Para uma solução extensível, mantenha as coisas à parte: você não deseja alterar as classes de blocos porque seu algoritmo de busca de caminhos foi alterado! Mantenha duas estruturas: uma representando blocos de jogo visíveis e outra representando a estrutura de busca de caminhos. Idealmente, um algoritmo de busca de caminho é mantido em baixo nível; portanto, talvez uma matriz de x, y pontos como entrada para o algoritmo seja uma idéia melhor do que fornecê-lo com suas classes de mosaico. O próprio algoritmo pode configurar matrizes para os valores F, G, H.

Penso que, neste caso (e presumo que você se esforça para ser um bom programador), você deve procurar a solução extensível, porque não será necessário muito esforço extra, mas mantém seu código mais limpo e você obtém boas práticas. experiência.

Nef
fonte
2

Certa vez, eu estava construindo um jogo em miniatura no Amiga 500 com 512x512 ladrilhos, mas o jogador só podia mover 8 ladrilhos, então gerei um "mapa de parede" 9x9 "ladrilhos". soldado. Se eu tivesse feito isso com o mapa original, teria que "esclarecê-lo" depois de cada cálculo + a quantidade de memória necessária para ter os dois dados do bloco + os dados de localização de caminho faria com que 512x512 se tornasse um porco muito exigente.

Portanto, não, mantenha as coisas o mais pequenas possíveis e separadas, para que você possa ajustá-las antes. objeto / classe, se necessário. Outra coisa a se pensar também pode ser que alguns de seus objetos em movimento PODEM se mover de maneira diferente sobre certas partes do mapa. Por exemplo. lento na areia, pode / não sabe nadar, pode abrir portas etc.

BerggreenDK
fonte