Atoll, c'est un petit projet de jeu en C++, inspiré d'un jeu de plateau : Kahuna. L'idée était de proposer un jeu simple, jouable rapidement, et sur lequel je puisse développer un IA assez simple.

Comme dans kahuna, le plateau de jeu est un archipel d'iles, entre lesquelles chaque joueurs peut construire un pont. En construisant plus de la moitié des ponts d'une ile, les joueurs deviennent propriétaires des iles, le but du jeu étant de posséder le plus d'ile possible.

Là ou le jeu devient stratégique, c'est que lorsqu'un joueur prend la propriété d'une ile, il détruit tout les ponts de son adversaire partant de cette ile. De cette manière, il peut faire perdre la propriété des iles voisine à son adversaire. A ceci s'ajoute la possibilité de placer des bombes sur certains ponts, ou de piéger les liens non construit entre les iles. Ces bonus seront gagnés aléatoirement lors de la prise d'une ile.

Dans ce projet, ce qui me tenais vraiment à cœur, c'était la génération aléatoire d'une carte de jeu. La carte étant un graphe, où les iles sont des nœuds et les liens des arêtes, il faut se plonger un chouilla dans la théorie.

Théorie des graphes

La carte de jeu doit présenter environ une dizaine de nœuds, et ils doivent être reliés aléatoirement a d'autres nœuds, de manière à ne pas croiser d'autres arêtes. En théorie des graphe, on dit que ce graphe est planaire. Donc il faut que je soit capable de générer un graphe planaire.

Mais il faut aussi que les ils ne soit pas trop proche d'autres iles, ou d'autres liens (un lien doit passer dans la mer, pas au dessus d'une ile). Ce qu'il faut réaliser, c'est une triangulation de Delaunay. On relie les iles de manière à réaliser un maillage ou les triangles sont les moins plats possible. De cette manière, les noeuds sont les plus éloignés possible des arêtes.

Sachant que le nombre de noeud restera petit, il est possible d'implémenter un algorithme simple, sans se soucier de son efficacité : la méthode incrémentale. On obtient alors de jolies triangulations.

Dessiner les iles

Pour dessiner les iles, il faut ruser un peu. On pourrait dessiner un cercle autour de chaque point, mais il ne faut pas que les iles se superposent. Donc il faut que le rayon soit plus petit que la moitié du plus petit lien. Mais on aura des iles toutes de la même taille, ce qui n'est pas très esthétique.

La solution retenue est la suivante. Pour chaque point à l'intérieur d'un triangle, on cherche le sommet dont il est le plus proche, et on traduit ses coordonnées en coordonnées barycentriques par rapport à ce sommet. Puis, en fonction de ces valeurs, je colorie le pixel en bleu si il est éloigné du sommet, ou en jaune si il est proche. J'aurais ainsi autour des iles des portions de cercles plus ou moins grand selon la taille du triangle dans lequel il se trouve.

Pour colorier l'extérieur du graphe, il a fallu ajouter des points en dehors de l'image, pour que les triangles couvrent toute l'image.

Maintenant, je peux ajouter un peu de bruit, pour déformer le contour de mes iles. Le bruit de valeur est le candidat idéal. Je multiplie la valeur de la distance en coordonnées barycentrique trouvée précédemment pour un pixel par la valeur du bruit en ce pixel. On obtient un visuel beaucoup plus réaliste.

Il reste quelques artefacts, comme ces grandes lignes droite dans la mer, mais la carte est satisfaisante.

La carte se génère en moins d'une seconde, ce qui est suffisamment rapide. On pourrait tout optimiser, mais ce n'est pas le but recherché pour le moment