Algorithmes de génération de ville

Dans ce post RPG.SE, une page perdue depuis longtemps avec plusieurs générateurs en ligne est mentionnée.

Je suis particulièrement curieux de savoir comment les villes ont été générées. Prenez cette image par exemple:

Bien que beaucoup de choses puissent être améliorées au niveau graphique, c'était très bon compte tenu des outils disponibles à l'époque (du milieu à la fin des années 90):

• Le tracé de la route semble assez organique (même si toutes les routes sont placées de manière orthogonale).
• Toutes les routes ne sont pas nécessairement connectées, mais cela semble bien .
• Les bâtiments sont placés dans des endroits crédibles .
• Même les arbres semblent être placés dans des endroits logiques .

Je pense que ce serait amusant de l'essayer et de l'essayer moi-même. D'autant plus que mes précédentes tentatives ont été trop "blocées":

Vous remarquerez que je décris de nombreuses qualités avec des adjectifs pas tout à fait mesurables ( semble , se sent , crédible , etc.), donc j'ai du mal à les traduire en instructions et, finalement, en algorithme.

Existe-t-il des algorithmes éprouvés pour la génération de villes?

Je comprends que cela semble être trop large, alors considérez ceci: si je demandais un algorithme pour générer des cartes des masses continentales, j'obtiendrais immédiatement des références à Perlin et à d'autres algorithmes de bruit; suivi de près par Voronoi.

J'ai vu des questions comme celle-ci, mais elles semblent avoir déjà une idée plus concrète en tête (par exemple: maisons 2x2, nombre fixe de maisons, restrictions de placement des canaux et des routes).

Ce que j'aimerais avoir, c'est quelque chose de moins contraint. Sauf peut-être pour la disposition de la grille, qui devrait être beaucoup plus facile pour une première tentative que, par exemple, le système L.

Introversion Software a créé un générateur de ville vraiment impressionnant pour leur projet annulé indéfiniment suspendu Subversion :

L'algorithme est conçu pour générer de grandes métropoles modernes. Mais les mêmes techniques peuvent être utilisées pour générer plus d'établissements ruraux.

