Micromanagement - Comparer nos solutions

[Roworll]

Je viens cette fois parler d'un problème de performance/algorithme et de la solution que j'ai appliquée.
Commençons par planter le décors.

Je souhaite, dans le cadre d'un module bien spécifique, faire évoluer une quantité de besoin pour tous les PNJs présents dans le jeu. (c'est assez orienté micro management)

Les besoins de ces PNJs varient en fonction de leur race. Par exemple

Code :

Race    | Faim  |Hygiène| Santé | Repos | Loisir| Zen |
--------|-------|-------|-------|-------|-------|-----|
Astyrion| 1 à 6 | 1 à 4 | 1 à 6 | 1 à 6 | 1 à 6 |1 à 6|
Bellist | 2 à 8 | 1 à 2 | 1 à 6 | 1 à 2 | 1 à 6 |1 à 6|
Curcen  | 1 à 4 | 1 à 6 | 3 à 9 | 1 à 6 | 4 à 8 |1 à 6|
Dyrtan  | 1 à 6 | 4 à 8 | 1 à 6 | 2 à 6 | 2 à 8 |1 à 2|

Pour simplifier le tout, l'évolution des besoins n'est pas le résultat d'un simple tirage aléatoire mais est déterminé sur une table de résultats.

Par exemple

Code :

Astyrion : Faim
01-25    1
25-50    2
51-80    3
81-95    4
96-99    5
100      6

Astyrion : Hygiène
01-50     1
51-75     2
76-90     3
90-100    4

etc

