[TomPliss]

Salut les faiseurs,

Bon voilà, je sais que d'habitude on parle plus des concepts de créations de jeux ici, mais je viens pour vous exposer un problème technique "simple" qui m'est apparu.
Je me suis mis à penser à ce que je pourrai faire (vu que je m'ennuie), et j'ai penser à essayer de concrétiser une idée de projet : faire un "MMORPG" par navigateur (vu du dessus, avec des "cases") dans le style "construction mais pas que" de Wurm Online en plus simpliste.

Donc je pensais à comment je pourrai gérer ça, et je me suis dis qu'avec une simple base de données en MySQL pour stocker les "cases", et un logiciel fait-maison tournant sur le serveur qui la changerai directement pour faire les actions de l'environnement (faire pousser les arbres et les plantes, notamment).
A ce moment là, pour faire au plus simple, j'ai penser à faire des cases de 1 mètre par 1 mètre, et je me suis rendu compte que je si voulais sur la "carte" pouvoir avoir plusieurs zones complémentaires et distinctes (une plage avec sable et poissons, une zone montagneuse pour rochers et métaux, une forêt plus ou moins dense pour bois et animaux sauvages,...), il me faudrait au moins 1 km² (1000*1000 cases), pour commencer (et que si jamais ça arrivait à avoir du succès, il faudrait agrandir de beaucoup ensuite (genre 3000 * 3000 cases).

C'est à ce moment là que je me suis rendu compte du problème :
avec de base 1 million de case, si je dois stocker quelques centaines d'octets d'infos par case, ça revient à quelques centaines de Mo au début (pour 1000*1000 cases), mais ensuite à quelques dizaine de Go (pour 3000*3000 cases) ...

Et le truc, c'est que j'aurai largement besoin d'avoir plusieurs centaines d'octets par case (pour gérer les types de terrain sur plusieurs hauteurs, sachant que je le ferai bien par pallier de 10cm sur 10m de haut)....
Et en plus, il n'y aura pas que ça à stocker, mais aussi la position des arbres, ainsi que leur age, leur type, si on leur a couper tel ou tel type de branches récemment, et la même chose pour les fougères/herbes médicinales; la place des filons de métaux et de pierres précieuses des bancs de poissons, ...

Bref, même si je pourrai à mon avis aller jusqu'à allouer une petite centaine de Go à un projet de jeu en ligne, je me dis qu'elle serait bien vite pleine ....

Y-a-t'il une "solution" ?

Comment est-ce que ceux d'entre vous qui avez eu ce genre de problèmes le gérez vous ?

[sicarius]

Bon déjà pour une si grosse base, MySQL ça va pas le faire. Si tu veux rester libre et gratuit PostgreSQL serait une bonne alternative, bien que ce soit un nouvel apprentissage.

Sinon pour la taille de tes données, à part les stocker compressées et les faire décompresser par le client, je vois pas d'autre solution, en la matière ya pas de miracle.

D'un autre côté je sais pas si c'est le cas, mais tu vas pas stocker les détails d'un arbre dans chaque case. Tu crées un arbre (genre un platane rouge à pois vert) et dans la case tu stockes une référence à ce type d'arbre.
La référence devrait être beaucoup moins lourde que les infos de l'arbre.

[Vanille]

salutation,

actuellement je m amuse à faire un truc plus ou moins pareil.... mais en plus simple

pour résoudre ce problème, j ai crée ( du moins sur papier, ça déconne encore ) un algo dont l idée vient du vectoriel.

cad je n enregistre pas
case1-1 = X, case 1-2 = X, case 1-3=X
case2-1 = X, case 2-2 = X, case 2-3=X
case3-1 = X, case 3-2 = X, case 3-3=X

, .... j enregistre 'zone 1-1 a 3-3 = X
et l algorithme de sortie me ressortira la même chose.

par contre c'est sur, si je cherche a faire un damier, ça le ferra pas.

pour ce qui du reste comme tes arbres et autre, essaye quelque chose du même genre ? mais j ai 20 type de 'case', et pour 'arbre' , c'est case de type foret tropical par exemple, je fait pas aussi précis dans le détail

la ou j en suis c'est que je calcule des superposition de carre/cercle/information

genre je dit = zone 1 de tel coord a tel coord c'est de l herbe, et je donne des hauteur de certain point et le système fait une moyenne pour trouver les hauteurs intermédiaire

je te conseil de regarde du coter du SVG, tu verras un peu l idée.

A voir si ça t as aider....


J ai aussi expérimenté un autre système mais qui ne m a pas convaincu, mais ça pourrais peut être te donné des idées ...
en gros, mon terrain as X case sur X, comme dit plus haut, j ai des type de case.
j ai enregistrer pour chaque case 1 pixel dans une image, la couleur du pixel déterminant le type.
maintenant, vu le nombre de couleur existante, tu pourrais te faire des plages de 'couleur' genre couleur A-B = type de terrain untel, et tu subdivise les A-B en d autre sous plage, te donnant des info diverse. Enfin ça de ça cote la, je px pas te dire, moi, avec 20 .... j ai déjà assez

puis ton image, tu l enregistre en png par exemple, format qui n a pas de perte.
et une image de 1000 pixel sur 1000 pixel, en imaginant que tu emplois un panel de couleur de 32b, ça fait pas tellement en taille. ( j avais fait mes test sur une image de 256 couleur perso, avec des plages de 10 )

Bref, pour ce qui est de la 2eme idée, t as un gain de place, mais il te faudra donc un dictionnaire de donnée avec les définition des codes couleur de chaque pixel.

En espérant t avoir donner une idée

[Toro]

Tu peux stocker 3 données (rouge - vert - bleu) d'un niveau 0-255 par pixel dans une image. C'est un moyen simple d'alléger la base de donnée.

En PHP tu peux analyser un pixel avec cette commande : http://fr.php.net/manual/fr/function.imagecolorat.php

Tu te fais des cartes en image pour les données peu changeantes et pour les autres données plus vives ou constamment analysée, tu stockes en BDD.

EDIT : en fait j'ai oublié de parler des fonctions spatiales des BDD.
Il est possible de faire travailler des polygones entre eux avec une BDD comme PostgreSQL.
MySQL le fait avec les MBR (le carré englobant un polygone), c'est donc moins intéressant. Une véritable gestion des polygones est prévue pour une version future.

[small_duck]

Pour le terrain
En effet, avoir un million de lignes dans ta base pour représenter chaque case est probablement très mauvais pour les performances!

Chaque objet devra plutôt être représenté par ses coordonnées. Pour chaque arbre, tu as une position en x, y. Si tu as 100 000 arbres, tu as 100 000 lignes, mais c'est probablement raisonnable.

Ensuite, pour les donnés "raster", de type élévation, type de terrain, tu peux utiliser une ou plusieurs images qui contiennent les données dont tu as besoin. En plus, l'édition de données sera simplifiée!

Aussi intéressant, est de gérer ton monde implicitement, à travers des fonctions pseudo-aléatoires qui définissent entièrement ton terrain. Tu peux jeter un coup d'oeil par exemple au bruit de Perlin, ou encore utiliser des formes géométriques que tu disposes suivant une fonction pseudo-aléatoire (j'ai fait ça en 3D ici), en 2D le principe est le même).

