Armazenando uma grade hexadecimal

10

Estou criando uma pequena estrutura de grade hexadecimal para o Unity3D e cheguei ao seguinte dilema. Este é o meu sistema de coordenadas (retirado daqui ):

insira a descrição da imagem aqui

Tudo funciona muito bem, exceto pelo fato de eu não ter idéia de como armazená-lo. Originalmente, pretendia armazenar isso em uma matriz 2D e usar imagens para gerar meus mapas.

Um problema era que ele tinha valores negativos (isso era facilmente resolvido deslocando um pouco as coordenadas).

No entanto, devido a esse sistema de coordenadas, essa imagem ou bitmap teria que ser em forma de diamante - e como essas estruturas são quadradas, isso causaria muitas dores de cabeça, mesmo que eu cortasse alguma coisa. Falta alguma coisa que possa corrigir isso? Lembro-me de ver uma postagem no fórum sobre isso nos fóruns da unidade, mas não consigo mais encontrar o link.

Escrever um conjunto de tradutores de coordenadas é a melhor solução aqui?

Se vocês acham que seria útil, posso postar código e imagens do meu problema.

PeeC
fonte
1
Você não pode simplesmente salvar imagens PNG transparentes em torno de hexágonos?
Markus von Broady
Meu principal problema ao salvar em pngs e matrizes é a quantidade de "espaço em branco" que eles precisariam conter para manter esse sistema de coordenadas intacto.
PEEC
1
Se "espaço em branco" significa pixels transparentes, por que a quantidade é um problema?
Markus von Broady
Esse é um ponto muito bom. A maioria dos formatos de imagem não gasta tanta memória armazenando padrões repetidos. Mas ainda assim, ligeiramente irrita-me que para armazenar este mapa eu estou usando esta quantidade de memória (pixels cinza são espaço vazio, outras cores são coordenadas hexadecimais válidos).
PeeC
1
Ah, você está armazenando os dados da grade, não imagens de mosaico! Por que você não apenas salva suas estruturas de dados (grade) em um arquivo binário ou codifica-as usando, por exemplo, JSON e as salva em um arquivo de texto? Mas não conheço as capacidades do Unity. Além disso, convém confirmar isso, mas acredito que uma área da mesma cor seja otimizada (compactada livremente) no formato PNG.
Markus von Broady

Respostas:

9

As coordenadas do paralelogramo que você está usando são mais fáceis de trabalhar, mas elas têm a desvantagem de serem estranhas para mapas retangulares. Uma abordagem é armazená-lo com as coordenadas de deslocamento, mas na verdade use coordenadas de paralelogramo na lógica do jogo.

Observação: em cada linha do mapa, os dados da grade são contíguos. Todo o espaço desperdiçado está à esquerda e à direita.

Solução: nessa linha, armazene dados começando na coluna mais à esquerda, em vez da coluna marcada com 0. Calcule a primeira coluna do mapa retangular em seu sistema de coordenadas e subtraia-o da coordenada da coluna para determinar para onde vai na matriz. Isso funciona também para coordenadas negativas da coluna.

Execute a conversão no getter e setter para o mapa, com algo como isto:

inline function get(q, r) {
    first_column_in_this_row = -floor(q/2);
    return array[r][q - first_column_in_this_row];
}

Você precisará modificá-lo para trabalhar com a sua escolha de coordenadas e mapa (preste atenção em uma diferença). Em alguns layouts, você deseja deslocar as colunas pela linha em vez de vice-versa.

Você pode usar o mesmo truque para criar mapas de outras formas; não é limitado a retângulos.

Se você estiver usando C ou C ++, poderá usar a aritmética dos ponteiros para tornar isso mais rápido. Em vez de armazenar uma matriz de ponteiros em matrizes, armazene uma matriz de ponteiros que foram ajustados por first_column_in_row. (Isso pode não ser portátil)

amitp
fonte
Isso funciona até onde eu sei, no entanto, a matemática era realmente estranha. Depois de experimentar várias equações que faziam sentido na minha cabeça, decidi yIndex = y-((x%2==0)?(x/2-x):(-x/2)-1)após algumas tentativas e erros. Não faço ideia de como isso funciona.
PEEC
Faça isso yIndex = y-((x%2==0)?(-x/2):(-x/2)-1). x / 2 é todo baseado em número inteiro, portanto, não é necessário andar.
PeeC
6

Pessoalmente, eu preferiria a simplicidade do que economizar memória. Não otimize até que seja necessário!

Se você ainda deseja economizar alguns bytes, veja como fazê-lo:

insira a descrição da imagem aqui

  1. Corte o paralelogramo ao meio para formar dois triângulos retângulos
  2. Reorganize os dois triângulos para formar um retângulo.
  3. (Observe que eu adicionei a faixa verde de buffer para que a matemática funcione bem.)

Código Python para mapear coordenadas retangulares para coordenadas de paralelogramo e vice-versa:

# Height of rectangle
H = 15

def r2p(x, y):
"rectangle to parallelogram"
if y < -x/2 + H:
    y = y + H
return (x - 1, y)

def p2r(x,y):
"parallelogram to rectangle"
if y >= H:
    y = y - H
return (x + 1, y)
Leftium
fonte
2
Você também pode apenas mover os pixels verticalmente para baixo - na imagem que seriaoffsetY = Math.floor ( (x+1)/2 )
Markus von Broady
1

Não é necessário distorcer seu mapa, pois a conversão entre coordenadas retangulares e "canônicas" é rápida e fácil. Aqui está um link para uma introdução sobre como fazê-lo:

Convertendo entre coordenadas hexagonais retangulares e canônicas

Essa técnica combina avaliação lenta com armazenamento em cache de conversões calculadas.

Pieter Geerkens
fonte