Mostrando alcance na grade hexagonal

10

Aqui está a situação.

Eu tenho placa hexagonal, e uma unidade nela, com velocidade ou valor de movimento. 4.Diferentes terrenos têm um custo diferente. Quando clico na unidade, o jogo deve me mostrar um alcance de movimentação.

Minha solução foi verificar cada hexadecimal no intervalo de 4, com A * pathfinding, e se o custo do caminho for menor que 4, esse hexadecimal estava no range.Finally game agradavelmente me mostra o range dessa unidade.

Minha pergunta é: Existe outra solução para procurar o alcance em grades hexagonais ou quadradas, porque mesmo que eu esteja realmente orgulhoso do que fiz na minha solução, acho que é um pouco exagerado? :))

Observei que, quando a velocidade da unidade é de 4, 6 ou mesmo 8, o tempo para o alcance do computador era realmente bom, mas quando a velocidade era de 10 anos ou mais, notei que precisava esperar alguns segundos para calcular .Bem em jogos reais, eu não vejo algo assim e meu A * pathfinding é bastante otimizado, então estou pensando que minha solução está errada.

Obrigado por todas as respostas.

user23673
fonte
1
Concordo com o Byte56 que um algoritmo de busca em primeiro lugar é uma boa solução. Isso não quer dizer que você não deva tentar ser criativo, mas, no que diz respeito aos algoritmos conhecidos, é bom que se aplique bem.
theJollySin 6/12/12

Respostas:

11

Você está certo de que A * é um pouco exagerado, mas não muito. Você não deveria estar vendo atrasos como está. A * é realmente apenas o algoritmo de Dijikstra modificado . Como você não está usando uma posição final (como sua posição final é "o mais longe possível"), o uso de A * com sua heurística adicional não é necessário. Basta usar o Dijikstra ou uma simples pesquisa de largura será suficiente.

Por exemplo, o Dikikstra se espalhará uniformemente em todas as direções:

insira a descrição da imagem aqui

(Uma primeira pesquisa de largura simples será semelhante a essa)

Acompanhe o custo da viagem para cada nó. Quando um nó tiver o custo máximo de viagem, não processe mais os nós conectados. (Semelhante ao local onde os nós se deparam com a parede abaixo).

Se você estiver enfrentando problemas de desempenho em apenas 10 nós, convém verificar como está acessando os nós. Uma primeira pesquisa abrangente deve ser capaz de navegar centenas de nós sem um atraso perceptível (certamente não alguns segundos). Considere armazenar uma versão simples do seu mundo em formato gráfico, para uma rápida navegação.

MichaelHouse
fonte
você consegue encontrar a distância entre dois nós usando o BFS e levando em consideração obstáculos / pesos diferentes?
Luke B.
O custo da movimentação entre nós deve ser pré-calculado em sua maior parte. O custo não é calculado usando o BFS, o BFS é um algoritmo para percorrer os nós. Como você determina o custo para viajar de um nó para outro é independente de como você percorre os nós.
MichaelHouse
Obrigado, agora entendo por que meu pensamento estava errado, a chave para isso foi esta afirmação "Como você não está usando uma posição final (pois sua posição final é apenas" o mais longe que puder ")". O problema é que, na maioria das vezes, o problema não é resolvido, mas o problema é resolvido, pois o problema não é resolvido, mas o problema é resolvido, o que pode levar a uma falha no processo de instalação do software. Quando minha velocidade aumenta, o número de computações também aumenta muito. A maneira como você me mostra, eu sempre visitarei o nó uma vez.
user23673
4

Amit Patel forneceu um excelente recurso para obter intervalos em seu site . No artigo, ele usa o seguinte algoritmo para coletar blocos hexadecimais em um intervalo:

for each -N  Δx  N:
    for each max(-N, x-N)  Δy  min(N, x+N):
        Δz = xy
        results.append(H.add(Cubex, Δy, Δz)))

Isso cria limites alinhados com a grade hexadecimal:

insira a descrição da imagem aqui

Isso encontrará todos os hexágonos a uma certa distância do hexágono central. Se você quiser considerar obstáculos, use a primeira pesquisa de largura da minha outra resposta.

MichaelHouse
fonte
1

Caso alguém precise, aqui está a implementação em C # do algoritmo de Patel:

IEnumerable<Hex> GetRange(Hex center, int range)
    {
        var inRange = new List<Hex>();
        for (int q = -range; q <= range; q++)
        {
            int r1 = Math.Max(-range, -q - range);
            int r2 = Math.Min(range, -q + range);
            for (int r = r1; r <= r2; r++)
            {
                inRange.Add(center.Add(new Hex(q, r, -q - r)));
            }
        }

        return inRange;
    }
Allan Haugsted
fonte