Génération Aléatoire d'Univers
Génération Aléatoire d'Univers
1. Introduction
J'ai tout récemment eu l'envie de m'atteler à la génération aléatoire d'univers, et cet article a pour but de vous faire partager mon expérience et mes résultats. Loin d'être un expert dans le domaine, toute contribution complémentaire sera appréciée. Le langage utilisé dans cet exposé sera TypeScript, dont vous pourrez trouver une présentation ici.
La génération procédurale pour créer des univers est une pratique très courante dans le domaine des jeux vidéos se déroulant dans le vide intersidéral. Le mythique Elite fut l'un des précurseurs et pour ne citer que quelques titres, on peut relever la série des Master of Orion, Galactic Civilization, Faster than Light, Star Wars: Empire at War, etc, etc, etc.
Je vais ici présenter les différentes approches que j'ai essayé pour générer des univers aléatoires ayant une topologie à peu près acceptable. Dans un plan en deux dimensions, il s'agira donc de générer un ensemble de positions (des étoiles ou des planètes dans le cas d'un contexte spatial, ou de villes s'il s'agit d'un contexte plus réaliste).
Ces positions devront être reliées par des liens (des chemins si on considère des villes, ou bien des routes spatiales si on est dans le vide intersidéral) de façon à respecter une certaine règle de proximité. On privilégiera de relier deux positions proches plutôt que deux positions éloignées.
2. Génération des positions
2.1. Approche naïve
Une position sera définie comme un point à deux dimensions ayant d'autres attributs que nous ajouterons par la suite. En TypeScript cela pourrait donner ceci :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Position extends Point {
// autres attributs...
constructor(x: number, y: number) {
super(x, y);
}
}
class Point {
x: number;
y: number;
constructor(x: number, y: number) {
this.x = x;
this.y = y;
}
} |
Pour le moment, la distinction entre Point et Position peut sembler assez artificielle. Elle n'est pas indispensable mais permet de bien séparer ce qui relève de l'outillage (la classe Point) et ce qui relève de la sémantique (la classe Position). Les fonctions utilitaires à usage généraliste seront associées à la classe Point, tandis que ce qui relèvera des spécificités de l'application sera associé à la classe Position.
Pour peupler notre univers, une façon naïve pourrait consister tout d'abord à générer un ensemble aléatoire de couples (x, y), où la valeur de l'abscisse (resp. de l'ordonnée) représente un pourcentage de la longueur (resp. de la largeur) de l'univers, puisque cette valeur est comprise entre 0 et 1. En retardant le plus possible l'utilisation des dimensions concrètes de l'Univers, cela permet de rendre l'implémentation plus générique.
Code:
1
2
3
4
5
6
| var nbPositions = 400; // Nombre de positions
univers: Position[] = [];
for (var i = 0; i < nbPositions; i++) {
univers.push(new Position(Math.random(), Math.random()));
} |
Ceci donne les résultats qu'on peut voir ci-dessous.
On se rend compte que cette approche naïve pose deux problèmes assez évidents. Le premier est que certaines positions sont trop proches du bord du domaine. Le second est que certaines positions sont trop proches les unes des autres ou se confondent.
La résolution de ces deux problèmes est assez simple. Pour le premier problème, nous réduirons l'intervalle des nombres aléatoires qui est pour le moment compris entre 0 et 1 avec la méthode de base Math.random(). Pour le second problème, nous empêcherons la génération d'une nouvelle position, si elle est trop proche de positions déjà générées.
2.2. Correction du phénomène de bord
Donnons-nous une "marge" autour du bord dans laquelle aucune position ne pourra être créé, et fixons sa valeur à 5% en longueur et à la même chose en largeur. Avec une simple règle de mise à l'échelle, cela donnerait la formule suivante applicable à la fois aux abscisses et aux ordonnées générées aléatoirement :
Code:
0.05 + 0.90 * Math.random()
2.3. Correction des points trop rapprochés
Pour éviter d'avoir des positions trop proches les unes des autres, il suffit de définir une distance minimale en deçà de laquelle générer une nouvelle position n'est pas permis. En utilisant l'approche simple, celle qui consiste à balayer linéairement l'ensemble des points existants, on pourrait avoir le code suivant :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| var nbPositions = 400; // Nombre de positions
var univers: Position[] = [];
var i = 0;
var point = new Point(0, 0);
while (i < nbPositions) {
point.x = 0.05 + 0.90 * Math.random()
point.y = 0.05 + 0.90 * Math.random();
if (isValidLocation(point, univers)) {
univers.push(new Position(point.x, point.y));
i++;
}
}
function isValidLocation(point: Point, univers: Position[]): boolean {
for (var i = 0; i < univers.length; i++) {
var pos = univers[i];
if (distance(point.x, point.y, pos.point.x, pos.point.y) < 0.02) {
return false;
}
}
return true;
}
function distance(x1: number, y1: number, x2: number, y2: number): number {
return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
} |
Il va sans dire au final, en terme d'efficacité algorithmique, que cette méthode n'est pas très efficiente puisque l'ordre de grandeur est une complexité en O(n²) ce qui peut vite se révéler rédhibitoire pour un grand ensemble de positions. Pour améliorer les performances de ce processus, il serait sans doute utile d'implémenter une variante de l'algorithme des plus proches voisins (All Nearest Neighbors)
Cependant, pour le moment, nous nous contenterons de l'approche "naïve" compte-tenu d'un nombre de positions à priori limité. Le résultat de ces modifications, l'ajout d'une "marge" et l'application d'une distance minimale entre les positions, donne ce qui suit.
Nous pouvons estimer en première approche cette distribution des positions comme satisfaisante ce qui nous amène à la seconde partie de cet exposé, à savoir la liaison entre les positions.
>> suite
