Encontrar células dentro do alcance na grade hexagonal

8

Primeiro - eu sei que estou sendo superdensa aqui.

Com isso fora do caminho, estou tentando escrever uma implementação em C # deste algoritmo:

var results = []
for each -N  dx  N:
  for each max(-N, -dx-N)  dy  min(N, -dx+N):
    var dz = -dx-dy
    results.append(cube_add(center, Cube(dx, dy, dz)))

Eu tirei isso deste tremendo recurso.

Meu problema é que todas as implementações que tentei até agora tiveram resultados loucos. Por exemplo, o código mostrado abaixo atualmente resulta nisso:

1 1

e isto:

2

Meu código atualmente fica assim:

for (int x = this.CellPositionX - distance; x <= this.CellPositionX + distance; x++)
    {
        for (int y = this.CellPositionY - Math.Max(-distance, -x - distance); y <= this.CellPositionY + Math.Min(distance, -x + distance); y++)
        {
            HexPosition rangePosition = new HexPosition(x, y);
            range.Add(rangePosition);
        }
    }

Alguém pode encontrar algo errado aqui? Todas as sugestões são bem-vindas. Eu tenho batido minha cabeça nisso há um tempo agora.

Obrigado!

Nota atualizada: estou usando coordenadas axiais na grade. Atualização # 2: como indicado abaixo, eu tive meu loop for..each errado e não estava usando deltas para o trabalho. Obrigado pela ajuda!

Atualmente, tenho um problema, como mostrado abaixo, com a implementação das respostas: insira a descrição da imagem aqui

Vou continuar investigando - se eu descobrir, postarei os resultados completos aqui. Obrigado a todos!

ligação aaron
fonte
11
Obrigado pelo recurso que parece realmente bom! Fiquei um pouco impressionado quando percebi que quase todos os gráficos eram interativos. :)
Christer
3
O exemplo que ele fornece usa coordenadas de cubo, enquanto parece que você está usando coordenadas de deslocamento ou axiais. Você precisa converter x, y, z das coordenadas cúbicas que ele possui para qualquer sistema de coordenadas que você estiver usando.
AlexScottman #
11
@ Vector57 Estou usando o Axial. Na seção de conversão, é mencionado que eu não preciso fazer nada com a propriedade Z e que q / reex / y são intercambiáveis ​​... ou eu entendi errado isso?
Aaron-ligação
Parece assim, embora nos exemplos ele use r = z, mas não vejo por que deveria importar qual você escolher.
Alex Sherman

Respostas:

4

Portanto, após uma inspeção mais aprofundada, seu problema não tem nada a ver com conversões do sistema de coordenadas. Isso poderia ter ficado mais claro se você não nomeasse as coordenadas axiais X e Y, mas sim com Q e R. O problema que você está enfrentando são as más condições de loop. O exemplo de código original produz delta qs e rs que você tenta converter, em seus loops for, em coordenadas absolutas e cometeu um erro. O algoritmo deve ter a seguinte aparência:

for (int dx = -distance; dx <= distance; dx++)
{
    for (int dy = Math.Max(-distance, -dx - distance); dy <= Math.Min(distance, -dx + distance); dy++)
    {
        HexPosition rangePosition = new HexPosition(
            this.CellPositionX + dx, this.CellPositionY + dy);
        range.Add(rangePosition);
    }
}
Alex Sherman
fonte
Oh derp ... o artigo ainda menciona que eles são valores delta :( Vou tentar fazer isso agora e ver como ele vai Thanks :).
Aaron-bond
Obrigado por isso. É definitivamente muito mais próximo da maneira correta de fazê-lo. Ainda estou bagunçando as coordenadas, mas pelo menos tenho o número certo! Por alguma razão, estou terminando com uma célula muito alta no -x e muito baixa no + x. Publiquei uma foto no topo, se você souber alguma coisa, mas continuarei a me investigar de qualquer maneira :) obrigado pela ajuda!
Aaron-ligação
Você está interpretando corretamente as coordenadoras axiais? Lembre-se de que você optou por usar x e y em vez de x e z; portanto, se o restante do seu código não responder por essa alteração nos exemplos, isso pode resultar em um comportamento estranho.
Alex Sherman
Sim, eu mudei para que sejam x e z. dx torna-se x e z = -dx - dy ...
aaron-bond
11
A nova foto que você postou mostra 7 hexágonos realçados. Isso é o que você esperaria com a distância = 1. Tente imprimir os valores. Com CellPosition definido como 0,0 e distância 1, os hexágonos obtidos devem ser (-1, 0); (-1, 1); (0, -1); (0, 0); (0, 1); (1, -1); (1, 0)
amitp 03/02
7

Como Vector57 observou, o problema é que você está usando o sistema de coordenadas errado . O algoritmo descrito deve ser usado com coordenadas de cubo , que possuem componentes x, ye z :

coordenadas do cubo

Isso pode não ser óbvio no pseudocódigo do algoritmo, mas é porque é uma simplificação disso :

var results = []
for each -N  dx  N:
    for each -N  dy  N:
        for each -N  dz  N:
            if dx + dy + dz = 0:
                results.append(cube_add(center, Cube(dx, dy, dz)))

... um loop aninhado simples sobre x, ye z, o que você esperaria de um algoritmo de intervalo.

Não sei qual sistema de coordenadas você está usando, mas acho que é um dos sistemas de "coordenadas de deslocamento", que são populares porque são fáceis de implementar, colocando as células da grade dentro de uma matriz 2D:

deslocamento q layouts verticais

Isso não significa que você não pode usar esses algoritmos de cubo; significa apenas que você precisa converter as coordenadas do cubo para as suas . Por exemplo, para converter de / para o layout vertical "ímpar-q", use estes:

# convert cube to odd-q offset
col = x
row = z + (x - (x&1)) / 2

# convert odd-q offset to cube
x = col
z = row - (col - (col&1)) / 2
y = -x-z
congusbongus
fonte
Tive a sensação de que era algo assim. Havia uma parte dessa página que mencionava a conversão de Cube para Axial e dizia apenas remover a parte z e os q e r restantes se tornam x e y. Eu acho que devo ter simplificado demais lá. Obrigado por isso. Excelente explicação do que estava faltando. Vou tentar depois! :)
aaron-bond
Acabei de dar uma olhada e estou usando axial. Certamente, como o algoritmo não menciona Z, também é um sistema direto q = xe r = ytambém?
Aaron-bond