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

[Xenos]

On se répète un peu...

Autre solution: une structure en arbre.
Tu considère chaque individu, mais tu rassemble les individus en groupes, eux-mêmes pouvant être rassemblés en super-groupes (etc).
Au sens d'un groupe, tu simule chaque individu. Mais un individu d'un groupe ne pourra pas interagir avec un autre groupe. En revanche, deux groupes pourront interagir l'un avec l'autre, comme somme d'individus.
Par exemple, dans un groupe (quartier de ville), les gen sont simulés un à un dans leur quartier. Mais si tu passes à l'échelle "ville", alors les quartiers sont simulés de façon statistique (je suis pas sûr d'être clair... l'idée est de reprendre le principe de l'oct-tree en faisant en sorte de découper le nuage granuleux de population en des blocs indépendants, simulables indépendamment et rapidement).

Ce système permet généralement de passer d'un algo O(n²) à un algo ~o(n²/k) avec k le nombre de personnes par groupe. En d'autres mots, pour n=1.000.000 (nombre d'habitants), et des groupes de k=1.000 personnes, on aura environ (10e6)² calculs pour le cas granuleux simple (soit 10e12 ou 1.000 milliards) contre ((10e6)²/1.000) = 1 milliard de calculs. On A déjà pas mal "élaggué" le code. C'est d'ailleurs l'idée principale: au lieu de traiter toutes les interactions, on décompose en groupes de personnes qui peuvent interagir, de sorte qu'une personne d'un groupe ne puisse jamais interagir avec les individus d'un autre groupe.

Mais, là, c'est assez tordu, et peut-être pas la meilleure piste pour un jeu en ligne ("faites simple" étant le credo d'un jeu en ligne).

[Thêta Tau Tau]

Je pige pas bien pourquoi l'aglo serait O(n²), un algo O(n) semble être assez facilement réalisable. Le problème c'est surtout que le nombre d'individu est beaucoup trop élevé (1M d'hab par ville x le nombre de villes...) et qu'il faut donc chercher des algo dont le temps de calcul dépends pas ou peu du nombre d'habitants.

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.

Pas dans le dernier Simcity qui va sortir, où les PNJ sont justement gérés un par un. Et même dans les vielles versions il y avait possibilité de suivre quelques sims individuellement.

[Ter Rowan]

Pas dans le dernier Simcity qui va sortir, où les PNJ sont justement gérés un par un. Et même dans les vielles versions il y avait possibilité de suivre quelques sims individuellement.

a mon sens c'est du pipeau marketing :

on peut choisir n'importe quel sim qui a un comportement, mais après il retourne dans la masse, où bien il vit comme échantillon, mais je ne vois pas l'intérêt de créer autant de personnes que d'habitants.

Au plus volumineux, on créé comme entrée les sim qu'on veut suivre, le reste est statistique
Au moins volumineux, on créé comme entrée les sim qu'on veut suivre, et au bout d'un certain temps (arrêt du jeu, temps fixe, ...) on les détruit

[Xenos]

Tout ne sera pas n², mais il suffit qu'un algo soit n² pour que les centaines d'algo en O(n) deviennent négligeables (10.000² >> k*10.000 même pour k=100).

Des algos O(n²), il risque d'en avoir: un homme cherche une femme (ou inversement), est-ce que deux personnes se croisent dans la rue, est-ce que deux personnes travaillent ensemble (et ne peuvent pas s'encadrer donc, elles travaillent mal) etc. Bref, il y a plein de cas où il risque de gérer des couples d'individus, ce qui fera un nombre de possibilités à traiter de l'ordre de n².
Peut-être n'en aura-t-il pas, ok, mais en ce cas, on retombera sur les pots précédents, qui disent "fait pas une simulation de chaque bonhomme individuellement (car si y'a pas de n², y'a pas de couple, donc on traite individuellement) mais une simulation de groupe".

[Ter Rowan]

et dans le cas de trucs à trois ? vous êtes trop ... "classiques"

[Xenos]

Ok...

Alors on sera en O(pow(n, k)) avec k le nombre de partenaires...

*sors*

[Ter Rowan]

Ok...

Alors on sera en O(pow(n, k)) avec k le nombre de partenaires...

*sors*

voilà, enfin une formule mathématique satisfaisante, générique et moralement tolérante

enfin pour en revenir à l affaire :

calcul par individu ok si moins de 100 individus sinon statistique

[Thêta Tau Tau]

il y a plein de cas où il risque de gérer des couples d'individus

Oui mais il suffit, pour un habitant, de tirer X "rencontres" au hasard parmi les autres habitants, et on reviens à une complexité de n (et c'est plus réaliste, on ne rencontre pas tous les habitant d'une ville).

Mais bon ok ça reviens un peut au même que ton système d'arbre et de toute façon on est tous d'accords pour dire que ça sert à rien de simuler les habitants individuellement si le joueur les gère pas individuellement derrière (donc en faible nombre et donc moins de problèmes de perfs).

[Harparine]

Si je me souviens bien, un des guides du maître de Dongeons et Dragons proposait des pistes super intéressantes pour faire évoluer une ville de façon aléatoire. C'était simple car basé sur des jets de dés mais ça peut donner des idées...

[Marc15]

Merci pour vos conseils.

Je vais donc faire des statistiques sur l'ensemble de la population. C'est mon premier jeu donc je dois rester dans le domaine du possile pour moi.