Génération automatique de map, dongeon, ...

[julien_s]

Bonjour,

J'ai commencé il y a quelques temps à coder un zelda-like où la map est auto générée (ce qui potentiellement permet des maps infinies - dans la me sure ou 2^256 peut être considéré comme infini). J'ai d'abord commencé en C puis en Python puis en JS (pour le côté graphique) puis après qq discussions avec Christopho j'aimerais l'implanter en Lua.

Le principe de base et la démo proviennent d'un article sur la simulation multi-agent:
"Auto-génération d'Environnement : l'exemple d'Infinite Forest "
http://payet.please.re/pub_date.html

Bref si des gens sont intéressés, qu'ils fasse signe.
Je vais essayé de poster l'avancement du programme à la suite de ce message.

++

[julien_s]

Bonjour,

bon j'ai posté la démo technique sur GitHub, enfin le code.
https://github.com/juliensiebert/Gurke

Le principe de la génération de map est le suivant:

On considère un 'monde' comme étant une grille de 'zones'.
Chaque zone est typée (zone marécage, zone désert, ...) et chaque 'zone' est elle même une grille de 'cellules'.
Chaque cellule contient un 'type' (eau, sol, arbre, roc, ...) et finalement, le joueur correspond (grosso-modo) à une cellule.

Ce découpage pourrait être amélioré pour ajouter d'autre choses. Pour le moment je m'en suis tenu à Monde, Zone, Cellule.

Ensuite, j'ai considéré un Monde (de coordonnées wx,wy) comme étant une grille de 16*16 Zones. Idem, une Zone (de coordonnées wx,zx et wy,zy) est une grille de 16*16 Cellules. Ce qui fait qu'un Monde donné fait 256*256 Cellules.

Le joueur est situé sur une Cellule donnée, dans une Zone donnée, dans un monde donné. On ne génère uniquement la Zone dans laquelle il se trouve et les 8 zones autour de lui (Nord,Sud,Est,Ouest,NO,NE,SO,SE) et le/s Monde/s correspondant.