Il s'agit d'un algorithme descendant qui génère d'abord les grandes lignes puis génère de plus en plus de détails pour s'y adapter (pour l'approche ascendante opposée à la génération procédurale, vérifiez la réponse de uliwitness). Voici une vidéo qui visualise l'algorithme en cours .

L'algorithme semble fonctionner comme suit (légèrement simplifié):

1. Centres-villes: choisissez certains points de la carte encore vide comme principaux nœuds de circulation. Ils doivent être répartis uniformément sur la carte
2. Autoroutes: connectez les principaux nœuds de circulation à leurs voisins et au monde extérieur en utilisant les routes principales.
3. Autoroutes: subdivisez les cellules générées par les routes principales en créant des routes secondaires.
4. Rues: Répétez le processus de subdivision récursivement avec des routes de plus en plus petites jusqu'à ce que vous ayez atteint la taille de bloc de construction souhaitée
5. Blocs: Décidez de l'objectif de chaque bloc de construction (résidentiel, commerce de détail, entreprise, industriel ...). Les facteurs pertinents sont la taille des routes voisines et la distance du centre.
6. Attributions: divisez les bords de tous les blocs de construction en lots (cela signifie que chaque lot a au moins un bord relié à une route).
7. Bâtiments: générez un bâtiment approprié pour chaque lot.

Concernant le placement des arbres: Ma première approche serait d'intégrer ceux dans l'algorithme de génération de bâtiment. Un bâtiment n'a pas besoin de remplir complètement son terrain. Vous pouvez remplir l'espace libre avec des objets décoratifs appropriés.

Le problème avec l'approche descendante est que même si elle peut générer une ville plausible, elle peut ne pas générer une ville plausible avec tout ce que vous voulez . Disons que chaque ville de votre jeu a besoin d'un magasin d'armes, d'un magasin d'armures, d'un magasin de potions et d'une auberge. L'algorithme ci-dessus sélectionne les bâtiments en fonction des exigences du lot, vous pourriez donc vous retrouver avec 12 magasins d'armures mais pas une seule auberge. J'aborderais ce problème dans la phase de génération du bâtiment. Avant de commencer à générer des bâtiments au hasard, parcourez votre liste de bâtiments incontournables et sélectionnez le lot le plus approprié pour chacun d'eux. Remplissez ensuite les lots restants avec des bâtiments randomisés.

J'ai hâte d'explorer les villes générées de manière procédurale dans votre jeu.

Obtenez des contraintes de la vie réelle

Souvent, la réponse sur la façon de trouver le bon algorithme commence par regarder comment ces choses se produisent dans la vie réelle. Avez-vous examiné cela? Du haut de ma tête, je peux penser à ce qui suit:

• Les routes sont là pour relier les bâtiments et autres points d'intérêt
• Les bâtiments sont placés le long des routes existantes, si possible
• S'il n'y a pas de route, un bâtiment est placé dans un endroit vide et connecté à une route voisine via sa propre route
• Les bâtiments sont placés à proximité d'autres bâtiments qui intéressent leurs habitants: les gens se déplacent pour vivre près de leurs lieux de travail, magasins d'alimentation et de vêtements, etc.
• Les bâtiments sont placés à proximité des ressources nécessaires à leur utilisation prévue. Par exemple, une scierie est placée près des forêts, ou même dans une clairière. les gens ont besoin d'eau et de nourriture (plantes, animaux) pour vivre quelque part.
• Les bâtiments sont placés loin des autres bâtiments qui sont préjudiciables à l'usage auquel ils sont destinés ou qui leur seraient préjudiciables. Par exemple, un magasin de teinturier sent horrible, il n'est donc généralement pas placé dans un quartier résidentiel. De même, les tavernes et les restaurants sont bruyants, de sorte que les résidents ne veulent pas vivre au-dessus d'eux, mais ont besoin de clients, doivent donc être à proximité des zones résidentielles.
• Certains pays ont des lois de zonage qui influencent également l'emplacement des bâtiments. Habituellement, il s'agit d'une façon plus formelle d'anticiper quels types de bâtiments peuvent se nuire les uns aux autres, ou quelles ressources sont uniques à la zone (comme un sol de haute qualité pour les champs, pas pour la construction de parkings).
• Les bâtiments sont destinés aux habitants, et leur style et leurs préférences personnelles se reflètent en eux. Par exemple, si une population est pauvre, ils sont beaucoup plus susceptibles de partager le sol (gratte-ciel, immeubles à appartements), s'ils sont plus aisés, ils peuvent obtenir des préservatifs, s'ils sont riches, ils obtiennent une villa autonome. Si certains groupes n'aiment pas d'autres groupes, ils seront moins susceptibles de cohabiter. S'il existe une affinité entre certains groupes, ils peuvent se déplacer vers des zones similaires.

Appliquez-les à votre topographie

Une fois que vous avez ces contraintes, vous pouvez essayer de construire un algorithme autour de lui. Par exemple, générez votre topographie et répartissez les ressources nécessaires sur la carte (en gardant peut-être un œil sur le placement de petits gisements des ressources les plus importantes dans la zone de départ, puis sur des gisements plus importants plus éloignés et les uns des autres). C'est là que les besoins et la mécanique de votre jeu entrent en jeu, bien sûr, mais vous ajouterez probablement également un élément aléatoire.

Construisez ensuite des entreprises (et leurs immeubles résidentiels) à proximité des ressources qui les utilisent. Par exemple, une carrière à côté d'une grande montagne. Ajoutez ensuite l'infrastructure dont ils ont besoin. Par exemple, un poste de traite avec bureau de poste et taverne où ils peuvent faire des affaires et vendre leur produit, une forge pour fournir des outils, etc.

Pour décider de ce qui va où, divisez la carte en tuiles où vous calculez un nombre pour chaque tuile combien il est souhaitable pour un certain but, en utilisant une fonction de pondération. Mettez les bâtiments dans les tuiles les plus souhaitables pour ce type de bâtiment. Ajoutez des règles comme «un poste de traite peut gérer 50 entreprises ou 100 maisons», ce qui augmente la probabilité d'ajouter un autre poste de traite si une ville atteint une certaine taille.

Une fois que vous avez cela, vous devriez obtenir des cartes assez décentes. Si vous remarquez que toutes les cartes se retrouvent sous des formes non naturelles, ajoutez des pénalités à vos fonctions de pondération pour ces formes, comme "si ma rue se retrouve juste à côté d'une autre rue, -100 désirable", ou "si ma rue se croise, -100 désirabilité "etc. Vous pouvez toujours ajouter un élément aléatoire pour permettre une sensation plus originale, ou ajouter d'autres mécanismes comme" si un croisement a plus de N bâtiments connectés à ses routes, transformez-le en un rond-point ".

Vous pouvez même utiliser ces contraintes pour donner à différentes cartes une sensation différente, comme faire en sorte qu'un certain pays ait plus de montagnes dans sa topographie, ou qu'une certaine culture construise plus de routes sinueuses, et une autre préfère les routes droites, etc. Tout simplement en modifiant l'une de vos fonctions de pondération.

Simplifier

Bien sûr, cette approche est trop complexe pour les jeux qui ne sont pas des simulations commerciales, mais travaillez quand même et voyez quels types de bâtiments conviennent à votre jeu et éliminez ceux qui ne sont pas nécessaires. Puis venez avec des règles simplifiées comme "placer les villes près d'une rivière, d'une montagne ou d'un bon sol. 1 bâtiment pour 100 ressources, entreprises basées sur le type de ressource, 10 bâtiments résidentiels pour chaque ensemble complet de ressources alimentaires / artisanales ... ou tout simplement" 1m de rivière / 1m2 de sol peut supporter 10 bâtiments résidentiels ... tout ce qui a du sens pour un jeu. Pourtant, une fois que vous savez quelle superficie vous avez (par exemple, pas de bâtiments sur les flancs des montagnes escarpés) et combien de bâtiments la zone peut supporter, placez simplement des ensembles de bâtiments dans cette zone jusqu'à ce qu'elle soit pleine (comme, 1 immeuble commercial, 10 résidentiel , 3 infrastructures ou autre) et les relier aux routes.