Obter anel de azulejos na grade hexagonal

17

Graças a este post: ladrilhos hexagonais e encontrando seus vizinhos adjacentes , sou capaz de coletar ladrilhos adjacentes a um determinado ladrilho. Mas estou praticamente preso a um algoritmo que me fornece apenas um "anel" de blocos especificado por um deslocamento. O algoritmo fornecido na publicação Stack Overflow não se importa exatamente com a ordem em que ele coleta os blocos.

Eu sei que a cada deslocamento são adicionados 6 blocos.

  • O deslocamento 1 fornece 6 blocos (os primeiros blocos adjacentes).
  • O deslocamento 2 fornece 12.
  • O deslocamento 3 fornece 18, etc.

Há um crescimento constante de 6 em cada deslocamento. Então, eu suponho que deve haver uma regra que se adapte a essas compensações. Não consigo entender exatamente isso. Qualquer um?

Sidar
fonte

Respostas:

23

Um anel hexagonal com raio de N consiste em 6 linhas retas, cada uma com comprimento N - veja meu exemplo extremamente bruto abaixo :) Para N = 2:

insira a descrição da imagem aqui

As setas cobrem 2 hexágonos cada.

Suponho que você tenha algumas funções que fornecem o bloco vizinho em uma direção específica, como norte (), sudeste () etc. Portanto, seu algoritmo, no pseudocódigo, deve ser algo como isto:

var point = startingPoint.north(N)
for i = 0..N-1:
    result.add(point)
    point = point.southeast(1);
for i = 0..N-1:
    result.add(point)
    point = point.south(1);
for i = 0..N-1:
    result.add(point)
    point = point.southwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.northwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.north(1);
for i = 0..N-1:
    result.add(point)
    point = point.northeast(1);

Observe que isso deve funcionar também para casos de borda N = 1, retornando 6 blocos e N = 0 retornando um conjunto vazio.

Eu sei que o código não é perfeito :) Há alguma redundância aqui. Nos meus projetos usando mapas lado a lado regularmente (hexagonais ou outros), geralmente tenho uma enumeração "Direction", que me permite fazer isso de maneira mais suave:

var point = startingPoint.inDir(N, Direction.North)
var dir = Direction.SouthEast.
for d = 0..Direction.count():
    for i = 0..N-1:
        result.add(point)
        point = point.inDir(1, dir);
    dir = nextDirection(dir);
Liosan
fonte
Isso deve me empurrar na direção certa. Obrigado!
Sidar 18/03/2013
2
Observe que o exemplo de código adicionará pontos duplicados para os cinco primeiros segmentos. No entanto, é uma boa resposta.
MichaelHouse
@ Byte56 Sim, eu imaginei. Mas pelo menos vejo a conexão entre mudanças de direção!
Sidar 18/03/2013
1
@ Byte56 Realmente? Hum. Tentei evitar esse ... 0..N-1 dá 0..1 para N = 2, então isso é i = 0 e i = 1, que são 2 valores. 2 valores de cada vez 6 direções são 12 peças, como deveria ser ...?
Liosan 18/03
Não. Você está certo. Como cada loop está adicionando um ponto do último loop, eu estava um fora para os loops, meu erro. É um algoritmo inteligente.
MichaelHouse
2

Eu achei este artigo uma excelente referência para algoritmos de grade hexagonal, e sua seção "Distâncias" fornece um método para determinar o número de etapas entre dois blocos. Se você converter suas coordenadas axiais (xy) em coordenadas do cubo (xyz), a distância será sempre igual à maior das compensações de coordenadas entre os dois blocos, ou max (| dx |, | dy |, | dz |).

O(n2)

insira a descrição da imagem aqui

KPM
fonte