algo de grilles, chunks, dichotomie, scalabilité horizontale, kamoulox

Salut,

Je suis en train de développer le premier prototype de mon jeu, je pense que dans quelques temps j'aurai trouvé une solution, bonne ou mauvaise, ou esquivé le problème, mais recueillir des avis extérieurs ça ne peut être que bon je pense.

Le problème :



Je suis en vue 2d et je compte représenter des planètes/astéroides/machinsFlottants par des grilles (C), capables de se connecter entre elles quand elles se touchent, pour ne former plus qu'une seule grille.

J'ai découpé les grilles en plusieurs niveaux (D), c'est à dire, un bloc rouge contient 4 blocs verts, un bloc vert 4 bleus, un bleu 4 blocs de matière.

Ces différents niveaux me permettent, en ayant de "plutôt grandes planètes" :

- de découper les calculs sur plusieurs serveurs

- d'optimiser le calcul des collisions (je ne calcule la collision entre deux blocs de matière que si leurs parents, grands-parents etc... sont en contact)

- d'optimiser l'affichage en cas de dézoom (A,B), par exemple si j'ai beaucoup dézoomé, je pourrais ne voir qu'un pixel de la couleur moyenne d'un groupe, et peut-être ne charger que ça en mémoire aussi.

J'arrive bien à afficher les blocs, à détecter les collisions, mais je galère pour établir les liens entre eux. Par exemple, en (E), je voudrais connaitre les voisins du bloc jaune. Pour les deux qui sont dans le même bloc bleu j'y arrive facilement, mais pour les autres c'est plus compliqué. Faudrait get parent.copainDuBas.hautAGauche et get parent.parent.copainDeGauche.hautdroite.basdroite.

Je pense qu'il y a des chances que j'arrive à décortiquer le truc pour pondre un algo à force de batailler, mais je me demandais si j'étais pas sur une mauvaise voie carrément, et je voulais avoir vos humbles avis, en matière d'algos surtout, et si jamais d'autres devs ont eu ce problème sur un certain jeu, etc

Je pense que si je bloque trop longtemps je sauterai cette optimisation pour le premier prototype, quitte à m'y remettre juste après.

Merci pour votre attention.


edits :

- Peut-être qu'une solution intermédiaire serait de ne faire que deux niveaux (comme dans minecraft je crois), des tronçons de 16x16x256 blocs. Mais ce serait moins optimisé pour la détection des collisions et le zoom-dézoom.

- Peut-être que je devrais ajouter des objets "liaison" entre chaque bloc, pour chaque niveau, et calculés en amont.

En gros tu fais un quadtree like, mais il te faut aussi un moyen d'avoir un système de double liste chaînée en même temps.

Alors déjà, un morceau qui contiens que 4 tiles, ça me semble totalement useless.
Dis toi que la plupart de tes algos, la partie qui va les ralentir, c'est les accès aux voisins en dehors du même "chunk".
Donc si tes chunks sont ridiculement petits, tu vas passer ta vie a faire ça.
Au final, ton truc risque d'être plus lourd avec le chunking que si t'avais juste un gros bout de map dans un bête tableau.

Pour te donner une idée, dans centauri, j'ai des chunks de 128x128 tiles, et c'est très très performant.
Je suis même pas sur que le système de quadtree soit réellement nécessaire, il faudrait vraiment faire des benchs avec les maps les
plus grosses possibles, mais surtout avec des algorithmes qui tournent dessus (je ne sais pas encore au dela des collisions ce que tu
comptes faire).

Oui t'as tout compris. (quadtree... tu as placé un mot sur mon idée, ce qui va me permettre de fouiner les internets de manière plus ciblée  )

C'est vrai qu'un morceau de 4 blocs a pas l'air rentable,
et même chose pour la hauteur de l'arbre qui va augmenter rapidement avec la taille de la map.

En fait je cherche à faire un moteur bien solide dès le début, pour pas avoir de surprises au moment où les maps vont s'agrandir.
C'est pour ça que j'ai essayé de partir sur quelque chose de complètement récursif, mais c'est peut-être un peu extrême.

Je pense que je vais zapper le quadtree pour mon prototype, faire de petites maps et un début de gameplay.

J'essaierai de découper en chunks dans un deuxième temps. Je peux p'tet toujours faire un arbre, mais pas quad... genre 128-tree

Je lis quand même sur wikipedia que les quadtrees sont utilisés dans les programmes de simulation du jeu de la vie de Conway. Or, ce type de jeu demande principalement de connaitre ses voisins, non ? ^^

Je dois t'avouer que j'ai un peu du mal a imaginer comment utiliser un quadtree pour optimiser un GoL.
Surtout qu'en général on utilise plutôt des Gigantic Lookup Tables.

