Os pensamentos de Amit sobre Grades [Parte 5: Relação entre as Partes da Grade]

by apecode1

Dadas cada uma das 3 partes da grade, nós podemos definir relações com 3 partes da grade, nos dando 9 relações. Há mais relações que você pode definir, porém irei me focar nestas 9. Eu não sei o nome destas relações, portanto eu dei-lhes alguns nomes.

Parte A (preto) Parte B (vermelho)
Face Borda Vértice
Face Vizinhos:
Neighbors of a square		 Fronteiras:
Borders of a square		 Cantos:
Corners of a square
Borda Juntam-se:
Joins of an edge		 Continua:
Continuation of an edge		 Pontos Finais:
Endpoints of an edge
Vértice Toca:
Vertex touching		 Sobressai:
Vertex protrusion		 Adjacentes:
Adjacent vertices

Em seus jogos você poderá utilizar variantes dos que precede. Por exemplo, as relações vizinhos e adjacentes poderiam incluir diagonais. A relação continua poderia incluir bordas que não são colineares com a borda original. Eu escolhi as relações mais simples.

Algoritmos

Cada uma dessas 9 relações pode ser expressa em algoritmos de A para uma lista de Bs; eu os escrevi como A → B1 B2 B3… . Há 3 formas, então isto nos da 27 algoritmos em potencial, expressos aqui de uma forma simples que possa ser traduzida em sua linguagem de programação favorita. Para algumas formas e algoritmos há algumas variantes de A, então eu listarei as regras para cada variante. Por exemplo, faces triangulares vêm nas variantes L e R. Aqui estão todos os algoritmos:

Relação Forma
Quadrado Hexágono Triângulo
Vizinhos:
 (u,v) → (u,v+1) (u+1,v) (u,v-1), (u-1,v) (u,v) → (u,v+1) (u+1,v) (u+1,v-1) (u,v-1) (u-1,v) (u-1,v+1) (u,v,L) → (u,v,R) (u,v-1,R) (u-1,v,R)(u,v,R) → (u,v+1,L) (u+1,v,L) (u,v,L)
Fronteiras:
 (u,v) → (u,v+1,S) (u+1,v,W) (u,v,S) (u,v,W) (u,v) → (u,v,N) (u,v,E) (u+1,v-1,W) (u,v-1,N) (u-1,v,E) (u,v,W) (u,v,L) → (u,v,E) (u,v,S) (u,v,W)(u,v,R) → (u,v+1,S) (u+1,v,W) (u,v,E)
Cantos:
 (u,v) → (u+1,v+1) (u+1,v) (u,v) (u,v+1) (u,v) → (u+1,v,L) (u,v,R) (u+1,v-1,L) (u-1,v,R) (u,v,L) (u-1,v+1,R) (u,v,L) → (u,v+1) (u+1,v) (u,v)(u,v,R) → (u+1,v+1) (u+1,v) (u,v+1)
Juntam-se:
 (u,v,W) → (u,v) (u-1,v)(u,v,S) → (u,v) (u,v-1) (u,v,N) → (u,v+1) (u,v)(u,v,E) → (u+1,v) (u,v)

(u,v,W) → (u,v) (u-1,v+1)

 (u,v,S) → (u,v,L) (u,v-1,R)(u,v,E) → (u,v,R) (u,v,L)

(u,v,W) → (u,v,L) (u-1,v,R)
Continua:
 (u,v,W) → (u,v+1,W) (u,v-1,W)(u,v,S) → (u+1,v,S) (u-1,v,S) Nenhuma borda continua reta em uma grade hexagonal (u,v,W) → (u,v+1,W) (u,v-1,W)(u,v,E) → (u+1,v-1,E) (u-1,v+1,E)

(u,v,S) → (u+1,v,S) (u-1,v,S)
Pontos Finais:
 (u,v,W) → (u,v+1) (u,v)(u,v,S) → (u+1,v) (u,v) (u,v,N) → (u+1,v,L) (u-1,v+1,R)(u,v,E) → (u,v,R) (u+1,v,L)

(u,v,W) → (u-1,v+1,R) (u,v,L)

 (u,v,W) → (u,v+1) (u,v)(u,v,E) → (u+1,v) (u,v+1)

(u,v,S) → (u+1,v) (u,v)
Toca:
 (u,v) → (u,v) (u,v-1) (u-1,v-1) (u-1,v) (u,v,L) → (u,v) (u-1,v) (u-1,v+1)(u,v,R) → (u+1,v) (u+1,v-1) (u,v) (u,v) → (u-1,v,R) (u,v,L) (u,v-1,R) (u,v-1,L) (u-1,v-1,R) (u-1,v,L)