Pour les objets
La solution la plus simple, c'est de simplement faire des grandes tables Mais il est possible de ruser, et de partir vers un design beaucoup plus dynamique. L'idée est de définir des listes de propriétés, sous forme de paires clé -> valeur. En permettant à une liste de dériver d'une autre liste, l'on peut spécialiser des objets à peu de frais.

Arbre
Nom -> Arbre
Matière -> Bois

Cyprès, dérive Arbre
Nom -> Cyprès
Vertu -> +10 PV
Vertu -> +5 PM

Cyprès 1, dérive Cyprès
Nom -> Cyprès près du chemin des Gargouilles
Hauteur -> 50m
Position -> 257, 354

Cyprès 2, dérive Cyprès
...

Ainsi, dans ta base, chaque cyprès n'a besoin que de définir un nom particulier (si tu en as besoin, sinon il apparaîtra juste comme "Cyprès"), sa hauteur, et sa position. Si tu veux changer le nombre de points de magie qu'un cyprès particulier peut fournir (par exemple, le cyprès dans le jardin du sorcier), cela ne te coûtera qu'une ligne en plus dans la base.

Le système est expliqué avec plus de détails sur le blog de Steve Yegge (en anglais). Un tel design, c'est plus de boulot au moment de la création, mais cela permet d'être très dynamique tout en étant relativement sobre question place. J'ai fait une petite implémentation de listes de propriétés avec Postgres, je peux poster si ça intéresse quelqu'un.

[TomPliss]

Heu... me paraissait "normal", d'après ce que j'avais écrit que les "objets" (arbres, ...) seraient à part, dans chaque case...