En tout cas y a tout un article et ça a l'air intéressant, je regarderais ça dès que j'aurais un peu de temps:
http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478

Il y a l'air d'avoir pas mal de réponses a tes questions dedans.

Sinon oui, a mon avis t'as tout intérêt a partir sur une version gameplay avant tout.
Parfois la version simple d'un algo marche déjà très bien, il vaut mieux passer beaucoup de temps sur une optimisation quand on est sur d'en avoir besoin.
A mon sens partitionner le monde en grille devrait être suffisant, même pour un très gros monde. C'est ce que font la majorité des sandbox en l'état.
Surtout qu'une fois le monde découpé, tu peux apporter d'autres optimisations en fonction du contexte.

Par exemple, tu peux stocker des entités statiques alignées à la grille dans un tableau dynamique trié, et faire une recherche dichotomique pour un accès très rapide.
C'est ce que j'utilise dans centauri pour représenter le feu, les "petites herbes" et les minerais par exemple. Comme ce sont des éléments qui ont pas besoin d'être accédé fréquemment, et qu'il y en a généralement peu ou pas du tout, il vaut mieux utiliser cette approche plutôt qu'une grille (qui sera presque toujours remplie de vide), on a des accès logarithmiques plutôt que constants mais ça suffit.

Ainsi dans un chunk j'ai de nombreux "sous systèmes", adaptés en fonction du besoin.
Dans ton cas, tu peux te contenter par exemple d'un système de partitionnement pour optimiser les collision dans un chunk, sans avoir a faire N sous chunks.

Bref, le plus important ça va déjà être de voir ce qui va bouffer les perfs, avant de faire de l'over engineering.
Si ça se trouve, t'auras majoritairement besoin d’accéder a tes voisins, et le reste ne sera pas si lourd que ça.

onilink_ a écrit:

Ainsi dans un chunk j'ai de nombreux "sous systèmes", adaptés en fonction du besoin

Hé ouais, le besoin avant tout...

onilink_ a écrit:

Par exemple, tu peux stocker des entités statiques alignées à la grille dans un tableau dynamique trié, et faire une recherche dichotomique pour un accès très rapide.

C'est de l'indexation en gros si j'ai bien compris.

En tout cas merci pour l'article et le nouveau mot Gigantic lookup table que j'ajoute à mon arc.

Ca va m'aider à faire quelques de plus

Chulien a écrit:

C'est de l'indexation en gros si j'ai bien compris.

Je suis pas sur que ce soit le mot (c'est un peu un mot valise), mais en gros c'est simple.
Quand t'as des entités a stocker sur un monde 2d, tu veux généralement faire certaines actions:
- récupérer les entités une a une
- ajouter une entité a une certaine position
- trouver une entité a une certaine position

En général, c'est le 3ième point qui peut poser soucis.
Si t'as des entités dynamiques, tu vas avoir une liste de bounding boxes, et sans partitionnement, eh bien il va falloir parcourir le tout, un a un, et faire un test de collision pour chaque élément.
On a donc un algorithme de complexité linéaire.

Quand t'as des entités de même taille et sur la grille, il y a alors deux solutions simples qui viennent a l'esprit.
Utiliser une tilemap (tableau 2d). Y a pas plus performant pour le 3ieme point, vu que c'est un accès constant.
Par contre, ben pour une grille de taille donné tu auras Width x Height éléments, même si t'as zero entités.
Et pour le premier point il faudra parcourir tous les éléments un à un, ce qui est pas forcement une bonne chose si tu veux accéder a tes entités constamment.
Bref, comme son nom l'indique, une tilemap c'est parfait pour stocker des tiles.

L'autre solution simple, c'est d'utiliser un bête tableau dynamique trié en fonction de la position.
Tu peux facilement comparer deux positions de cette façon:

Code:

bool operator<(const ClampedCell& o) const {
    return _x < o._x || (_x == o._x && _y < o._y);
}

Pour l'accès à tes entités, il suffit de parcourir le tableau.
Pour trouver une entité, il te suffit de faire une recherche dichotomique. La complexité est logarithmique (donc rapide).
Pour ajouter une entité, il faut l'insérer après avoir trouvé sa position pour que le tableau reste trié, cela peut vite devenir lourd car l'insertion dans un tableau est linéaire.
Bref, cela est très adapté a des types d'entités peu fréquentes dans un chunk, et ou on a besoin rarement a des accès/insertions.

Après, t'as encore pas mal d'autres approches, mais forcement ça devient plus compliqué, avec potentiellement des structures plus lourdes (au niveau des allocations dynamiques, ou au niveau structurel).
Bref, avant de choisir le type de structure a utiliser, il faut tout d'abord être sur des besoins.

Faire une structure qui serait adaptée à tous les besoins, c'est généralement une mauvaise idée (et surtout utopique) car un truc généraliste est généralement moyen dans la plupart des domaines, alors qu'on peut avoir une structure spécifique très efficace dans les domaines que l'on veut.

Et je ne parle même pas des entités dynamiques, ou au niveau des système de partitionnement, il y a vraiment beaucoup, beaucoup de choix.
Il y a pas mal de documentation a ce propos quand on cherche les méthodes utilisées dans les moteurs de collision (comme box2d).

C'est cool, en fait faudrait que je passe plus de temps à me renseigner sur ce qui existe plutôt que de réinventer la roue. Le truc c'est que c'est pas évident de savoir dans quelle direction aller dans ces vastes internets.

Le tableau dynamique trié en fonction de la position me plait bien, reste à voir niveau performance une fois qu'un début de gameplay sera posé.

J'ai remplacé mon quadtree par un simple tableau 2d, et ça me permet de coder l'agrégation beaucoup plus facilement.

Au moins j'aurai atteint cette étape, et j'vais essayer de pas revenir en arrière sur cette fonctionnalité qui est à la base de mon moteur de jeu, tout en essayant différentes stratégies.

J'en ai pas parlé ici, mais mes blocs sont en fait des triangles équilatéraux, et dans le quadtree ils étaient organisés comme ça, et c'était assez chaud de se représenter le truc mentalement



Maintenant je les stocke en tableau 2d, avec rotation et décalage en fonction d'un modulo de ligne, et là ça devient plus clair (à un coup de trigonométrie près pour qu'ils se touchent) (en rouge et bleu, ce sont les collisions "gagnante" et "perdante")


