Comment générer un réseau de voirie urbaine?

Je voudrais créer un générateur de ville pour un jeu, mais je suis confronté à un problème au tout début de la génération: le réseau routier.

Comme c'est un monde médiéval, je ne veux pas de plan de grille comme beaucoup de villes modernes. Je préférerais idéalement une génération pseudo-aléatoire de grandes avenues et de rues plus petites, où il pourrait être possible de se perdre, mais avec encore une certaine logique - pas un labyrinthe complet.
Quelque chose qui ressemblerait à une ville cultivée naturellement.

Afin de rester simple, disons que mes villes seraient sur des terrains plats et stables, sans aucun problème de traversée de rivière ou de secours. Je pourrais essayer de l'intégrer à une solution après.

Je n'ai pas décidé d'une taille ou d'une disposition précise pour mes villes, donc si vous avez une solution qui ne fonctionnerait qu'avec des villes d'une forme précise (carré, cercle, rectangle, etc.), je la prendrais.

Un bon point de départ pour la génération procédurale des villes est la modélisation procédurale des villes de Parish et Müller . Leur article présente un L-System dans lequel les règles concernant la densité de population et les modèles de route (grille rectangulaire, changement radial et de moindre élévation) sont combinées puis fixées pour s'adapter aux contraintes locales telles que les fronts d'eau et l'esthétique des routes. Bien que les résultats de ce système soient impressionnants, il a été critiqué comme étant inutilement compliqué . La solution alternative de Barrett est reformulée dans le blog de développement de Rudzicz Spare Parts comme suit:

• tenir une liste des routes «proposées»
• les évaluer dans un certain ordre
• s'ils sont acceptables (avec ou sans quelques modifications mineures)
• stocker chaque route acceptée tout en "proposant" une poignée de branches supplémentaires

Cette approche supprime la plupart des tâches ménagères de réécriture de symboles héritées de Parish et du système L de Müller. Vous pouvez voir une démo de cette approche ici .

Un avantage de cette approche est qu'elle est indépendante de la forme de la ville - vous pouvez ajouter des contraintes de contour au besoin, de sorte que la forme de votre ville puisse être déterminée par vos besoins en matière de conception de jeu plutôt que par l'algorithme. Selon la taille de votre ville, cela pourrait être suffisant en l'état. Voici un résultat de la démo ci-dessus avec une limite de segment de 100: Mais si vous avez besoin de quelque chose de gros, vous pouvez avoir des problèmes; voici un résultat avec une limite de segment de 500:

En partie, vous pouvez ajuster cela en modifiant les règles de branchement des routes, en évitant les angles à 90 degrés, etc. Si votre disposition est encore trop régulière, voici ma correction:

Transformez votre grille de ville en un graphique où chaque rue est un bord et chaque intersection est un nœud. Ensuite, utilisez l' algorithme que vous préférez pour convertir le graphique en labyrinthe . Voici le dernier exemple transformé en labyrinthe:

