+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Micromanagement - Comparer nos solutions (/showthread.php?tid=4004)
RE: Micromanagement - Comparer nos solutions - keke - 28-05-2009
(28-05-2009, 09:10 AM)barst a écrit : Avec 4 races et 6 besoins, les tirages étant toujours compris entre 1 et 100, cela reste de la combinatoire : 4x6x100 = 2400.
2400 représente l'ensemble des tirages possibles pour chaque combinaison de race et de besoin.
Je crois pas ^^.
Si y'a 1 race et 2 caracs (F et H par exemple), il existe :
100 valeurs de H possible pour la valeur 1 F +
100 valeurs de H possible pour la valeur 2 F +
100 valeurs de H possible pour la valeur 3 F +
...
100 valeurs de H possible pour la valeur 100 F
Soit 100 * 100 possibilité.
La formule de roworld est bien la bonne ^^ 4 races * 100^6 (soit : 4000000000000 lignes dans ta base ) . Mais néanmoins, ta solution pourrait s'avérer bonne pour de plus petit volume.
Kéké
RE: Micromanagement - Comparer nos solutions - Roworll - 28-05-2009
Oups, désolé. J'avais lu tes explication trop vite.
Effectivement, ton compte est bon et les besoins évoluent bien différemment pour chaque PNJ.
Par contre, j'ai fait quelques essais et les performances sont assez décevantes. 8 secondes pour mettre à jour 10.000 lignes, plus de 3 minutes pour 250.000 lignes et ce malgré des index posés de manière adéquate.
Comme je le craignais, les requêtes imbriquées plombent les performances.
[Edit]
@Kéké
Je penses que tu as fait la même erreur que moi dans ton calcul en supposant qu'on recherchait toutes les solutions possibles pour les 6 caractéristiques dans un même enregistrement et non pas individuellement.
Dans la cas présenté par barst on a juste toutes les valeurs possible groupées par race/besoin/D100
RE: Micromanagement - Comparer nos solutions - barst - 28-05-2009
Dommage que les performances soient plombées.... j'aimais bien ma solution de tout faire en une seule requête.
J'aurais au moins le mérite d'avoir proposé la solution la plus courte au niveau code
RE: Micromanagement - Comparer nos solutions - Roworll - 28-05-2009
Voici la solution que j'ai apportée au problème.
Souhaitant éviter de charger le PHP avec trop de boucles et de tests, je me suis orienté vers une solution tout SQL.
J'ai cherché un moyen me permettant de mettre à jour toute la table des PNJs en une seule passe tout en évitant les requêtes imbriquées et les syntaxes trop lourdes (bourrées de IF, RAND et autre fonctions).
Finalement, j'ai décidé de m'appuyer sur une table que je qualifierai de 'modèle de progression'
J'ai une procédure qui tire à l'avance l'évolution des caractéristiques et la range dans une table.
Ces évolutions sont regroupées par 'modèle'.
La structure de la table est la suivante
Code :
Race | Ref | Faim |Hygiène| Santé | Repos | Loisir| Zen |
--------|--------|-------|-------|-------|-------|-------|-----|
Astyrion| 1 | 4 | 1 | 2 | 4 | 3 | 1 |
Astyrion| 2 | 1 | 2 | 4 | 3 | 1 | 2 |
Astyrion| 3 | 3 | 5 | 2 | 4 | 2 | 3 |
...
Bellist | 1 | 1 | 3 | 4 | 3 | 4 | 3 |
Bellist | 2 | 1 | 1 | 1 | 5 | 1 | 3 |
Bellist | 3 | 3 | 1 | 3 | 3 | 2 | 1 |
...Lorsqu'un PNJ est créé, je lui affecte au hasard un profil (j'en ai 1000 différents par race).
Ces informations sont stockées avec les informations du PNJ.
Quand vient l'heure de faire évoluer les besoins, une simple requête avec un join me permet de mettre à jour tous les personnages en même temps.
Code :
UPDATE pnj p
INNER JOIN modele m ON
p.race=m.race AND p.ref=m.ref
SET
r.ref=FLOOR(RAND()*1000)+1,
p.faim = p.faim + m.faim,
p.hygi = p.hygi + m.hygi,
p.sant = p.sant + m.faim,
p.repo = p.repo + m.repo,
p.lois = p.lois + m.lois,
p.zen = p.zen + m.zenComme je l'ai noté plus haut, cette méthode me permet de faire évoluer 250.000 PNJs d'un coup en quelques secondes.
Sur ma machine locale, la moyenne est de 4.5 secondes
En passant la table des Modèles en type MEMORY, je descends à 3.6 (comme quoi, les formats de table influent énormément. En MyISAM sur la table modèle, ça monte à 18s de traitement...)
Vous remarquerez que j'utilise un RAND() dans la procédure de mise à jour.
Cela me permet de changer les profils en réassignant un N° de modèle à chaque tour.
J'ai testé diverses méthodes
- actualiser le profil via une 2e requête
- régénérer une nouvelle table de modèles
- utiliser un IF avec un offset pour réassigner un nouveau N°)
Au final, le RAND est la méthode qui en moyenne semble le plus efficace.
RE: Micromanagement - Comparer nos solutions - wild-D - 28-05-2009
même si j'aime bien ta solution, vu que tu réduit ton modèle sur 1000 valeurs, ça va quand même te faire de sacré biais statistique journalier (entre ton système "théorique" et la version de ton algo implémenté).
RE: Micromanagement - Comparer nos solutions - Roworll - 28-05-2009
La table de modèles sera régénérée une fois par 24 heures histoire de diversifier les évolutions.
Dans l'absolu, il faudrait tout de même manquer de pot pour avoir des PNJs qui suivent exactement la même courbe de progression (en gros le même modèle à chaque fois) pendant toute une journée.
Au pire, la régénération de la table modèle ne prends que 0.3 secondes en moyenne. Si vraiment statistiquement la progression par le système actuel est moisie, je pourrais penser à intégrer le rebuild des modèles dans la procédure horaire.
RE: Micromanagement - Comparer nos solutions - keke - 28-05-2009
Moi, j'aime bien ta solution RoworII ^^.
Elle biaise de manière intéressante une réalité pour la simplifier. Simple, neutre et efficace. Well done ! Aucun PNJ ne pourra se plaindre (comment ça un PNJ ça ne se plains pas ?)
Par contre, j'aimerais savoir comment tu gènère ta table de progression :
"J'ai une procédure qui tire à l'avance l'évolution des caractéristiques et la range dans une table."
Se peut-il que certaines caracts ne ne soient pas présente ? Par exemple si pour l'hygiène (H), tu as 1 chance sur 100 d'avoir un +30, cela signifie que dans ta table d'évolution, statistiquement sur 1000 tirage, il devrait y en avoir 10 avec la valeur H+30. Donc en pratique, tu as une probabilité non négligeable de ne pas en avoir du tout.
Et si tu n'a pas ce tirage dans ta table de progression, tu prives pendant une journée, toute l'espèce d'avoir des problèmes d'hygiènes important.
Ca n'a peut-être pas d'importance, mais la méthode employé biaise tes stats ^^. Mais je me doute que tu en as conscience.
kéké
RE: Micromanagement - Comparer nos solutions - Roworll - 28-05-2009
Pour générer les modèles, je pars d'un tableau qui contient les règles.
J'ai transformé volontairement certains ID en chaine de caractère pour une meilleure lisibilité.
Code PHP :
<?php
$aRules=Array(
'Astyrion'=>
Array('Faim'=>array(25=>1, 50=>2, 80=>3, 95=>4, 99=> 5, 100=>6),
'Higi'=>array(50=>1, 75=>2, 90=>3, 100=>4),
'Sant'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5),
'Repo'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5),
'Lois'=>array(25=>1, 80=>2, 100=>3),
'Zen'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5)),
'Bellist'=>
Array('Faim'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5),
'Higi'=>array(100=>0),
'Sant'=>array(95=>0, 100=>1),
'Repo'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5),
'Lois'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5),
'Zen'=>array(25=>1, 50=>2, 75=>3, 90=>4, 100=>5)),
//etc
J'utilise les clés des éléments de tableau pour encadrer les résultats des tirages aléatoires.
On peut d'ailleurs remarquer que les Bellist ignorent carrément la notion d'hygiène et que leur santé est plutôt solide.
Code PHP :
<?php
foreach($aRules[$race] as $kCar=>$aCar){
//$aCar va contenir les tableaux Faim, Higi, etc
// On tire une valeur aléatoire pour le besoin en cours
$setVal=mt_rand(1,100);
foreach($aCar as $kVal=>$Val){
//Je parcours le tableau associé au besoin
if($setVal<=$kVal){
// Le jet de dé est inférieur ou égal à la clef ($kVal) de la valeur
// Je construit ma requête en initialisant la valeur $Val pour le besoin $kCar
/*
Code de construction de requête
*/
break;
}
}
}
// Exécution de la requête
La création du tableau de modèle suit donc les règles établies pour les évolutions des caractéristiques.
Donc, pour reprendre la remarque de Kéké, statistiquement, sur 1000 profils de Bellist, 50 d'entre eux devraient avoir une légère défaillance au niveau santé de qui correspond à ma règle établie à la base.
Note : J'utilise souvent la méthode clé/élément (mes tableaux 25=>1, 50=>2, etc) pour manipuler les résultats de jet aléatoires à lire dans une table.
RE: Micromanagement - Comparer nos solutions - wild-D - 28-05-2009
tu as grosso modo 30'000 combinaisons pour chaque race (certaine avec une proba quasi nulle est d'autre avec des proba bcp plus régulière). Ton modèle en a 1000. Donc si tu garde le même modèle toute une journée (24 tirages à l'identique), sur 250'000 PNJ t'as un biais important.
Le biais ne devrait pas être sur la moyenne/médiane (normalement avec mille tirage tu dois avoir quelque chose qui soit approchant à ce niveau); mais sur la répartition statistique des combinaisons hygiène*santé*repos*...
et le problème est que plus le nombre de PNJ sera important plus le biais augmente. prenons le cas extrême: 4000000000000 PNJ, on va dire qu'idylliquement on devrait avoir un bais assez faible par rapport à la répartition théorique des combinaisons. Toi t'auras juste une répartition sur 4000 combinaisons assorties d'un facteur multiplié par 24.
Mais après kéké a raison; Ce biais, c'est pas le genre de truc qui va fondamentalement nuire au gameplay de ton jeu.
Je sais pas comment fonctionne le jeu dans le détail. Mais si les joueurs ont accès en détail à toutes les infos de leur PNJ, avec 100PNJ/joueur 24 tirages sur un modèle de 1000; pas de doute que si t'as dans tes joueurs un malade qui s'amuse à faire des stats complètes (si il se contente par caras/ et non par combi, il verra rien je pense) il devrait être en mesure de détecter rapidement l'arnaque
RE: Micromanagement - Comparer nos solutions - Roworll - 03-06-2009
Merci pour toutes vos contributions sur la problématique N°1.
Passons maintenant à la problématique N°2
J'en reviens à mes PNJs et à leurs besoins.
Dans la première étape, j'ai travaillé sur la manière dont je pouvais faire évoluer les besoins des PNJs périodiquement sans écrouler le serveur. Maintenant, je cherche un mécanisme décisionnel (et performant, bien sur) permettant de répartir les PNJs dans les bâtiments du joueur en fonction de leurs besoins les plus urgents.
Je repars avec mon postulat de base, à savoir 250.000 PNJS et 1000 joueurs.
Voici les données du problème
- Chaque joueur peut posséder des bâtiments
- Ces bâtiments permet de satisfaire un ou plusieurs besoins de base
- Les bâtiments peuvent avoir des restrictions de race (mais pas obligatoirement)
- Un bâtiment peut accueillir de 1 à N PNJs par tour de jeu.
- Les PNJs utilisent les bâtiments correspondant à leur(s) besoin(s) le(s) plus élevé(s) à raison d'un batiment par tour de jeu
Les structures actuelles des tables ressemblent à peu de choses près à ceci :
Visiteur
- ID Joueur
- ID Race
- Besoin Faim
- Besoin Hygiène
- Besoin Santé
- Besoin Repos
- Besoin Loisir
- Besoin Zen
Batiment
- ID Joueur
- ID Bâtiment
- ID Race
- Besoin Faim
- Besoin Hygiène
- Besoin Santé
- Besoin Repos
- Besoin Loisir
- Besoin Zen
Pour le moment, je n'ai pas d'algorithme satisfaisant solutionnant ce problème. Juste quelques pistes pour démarrer.
Par exemple, j'ai codé les races de manière à pouvoir utiliser les opérations binaires lors des recherches
Code :
ID | Race
---|---------
1 | Astyrion
2 | Bellist
4 | Curcen
8 | DyrtanDe cette manière,
- un bâtiment acceptant toutes les races aura un race_id égal à 15
- un bâtiment réservé aux Astyrions et aux Dyrtans aura un race_id égal à 9
- un bâtiment uniquement fait pour les Curcen aura un race_id égal à 4
Ca me permet de récupérer par exemple tous les bâtiments accessibles aux Curcen en faisant
Code :
SELECT ... FROM batiments WHERE race_ID & 4 <> 0 AND ...Quelle méthode utiliseriez-vous pour traiter cette problématique ?