Sobressai:
 (u,v) → (u,v,W) (u,v,S) (u,v-1,W) (u-1,v,S) (u,v,L) → (u,v,W) (u-1,v,E) (u-1,v,N)(u,v,R) → (u+1,v-1,N) (u+1,v-1,W) (u,v,E) (u,v) → (u,v,W) (u,v,S) (u,v-1,E) (u,v-1,W) (u-1,v,S) (u-1,v,E)
Adjacente:
 (u,v) → (u,v+1) (u+1,v) (u,v-1) (u-1,v) (u,v,L) → (u-1,v+1,R) (u-1,v,R) (u-2,v+1,R)(u,v,R) → (u+2,v-1,L) (u+1,v-1,L) (u+1,v,L) (u,v) → (u,v+1) (u+1,v) (u+1,v-1)(u,v-1) (u-1,v) (u-1,v+1)

Relações

(Sinta-se livre para pular esta seção.) As relações listadas a cima são elas mesmas relacionadas umas as outras. Por exemplo, fronteiras vão de faces para bordas, e é o inverso de juntam-se, que vai de bordas para faces. Se alguma borda B está na lista fronteiras de algum A, então A estará na lista juntam-se da borda B. Estas 9 relações podem ser destiladas em 6 relações matemáticas.

Se você tivesse um banco de dados, você poderia expressar as relações diretamente. Por exemplo, aqui está a relação entre faces e bordas de uma pequena grade quadrangular 1×2:

Face Borda
0,0 0,0,S
0,0 0,0,W
0,0 0,1,S
0,0 1,0,W
1,0 1,0,S
1,0 1,0,W
1,0 1,1,S
1,0 2,0,W

Dada a relação, você pode olhar as coisas em cada coluna. Por exemplo, com a tabela a cima, procurando Face==(0, 0) resulta em 4 bordas, que é o que a relação fronteiras expressa. Procurando Borda==(1, 0, W), resulta em 2 faces, que é o que a relação juntam-se expressa. Uma relação é mais geral, e permite que você olhe as coisas de várias maneiras; cada relação(e algoritmo) é uma expressão de uma maneira particular de olhar as coisas.

Dadas 6 relações, deveria então existir 12 relacionamentos. Por que só temos 9? Porque as relações Face/ Face, Borda/ Borda, e Vértice/ Vértice são simétricas então olhando as coisas de outras maneiras produz mesmo resultado. Logo, 3 dos 12 relacionamentos são redundantes, o que nos deixa com 9.

Implementação

Todos os algoritmos são diretos. Como você poderia implementá-los então? Você primeiro irá escolher estruturas de dados para cada um dos três tipos de sistemas de coordenadas. Eu recomendo deixar bem simples e transparente. Todos os sistemas de coordenadas que utilizei possuem um inteiro “u” e um inteiro “v”, e alguns deles tem anotações como “L” ou “W”. Para a estrutura, em Ruby use uma classe com attrs públicas; em Lisp use uma lista; em C use uma struct; em Java use uma classe com campos públicos; em Python use um simples objeto ou dict. Para as anotações, em Ruby ou Lisp use símbolos(‘L ou :L); em C, use caracteres(‘L’) ou uma enumeração (L); em Java, use caracteres; em Python, use strings com um caractere.

O próximo passo é implementar os algoritmos que você precisa. A coisa mais simples a se fazer é escrever funções(ou métodos) que tomem A e retornem uma lista de B. Se houverem múltiplas variantes de A, use uma afirmação switch/case para ramificar para as anotações. Esta é a abordagem mais simples, mas não é a mais rápida. Para tornar as coisas mais rápidas, seu caller deve pré-alocar a lista, ou você pode prover um callback que estejam inline(inglês)(por exemplo, objetos funções STL em C++). Em algumas situações você irá querer procurar o máximo de As ao mesmo tempo então você poderá providenciar um algoritmo que funcione com listas de A que produzam listas de listas de B.

Eu geralmente evito dar implementações, porque elas são muito específicas para cada jogo, mas darei um exemplo da forma do Triângulo em Ruby. Eu escolhi usar uma lista como minha estrutura básica de dados. E eu usei os símbolos em Ruby(como :L) para anotações.

Algoritmo Código Ruby
(u,v,L) →
(u,v+1) (u+1,v) (u,v)(u,v,R) →
(u+1,v+1) (u+1,v) (u,v+1)		 
  def corners(face)
     u, v, side = face
    case side
    when :L 
      [[u, v+1], [u+1, v], [u, v]]
    when :R 
      [[u+1, v+1], [u+1, v], [u, v+1]]
    end
  end

É simples. Cada variante se torna um caso dentro da afirmação “case”.