Le problème auquel j'ai du faire face est le suivant :
Toutes les heures, les besoins de tous les PNJs doivent être réévalués en utilisant les règles ci dessus (j'utilise un CRON pour cela).
Comment y parvenir de manière efficace et pas trop lourde sans écrouler ni le serveur SQL ni le serveur PHP (imaginez 200 joueurs avec chacun 100 PNJs) ?

Je vous laisse réfléchir au problème avant de proposer ma solution (qui n'est peut être pas la meilleure) histoire de comparer nos approches et nos méthodes.

[keke]

Si je comprends bien, ton besoin n'est pas équiprobable. La faim des Astyrion de 1 à 6 se calcule ainsi : tu jettes 1 dé à 100 faces, tu regardes ta table de résultat et tu applique le modificateur. Dans ton cas précis, ça laisse une forte probabilité pour les valeurs 1-2-3 (80% de chance) contre 4-5-6 à 20% de chance. Ensuite, tu soustrais (ou ajoute) cette valeur à une variable indiquant l'état de faim du perso.

Y'a 20 minutes il avait 10 points de faim. Je fais alors un nouveau tirage via crontab : 83 ce qui équivaut à une augmentation de 4 : il a maintenant 14 points de faim.

Dis moi si je me trompe dans cette reformulation orientée de ton contexte.


Perso, je vois plusieurs méthodes.

Si tu cherches un optimum d'algo je te propose celui-ci :
- Mettre en mémoire ton tableau de correspondance.
- Récupérer dans un tableau la liste de tout les PNJ trié par race (id_png, id_race, Faim |Hygiène| Santé | Repos | Loisir| Zen)
- Je fais un tableau contenant 6 * Nb PNJ valeur aléatoires de 1 à 100
- Pour chaque groupe de PNJ par race, je calcule dans un tableau la valeur de modification grâce au tableau de correspondance
- Je Update toutes les lignes. Là 2 cas :
- soit PNJ par PNJ,
- soit je regroupe par caractéristique modifié :
On récupère en PHP la liste de tous les PNJ pour lesquels on a une augmentation faim de 1 :
Un Update faim = faim +1 where id_PNJ IN (122, 123, 124, ...)
Puis on récupère en PHP la liste de tous les PNJ pour lesquels on a une augmentation faim de 2 :
Un Update faim = faim + 2 where id_PNJ IN (125, 126, 127, ...)

Mon choix lors du UPDATE dépendra beaucoup du fait d'avoir un serveur PHP puissant ou un serveur SQL puissant... La première solution étant très gourmande en terme SQL, la deuxième (que je privilégie) étant moyennement gourmant en terme de PHP.

Kéké
PS : après réflexion, il n'est pas utile de trier par race dans la 2eme étape.

[Roworll]

La reformulation est correcte.

A chaque "tour" les besoins d'un PNJ évolue bien différemment d'un individu à l'autre et ce même au sein de la même race.
Astyrion N°1 peut avoir +1/+2/+1/+3/+4/+2 et Astyrion N°2 +3/+1/+2/+3/+1/+2

[keke]

Oki ^^. Bon on attends voir si d'autres proposent des algorithmes intéressants ^^

kéké

[wild-D]

- Récupérer dans un tableau la liste de tout les PNJ trié par race (id_png, id_race, Faim |Hygiène| Santé | Repos | Loisir| Zen)

j'ai peur sur le long terme que ça soit un peu rustre (devoir faire transiter toutes les données -la table complète- entre PHP est SQL je le sens pas trop; au final je sais pas si ça permet vraiment d'alléger le serveur SQL )

la première idée qui m'est venue aurait été (mais lourd coté serveur bdd puisque tout sql ):
une requête update par race avec procédures stockées.

[Allwise]

Comme Keke pour l'idée de stocker les données en mémoire : Memcache ou le moteur de MySQL qui gère les tables en RAM. Je pense aussi qu'il faut pas une instance par PNJ mais qu'il faut les regrouper au maximum. Par contre, pour ce qui est de faire une update de la BDD toutes les heures, moi j'en ferais plutôt une toutes les nuits à une heure creuse, par sécurité, et au lieu de taper sur la véritable table qui stocke les données, je taperais toujours sur mon serveur Memcache ou sur ma table MySQL en RAM.

[Roworll]

Je viens de faire des essais avec ma solution (je détaillerai plus tard) en utilisant une table de 250.000 PNJs histoire d'avoir des résultats vraiment visibles.

Je mets en moyenne 4.3 secondes pour faire tourner la procédure en local et 3.1 sur le serveur mutualisé (pas de MEMCache disponible dessus) qui m'héberge.

[barst]

Je peux te proposer une solution purement SQL si tu veux.

Il te faut créer une nouvelle table :

Code :

besoin
=====================
race_id
besoin_id
tirage
valeur

et les besoins des PNJ seront stockés dans la table suivante :

Code :

besoin_pnj
======================
pnj_id
race_id
besoin_id
valeur

En gros la table "besoin" va te contenir par race et par besoin 100 lignes correspondant chacune aux résultats de chaque tirage possible.

Donc tu as recensé 4 races et 6 besoins avec 100 valeurs possibles de tirage ce qui te donne une table avec 2400 lignes au total (4x6x100)

Pour connaître la valeur d'un tirage aléatoire d'un besoin d'une race, il suffit d'exécuter la requête :

Code :

select valeur from besoin where race_id=<race> and besoin_id=<besoin> order by rand() limit 1

Et pour mettre le tout à jour, tu as besoin d'une seule requête :

Code :

update besoin_pnj a set a.valeur = a.valeur+(select b.valeur from besoin b where b.race_id=a.race_id and b.besoin_id=a.besoin_id order by rand() limit 1)

[Roworll]

Donc tu as recensé 4 races et 6 besoins avec 100 valeurs possibles de tirage ce qui te donne une table avec 2400 lignes au total (4x6x100)

Il y a une petite erreur d'analyse sur ce point je pense (je n'ai peut être pas été assez clair). Il n'y a pas un tirage qui détermine les 6 caractéristiques mais un tirage par caractéristique. Si on veut envisager toutes les combinaisons possibles, on a par race 100^6 combinaisons sur les tirages.

Je me pose aussi la question des performances d'un SELECT imbriqué incluant qui plus est un ORDER BY RAND() mais je vais faire quelques tests dessus.

[barst]

Pour la race "Astyrion" et le besoin "Faim", tu as bien 100 valeurs possibles de à chaque tirage de 1 à 100.

Ce qu'on sait, c'est que chaque fois que tu effectueras un tirage donnant la valeur "97" pour la race "Astyrion" et le besoin "Faim", il faudra ajouter "5" à ce besoin.

Ceci est donc des données de référence et statiques du type

Code :

Race : Astyrion
Besoin : Faim
Valeur tirage : 97
Augmentation besoin : 5

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.
Tu as donc bien un tirage indépendant par couple <race;besoin>.

Il n'y a pas un tirage qui détermine les 6 caractéristiques mais un tirage par caractéristique

Cette phrase veut-elle dire que la "Faim" de tout les PNJ de la race des "Astyrion" progresse de façon identique à chaque tirage ?
Si oui, alors il faut simplifier ma méthode car elle s'applique à chaque PNJ de manière indépendante.