Maintenant, la sortie a le problème opposé, c'est trop comme un labyrinthe. Mais maintenant, nous pouvons appliquer quelques techniques du fonctionnement secret du générateur de donjon de Jamis Buck . Tout d'abord, augmentez la rareté en supprimant certains couloirs sans issue. Ensuite, augmentez la connectivité en ajoutant des routes qui créent des boucles (c'est-à-dire introduisent des cycles dans le graphique). Voici un exemple de résultat:

Remarque: il est possible d'obtenir le même résultat final directement à partir de l'étape de mise en page orientée vers la grille précédente (avant de générer le labyrinthe), en appliquant uniquement des suppressions de bord à la grille de la ville. Le problème avec cette approche est que vous devez vous assurer que la suppression d'un bord ne partitionne pas la ville, ce qui rend les parties inaccessibles.

Si vous recherchez des plans de ville médiévale / ancienne sur Google vous trouverez de nombreuses variantes différentes, principalement basées sur les origines de la ville (par exemple, règlement aléatoire ou position militaire organisée).

Je suppose que vous cherchez un règlement plus naturellement développé / chaotique.

Pour ceux-ci, j'essaierais une approche comme celle-ci:

• Commencez par une route principale allant d'un bout à l'autre (et reliant idéalement d'autres colonies. Si vous le souhaitez, créez une troisième route pour obtenir une jonction sur laquelle commencer votre colonie.
• Placez quelques maisons le long de la route (d'un côté seulement).
• Maintenant, élargissez cette route le long des maisons et ajoutez un point de repère majeur de l'autre côté (généralement une église, mais cela pourrait également être un moulin ou similaire). Ce sera votre centre / marché.
• Choisissez maintenant deux positions en dehors de la zone avec les maisons et créez une nouvelle route entourant les maisons.
• Créez éventuellement des alliés plus petits entre les maisons reliant l'ancienne et la nouvelle route.
• Maintenant, répétez jusqu'à ce que vous soyez satisfait de votre "noyau":
  • Ajoutez quelques maisons supplémentaires.
  • Ajoutez une autre route les entourant.
  • Ajoutez des ruelles reliant les routes.
• Une fois que vous êtes satisfait de cela, vous avez terminé. Si c'est censé être une ville, entourez-la de murs et répétez les dernières étapes plusieurs fois, en ajoutant des maisons supplémentaires à l'extérieur des murs.

Tout d'abord, il existe de nombreuses façons de faire de la génération procédurale et aucune d'entre elles n'est facile du tout, je vais faire une sorte d'approche sur la façon dont vous pourriez le faire fonctionner, à vous de le prendre, de le modifier ou de le rejeter.

Sera pseudo-code dans JS car il est plus facile à comprendre.

1º définissez un point d'entrée, comme vous voulez construire une ville médiévale, nous allons commencer par un carré, alors disons que votre ville aura 300 unités carrées et que la place sera au milieu d'elle (représentée par un X).

       300
________________
|               |
|               |
|               | 300
|       X       |
|               |
|               |
|_______________|

const square = [ 150, 150 ];

2º maintenant nous allons les avenues, il y en aura un nombre aléatoire, elles seront droites et partiront de la place du milieu ou d'autres avenues

let avenues = [] // will contain start and end [[sx,sy],[ex,ey]]
const n_avenues = RANDOM(4, 8); // number of avenues
const n_av_from_square = RANDOM(0, avenues); // starting in the square

for av in av_from_square
  avenues.push(square, [RANDOM(0, 200) + 100, RANDOM(0, 200) + 100])
  // we want avenues to have, at least 100 units length, thats why we randomize just te last 200 units of the whole town size

Cela devrait vous donner une place et quelques rues principales

       300
________________
|   \\          |
|    \\         |
|     \\        | 300
|       X=====  |
|               |
|               |
|_______________|

Maintenant, nous devons définir les avenues qui ne commencent pas sur la place principale, elles intersecteront les autres avenues

for av in (n_avenues - av_from_square){
  const av_to_intersect = avenues[RANDOM(0,avenues.length)];

  //check av_to... and get a perpendicular vector (explained bellow)
  av[0] = [ av_to_intersect[0][1], - av_to_intersect[0][0] ];
  av[1] = [ av_to_intersect[1][1], - av_to_intersect[1][0] ];

}

Pour obtenir des vecteurs perpendiculaires, vous devez permuter les cordons x, y et annuler le nouveau y:

glissé == x: noswiped.y, y: -1 * (noswiped.x)

En ce moment, vous devriez avoir quelque chose de similaire à ça, ça ne ressemble pas à une ville? : P

       300
________________
|   \\  //      |
|    \\//  ||   |
|     \\   ||   | 300
|    //\X=====  |
|   //     ||   |
|          ||   |
|_______________|

3º maintenant, il vous suffit d'interconnecter les avenues avec des rues courtes, vous pouvez également créer des carrés aléatoires tout au long de la ville et faire la même chose que ci-dessus pour chacun d'eux, ou simplement créer de petites rues à partir de certaines places secondaires, c'est à vous de décider.

N'oubliez pas que plus vos rues sont courtes, plus la ville est chaotique.