Discussion :

[SKone]

Bonjour,
je travail actuellement avec des amis programmeurs et graphiste sur un petit jeu. Un jeu sans prétention mais dont les algos à mettre en place me font devenir chauve. 2 principes pour ce jeu. Que chaque joueur est sa propre ville et sont propre scénario pour le scénario aucun problème un arbre conditionnel fera l'affaire. Il existera N scénario. Mais pour la ville cela se complique.
En faisant des recherches sur les solutions existante les L-Systèmes semblaient s'imposer d'eux même. Je suis tombé sur un thèse très intéressante d'un certain Julien Perret (ici). Qui présentait toute les techniques existantes pour la modélisation de ville, la génération de ville, les réflexions sur la ville, les modélisations de bâtiment, ... Bref tout ce qui a été fait sur les villes.
Et dans mes recherches je suis tombé sur 2 vidéos :
http://www.youtube.com/watch?v=xo5zO4QULcE
et
http://www.youtube.com/watch?v=yI5YOFR1Wus
Assez impressionnante dans la thèse Julien Perret parle que très bièvement des techniques utilisées pour réussir à faire cela. 4 modèles sont utilisés dans l'algo : Le modèle sans motif, Le motif San Francisco (pour les villes avec grand relief), Le motif New York très cartésien, et le motif radial style Paris.
Mon objectif est de réussir dans un premier temps à faire un équivalent de la première vidéo.

Pour l'instant mon L-Système est très simple puisque je ne sais pas par où commencé :
A veut dire allez tout droit dans un intervalle de +-45°
B veut dire allez à 90° à droite où à gauche.
Mon axiome A à 0 degré.
Mes règles :
A donne A, B ou AB (bifurcation)
B donne A ou AB
Le tout avec une probabilité de présence uniforme.
Et le résultat :
au rang 3
http://img297.imageshack.us/my.php?i...7792151bn9.jpg
au rang 10 :
http://img98.imageshack.us/my.php?image=10dn8.jpg
au rang beaucoup :
http://img299.imageshack.us/my.php?i...eaucouppw7.jpg
Pas très jolie aucun motif, ...
Donc je demande votre aide pour l'élaboration de cet algo.

PS : Sur les exemples je n'est pas encore implémenté les algos correctifs au L-Système :

1. Si la route tracer coupe une autre route on l'arrête avant et on crée une intersection
2. Si devant la route tracer dans un cercle autour du point d'arrivé il existe une route dans ce cas on ce colle à la route
3. Si devant la route dans un cercle donné il existe une intersection on ce colle à cette dernière

Ces corrections n'ont pas été collé puisque qu'aucun motif n'apparait.
Merci pour vos futurs réponse

[luckyvae]

j'ai déjà bossé pendant un bon petit temps avec les L-System (j'ai fait un compilateur L-System) et je pense qu'il y a certaines choses qui ne vont pas.
Selon moi, il faudrait combiner plusieurs techniques.
Le L-System que tu vas décrire te permettra de donner les grandes lignes de ta villes, mais pour ce qui est de faire les trois conditions que tu cites, ça va être difficile d'exprimer ça via un L-System...

Tout d'abord, je me pose la question de savoir quel genre de villes parmi les trois que tu cites tu aimerais?

Ensuite, crées ton L-System relatif à ce motif de ville. Tu transformes ce L-System généré en un graphe ce qui te permettra d'effectuer les trois modifications dont tu parles.

Et puis, ça dépend aussi de quelles fonctions sont présentes dans ton L-System. Est-ce qu'il prend en compte plusieurs règles pour une variables? (A -> B ou A-> C) Est-ce qu'il est sensible au contexte? (AB -> C, mais BA->D)

Sinon, tu peux aussi te créer une autre façon de faire:
utiliser des algorithmes de création de chemins via une IA comme décrit sur ce site: http://www.rennard.org/alife/french/ants.html
Tu n'auras plus qu'à créer les centres d'intérêts dans ta ville et déterminer ton nombre d'habitant. Mais ça, je suppose que ça peut être extrait du gameplay, non?

[SKone]

Pour l'instant je me concentre surtout sur la ville style New York. Et l'algo correctif (3 conditions) je les faits lors de la création d'une branche de route.
Pour l'instant l'objectif c'est de convergé vers les densités de population, esquivé les zones interdites (eau, parc, ...). Mais je ne saisi pas le truc a plusieurs variable ?
Voilà ce que j'ai réussi à faire en jouant depuis tout a l'heure avec les densités de probabilité de présence des angles et des règles, ... (Après intégration sur le moteur kjAPI) :



Les traits verticaux rouges sont les carfours, les traits fuchia son les A et les traits cyan les B.
[EDIT]time=5h47
Nous venons de faire un progrès en ajoutant le petit 1 des contraintes que j'appel algo correctif :
résultat :

et

La dernière est au rang 123
[/EDIT]

[Emmanuel Deloget]

Il faut effectivement combiner plusieurs techniques - un L-System, mais aussi un méta-langage qui est capable de décrire comment placer les différents éléments du décors (les affiches? les lampadaires? ...), comment la ville grandit (ce qui permet de situer un centre-ville historique ou le style de bâtiment est différent par exemple), etc.

C'est ce que Gamr7 fait avec son middleware spécialisé. Lionel (le fondateur de la société) a accepté de nous parler un peu de sa technologie dans une interview en anglais qui a été postée l'an dernier sur gamedev.net (à l'occasion de la GCDC'07) (si vous n'arrivez pas à lire l'interview à partir de la page, le fichier MP3 est ici).

C'est aussi le chemin qu'a pris la société Procedural Inc pour CityEngine. A noter que plusieurs publications scientifiques concernant ce projet sont disponibles. A voir aussi, le wiki du fondateur de Procedural Inc.