Jeu à base de case "tilegame"

Bonjour,

je réalise en ce moment un petit jeu type rpg où un personnage se déplace dans un monde d'hexagone. A terme, j'aimerais que mon monde soit infini et que mon moteur charge en temps réel la suite du terrain.

J'ai pour l'instant quelque chose qui marche mais qui n'est pas du tout optimisé. J'essaye donc de trouver la manière la plus optimisé pour réaliser ce chargement temps réel.

Donc sans rentrer dans le fonctionnement de mon application actuelle qui rame entre les différents cartes, je pensais améliorer mon moteur avec ce qui suis :

J'aimerais donc avoir un tableau 2D tel que celui ci-dessous en image.
Ce tableau représenterait le monde complet en vue de dessus. Chaque numéro représenterait une hauteur de terrain (mon jeu est en 3D).

http://img51.imageshack.us/img51/5638/sansre1y.png

Le carré rouge quant à lui serait un second tableau représentant la carte que le personnage voit (beaucoup plus petite que le monde pour pas que sa rame bien sur).

Mon moteur chargerait petit à petit la suite du monde et la 3D (grâce à un thread et en fonction de la position du personnage).
Et en temps réel (boucle principal), j'actualiserai le second tableau qui me sert en continu à gérer le pathfinding, les objets, obstacles, ...

J'ai donc quelques questions, pour ne pas re-coder une seconde fois inutilement un moteur foireux qui ramerait :
- Est-ce que cette vision de mon jeu est réalisable et paraitrait assez optimisé.
- Voyez-vous une autre façon de faire qui paraitrait plus optimiser ?
- Voyez-vous des failles dans mon système ? A court terme ou long terme ?

Et une dernière question :
En C++ donc bien sur, quelle serait le meilleur conteneur pour gérer mon tableau représenté par le carré rouge ?
Actuellement, j'utilise un vecteur de vecteur pour faire ce tableau 2D. Ce tableau représente une carte de 60x60, je fais à chaque frame (vu que j'ai un moteur 3D), le calcul du nouveau tableau avec une double boucle (x, y). Je ne trouve pas ça super optimiser, comment je pourrais envisager mieux ?

J'espère avoir été à peu prêt clair et pouvoir trouvé de l'aide.
Merci,

Olivier.

Salut !

C'est une bonne idée, et pour améliorer les performances, un système à base de Memory Pool est recommandé.

Sinon pour le conteneur, j'ai envie de te recommander boost::array.

Pour les failles à court terme, ça dépend en fait de ton algo de pathfinding : s'il ne prend en compte que le second tableau il n'y aura pas de problème majeur, par contre s'il prend le premier, il faut faire attention à générer une map de départ suffisamment grande pour avoir un pathfinding cohérent.
A long terme, je dirais qu'il serait pas mal de limiter en ram la taille générée pour la map par ton thread sinon tu risques vite d'atteindre les limites (2 Go pour une appli sous Windows) pense à utiliser des fichiers et à ne pas faire tourner ton thread non stop mais uniquement quand le besoin s'en fait sentir.
Ensuite je ne suis pas d'accord avec jblecanard pour l'utilisation de boost::array, car ce type de tableau a une taille fixe (pas problématique pour le second tableau) et il gère son tableau de données (pas vraiment problématique, mais pas optimisé) personnellement je me pencherais sur une structure que l'on puisse faire pointer sur un tableau déjà existant (je ne sais pas si c'est possible avec vector), j'ai déjà fait des structures de ce type pour mon moteur 3d : les points et les matrices (les matrices 4x4 sont constituées de 4 "points" de 4 coordonnées chacuns, ce qui permet des opérations plus aisées)

Pour l'histoire de la RAM, une politique de memmory pool bien faite permet justement d'éviter ces problèmes.

Citation:

---

Envoyé par dragonjoker59

Ensuite je ne suis pas d'accord avec jblecanard pour l'utilisation de boost::array, car ce type de tableau a une taille fixe

---

C'est justement tout l'intérêt, puisque la map visible a une taille fixe ! Mais je vois ce que tu veux dire : ce tableau sert juste de pointage sur des données stockées différemment, dans lequel cas c'est peu adapté.

