Como gerenciar dependências entre o mapa e as unidades do bloco

Eu tenho uma estratégia baseada em blocos 2D em andamento. Estou pensando em como lidar com o relacionamento entre o mapa e as unidades no mapa.

Dada uma coordenada de ladrilhos, precisarei conseguir colocar a unidade nela, se houver. Ao mesmo tempo, se for dada uma unidade, desejarei obter a coordenada da unidade.

Eu já vi duas soluções para isso. A primeira solução seria fazer com que as unidades armazenassem uma coordenada e a unidade de armazenamento do mapa fizesse referência em seus blocos. Isso cria uma dependência cíclica entre o mapa e as unidades. Eu precisaria garantir que o mapa de qualquer unidade seja mantido sincronizado se a unidade se mover.

A segunda solução seria apenas fazer com que as unidades controlassem suas coordenadas. Para saber se um bloco contém uma unidade e para obtê-la, eu percorreria todo o conjunto de unidades, encontrando uma com coordenadas correspondentes. Isso elimina a dependência cíclica, mas perde a propriedade O (1) que a primeira solução possuía para procurar unidades no mapa. Isso pode aumentar, já que eu quero poder escanear o mapa regularmente em busca de coisas como localização de caminhos, determinação da amplitude de movimento e localização de alvos válidos para uma determinada unidade.

Também não posso apenas armazenar as unidades no mapa (ou posso?). As unidades estão associadas a "exércitos", jogador ou IA. Um exército deve ser capaz de acessar e interagir facilmente sobre todas as suas unidades.

Como esse parece ser um problema comum nos jogos de estratégia, existem outros padrões além dos dois que descrevi para gerenciar relacionamentos de unidade / mapa?

Não é um padrão popular, mas o mundo dos bancos de dados relacionais oferece uma terceira maneira: use uma estrutura de dados que possua várias chaves. Em forma de tabela, pode ser assim:

Unit id    Location
-------------------
  1309     13,15
  2357      7,93
  8552      7,93

Você quer poder perguntar: "onde está a unidade 2357?" e volte 7,93. Você também pode perguntar: "o que há no local 7,93?" e volte para 2357 e 8552. Existem estruturas de dados que permitem várias chaves para pesquisar as coisas. Você pode armazenar isso fora das unidades e fora do mapa, se desejar remover dependências.

No entanto, na prática, é mais comum armazenar a localização em cada unidade e, ao lado, usar uma estrutura de dados de particionamento espacial que informa quais unidades estão em uma determinada região. Como é uma estrutura separada, as regiões não precisam ser espaços de grade; eles podem ser áreas maiores.

Eu recomendo fazer o que for mais fácil (sua segunda solução) e, posteriormente, se for um problema de desempenho, você poderá adicionar uma partição espacial para acelerar as pesquisas.

Bem, a menos que você milhares de unidades por jogador, eu não me preocuparia com o uso de memória e usaria a primeira solução. A memória é mais barata que a CPU, ao que parece.

De fato, mesmo se você tivesse 4000 unidades por jogador, usando dois números inteiros para armazenar a localização e 8 jogadores, isso leva apenas 2 MB, mas com a primeira solução, você poderá usar um getter de coordenadas O (1), em vez de O (n) (assumindo uma classificação), que com muitas unidades pode ser lenta.

A maioria dos jogos parece ser baseada em pixels, em vez de lado a lado, hoje em dia, então eles só precisam que a unidade armazene as coordenadas.