Jeu de gestion d'une ville où chaque citoyen a son IA

[Marc15]

Bonjour,

J'aimerais que dans mon jeu (gestion d'une ville), chaque citoyen ait sa propre intelligence. J'aimerais que tous les citoyens soient indépendants. Ils n'ont pas besoin d'un nom, mais seulement de quelques caractéristiques (éducation, santé, humeur, argent) et qu'à chaque tour, ils prennent des décisions comme changer de travail, acheter une plus grand maison, avoir des enfants, etc.

Est-ce que ceci est techniquement possible en PHP? Je suis presque sûr que oui. J'ai déjà quelques idées pour l'implémentation, mais je me demande si j'aurai les ressources nécessaires côté serveur.

Le problème, c'est qu'une ville doit avoir au moins 100 habitants pour que ça soit intéressant, mais j'aimerais des villes avec des centaines de milliers voire des millions d'habitants. Pour une jeu de petite envergure, disons 100 joueurs seulement, cela demande une table avec plusieurs millions d'entrées. Je ne crois pas qu'une base de données standard comme MySQL sera utile dans ce cas.

Pour le moment, j'ai pensé faire prendre les décisions pendant le tour et non pendant les changements de tour. Par exemple, lorsqu'une usine ouvre ses portes dans une ville, un algorithme trouvera une liste de citoyens qui changeront de travail à la fin du tour. À la fin, tout est déjà précalculé donc le changement de tour se fait plus rapidement. Bon, c'est toujours dans les grandes lignes, c'est sûr...

Avez-vous des pistes ou des idées pour l'implémentation de ce genre de mécanisme? Le jeu est en PHP, mais je suis ouvert aux autres langages/technologies.

Marc15

[Malya]

Salut

Désolée de décevoir, je ne peux techniquement pas t'aider, mais j'ai une petite question... Le joueur il décide quoi du coup si ce sont tes algorithmes qui décident des meilleurs choix possibles pour l'évolution de ta cité?