Pour ce qui est des génération pseudo aléatoire, c'est justement un truc que je peux pas faire :
Les joueurs pourront directement influencer le terrain (creuser, poser certaines matière, par exemple mettre la même hauteur dans tout un endroit pour construire une maison par dessus, pour déposer 50 cm de terre sur un large terrain pour y faire des plantations, ...

C'est pour ça qu'il faut que je stocke précisément les différents terrains partout ..
Pour ce qui est de l'enregistrer en tant qu'image, je pense que ça peut en effet être une bonne solution, vu que c'est à ce moment là la compression de l'image elle même qui permet la compression des données...

Mais bon, il me faut un type d'image qui reste accessible dans la donnée "brute" :
Je veux faire tourner sur le serveur un programme fait maison qui permettra par exemple aux arbres de pousser s'ils ont de la terre et/ou du sable et/ou de l'eau (en fonction de l'arbre), et donc il faut que j'arrive à extraire les données du terrain facilement ^^

'Fin bon, merci pour les idées ^^

[small_duck]

Citation :

Publié par TomPliss

Les joueurs pourront directement influencer le terrain (creuser, poser certaines matière, par exemple mettre la même hauteur dans tout un endroit pour construire une maison par dessus, pour déposer 50 cm de terre sur un large terrain pour y faire des plantations, ...

Ça n'empêche pas! Simplement, en plus de ta génération aléatoire, tu as des surcharges sur les cases en particulier. Si tes joueurs modifient 90% du terrain, c'est en effet mieux d'avoir une image, mais si tu as des grandes étendues d'eau, beaucoup de terrain inconstructible, ou que le gameplay limite le nombre de constructions, il est plus avantageux de gérer la surcharge.

La raison pour laquelle je préfère la génération implicite + la surcharge est que tout est dans la base, ce qui permet d'une part de simplifier énormément la maintenance (sauvegarde, etc), d'autre part de rendre bien plus aisée l'extraction de données du jeu ou de statistiques intéressantes. Tu parlais de faire pousser les arbres: avec le terrain implicite, c'est trivial. Pour chaque arbre, tu calcules l'altitude / la fertilité du sol / la quantité d'eau, et si tout va bien, hop, l'arbre pousse, et tout ça avec un poil de SQL.

Ah, et ais-je mentionné les soucis liés à l'absence de transactions sur ton système de fichiers?

Ceci dit, la meilleure approche, c'est de se lancer avec la solution que tu te sens maîtriser le mieux, et d'être prêt à en changer quand elle commence à poser problème!

[Toro]

N'hésite pas également à triturer ton gameplay quand tu vois que cela va coincer au niveau technique.
Cela ne sert à rien d'avoir de belles idées si au final on se retrouve avec un jeu injouable dès qu'on dépasse les 10 joueurs...

Et quelquefois, la solution se place au niveau du gameplay, pas de la technique.

[Toro]

Citation :

Publié par small_duck

J'ai fait une petite implémentation de listes de propriétés avec Postgres, je peux poster si ça intéresse quelqu'un.

Ca m'intéresse beaucoup !

Sinon, tu as déjà utilisé les données spatiales de Postgresql ?
Je ne connais que MySQL mais c'est peut-être le truc qui me ferait basculer sur Postgresql pour mon projet. Mais je n'ai pas encore pu tester ce que ca donnait, un retour serait apprécié.

edit : oops, désolé pour le double post

[Gwym]

Citation :

Publié par TomPliss

Comment est-ce que ceux d'entre vous qui avez eu ce genre de problèmes le gérez vous ?

Bonjour,

J'ai cette problématique pour créer les planètes d'un jeu à ecosystème "autonome", et j'utilise certaines des techniques citées ci-dessus. Tout n'est pas encore validé, mais les idées pourront peut-être te servir

Parmi les informations à conserver, j'ai par exemple la décomposition du cadavre d'une créature qui va apporter de l'engrais sur une case, améliorant la pousse de la végétation, je conserve aussi des "traces de pas" simplifiées (au travers d'une modification de la densité de la végétation liée au passage d'une créature), le type de végétation, etc

L'initialisation de la carte représentant la planète est pseudo aléatoire (un fonction pseudo aléatoire + une grille de valeur prédéfinie pour modeler la forme à souhait) qui détermine pour chaque case l'état d'équilibre de la flore, c'est à dire l'état dans lequel elle est sans modification extérieur. Ceci n'est fonction que de x, y, z et t

Je travaille sur une carte de 8192 * 16384 cases (2^13 * 2^14) mais dans l'absolu elle peut être de n'importe quelle taille tout dépend du codage des coordonnées : elle est calculée, et une fois le générateur implémenté on peut générer autant de planètes de tailles et de géographies différentes que l'on veut.

C'est uniquement l'aspect dynamique qui prend de la place. Je ne stocke en base de donnée que les écarts par rapport à cet équilibre, par exemple pour ce que j'ai cité : l'apport de matière organique et la modification de la densité de la végétation

Surtout, j'essaie de gagner de la place :

- simplification : *beaucoup* de terrains sans besoin en ressource de stockage (i.e. beaucoup d'eau profonde)

- modélisation : toute plante/créature est une "boite noire" fonction de paramètres (initialisation + modificateurs) déterminés par le modèle global et/ou les modèles locaux.
Typiquement ce seront par exemple les modèles de plantes annuelles, bisannuelles, vivaces, est-ce que la plante repousse ou meurt si elle est coupée, sa dépendance à la température et à l'hygrométrie, etc etc..

- discrétisation : on peut ne stocker que les grandes lignes de certaines caractéristiques et affiner le reste par la méthode pseudo-aléatoire, par exemple période de floraison d'une plante définie par une valeur sur 2 bits (4 saisons) mais pour éviter que toutes les plantes de cette famille ne s'ouvrent en même temps, le moment exact dans la saison est pseudo-aléatoire. On peut aussi utiliser une échelle logarithmique pour avoir plus de détails sur les petites valeurs et réciproquement. Je l'utilise par exemple pour le codage des masses. Que le mammouth adulte fasse 6 tonne ou 6,2 tonne, celui qui se fait charger s'en moque. Mais si la hache fait 5 ou 6 Kg, la fatigue du bucheron ne sera pas la même ! Ce qui permet avec la même variable d'avoir des précision à quelques grammes mais de définir aussi le poids d'objets gigantesques.


- compression : une caractéristique qui peut se coder sur un nombre de bits restreints peut se combiner avec d'autres dans une même valeur en base (exemple type de terrain sur 4 bits, densité sur 8 bits, ainsi de suite, le tout pouvant tenir dans un ou plusieurs entiers en base de donnée.) Je n'utilise pas de compression supplémentaire, car le champ de bit garde la faculté de pouvoir interroger directement certaines information dont j'ai besoin à l'aide d' un simple masque.

- entropie : le terme n'est pas vraiment adéquat, mais c'est le retour à l'équilibre, pour éviter la saturation de la base de donnée à long terme. Toutes les cases reviennent inexorablement à leur état d'équilibre (ex : pousse des plantes, usure des modifications faites par les joueurs...) et une fois l'état d'équilibre atteint, l'information est supprimée puisque devenue inutile

- "best effort" : en dernier recours, si la quantité de données à conserver dépassent le seuil que je me suis fixé, ce sont les modificateurs les plus faibles qui sont remplacés. Un joueur verra peut-être le cadavre de sa créature se décomposer plus vite que prévu sur la fin, mais c'est le prix à payer (en qualité de service) pour ne pas avoir a augmenter sa capacité de stockage.
Et si ce cas brutal arrive trop souvent pour la flore, il suffit d'augmenter l'entropie. L'avantage est que l'adaptation peut être dynamique et automatique. (Et en somme pour la faune, s'il y a surpopulation j'augmente la difficulté de survire

Après, avec un telle solution entièrement calculée, il y a des soucis de performances.
Pour ma part j'utilise un cache et je stocke des valeurs pré-calculées (qui peuvent l'être) aux alentours des positions les plus dynamiques (fonction de la présence des joueurs).

[Toro]

Citation :

Publié par Gwym

- entropie : le terme n'est pas vraiment adéquat, mais c'est le retour à l'équilibre, pour éviter la saturation de la base de donnée à long terme.

C'est une excellente idée ca !

[small_duck]

Gwym - Concepts très intéressants, qui devrait rendre le monde extrêmement dynamique. Le public réclame une démo!

Toro - J'ai remis mon implémentation au goût du jour, en utilisant les fonctionnalités de Postgresql 8.4 pour faire de la récursion en pur SQL. Le code est ici:

PropertyList.sql

La fin du script contient l'exemple des cyprès, et utilise les fonctions getValue et getAllValues pour récupérer soit une valeur donnée, soit toutes les valeurs pour un objet, en prenant donc la valeur de l'objet le plus bas dans la hiérarchie. Les listes sont supportées sous forme de plusieurs entrées avec la même clé, et une liste à un niveau cache les listes des niveaux supérieurs.

J'ai un petit peu joué avec Postgis en chargeant des données géographiques récupérées sur le Net. Je pense que cela pourrait être un socle très solide pour un wargame ou un Sim City, avec l'avantage de pouvoir utiliser tout plein d'outils standards pour faire les cartes, les charger et les afficher. J'espère bien faire bientôt quelque chose de sérieux avec ça!