Ensuite, on veut un monde cohérent (c'est-à-dire que si on revient sur ses pas,  on retrouve le même décor). Une solution possible est de générer un identifiant unique pour chaque Monde et chaque Zone et les construire de manière déterministe à partir de ces identifiants unique. Pour faire cela, j'ai utilisé la fonction de Hachage MD5 qui à la particularité de retourner 128bits. Je fais MD5(wx) MD5(wy) et je me retrouve avec 256 bits (idéal pour remplir une grille de 16*16).

À partir de mes 256bits, j'applique un algo (ici un automate cellulaire type jeux de la vie de Conway) pour générer différentes couches (une couche zone 'marécage', une couche zones 'terre', une couche zone 'montagneuse'...) que je fusionne ensuite pour donner un Monde.

Idem pour les zones, on génère un identifiant unique pour chaque zone (là encore j'utilise MD5: MD5(wx,zx) MD5(wy,zy)), j'applique un algo déterministe pour générer différentes couches (une couche 'herbe', une couche 'sable', une couche 'eau'...) que je fusionne pour donner une zone particulière.


Voilà
++

[julien_s]

Avec le screenshot

https://github.com/juliensiebert/Gurke/blob/master/ScreenShot.png

[Christopho]

Pas mal
Est-ce qu'il y a un moyen d'avoir la cohérence entre deux zones adjacentes ? Par exemple pour éviter qu'une grande étendue d'eau s'arrête net lorsqu'on change de zone.

[Wouf]

Tiens, est-ce que tu as souvent entendu parler de jeu se basant sur le jeu de la vie de Conway ?
Si tu as des références, ça m'intéresse. J'ai pas mal cherché et n'ayant rien trouvé, je pensais tenir une idée originale x')

C'est dingue, plus je regarde ton jeu, plus j'y vois de ressemblance avec mon projet (tiles/automate/hashage). comme quoi, one est rarement seul à avoir la même idée

[julien_s]

Salut,

Est-ce qu'il y a un moyen d'avoir la cohérence entre deux zones adjacentes

@Christopho: j'y ai un peu réfléchit et pour le moment je ne vois pas trop comment faire simple. C'est vrai que par moment il peut y avoir des séparations un peu trop net. Quoique avec des zones de 16*16 c'est pas encore trop visible.

est-ce que tu as souvent entendu parler de jeu se basant sur le jeu de la vie de Conway

@Wouf: à part l'article que j'ai cité dans le 1er message (j'allais dire en intro :p ), j'ai pas d'autres références.
Sinon, c'est quoi ton projet?

++

[Daru13]

J'avoue ne pas avoir tout parfaitement compris (notamment le coup du jeu de la vie de Conway), mais à propos de la cohérence inter-zones, deux algorithmes complémentaires qui me passent par la tête, qui seraient appliquées à la suite d'une génération aléatoire telle que décrite dans ton premier post :

Un premier algorithme pourrait vérifier si des éléments orphelins (ou même groupées en petit nombre : 2, 3) sont situées aux extrémités de chaque zone, et le plus simple serait alors de les retirer. D'ailleurs, un tel algorithme pourrait être utile pour la totalité de la surface des zones et non seulement les extrémités, afin d'éviter d'avoir un effet de dispersion des ressources vraiment très aléatoire (une case d'eau ou un buisson seul en plein milieu d'une zone, c'est souvent assez étrange et rare !).

Un second algorithme qui vérifie cette fois si des éléments de taille plus importantes sont en contact avec certaines extrémités de zones (par exemple, un étang coupé en plein milieu par un changement de zone). L'idée serait alors de créer l'autre bout de la zone concernée sur la zone concernée ; à partir de rien (simplement des coordonnées des cellules qui devraient forcément être en "contact" si les deux zones ne faisaient qu'une), ou par exemple en copiant l'élément (ex. l'étang coupé) sur la seconde zone, quitte à lui faire subir une symétrie/rotation, et en détruisant/ajoutant certaines cases autour de celui que l'on vient de copier afin de varier un peu d'un côté à l'autre...

Je ne sais pas si j'ai été très clair, je ferais bien quelques schémas pour illustrer ça, mais peut-être pas dans l'immédiat x).
Je serais curieux d'en savoir brièvement plus sur le "jeu de la vie de Conway" ou du moins le principe derrière en tout cas .

[pouetpouet]

On parle de génération aléatoire de contenu... le bat-signal s'allume dans les nuages de Solarus-ville.

Les jeux 3D se basent (presque) tous sur du bruit perlin pour la génération de map (avec de l'interpolation pour faire des caves, comme dans Minecraft). Le problème avec ça c'est que pour des jeux 3D ça peut rendre pas trop mal, mais pour des jeux 2D on a vite une carte très chiante.

Pour les premiers prototypes de Zelda Infinite, je me basais aussi sur une approche à automate cellulaire.
Le problème c'est que:
-  ça fait des cartes très chiantes.
- si on veut faire des cartes moins chiantes, faut mettre plein de cas particuliers dans le code et/ou faire des douzaines et des douzaines de passes, et ça devient *super* chiant à débugger. (heureusement vu qu'on est en 2D, c'est rarement un problème de performance).

Du coup depuis quelque temps (oui oui, PI n'est pas mort) je m'amuse avec des chaines de Markov basées sur des écrans de jeux Zelda 2D pré-existents - ça donne des résultats très sympa. Je suis encore en train d'explorer tout ça, mais c'est prometteur. Je posterai peut être un truc en ligne avec des screenshots etc. quand j'en serais à un stade plus avancé.

Sinon y'a pas mal de trucs sympa sur GDC Vault, et le subreddit r/proceduralgeneration. Peut être même dans les Game Gems, mais je suis pas chez moi donc je peux pas vérifier. Ah oui, il y'a aussi 2-3 articles sur le fonctionnement de Spelunky que l'on peut dénicher en fouillant un peu - ils ont une approche peu complexe qui marche très très bien.

Après, tout comme l'on dit "make games not engines", je dirais: "make games not procedural content generators". On peut passer tout le temps qu'on veut sur ses algorithmes de génération, au final il ne faut pas perdre de vue que l'on fait un jeu, et que le but d'un jeu est d'être plaisant à jouer. On peut avoir des algorithmes de génération super-complexes qu'on a passé des mois à créer, si le jeu est chiant, on aura juste fait un jeu chiant. Donc vaut mieux ne pas mettre la charrue avant les boeufs et ne pas perdre trop de son temps à obséder sur les algos. Et ne pas avoir peut d'utiliser des petits "trucs" pour rendre le résultat final sympa, même si ce n'est pas vraiment complètement "aléatoire".

Dans cet esprit, je finirais juste mon post avec cette petite histoire:



In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.

"What are you doing?", asked Minsky.

"I am training a randomly wired neural net to play Tic-tac-toe", Sussman replied.

"Why is the net wired randomly?", asked Minsky.

"I do not want it to have any preconceptions of how to play", Sussman said.

Minsky then shut his eyes.

"Why do you close your eyes?" Sussman asked his teacher.

"So that the room will be empty."

At that moment, Sussman was enlightened.

[Renkineko]

Après, tout comme l'on dit "make games not engines", je dirais: "make games not procedural content generators". On peut passer tout le temps qu'on veut sur ses algorithmes de génération, au final il ne faut pas perdre de vue que l'on fait un jeu, et que le but d'un jeu est d'être plaisant à jouer. On peut avoir des algorithmes de génération super-complexes qu'on a passé des mois à créer, si le jeu est chiant, on aura juste fait un jeu chiant. Donc vaut mieux ne pas mettre la charrue avant les boeufs et ne pas perdre trop de son temps à obséder sur les algos.

Je suis d'accord que le but d'un jeu est avant tout d'être amusant, mais il peut aussi être créé non pas pour amuser mais comme un défi personnel, le but à terme n'étant pas forcément d'y jouer mais d'arriver à générer un monde cohérent aléatoirement. Cohérent, pas amusant. Je ne suis pas sûr que Julien cherche vraiment ensuite à faire un jeu complet, j'ai plus l'impression qu'il s'axe vraiment sur le défi de la génération aléatoire. Après, je voudrais pas m'avancer, c'est surtout ce que j'ai ressenti en papotant un peu avec lui sur IRC :p il me corrigera si je me gourre =]

[pouetpouet]

Julien parlait d'un Zelda-like dans son premier post; j'ai donc assumé que c'était dans l'optique de faire un jeu.

Après, certes, si on veut s'amuser à faire un générateur pour le fun sans jeu derrière, on peut - mais à ce moment là, il faut définir une mesure de réussite. Réalisme géologique des maps? Ou bien préférence esthétique? Quand on ne sait pas où l'on va, c'est dur de savoir quand on est arrivé.

[julien_s]

Salut,

en vrac pour répondre dans le désordre :

merci pour la biblio sur la génération procédurale,
le but pour le moment c'est de voir jusqu'où on peut aller et de pratiquer un peu de Lua au passage,
et oui générer une map pour générer une map ça peut être fun et enrichissant techniquement parlant mais déboucher sur un jeu complètement ennuyeux,

donc pour le moment je fais au pas par pas sans trop me fixer d'objectifs (ps le code (js) est dispo sur github, et la démo jouable (pour le moment firefox ok, chromium pas ok) http://juliensiebert.github.io/Gurke/ )

++

[Renkineko]

Quand on ne sait pas où l'on va, c'est dur de savoir quand on est arrivé.

Je ne suis pas d'accord. Le voyage est plus important que le but, c'est ce que m'a appris Journey Le but peut très bien être de s'amuser et de dépasser ses limites, d'appliquer des algos, jusqu'à ce que l'on se lasse. C'est plus ou moins le cas de mon projet (sur lequel je ne communique pas car il n'a aucun intérêt aux yeux du grand public, il s'agit juste de tester des idées de game design avec le moteur Solarus et parfois de tester aussi les fonctionnalités du moteur lui-même). Le but peut être le voyage lui-même. Pourquoi inclure une notion de réussite dans tout ? Après tout, certains artistes ont déjà peint sans but précis, mais une fois la toile terminée ils savaient qu'elle était parfaite : et il a été prouvé que nous autres programmeurs sommes assimilés à des artistes, donc rien ne nous empêche de nous lancer dans un projet similaire =]

Bon après on s'éloigne un peu beaucoup du sujet avec ce genre de considérations :p

[Wouf]

"C'est dur" ne veut pas dire "c'est impossible"