J'avoue ne pas avoir de bon conseils sur le sujet.

C'est ce que je me suis demandé immédiatement: est-ce que la taille du 2nd carré est fixe? Comment est gérée la caméra?
D'ailleurs, je suis curieux de savoir comment tu fais pour gérer un maillage hexagonal avec du relief. J'y ai souvent réfléchi, mais je n'ai pas trouvé de solution satisfaisante. Et en plus, s'il doit être générée dynamiquement, ça doit pas être simple!

Pour le reste je ne sais pas trop. Juste un truc: un vector< vector > c'est vraiment pas top. Moi pour ça j'utiliserais un simple vector (à une dimension quoi), encapsulé dans une classe Matrix qui fourni les accesseurs et iterateurs, en utilisant de préférence les iterateurs (plus rapide généralement).

L'intérêt de boost::array (ou équivalent tr1 ou std) est qu'il a une taille fixe (et aussi qu'il n'a pas l'overhead d'un vector mais là n'est pas la question)
=> bien pour le second tableau
=> pas top pour le premier

L'inconvénient de boost::array (de même pour les autres) est qu'il gère lui-même son tableau ce qui dans le cas présent impliquerait des copies de tableaux à chaque déplacement du personnage. C'est pour ça que je proposais la structure qui positionnerait et déplacerait son buffer sur le tableau existant. ça n'impliquerait essentiellement que des incrémentations / décrémentations d'adresse. Cependant ça implique que la map est sur une zone mémoire continue, ce qui n'est pas forcément le cas.

Il ne faut pas oublier non plus que:

Citation:

---

Envoyé par Donald Knuth

premature optimization is the root of all evil

---

Franchement, moi je te conseille de surtout bien penser ton architecture, et tu optimiseras ensuite, si c'est necessaire. Surtout sur ce genre de choses, le gain que tu vas obtenir sera négligeable comparé au temps d'exécution global du programme.

Je suis tout à fait d'accord, mais bien penser son modèle de mémoire en vue d'être performant ne me paraît pas du tout prématuré quand on se doute qu'il va y avoir un os dedans. Surtout que là, c'est directement le sujet du post :D

Je pense que notre ami Knuth parle des optimisations qui ne s'inscrivent pas dans l'architecture globale du système. En l'occurence, y penser dès maintenant est une bonne idée.

De plus, le sujet du chargement "par tuile" est un sujet récurrent dans le jeu vidéo. Bien se renseigner sur les algos existants est une bonne idée. Il va falloir fouiner un peu...

J'avoue ne pas être très convaincu pas cette structure de données. Tout d’abord, ce mini rectangle, à quoi sert-il ? A limiter la zone dans laquelle la physique du monde est simulée, ou bien la zone d'affichage ? Les deux pourraient avoir de l'intérêt, et je ne suis pas certains que les critères soient les mêmes. Ensuite, pourquoi une forme carrée ?

Si le but est de limiter les polygones à afficher, un carré n'est pas très représentatif (un cercle aurait déjà plus de sens), Et surtout des règles d'occlusion permettent de virer bien plus de choses, si tant est que le relief est prononcé.

Si le but est de limiter la zone de simulation, je pense qu'un joueur classique va avoir tendance à pas mal osciller entre plusieurs points. Avoir donc comme actif non pas un carré mais une certaine zone autour du chemin qu'il a parcouru dans le passé, voire quand on peut le deviner autour de là où il va aller dans le futur proche, me semble plus intéressant.

Dans tous les cas, la détermination de ces zones n'est pas évidente, et une première version à base d'un "carré" autour du joueur n'est pas forcément un mauvais choix initial. C'est juste qu'une structure de données plus souple qui permette une évolution par la suite me semble plus intéressante.

a l'epoque ou j'etait jeune, on avait retroingeniere les deux Diablo, la strategie de Blizzard a l'epoque etait de conserver un historique du monde en "salle" (au sens large) et de garder dans l'histoirque les 9-12 dernieres salles parcourues.

La solution de Loic me parait donc la plus judicieuse.

J'avais utilisé la même solution pour un terrain en 3D, effectivement ça marche bien même sans multithread.