J'aurais aimé rester sur du triangle jusqu'au plus bas niveau, faire des grilles triangulaires, mais rester bloqué trop longtemps ça m'aurait foutu en l'air ma motivation...

Je sais pas exactement ce que tu comptes faire comme règles, mais dit toi une chose, des triangles c'est exactement pareil qu'une grille de "carrés".

La seule différence qu'il peut y avoir, c'est la façon dont tu représentes l'accès a tes voisins, et les limites accessibles (mais si t'es dans un monde "infinis" on s'en fout un peu du coup).





La gauche et la droite sont totalement équivalents.
Bref, faut bien faire attention a ne pas croire que parce que visuellement c'est différent, qu'en interne c'est différent aussi.

Un autre bon exemple c'est les jeux en isométrique.
Une grille isométrique reste une bête grille, la seule différence est au niveau de l'affichage (et la détection de la cellule sous la souris).

Pour une grille iso c'est encore plus évident, c'est juste une grille vue d'un autre "angle de caméra".

Oui, d'accord. Bon alors je fais bien de repartir sur un tableau 2d.

C'est rassurant parce que j'ai régulièrement entendu "mais pourquoi tu fais des triangles, tu vas te faire chiiiieeeer", et ma réponse habituelle c'était des trucs du genre "ouais mais j'accepte le challenge". Maintenant je pourrai dire "ah non mais c'est des carrés déguisés, t'inquiète.

Là où je vais devoir sortir de ma zone de confort c'est pour le moteur de plates-formes. Un mario avec des triangles, mais faudra juste regarder comment gérer les pentes. J'avais déjà fait ça avec des escaliers dans ma période game maker, donc ça devrait bien se passer. (Jean-Michel raconte sa vie )

@onilink, par curiosité, ton dessin grille de carrés vs grille de triangles, c'est toi qui l'as fait pour tes besoins, ou bien ça vient d'un super livre / tutoriel / etc... ?

Je l'ai fait pour le post :p

ok cool merci ^^
c'était propre

J'avance petit à petit sur le prototype. J'en suis à placer précisément les blocs lors d'une aggrégation. Y'a des effets de bord à corriger.

Je posterai le lien par ici une fois que ce sera un minimum jouable.

Voilà, c'est pas le gameplay prévu, mais c'était histoire de pouvoir interagir un minimum avec le décor :

accretio 0.2.0
https://chuw.itch.io/accretio

T'as pas un build linux? J'arrive pas à le wine :/
(ou une vidéo pour voir la gueule du truc)

Yep. J'ai mis un fichier love, utilisable avec LÖVE 11.2

Edit : C'est pas un build linux, mais c'est pas pénible à installer / désinstaller, et c'est plus facile pour moi qui suis sous windoze.

Yep ça marche bien avec le fichier love, et le jeu fonctionne bien c'est plutôt cool

Chouette