Comment gérer les dépendances entre la carte des tuiles et les unités

J'ai une stratégie 2D basée sur les tuiles en cours d'élaboration. Je me demande comment gérer la relation entre la carte et les unités sur la carte.

Étant donné une coordonnée de tuile, je devrai être en mesure de placer l'unité sur elle, le cas échéant. En même temps, si on me donne une unité, je veux pouvoir obtenir les coordonnées de l'unité.

J'ai vu deux solutions à cela. La première solution serait que les unités stockent une coordonnée et que la carte stocke les références d'unité dans ses tuiles. Cela crée une dépendance cyclique entre la carte et les unités. Je devrais m'assurer que la carte et n'importe quelle unité sont synchronisées si l'unité se déplace.

La deuxième solution consisterait à ce que seules les unités gardent une trace de leurs coordonnées. Pour savoir si une tuile contient une unité et pour obtenir cette unité, je ferais une boucle à travers l'ensemble des unités. J'en trouve une avec les coordonnées correspondantes. Cela supprime la dépendance cyclique, mais il perd la propriété O (1) que la première solution avait pour rechercher des unités sur la carte. Cela peut s'additionner car je veux pouvoir numériser la carte régulièrement pour des choses telles que la recherche de chemin, la détermination de la plage de mouvement et la recherche de cibles valides pour une unité donnée.

Je ne peux pas non plus simplement stocker les unités sur la carte (ou puis-je?). Les unités sont associées à des "armées", soit des joueurs, soit des IA. Une armée devrait pouvoir accéder facilement à toutes ses unités et les parcourir.

Étant donné que cela semble être un problème commun dans les jeux de stratégie, existe-t-il d'autres modèles que les deux que j'ai décrits pour gérer les relations unité / carte?

Ce n'est pas un modèle populaire, mais le monde de la base de données relationnelle offre une troisième façon: utiliser une structure de données qui a plusieurs clés. Sous forme de tableau, cela pourrait ressembler à ceci:

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

Vous voulez pouvoir demander, "où est l'unité 2357?" et récupérez 7,93. Vous voulez également pouvoir demander, "qu'est-ce qui se trouve à l'emplacement 7,93?" et récupérez 2357 et 8552. Il existe des structures de données qui autorisent plusieurs clés pour rechercher les choses. Vous pouvez le stocker en dehors des unités et en dehors de la carte si vous souhaitez supprimer les dépendances.

Cependant, dans la pratique, il est plus courant de stocker l'emplacement dans chaque unité, puis d'utiliser latéralement une structure de données de partitionnement spatial qui vous indique quelles unités se trouvent dans une région donnée. Puisqu'il s'agit d'une structure distincte, les régions ne doivent pas nécessairement être des espaces de grille; il peut s'agir de zones plus grandes.

Je recommande de faire ce qui est le plus simple (votre deuxième solution), puis plus tard, si c'est un problème de performances, vous pouvez ajouter une partition spatiale pour accélérer les recherches.

Eh bien, sauf si vous avez plusieurs milliers d'unités par joueur, je ne me soucierais pas de l'utilisation de la mémoire et n'utiliserais pas la première solution. La mémoire est moins chère que le CPU semble-t-il.

En fait, même si vous aviez 4000 unités par joueur, en utilisant deux entiers pour y stocker l'emplacement et 8 joueurs, cela ne prend que 2 Mo, mais avec la première solution, vous pouvez utiliser un getter de coordination O (1), plutôt que O (n) (en supposant non trié), qui avec beaucoup d'unités pourrait être lent.

La plupart des jeux semblent être basés sur des pixels plutôt que sur des tuiles, maintenant il y a quelques jours, ils n'ont plus besoin que de l'unité pour stocker les coordonnées.