Tant bien même, un joueur tente l'expérience et peut choisir d'accepter ou non les choix (s'il sont proposés et non pas imposés), il faudrait qu'ils connaissent la vie de milliers de citoyens? oO Ou alors je n'ai pas compris un truc dans le jeu? C'est une sorte de supers sims? Ou un jeux avec un perso jouable mais qui est soumit à une multitude de changements extérieurs opérés par les pnj et leur IA?

[SorenS]

La difficulté est plutôt dans les différents algos.

Pour la base de donnée t'inquiète c'est pas des millions d'entrées qui feront peur à MySQL.

[Marc15]

Le joueur (personne réelle, physique) construit des bâtiments (usines, écoles, etc). Ils choisit aussi les salaires.

Les citoyens (fictifs, controllés grâce à l'IA) doivent trouver du travail, acheter des biens, etc. Ces décisions sont prises selon des algorithmes. Un algorithme simple serait, par exemple, de prendre le travaille le plus payant. Ensuite, la décision sur la maison achetée sera calculée selon le salaire.

Le problème, c'est comment faire tous ces calculs pour des millions de citoyens et ce, à chaque changement de tour (24 heures par tour). J'ose pas imaginer faire une boucle sur 10 millions de citoyens, et pour chacun d'entre eux, faire des boucles parmi la liste d'emplois disponibles, de trucs à acheter, etc.

D'où ma première idée : exécuter les algorithmes dès qu'un joueur propose fait des changements dans sa ville (expliqué dans mon premier message). Ça reste quand même quelque chose de grand à programmer et assez lourd.

---

La difficulté est plutôt dans les différents algos.

Pour la base de donnée t'inquiète c'est pas des millions d'entrées qui feront peur à MySQL.

Chercher dans des millions de données, je sais que c'est possible. Mais si je veux faire un SELECT, puis exécuter tous les algos, puis faire une UPDATE pour chaque entrée, je sais pas si c'est pareil. Je crois pas, mais peut-être que je me trompe.

[Xenos]

Effectivement, la puissance va te poser soucis:
- La complexité des algos, comme l'a souligné Sorens, au sens de "complexité d'exécution" et non "conception compliquée" (autrement dit, les algorithmes seront leeeeeeents*)
- La masse de données dans la DB (des millions d'entrées, pas de soucis pour MySQL... mais si chaque entrée fait 100 octets, tu te retrouve avec des BDD qui montent rapidement à des centaines de Mo, et tu seras forcé de prendre un hébergement "lourd", un dédié ou un VPS: bye bye le mutualisé pas cher qui permet de démarrer presque sans frais)

Le principe de n'exécuter l'algo que si un joueur fait un changement dans sa ville ne sera probablement pas une solution miracle, car cela fera quand même des masses importantes de données à traiter. De plus, si tu pars là dessus, attention à ne pas faire (comme j'ai fait...) attendre le joueur 10 ou 20 secondes le temps de simuler ta ville. Crois-moi, après expérience réelle ("IRL"), les joueurs ne restent pas sur ton jeu s'il mets 20 secondes avant d'afficher une page...
L'asynchrone ne résoudra pas grand chose car le joueur aura des données obsolètes tant que la simulation ne sera pas faite (en synchrone: j'envoie un ordre, le serveur mouline, et il me répond avec un résultat actuel; en asynchrone: j'envoie un ordre, le serveur mouline, je continue à jouer avec les données de "avant l'ordre", le serveur me répond plus tard: pendant un laps de temps, j'ai joué avec des données obsolètes).

Si tu pars sur des millions de citoyens, il vaut mieux, à mon avis, revoir la conception et constituer des "intelligences collectives" plutôt que de faire des IA individuelles. Par exemple, au lieu de dire "je vais considérer l'attribut 'santé' pour chaque citoyen, tu peux considérer une valeur de santé pour tous les citoyens, et définir une fonction de répartitions de la santé entre tous les citoyens, c'est à dire une fonction qui à x, "l'identifiant" du citoyen, associe f(x), sa santé. Cette fonction aura une "aire" égale à la santé totale de ta population, mais au lieu de manipuler 10.000 valeurs de santé indépendantes, tu manipules uniquement une fonction avec un minimum (le citoyen le plus faible, osef de qui c'est) et un maxima (le plus en forme).

Bref, à mon avis, simuler chaque unité indépendamment aura l'inconvénient d'être trop lourd pour le serveur, et n'aura pas l'avantage d'une étude statistique sur toute la population (en d'autres mots, que tu simules chaque citoyen ou que tu simule tout le groupe de citoyen avec des outils mathématiques et statistiques, tu auras les mêmes résultats, à un pet de lapin près qui ne justifiera pas la puissance de calcul déployée).


*: Exemple pour une ville de 2*N habitants: N hommes, N femmes.
Un homme cherche une femme. Il a N choix.
Un autre cherche une autre femme, il a "grosso modo" N choix aussi (N-1 en pratique, mais si N est grand, exemple 10.000, alors N-1~=N car 10.000, c'est "pas loin" de 9.999; la notion de "pas loin" simplifie les calculs et se justifie mathématiquement).
Si, pour chaque homme, tu "teste" si une femme peut lui plaire, alors, pour chaque homme, tu va faire N tests.
Comme il y a N hommes, tu vas faire N² tests. Et donc, si N=10.000, tu te retrouves avec 100.000.000 de tests à faire: pour php, ca va dérouiller le serveur...
Tu risques donc d'avoir une difficulté de puissance de calcul, PHP ne sera probablement ps adapté, et il faudra se tourner vers du C au moins.

[Marc15]

Merci, très intéressant.

J'avais pensé faire des calculs collectifs, mais j'avais peur que les résultats soient trop différents de la vraie situation. Par exemple, dans une ville de 1000 citoyens, il y a 500 jobs à 10000$/mois et 500 jobs à 100$/mois, alors le résultat est positif : 5050$/mois en moyenne dans la ville. Mais en vérité, c'est 50% de riches et 50% de très pauvres.

Mais j'imagine que ça n'arrivera pratiquement jamais. En général, les joueurs ne se rendront jamais compte des écarts entre réalité et statistiques.

D'autres idées sont toujours la bienvenue.

[srm]

Même si ça arrive, tu peux très bien dire que tu as un salaire moyen de 5050$ et que tu as x% des jobs qui sont payés en dessous de X$/mois

[Ter Rowan]

Travaille par type de population

Exemple simpliste

Tous les hommes de moins de 25 ans ont le meme comportement
Toutes les femmes de moins de 25 ont le meme comportement
Tous les hommes de plus de 25 ont le meme comportement
Toutes les femmes de plus de 25 ans ont le meme comportement

Ça fait 4 comportements, quelque soit le nombre de citoyens

Maintenant un comportement est en réalité un ensemble de changement avec un peu de hasard

Exemple : le comportement homme de moins de 25 ans :

Entre 0 et 1 h-25 pour une population de 10000 devient f-25 (transsexualité)
Entre 5 et 10 h-25 pour une population de 1000 disparaissent (mort accidentelle, maladie, ...)
Entre 4 et 6 h-25 pour une population de 100 deviennent h+25 (ils vieillissent)

Après tu peux multiplier les catégories :

Richesse, couple ou non, nb enfants, etc...

Tu n es pas obligé d avoir des catégories unitaires, tu peux avoir des intervalles :
0 enfant
1 enfant
2-3 enfants
4-6 enfants
7 enfants et plus

Etc...

De meme les variables du comportement (exemple le taux de mortalité des -25 ans) peut évoluer fonction des décisions du joueur(prévention routière + hôpitaux + hygiène + pompiers, ....)

Les calculs peuvent être volumineux mais ils seront forcement plus petits que realiser des calculs unitaires

---

A noter pour les calculs, une option est de realiser une/plusieurs matrice(s) de transformation, par joueur (pour tenir compte des paramètres) après tout dépend si tu es a l aise avec le calcul matriciel

[Thêta Tau Tau]

Il y a plein de façon de représenter :
-Chaque individu a ses stats comme tu le proposait au départ, ça peut être très intéressant dans un jeu de micro-gestion, mais dès qu'on dépasse quelques dizaines d'individus ça deviens transparent du point de vue du joueur et ça pose des problèmes de performance.
-Avec des intervales pour chaque statistique, tu défini chaque catégorie comme un combinaison de statistiques possibles et tu lui assigne un nombre (par exemple il y a 112 "hommes de 20 à 30 ans, gagnant entre 1000 et 1500 euros par mois, mariés et avec 1 enfant"). Pour chaque modification possible, tu calcule la probabilité pour chaque catégories et tu tires le nombre d'individus avec une loi binomiale. Ça reviens au final à la même chose que la gestion individu par individu, sauf que tu es plus limité au niveau du nombre de stats et catégories (sinon le nombre de catégories deviens trop élevé et on perd à nouveau en performances).
-Pour chaque stat, tu enregistre sa distribution. Par exemple tu saura qu'il y a 800 personnes entre 20 et 30 ans, et 2000 entre 1000 et 1500 euros, mais contrairement à la méthode précédente, tu ne saura combien il y a de 20-30 ans qui gagnent entre 1000 et 1500 euros, tu pourras l'estimer par exemple, en multipliant les fréquences (20% de 20-30 ans et 35% de 1000-1500 = 0.2*0.35 = 7%), ou simplement en n'utilisant pas les stats dont tu n'as pas besoin (par exemple, pour le vieillissement de la population, tu n'as besoin que de l'âge). La c'est forcément plus bricolage, mais tu n'as plus de problèmes de performances.
-Tu ne garde que les moyennes, et le nombre d'individu faisant une action est déterminé arbitrairement (par exemple, si la moyenne d'âge est de 20 ans -> 0.5% de mort de viellesse, si la moyenne est de 75 ans -> 10% etc.). C'est forcément moins réaliste mais c'est aussi plus simple, à la fois à concevoir qu'à faire comprendre au joueur, et c'est pas forcément moins bien que des méthodes plus complexes.

Et bien sur on peux mixer le tout, avec par exemple une matrice "nombre d'enfant x superficie maison" (méthode 2), les distributions de salaire et d'âge (méthode 3), des moyennes (satisfactions, santé...). Et il reste possible d'avoir une partie des PNJ "uniques" avec un nom et des stats propres et gérés un par un, et le gros de la population "anonyme" géré par catégories. C'est un peu ce que je compte faire dans un projet actuellement en stand bye, avec des PNJ importants (officiers, maître artisans, scientifiques, bureaucrates, nobles...) gérés individuellement et le gros de la population (soldats, habitants), gérés globalement.

[Roworll]

En sortant de l'optique PHP, l'univers des jeux PC nous propose plusieurs approches ans la manière de gérer les populations.

L'une d'elle est la version 'Tropico'. Chaque citoyen est suivi à la trace avec ses envies, sa situation, ses activités, etc. Dans ce jeu, le joueurs peut même influer directement sur les habitants. Cette granularité implique une population réduite car chaque citoyen est considéré comme une entité à part entière. Dans une moindre mesure, on retrouve ces mécanismes dans d'autres jeux comme Settlers ou Startopia.

A l'autre bout de l'échelle, nous avons SimCity avec ses mégapoles ou résident des millions de personnes. Ici, on se contente de classer la population dans des statistiques en fonction de zones d'influence. Age, emploi, sécurité, loisirs, tout ou presque y est. Inutile de descendre au niveau de l'individu car cela n'apporterait pas grand chose. D'autres jeux comme Caesar, Pharaon et Zeus fonctionnent sur un principe similaire.

Maintenant, quel est l'intérêt dans ton jeu d'avoir des caractéristiques liées au citoyen ? J'imagine que les décisions des joueurs ne seront pas prises en fonction d'une poignée de personnes triées sur le volet mais bien à grande échelle selon les statistiques de la ville. Du coup, implémenter un algorithme qui de toute manière ne servira qu'à ressortir des stats globales nécessaires à la prise de décision me semble inutile, exception faite du coté 'défi technique'.

Rien qu'avec des règles de bases, le modèle peut être très compliqué.
Imaginons trois types d'entreprise (usine/commerce/high-tech). Chaque type d'entreprise requiert un niveau d'étude différent (basique/moyen/haut). La taux d'emploi sera fonction de la quantité d'offre disponible dans la catégorie correspondante. Ainsi, si tu n'as que des centres de recherche high tech mais pas d'université pour que tes habitants puissent étudier et y postuler, les citoyens ne trouveront pas de boulot, l'entreprise ne tournera pas et le rendement sera nul.
Même chose pour le domicile. Un employé dans une usine n'aura pas de quoi emménager dans un quartier huppé. S'il n'a pas d'offre correspondante à son niveau de vie, il y a de grande chances qu'il quitte la ville ou vienne grossir les chiffres de l'insécurité.
Ajoute là dessus des contraintes de lieu (distance travail/domicile), de besoin (commerces, loisirs, sécurité) et tu verras que le modèle commence déjà à se compliquer.

Donc, à mon avis, pas la peine de faire du cas par cas. Le moteur statistique sera déjà bien assez ardu à mettre en place.