Realisation d'un algorithme de generation procedurale de donjon

Salut les gens,

En me balandant il y a peu de temps, je suis tombe sur ca. Et desirant perfectionner mon C++, je me suis dis "aller, on realise ca".
Malheureusement le 2 auteurs (l'original et celui la) sont un peu radin en code, et je galere un peu.

Actuellement, j'en suis la http://imgur.com/byE4LaN.png (j'ai volontairement pas mis le link en affichage, c'est du 3200*1800). La gen dans le cercle a l'air plutot correcte, mais l'algo pour separer les rooms a l'air de patauger dans le yahourt.

Est-ce que je ferais mieux de mettre de la physique avec box2d, et de tout delete ensuite? Ou quelqu'un pourrais me dire ce qu'y couille dans mon algo?

Tous les fichiers sont >LA<.


Merci d'avance!

Regarde donjon.bin.sh.
Le site utilise un script perl pour générer les donjons, dont il propose le code source, et même des explications.

Dans mon souvenir, l'algo place des salles, puis des portes, et balade un "ver" qui creuse les couloirs.

Une autre solution consiste à réaliser un quadtree(2D) ou octree (3D) pour placer aléatoirement des salles. Ensuite les lié avec un algorithme A* :)

Wao je ne m'étais jamais penché sur ce genre de sujet, et ça fait rêver ce genre de choses ^^.
Bon courage pour ta génération ;)

Voici un article intéressant sur la génération dans Diablo 3. Ils se basent sur des tiles qu'il colle aléatoirement.
http://www.diablowiki.net/Randomization

@leternel : Je connais deja leurs donjons, en fouillant le net pour trouver le resultat qui me conviens le mieux je suis tombe dessus, mais c'est pas la forme de donjon que je cherche.

@Astraya : Interessant comme article, mais c'est aussi pas du tout ce que je cherche.

Update!

Ma fonction qui renvoyais une position aleatoire dans un cercle etait pas bonne. Maintenant j'arrive a faire spawn toutes les rooms dans un cercle! http://imgur.com/uIn5Hex

Y reste plus qu'a les separer. Si quelqu'un a l'algo sous le coude je veux bien. Mais en attendant, je vais continuer a fouiller

Salut,

Citation:

---

Envoyé par Bl4ckb0ne

Si quelqu'un a l'algo sous le coude je veux bien. Mais en attendant, je vais continuer a fouiller

---

Ben, pourquoi ne pas utiliser "tout bêtement" un algo simple de gestion de collision (style AABB) :question:

après tout : toutes tes "pièces" peuvent -- en simplifiant très fort, peut être -- n'être considérées que comme des rectangles proposant une longueur et une largeur et positionnés à une place bien précise...

Tu peux donc définir une formule de "déplacement" qui fait que chaque "pièce" s'écarte d'autant plus du centre à chaque itération qu'elle est... déjà loin du centre et, une fois que tu as corrigé la position de chaque pièce, tu peux vérifier s'il reste des pièces qui entre en collision les unes avec les autres.

Il n'est même pas forcément nécessaire de trouver toutes les pièces qui entrent en collision : si tu n'en trouves ne serait-ce qu'une seule, tu recommence une itération d'écartement de tes pièces, avant de refaire un test de collision ;)

Une fois que tu n'as plus une seule collision entre les pièces, ton écartement est terminé, et tu peux commencer à supprimer les pièces qui sont "décidément trop petites", avant de les relier entre elles ;)

J'ai deja ma collision AABB, mais l'idee de les faire se deplacer du centre c'est pas bete du tout.

Sinon je pensais mettre une gravite avec box2d pour qu'il se charge de les separer.

Edit : FIXED IT!

Je mettais a jour la position de la room dans la classe, mais pas celle de la sf::Shape (oui, j'ai honte).