www

commit aaaa71388914fd65446bd6501a17a632519d0062
parent 6e9661315b0537cdcb087dda12f89cc42009c006
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date:   Sun, 16 Oct 2011 20:41:31 +0200

Algorithmes (approx) de création de routes, plus de quoi les afficher en svg (make testroads).

Diffstat:
M
.gitignore
 | 
1
+
M
Makefile
 | 
6
+++++-
A
roads.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
A
roads.md
 | 
130
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 180 insertions(+), 1 deletion(-)
diff --git a/.gitignore b/.gitignore
@@ -1,4 +1,5 @@
 simple-terrain
 display
 roam
+roads
 *.o
diff --git a/Makefile b/Makefile
@@ -4,13 +4,17 @@ CCWARN=-Wall -Wextra -Werror
 CFLAGS=-O3 $(CCWARN) -g3
 
 .PHONY: all
-all: display
+all: display roads
 
 .PHONY: test
 test: all
 	# ./simple-terrain | display
 	./display
 
+.PHONY: testroads
+testroads: all
+	./roads | display
+
 simple-terrain: simple-terrain.c
 	$(CC) $< -o $@
 
diff --git a/roads.c b/roads.c
@@ -0,0 +1,44 @@
+#include <stdio.h>
+
+typedef struct Vertex {
+	int x;
+	int y;
+} Vertex;
+
+typedef Vertex Polygon;
+
+void svg_start(int w, int h) {
+	printf("<?xml version=\"1.0\" encoding=\"utf-8\"?>");
+	printf("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"%d\" height=\"%d\">", w, h);
+}
+
+void svg_end() {
+	printf("</svg>");
+}
+
+void svg_line(Vertex* a, Vertex* b) {
+	printf("<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" stroke=\"black\" />", a->x, a->y, b->x, b->y);
+}
+
+void roads(Polygon* quartier) {
+	quartier = quartier;
+	Vertex center = { .x=400, .y=300 };
+	svg_line(&center, &(quartier[0]));
+}
+
+int main() {
+	Vertex points[] = {
+		{ .x=10, .y=10 },
+		{ .x=790, .y=10 },
+		{ .x=790, .y=590 },
+		{ .x=10, .y=590 },
+	};
+	svg_start(800,600);
+	int i;
+	for (i = 0; i < 4; i++) {
+		svg_line(&(points[i]), &(points[(i+1)%4]));
+	}
+	roads(points);
+	svg_end();
+	return 0;
+}
diff --git a/roads.md b/roads.md
@@ -0,0 +1,130 @@
+Réseaux de routes/quartiers
+===========================
+
+On part d'un quartier qu'on subdivise en plus petits quartiers en y
+trançant des rues.
+
+Un quartier est un polygone (pas forcément convexe !). Sur les côtés
+du polygone, des routes entrantes et sortantes peuvent être
+marquées. La somme des entrées (+) et sorties (-) du polygone est
+nulle.
+
+Concentrique
+------------
+
+C'est équivalent à dé-polariser le repère et construire un « mur »
+(sorte de grille avec beaucoup d'horizontales de grande longueur).
+
+Il faut trouver un algorithme de construction de mur, puis le
+re-polariser afin de pouvoir le lancer avec plusieurs centres.
+
+Grille
+------
+
+Algo 1
+
+* Choisir un angle.
+* Tracer des routes suivant cet angle et cet angle + 90°.
+* Les routes doivent pouvoir être assez longues (le tracé doit survivre à une intersection).
+
+Algo 2
+
+* Choisir un angle.
+* Tracer des petits segments de route suivant l'angle et l'angle+90°
+* Inhiber la subdivision de segments (ne pas les couper en deux).
+* Raccrocher les bouts des routes à des points proches si possible (et
+  tant qu'on ne dévie pas trop en angle).
+
+Algo 3
+* Prendre une grille carrée / rectangulaire.
+* La tourner d'un certain angle.
+* Rattacher au bord du quartier les segments de la grille qui le
+  croisent.
+* Supprimer aléatoirement certains segments, en gardant le graphe
+  connexe.
+
+Algo 4
+* Choisir un angle pour dessiner les croix.
+* Dessiner une grosse croix avec des angles de 90° entre les segments,
+  ± au milieu du quartier.
+* Subdiviser de la même manière les quatre (ou plus si le quartier
+  d'origine n'est pas convexe) quartiers ainsi créés, en gardant le
+  même angle (petites variations possibles).
+
+« Mur »
+-------
+
+Comme une grille, mais les angles ne sont pas vraiment à 90°, et il y
+a beaucoup de longues rues dans l'une ou l'autre des directions.
+
+    .________________________.
+	|   |        |      |    |
+	|___|________|______|____|
+	|         |       |______|
+	|_________|_______|      |
+	|______|__________|______|
+
+TODO : trouver un algo pour générer des « murs »
+
+Arborescent
+-----------
+
+On subdivise le quartier en polygones plus ou moins réguliers (grille,
+voronoi, …), et on fait partir un arbre depuis un point, qu'on étend
+jusqu'à avoir touché tous les polygones. Chaque polygone est un
+sous-quartier.
+
+Il est possible de s'arrêter avant d'avoir touché tous les polygones,
+auquel cas il faut regrouper les polygones non touchés avec d'autres
+pour qu'ils forment un seul quartier.
+
+Courbes de niveau
+-----------------
+
+Faire des routes suivant les courbes de niveau, avec la possibilité de
+monter ou descendre très légèrement pour rejoindre une autre ligne.
+
+* Partir d'un point, et choisir le point à X de distance qui minimise
+  le dénivellé
+* Condinuer à partir du point ainsi créé, en s'interdisant les retours
+  en arrière trop brutaux
+* Arrêter la ligne quand le dénivellé devient trop important, ou quand
+  on rejoint une autre ligne.
+
+Calculs nécessaires
+===================
+
+Polygones
+---------
+
+Il faut pouvoir, à partir d'une liste de lignes, déterminer les
+polygones ainsi découpés (ou bien maintenir un arbre de polygones
+qu'on découpe au fur et à mesure qu'on trace des lignes traversant un
+polygone), pour connaître les sous-quartiers créés en traçant les
+routes.
+
+Points proches
+--------------
+
+Énumérer les points et lignes proches d'un point donné.
+
+Pour cela, faire un quadtree (un arbre avec 4 fils à chaque noeud)
+représentant des carrés composés de quatre carrés, et stocker dans
+chaque noeud s'il contient des points dans son sous-arbre ou non. Les
+noeuds feuille listent les points qu'ils contiennent. Quand on dépasse
+un certain seuil pour le nombre de points contenus dans un noeud
+feuille, on le subdivise.
+
+Quand on ajoute un point au graphe des routes, on l'insère à la bonne
+position dans le quadtree.
+
+Quand on trace un segment entre deux points, on indique sa présence
+dans tous les noeuds qu'il traverse. *TODO* : cela coûte cher en temps
+et en espace !
+
+Intérieur d'un polygone
+--------------------
+
+Pouvoir sélectionner aléatoirement des points à l'intérieur d'un
+polygone (pour pouvoir faire les centres des réseaux concentriques par
+exemple).