Forums Développement Multimédia

Aller au contenu

Donjon, générer automatiquement les portes et clés ✔

CODE

80 réponses à ce sujet

#1 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 22 February 2013 - 15:11 PM

Salut la compagnie,

C'est pas souvent que je poste pour une question mais pour une fois j'en ai une ;-)

Pour mes exercices sur le Wiki je suis en train de travailler un générateur automatique de donjon.
Techniquement je génère d'abord un labyrinthe classique, puis j'y ajoute des pièces, je vous passe les détails ce sera expliqué dans l'exercice correspondant.

Maintenant j'ai une map qui ressemble à un donjon, c'est à dire avec des pièces, des couloirs, et une solution pour atteindre la sortie où qu'elle soit, ça c'est bon.

A présent je voudrait poser des portes fermées qu'on ne peut ouvrir qu'avec une clé.
Poser les porte n'est pas un problème mais..... pour ouvrir une porte il faut la bonne clé.
Si je construisait la map de mon donjon à la main pas de problème, là où ça coince c'est que la génération du donjon est totalement aléatoire, donc si je pose mes portes aléatoirement (avec des restrictions) comment faire pour que la clé qui ouvre telle porte se trouve dans une zone accessible sans avoir besoin de passer cette porte ?

J'imagine un truc à base de pathfinding, c'est à dire générer une porte, puis une clé, et vérifier avec un pathfinding dans lequel j’inclus une restriction sur la porte, si cette clé est accessible. Mais ça me semble lourd et peu sécurisé si jamais j'ai plusieurs portes et plusieurs clés.

Donc avant de me lancer dans la programmation de mon générateur de portes, je me permet de vous demander si vous auriez des idées. Je résume pour ceux qui n'auraient pas suivit :

Je dispose d'une map de donjons (pièces et couloirs).
Je veux poser des portes aléatoirement.
Je veux poser des clés aléatoirement.
Je veux qu'on soit sur de pouvoir aller chercher la clé qui ouvre la porte concernée sans être bloqué.

A faire entrer dans les paramètres :

Il peut y avoir plusieurs portes et plusieurs clés.
Le joueur doit pouvoir accéder à une clé qui ouvre une porte.
Soit parce que la clé est dans une zone libre, soit parce que la clé est dans un zone fermée par une porte qu'on a déjà pu ouvrir via une autre clé déjà ramassée auparavant.

Ma solution actuelle :
Utiliser un pathfinding depuis la case de départ (entrée du donjon) via une clé.
Prendre en compte la porte fermée correspondante comme restriction sur la clé testée.
Si la clé est accessible on la pose sinon, on refait un tirage jusqu'à ce que la clé soit accessible.
Lorsque le veux tirer une nouvelle porte, je relance un pathfinding, même cinéma.



Des idées ?

#2 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 22 February 2013 - 15:40 PM

Un début d'idée… (réflexions à brûle-pourpoint)

- parcourir la map portes fermées
- conserver toutes les cases parcourues dans un tableau
- tirer une case du tableau au hasard pour y poser la clef de la première porte

- ouvrir la première porte
- parcourir toutes les cases : les stocker à la fin du même tableau
- tirer une case du tableau au hasard pour y poser la clef de la seconde porte
- etc

Ça c'est pour l'idée. Mais je m'apperÇois évidemment que Ça tourne autour d'outils visuels comme le floodFill

Techniquement, je dessinerais la map sur un bitmapData
Murs en 0x00
Chemins en 0xFFFFFF
Portes avec leur référence ordonnée : 0x000001, 0x000002…
0x000001 serait le point de départ, donc géré comme une porte, et :

boucle sur les portes -
- remplissage de la porte 0x000001 par du xFFFFFF
- floodFill 0xF0F0F0 en partant de la sus-dite porte
- choix d'un des pixels remplis par le fllodFill pour y poser la clef 0x00002
etc…


:) Mais bon, en y réfléchissant, je pense que je créerais mon labyrinthe par une sorte de promenade.
Donc il me suffirait de "perdre" la clef lors de ma promenade avant de déposer une porte.

Ça me rappelle Inception…
Intéressant comme challenge en tous cas.

[EDIT] Je m'aperÇois en continuant ma réflexion que ma première proposition ne répond pas à la question de poser les portes de faÇon aléatoire… La seconde pourrait, mais c'est une idée beaucoup plus confuse et si tu as déjà la carte, Ç'est contre productif…[/EDIT]

#3 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 22 February 2013 - 16:04 PM

Yop Didier,

Alors, pour la gestion de la map c'est pas un problème, je gère ça dans une liste simple qui me renvoie une grille avec des index classiques (0 = sol, 1=murs) dont je me sert ensuite pour texturer et gérer les collisions. Je n'aborde pas le floodfill car ce n'est pas le but de l'exercice et on peut se débrouiller sans pour le moment.

la génération de labyrinthe se fait effectivement via un principe de "ballade", je pars du point de départ et j’essaye d'atteindre le point d'arrivée, mais je ne peux pas poser mes portes à ce moment là.

Ensuite j'ai un deuxième passage qui me permet de poser des pièces et de faire du labyrinthe un donjon, je me retrouve avec une map simple composée de deux types d'infos, 0 = sol et 1 = murs, composée de couloirs et de pièces ouvertes.

Ensuite j'ai un troisième passage qui, en fonction de cette map définitive pour les murs, me pose des objets, là aussi c'est bon.

Je ne peux pas poser mes portes/clés au cours du premier passage car après j'ajoute les pièces.
Ni lors du deuxième car il ne sert qu'à faire des "trous" dans la map en s'assurant qu'il y a toujours un passage libre pour atteindre la sortie.

Je dois donc faire un troisième passage au cours duquel je pose mes objets, et mes portes.
Le principe de ballade est pas mal mais il pose des problèmes, pour bien voir le principe je te mets deux captures :

Capture 1 : le labyrinthe généré automatiquement

Image attachée: labyrinthe.jpg

Capture 2 : le donjon créé à partir du labyrinthe

Image attachée: donjon.jpg

Si dans la capture 1 il n'y a qu'un seul passage pour aller à la sortie, dans la capture 2 avec les trous posés il peut y avoir de multiples passages.

Je peux me débrouiller pour qu'une porte se trouve obligatoirement dans un couloir, en regardant au moment où je pose la porte si elle est bien entourée de murs sur deux côté opposés et uniquement sur deux côtés opposés. Mais avec le principe de "ballade" rien ne m'assure que la clé est accessible. D'où ma réflexion sur le pathfinding, me disant qu'il faut tester à chaque fois que je pose une porte, si la clé correspondante est bien accessible si je prend en compte la porte concernée comme un mur dans mon pathfinding, qui irait donc de la position de départ à la clé.

Autre solution possible, au lieu de poser des portes aléatoirement, je peux en mettre uniquement sur les pièces générées (les "trous"), à chaque fois qu'un couloir mène à une pièce j'ajoute une porte, c'est assez facile à faire, du coup j'aurais un passage où je pose les portes sur les pièces, et il me faudrait un autre passage pour poser les clés et les répartir dans le donjon de manière à ce qu'elles soient accessibles en fonction des pièces.

#4 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 22 February 2013 - 16:18 PM

Alors, si tu veux bien, je continue de divaguer … :-D sans aucune certitude.

La façon dont tu me le racontes, je tenterais ceci :

- au lieu de faire une map de 0 et de 1, je ferais :

- toutes les cases sont à 00;
- première ballade :
- première case : valeur 01,
- seconde case : valeur 02,
- etc

- second passage : faire les pièces :
- quand je fais une pièce, je liste les cases qu'elle occupe. La valeur la plus basse (sauf le 00) donne la valeur de la pièce.
- je donne la valeur (max + valeur de la pièce) aux cases qu'elle occupe (pour éviter de les réutiliser plus tard).

- troisième passage :
- pour chaque pièce, je pose une porte sur une des cases de valeur inférieure à la valeur de la pièce
- je pose la clé correspondante sur une case de valeur inférieure à celle de la porte…

Il y aura sans doute des trous… mais ça ne serait peut-être pas très grave… Ou alors, et bien j'aviserais.
Par exemple, peut être que je poserais l'entrée à la fin de ma ballade, et du coup j'inverserais les valeurs, pour voir ce que ça donne.

#5 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 22 February 2013 - 16:39 PM

Citation

Alors, si tu veux bien, je continue de divaguer

Fais, fais, toute idée ou brainstorm est bon à prendre ;-)

Pour ta solution, voici comment je procède pour le moment :

Je remplis une grille avec des murs (1 dans la map).
Je pose un point de départ (1,1) et un point d'arrivée (aléatoire).
Je pars du point de départ et je "ballade" le pointeur avec un pas de 3 cases.
Soit le pointeur peut continuer soit il est bloqué (fin de map, etc....) dans tous les cas à la fin du pas ou si il est bloqué, il fait un choix sur la prochaine direction à suivre.
J'efface au fur et a mesure de sa progression les murs de la map (je passe les index à 0) sur lesquels il passe.

Là j'ai mon labyrinthe.

Puis je vais créer le donjon, pour ça je divise ma grille en cellules de taille identiques (36 cellules de 8*8 pour une map totale de de 48*48).
Pour chaque cellule, je la remplis avec des murs, puis je remplace les murs par des vides avec des marges aléatoires dans la cellule (ligne de départ aléatoire mais normée, ligne d'arrivée aléatoire mais normée et pareil pour les colonnes), ce qui me permet de remplir mes cellules avec des "pièces" de taille aléatoire tout en m'assurant que je n'ai pas de chevauchement.

Enfin, je viens remplacer dans ma grille du labyrinthe, les vides correspondant aux pièces que je viens de tirer.
J'obtiens mon donjon.

Pour m'assurer que j'ai toujours un passage disponible vers la sortie, lorsque je remplis une cellule je vérifie si elle chevauche un couloir de la grille du labyrinthe, si c'est le cas je met non pas un mur mais un vide dans ma cellule, ce qui m'assure de conserver les ouvertures créées dans le labyrinthe, c'est à ce moment là que je pourrais poser des portes pour chaque pièce, justement aux endroits où je suis tombé sur un accès dans la grille, il suffit pour ça de s'assurer que je suis bien sur les bords de ma cellule et de remplacer le vide (le couloir d'accès) par une porte.

Reste donc le problème des clés, si je ferme les pièces avec des portes, mettons une clé par pièces quel que soit le nombre de portes, il faut que je puisse être sur que cette clé se trouve à un endroit de la grille qui est accessible sans avoir à passer cette pièce, donc qu'elle ne se trouve pas au delà de la pièce fermée par rapport au point d'origine (le départ) et en fonction du chemin tracé.

Voilà, ça c'est pour le moment la méthode que j'utilise, ton idée de numéroter les cases suivant différentes valeur peut être jouable pour poser les portes, mais reste le problème des clés à présent, car ta solution (si je comprend bien) est de poser une clé sur une case de valeur inférieure à la pièce, sauf que je ne suis pas sur que cette case soit accessible car ce tirage ne prend pas en compte les chemins du labyrinthe, tu vois ce que je veux dire ?

#6 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 22 February 2013 - 16:53 PM

Voir le messageMonsieur Spi, le 22 February 2013 - 16:39 PM, dit :

ta solution (si je comprend bien) est de poser une clé sur une case de valeur inférieure à la pièce, sauf que je ne suis pas sur que cette case soit accessible car ce tirage ne prend pas en compte les chemins du labyrinthe, tu vois ce que je veux dire ?
Je reprécise pour éviter toute ambiguité :
- je poserais la porte sur une case inférieure à la pièce
- je poserais la clé de cette porte sur une case inférieure à la case ou j'ai posé la porte.

Et les salles ont la valeur de la case la plus basse sur laquelle elles ont été posées.

Si on imagine une salle posée sur les cases 100,120,89,37,90… le premier chemin permettant d'arriver à cette salle passe par les cases 1 à 37. Je peux donc poser la porte sur une case au hasard parmi les cases 1 à 36.
Admettons 13.
Je dois donc poser maintenant la clef de cette porte sur une des cases entre 1 et 12…

Le fait que la salle recouvre d'autres segments de chemin change t-il quelque-chose ? Je dirais que non.
Dans mon exemple, il y a sûrement une boucle qui passe dans la salle vers les valeurs 90 du chemin, mais ça ne gène pas.
Enfin, je ne crois pas.

#7 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 22 February 2013 - 16:59 PM

Voir le messageMonsieur Spi, le 22 February 2013 - 16:39 PM, dit :

[…] ce qui m'assure de conserver les ouvertures créées dans le labyrinthe, c'est à ce moment là que je pourrais poser des portes pour chaque pièce, justement aux endroits où je suis tombé sur un accès dans la grille, il suffit pour ça de s'assurer que je suis bien sur les bords de ma cellule et de remplacer le vide (le couloir d'accès) par une porte.


Et je pense que c'est à ce moment là que tu pourrais consulter la valeur de la case. Si elle est inférieure à la valeur déjà rencontrée, tu la stocke comme valeur de toute la salle. En posant une porte sur une case inférieure à cette valeur, tu devrais être sûr que la porte se trouve avant la salle. Si tu poses la clef sur une case de valeur inférieure à celle de la porte, tu es sûr que la clef se trouve avant la porte…

#8 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 23 February 2013 - 12:15 PM

Yop,

Je crois que j'ai compris ce que tu veux faire, mais je n'ai pas pensé à cette manière de faire quand j'ai conçut le générateur.

Citation

Si on imagine une salle posée sur les cases 100,120,89,37,90… le premier chemin permettant d'arriver à cette salle passe par les cases 1 à 37.

Le seul moment où je peut suivre un chemin c'est lorsque je crée le labyrinthe, c'est à dire lorsque le pointeur passe par tous les chemins possibles. Puis je tire les pièces aléatoirement et je viens les poser sur le labyrinthe, a ce moment là je n'ai plus de notions de chemins ni de parcours du pointeur puisque plusieurs solutions deviennent possible pour atteindre une pièce (à cause des trous creusés). Pour mettre en œuvre ta solution il faudrait en fait que je génère d'abord les pièces puis que je lance le tracé du labyrinthe, lorsque le pointeur arrive sur une pièce il prend en compte la porte qu'il trouve et là je pourrais prendre en compte un décompte de cases et placer la clé en amont.

Citation

Admettons 13.
Je dois donc poser maintenant la clef de cette porte sur une des cases entre 1 et 12…

Là ça ne convient pas à ce que je cherches à faire, puisque la clé se trouverait automatiquement sur le chemin du joueur, et la porte juste après, donc cela perds de son intérêt. Il faudrait que je puisse poser la clé un peu n'importe où dans le donjon, mais que je soit sur que je peux atteindre cette clé par un chemin, même si la pièce se trouve avant dans le décompte des cases. Puisque plusieurs chemins sont possibles il ne s'agit pas là de bloquer le chemin avec une porte, mais de fermer une pièce avec des portes et d'imposer d'aller chercher la clé ailleurs dans le donjon. Du coup je ne peux pas penser ça de manière linéaire où je suis un parcours et numérote les cases, c'est pour ça que je me suis dirigé vers le pathfinding qui me semble une solution (bonne mais lourde) pour tester la viabilité d'un chemin pour aller chercher une clé, je dois juste vérifier que la clé est accessible même si toutes les portes de la pièce sont fermées.

Citation

Et je pense que c'est à ce moment là que tu pourrais consulter la valeur de la case. Si elle est inférieure à la valeur déjà rencontrée, tu la stocke comme valeur de toute la salle. En posant une porte sur une case inférieure à cette valeur, tu devrais être sûr que la porte se trouve avant la salle.

Je pense (mais je peux me tromper) que cela marcherait si je n'avais qu'une porte par salle, mais je peux en avoir plusieurs comme le montre ce petit schéma :

Image attachée: donjon_portes.jpg

Ici les portes de la même salle (en vert) peuvent être atteintes par de multiples chemins, c'est là que j'ai du mal à voir comment je peux compter les cases et les chemins possibles, ma clé pouvant très bien se retrouver à l'angle inférieur droit du donjon, donc après la salle concernée, et rester pourtant accessible puisque j'ai bien un chemin qui y mène en contournant la pièce. Peu importe si je pose d'autres portes pour d'autres salles après et que ces portes bloquent le chemin à cette première clé, puisque si pour chaque porte je m'assure que la clé correspondante est bien atteignable, je m'assure du même coup qu'il y a une solution pour ouvrir les portes qui bloquent le passage vers la première clé.

C'est pas simple du tout, mais je commence à entrevoir des solutions, merci car c'est en causant que les idées viennent. ;-)

#9 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 23 February 2013 - 12:42 PM

Petite info sympa pour ceux que ça intéresse il y a ici tous les générateurs qu'on veut pour les JDR : http://donjon.bin.sh/
Problème, les codes sources donnés sont en Perl, notament celui-ci : http://donjon.bin.sh.../dungeon/about/ , je suis en train d'essayer de faire une traduction en AS3 mais je lutte...... si quelqu'un est assez doué en Perl qu'il me fasse signe ;-)


Et pour générer automatiquement des cavernes voici le code en C : http://roguebasin.ro...ave-Like_Levels
Et en Python : http://pixelenvy.ca/wa/ca_cave.html

#10 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 23 February 2013 - 22:15 PM

Bon, il va falloir que je tente alors… parce que, malgré tes remarques, je continue de croire que la logique est bonne et qu'elle fait ce que tu veux.

- la première salle, tu es bien obligé de mettre la clé sur le chemin qui mène à la salle.
- ensuite, la salle en chevauchant plusieurs fois le chemin crée des boucles et sans doute des raccourcis, qui font que le meilleur chemin pour le joueur n'est plus obligatoirement celui qui a été créé lors de la ballade génératrice. Mais, le fait que la clé de la salle suivante soit sur ce chemin veut dire qu'elle est accessible, et c'est ce que tu veux.
- enfin, pour la dernière salle, on se rend bien compte que tout le chemin d'origine est disponible, donc la clé peut être n'importe ou… peut-être même sur une petite boucle de la première salle au début.

Bref, je continue de croire que ça marche et je crois que je vais me le tenter. Même si je n'ai pas trop de temps dispo actuellement.
Encore que, toute ma petite famille part en vacances la semaine en huit, ça pourrait être l'occasion.

#11 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 24 February 2013 - 15:26 PM

Hello,

Je vois bien ta logique, elle peut fonctionner, c'est juste que je n'étais pas parti dans cette direction au départ.
Ne t'embêtes pas avec ça si tu as d'autres choses en cours, je viens de tomber sur un générateur de donjon complet en C et sous licence GNU, le C étant pour moi plus abordable que le Perl je pense que je vais me lancer dans une traduction complète pour voir comment c'est foutu et adapter à mon projet.

Pour ceux qui voudraient partir sur cette base on trouve la source gratuite et entièrement commentée du jeu utilisant ce type de générateur ici : http://rephial.org/
Le générateur de donjon est dans le fichier : "generate.c"
La licence d'utilisation est au début, vous pouvez librement vous en servir (sous respect de la licence).

Ayant plus de facilités à lire l'AS que le C, je me lance dans une traduction rapide du fichier pour étude.
A mon avis j'en ai pour quelques jours, on verra, mais je pense que la vraie base de départ est là et non via la solution que j'avais commencé à adopter, ça va être beaucoup plus compliqué (mon code original tenait en moins de 100 lignes) mais au moins ça sera fonctionnel.

#12 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 24 February 2013 - 22:30 PM

Salut tous les deux,

Je me suis aussi mis à réfléchir à cet intéressant problème. Je commençais à entrevoir une possibilité de solution. Pour vérifier mon approche, j'avais besoin de pouvoir identifier les éléments du donjon, à savoir les pièces et les corridors.

J'ai donc commencé à développer ce qu'il faut pour analyser un donjon et identifier ses éléments. Je ne me suis pas questionné sur ce qui est faisable au moment de la conception du donjon lui-même, mais j'ai pris un donjon tout fait de M.Spi et me suis mis en tête de trouver comment l'analyser. J'y ai passé un bon moment ! ça m'a bien amusé en fait, mais ça ne réponds pas à ta question encore (et je ne suis pas sûr d'aller plus loin à vrai dire :D ).

Au cas où ça puisse servir, je le mets ici.
ça fonctionne ainsi:

- L'image du donjon que tu as donnée plus haut est scannée pour créer une Map. La map est un tableau de Tile. Chaque tile a une propriété isWall (et son opposée isFree qui signifie qu'on peut marcher dessus).

- Chaque Tile est analysée pour savoir si elle fait partie d'une pièce ou d'un corridor. Pour ceci je regarde les Tiles voisines, et déduis le résultat en fonction de leur disposition.
Ensuite, on peut consulter les propriétés isRoom et isCorridor de chaque Tile.
Voici ce que ça donne (quand la souris est à gauche on voit le donjon de base, quand elle est à droite les corridors apparaissent colorés en bleu).


- Afficher le SWF -
Fichier joint  Couloirs.swf   29.81 Ko   12 téléchargement(s)

- Puis je crée un Explorer et lui demande d'explorer la map en partant d'une Tile praticable:
var tile:Tile = findAFreeTile();
var explorer:Explorer = new Explorer();
explorer.startExploration(tile);
L'explorateur explore l'élément de la map dans lequel il se trouve, que ce soit une pièce ou un couloir.
Pendant son exploration il crée un rapport d'exploration:
public class Report {
  public var newRoom:Room;
  public var newRoomsEntrances:Vector.<Tile>;
  public var newCorridorsEntrances:Vector.<Tile>;
}
Dans ce rapport figure:
- Dans le cas où il explorait une pièce: la pièce explorée (newRoom), et les Tiles de sortie de cette pièce (newCorridorsEntrances),
- dans le cas où il explorait un couloir: Les entrées des pièces au bout de ce couloir (newRoomsEntrances)
Ensuite, une nouvel explorateur est créé pour chaque tile de newRoomsEntrances et de newCorridorsEntrances, et démarre son exploration.
Au fur et à mesure les différentes pièces sont identifiées:


- Afficher le SWF -
Fichier joint  Pieces.swf   29.8 Ko   19 téléchargement(s)

J'ai trouvé très rigolo de programmer ces explorateurs, qui crapahutent la map en fabricant des rapports d'exploration !


J'ai fait en sorte que les cul-de-sac soient identifiés comme des pièces, car mon idée est de mettre les portes dans les couloirs, et les clés dans les pièces. Du coup des clés au fond d'un cul-de-sac me semblait une bonne idée.

Voilou, ça va peut-être servir à rien du tout mais j'y ai pris du plaisir, ce qui est très bien pour un dimanche :)
D'ailleurs je testerais bien ça sur d'autres donjons. Tu m'en passerais les cartes au même format 480x480 px ? Ou carrément le code qui génére le donjon ?

Fichier(s) joint(s)

  • Fichier joint  Donjon.zip   107.25 Ko   14 téléchargement(s)


#13 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 25 February 2013 - 14:41 PM

Salut Lilive,

Houla je vois que tu y vas toi aussi de tes tests, :Hola:

Pour le moment je n'ai pas beaucoup avancé, je fais des tests, j'en suis aussi à détecter les salles et les numéroter, détecter les contours en prenant une marge de 1 case externe pour trouver où se trouvent les entrées de la salle via les couloirs.

Je te files la base simplifiée du générateur (c'est un brouillon) si tu veux continuer à faire des tests et je vais regarder les tiens pour voir si je peux m'en inspirer.

Mon approche est la plus simple possible, je trace d'abord un labyrinthe que je stocke dans une liste. Puis je reprend la taille de la grille, je la découpe en sous cellules égales dans lesquelles je tire une nouvelle liste pour créer des pièces rectangulaires de tailles diverses, puis j'associe les deux listes pour n'en avoir plus qu'une avec les couloirs du labyrinthe et par dessus les trous que je viens de faire dans les cellules.

Avec cette nouvelle liste je peux à présent tirer tout ce que je veux comme les objets, les ennemis, les pnj, les magasins, etc..., je réfléchis aussi à la manière de texturer le tout de manière cohérente, et le point qui me bloque encore pour le moment, poser les portes et les clés.

Merci en tout cas je pense qu'il y a des choses dans ce que tu as fait qui vont m'aider à trouver des solutions simples.
Mon objectif c'est de trouver une approche la plus simple possible, je suis en train de dépiauter le générateur en C donné un peu plus haut mais ça fait quand même 4500 lignes de code, certes le générateur est complet avec portes, objets, salles, couloirs, ennemis, quêtes etc.... mais c'est beaucoup trop long pour mes besoins.

Fichier(s) joint(s)



#14 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 25 February 2013 - 17:57 PM

Aurais-tu ton flash en version CS5 ?

#15 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 25 February 2013 - 18:27 PM

Ha oui désolé, voila la version CS5.

Fichier(s) joint(s)



#16 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 25 February 2013 - 19:14 PM

Re,

J'ai réfléchis à vos solutions, pour le moment je suis toujours en phase de recherche.
J'en suis là (cliquez pour changer de map) :



- Afficher le SWF -
Fichier joint  labirynthes_partie_1_v2.2_tests.swf   3.16 Ko   13 téléchargement(s)

Phase 1 : générer les murs de la map

Je crée une grille de labyrinthe en effectuant un parcours aléatoire entre le point de départ (en vert) et le point d'arrivée (en rouge). Je crée une seconde grille de la même taille fractionnée en 36 cellules de 8*8 cases afin de m'assurer qu'aucune salle se chevauche. Je tire pour chaque cellule un rectangle de taille et position aléatoire dans la cellule, représentant les salles. Je parcours la grille du labyrinthe et je viens y creuser les salles tirées dans la grille du donjon.

Phase 2 : différencier les salles et les couloirs

Je parcours toute la grille définitive, pour chaque tuile je regarde les 8 voisines et j'enregistre leur disposition.
En fonction des solutions possibles (cul de sac, couloir, angle de couloir, croisement, salle, angle de salle) j'affecte une couleur différente à chaque tuile. Ce passage me permet de délimiter plus précisément le contour des pièces en combinant les tracés des couloirs et des pièces.

J'ai donc les salles et les couloir différenciés, je peux aussi compter facilement les salles pour leur attribuer un identifiant.

Phase 3 : générer les portes et les clés

Je suis d'accord avec l'idée de Lilive sur le fait de poser les clés dans les salles, sauf peut être la première qui doit forcément se trouver hors de la première salle, et le fait que les culs de sac puissent être comptés comme salles (ouvertes dans ce cas).

Je vois à peu près comment trouver les endroits où il faut poser les portes pour boucher les salles, une fois les couloirs et salles différenciées c'est assez simple, reste donc à savoir comment poser les clés.

Si je suis ce que préconise Lilive, on peut s'éviter de se balader dans le donjon en posant les clés dans des salles, elles sont déjà identifiées. Reste plus qu'à trouver comment effectuer un tirage qui assure à la fois le mélange des clés/salles, et la faisabilité, c'est à dire s'assurer qu'on peu ouvrir une certaine salle car la clé est accessible sans que le donjon soit trop linéaire (salle 1/clé 2 puis salle 2/ clé3, puis ....). Avec toujours en tête l'option bonus, c'est à dire les clés qui se trouvent dans des culs de sacs (donc forcément ouverts).

#17 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 25 February 2013 - 19:35 PM

Voilà, les portes sont posées (en rose).



- Afficher le SWF -
Fichier joint  labirynthes_partie_1_v2.2_tests.swf   3.28 Ko   12 téléchargement(s)

Phase 3 : poser les portes

Je parcours une nouvelle fois la grille, pour toute tuile identifiée comme couloir ayant comme voisine une tuile identifiée comme une salle, je place une porte.

#18 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 25 February 2013 - 21:54 PM

Toutes les pièces sont à présent identifiées avec une couleur et un numéro (zoomer pour voir le numéro sur les tuiles).



- Afficher le SWF -
Fichier joint  labirynthes_partie_1_v2.3_tests.swf   7.74 Ko   22 téléchargement(s)

Je pense pouvoir faire en sorte d'attribuer également le numéro de la pièce concernée à chaque porte, ce qui permettrait d'associer les clés et les portes. Au final je pense me retrouver avec une liste de clés (un trousseau quoi) permettant d'ouvrir les portes identifiées par numéro de salle, reste à savoir comment les distribuer intelligemment.

Une des idées qui reprend un peu l'approche de Didier c'est de partir en ballade.

J'envoie un pointeur se balader dans le donjon à partir de la sortie.

Quand il tombe sur une porte il entre dans la salle et note la clé utile pour l'ouvrir.

Quand il tombe sur une nouvelle porte il sort de la salle.

A partir de là tant qu'il n'a pas rencontré une nouvelle porte il peut aléatoirement perdre la clé du trousseau

Si il arrive à une nouvelle porte mais n'a pas encore perdu la clé de la dernière salle, il pose la clé devant la porte


Ou alors on peu enregistrer les tuiles du trajet entre les deux portes et jeter la clé aléatoirement sur une de ces tuiles, ça rendrait la répartition plus cohérente en réduisant le risque de trouver une clé juste derrière une porte.



Autre idée en partant du principe qu'on pose les clés dans les salles comme le disait Lilive.

J'envoie un pointeur se balader dans le donjon à partir de la sortie.

Quand il tombe sur une porte il entre dans la salle et note la clé utile pour l'ouvrir.

Quand il tombe sur une nouvelle porte il sort de la salle et enregistre la salle et la clé correspondante.

Quand il tombe sur une nouvelle porte et qu'il ne s'agit pas d'une salle déjà découverte

Il fait le choix de jeter ou non une clé d'une des salles précédentes

Quand il tombe sur un cul de sac

Il fait le choix de jeter ou non une clé d'une des salles précédentes


Avec cette méthode il n'y a pas de clés dans les couloirs sauf les culs de sac.


Problème avec les deux méthodes, je ne suis pas sur de parcourir tout le donjon. Selon les multiples chemins possibles il se peut que le pointeur ne parcoure pas toute les cases, ou mette énormément de temps à y arriver. Du coup je cherche quelque chose de plus général avec un simple parcours linéaire de la grille.

#19 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 25 February 2013 - 23:05 PM

Je joue un peu tout seul ce soir mais c'est pas grave je progresse dans mes réflexions.

Je pense avoir trouvé une solution simple mais pas forcément la meilleure pour poser les clés.
Je vais remplir le donjon avec un liquide.......

En gros je part de l'entrée, je remplis les tuiles libres.
Si j'arrive à un embranchement avec plusieurs choix possibles je part dans toutes les directions.

Toutes les tuiles de la zone parcourue sont stockées dans un tableau.


Quand le liquide tombe sur une porte

Identifie la salle correspondante

Stocke sa valeur dans un tableau

Stoppe sa progression dans cette direction


Quand le liquide tombe sur tuile déjà parcourue

Stoppe sa progression dans cette direction


Lorsque le liquide ne peut plus se propager (plus de directions possibles).

Regarde les portes disponibles sur le parcours.
Jette une ou plusieurs clés (aléatoire) des salles identifiées sur le parcours

Supprime la référence des salles dans le tableau

Supprime les tuiles où on a posé des clés du tableau
La salle qu'on vient d'ouvrir n’oppose plus de résistance


La progression reprend depuis la ou les portes ouvertes.


Stoppe la dispersion du liquide quand plus aucune direction possible.


A ce stade les clés sont à la fois accessibles et leur répartition non linéaire, tout le donjon à été "scanné". Reste à s'assurer que toutes les clés sont bien distribuées et que je ne me retrouve pas à la fin avec 10 clés restantes sur le trousseau.

#20 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 26 February 2013 - 14:14 PM

Salut,

Alors je viens de tester le remplissage du donjon avec de la tuile récursive (genre fluide), ça marche, voici le résultat brut (pas d'anim de remplissage) :



- Afficher le SWF -
Fichier joint  labirynthes_partie_1.swf   8.08 Ko   12 téléchargement(s)

Là je suis sur de bien parcourir toutes les possibilités du donjon.

Prochaine étape, détecter les portes et les salles au fur et a mesure de la progression des tuiles, interdire l'accès à la salle, jeter une clé sur le parcours, et ouvrir la salle correspondante puis relancer la propagation du fluide.

J'aurais une grosse étape d'optimisation à faire parce que là c'est super brouillon et la génération du donjon peut mettre un moment selon les cas.

C'est cool j'avance ;-)

#21 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 26 February 2013 - 18:19 PM

C'est sympa de suivre le cheminement de ta pensée :)
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#22 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 26 February 2013 - 18:29 PM

Bah y a pas que la mienne, je m'inspire des idées posées par Didier et Lilive aussi (merci à eux au passage).... sauf que je tente mes propres méthodes :P
Bon après c'est sur que je cause un peu tout seul depuis hier, mais j'ai eu les pistes que je cherchais c'est déjà ça.

#23 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 26 February 2013 - 19:24 PM

Et pour ceux qui veulent suivre, l'exploration des chemins s'arrête à présent à la première porte, toutes les portes sont numérotées en fonction de la salle qu'elles ferment, le trousseau de clés est enregistré. J'attaque la détection des portes en fonction des chemins parcourus et le tirage d'une clé parmi celles correspondantes et l'ouverture des portes correspondant aux clés tirées, puis je tenterai de relancer l'exploration à partir des portes ouvertes.

Fichier(s) joint(s)



#24 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 26 February 2013 - 19:28 PM

Voir le messageMonsieur Spi, le 26 February 2013 - 18:29 PM, dit :

Bon après c'est sur que je cause un peu tout seul depuis hier, mais j'ai eu les pistes que je cherchais c'est déjà ça.
Moi je regarde ce que tu fais mais je n'ai pas avancé de mon côté :)

#25 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 26 February 2013 - 23:41 PM

Cool ça marche :



- Afficher le SWF -
Fichier joint  labirynthes_partie_1.swf   8.63 Ko   11 téléchargement(s)

J'ai franchi la première porte et la clé est posée sur une tuile aléatoire située sur le chemin avant de rencontrer la porte.
(la clé est la pastille rouge et ronde)

Si il y a plusieurs salles accessibles on choisi aléatoirement de n'en ouvrir qu'une
On jette la clé derrière soit sur le chemin disponible avant d'entrer dans la salle.
Si la salle a plusieurs portes on les ouvre toutes et on continue la progression.

Reste plus qu'à régler un détail sur la gestion des événements quand mes tuiles progressent pour ouvrir les portes et ce sera tout bon, du moins je pense.

#26 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 27 February 2013 - 02:07 AM

Ayé je crois que j'y suis arrivé (j'ai fait une version plus grande pour voir le numéro des portes) :



- Afficher le SWF -
Fichier joint  labirynthes_partie_1.swf   8.96 Ko   18 téléchargement(s)

Il reste encore un petit problème de clés, a la fin du parcours il me reste un certain nombre de clés dans les mains alors qu'elles sont toutes distribuées. Sinon je trouve que la répartition n'est pas super homogène, peut être en ajoutant des restrictions sur les chemins déjà parcourus au delà d'un certain nombre de portes.

#27 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 28 February 2013 - 16:55 PM

Salut,

(ouais, chuis encore tout seul....)

C'est juste pour dire que ça y est j'ai réussi, voila le résultat :



- Afficher le SWF -
Fichier joint  labirynthes_partie_1_v5.swf   9.45 Ko   15 téléchargement(s)

Cliquez pour changer de donjon.
Si aucun objet ne s'affiche recliquer (voir bug à la fin de ce message)

Voici la technique employée :

1 - générer un labyrinthe avec la méthode de : Backtracking (wikipedia : http://fr.wikipedia....ki/Backtracking )
2 - générer les pièces du donjon avec une partie de la méthode de placement trouvée ici : http://donjon.bin.sh.../dungeon/about/
3 - nettoyer la grille pour obtenir des pièces cohérentes (mix entre les couloirs et pièces) : idée de Lilive (voir au dessus)
4 - trouver, placer et numéroter les portes avec une méthode simple qui regarde si la voisine d'une tuile d'un couloir est une tuile d'une pièce.
5 - disperser les clés de manière cohérente pour s'assurer qu'une clé se trouve bien sur un chemin valide avant la porte, pour ça j'ai utilisé une méthode de propagation de tuiles à partir de l'entrée du donjon, lorsqu'une tuile trouve une porte elle jette la clé sur le chemin parcouru, ouvre la porte et continue sa progression.
6 - répartir les différents objets dans le donjon.

Les objets présent et affichés sont :

- clés (gros carré rouge avec le numéro de la porte qu'elle ouvre)
- portes (gros carré rose avec le numéro de la salle qu'elle bloque)
- magasins (gros carré orange), ils sont toujours dans un mur
- portes dérobées (gros carré bleu ciel), elles sont toujours dans un mur et peuvent ouvrir un passage
- coffres (petit carré jaune), qui se rempliront par la suite
- ennemis (petit carré rouge), dont les caractéristiques seront définies par la suite
- nids de monstres (petits carrés bleus), dont les caractéristiques seront définies par la suite
- pnjs (petits carrés verts), dont les caractéristiques seront définies par la suite
- objets de quête (petit carré multicolore), dont les attachements seront définis par la suite

- entrée (gros carré vert sans indications)
- sortie (gros carré rouge sans indications)
- cul de sac (gros carré gris foncé)
- couloir (gros carré gris clair)
- salle (tuiles blanche avec un numéro)

Voilà, je pense que j'ai tout pour commencer, merci à Didier et Lilive pour leurs idées.

Prochains objectifs :

- attribuer les différents paramètres aux objets (coffres, magasins, ennemis, pnjs, quêtes, nids, portes dérobées)
- créer un perso qu'on peut déplacer et son interactivité avec les objets
- texturer le donjon
- proposer plusieurs vues (générale, top down, FPS) et gameplay
- gérer l'enchaînement des donjons
- gérer l'équipe du joueur (4 membres dans l'équipe)
- gérer les combats

Correction de bugs :

- il me reste encore un bug lors de la génération du donjon, parfois le compte de tuiles parcourues pour poser les clés n'est pas égal au nombre de tuiles libres du donjon, ce qui plante la génération.
- gros nettoyage de prévu pour optimiser le tout avant de créer le tuto car là c'est un peu barbare comme code....

#28 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 28 February 2013 - 18:14 PM

Un grand bravo Mr Spi

De mon coté je ne fais que réfléchir et j'ai tout juste commencé à voir comment générer un labyrinthe "from scratch". Pas beaucoup de temps actuellement… Ça explique la solitude, accentuée par la rapidité à laquelle toi tu avances.

Comme je le disais j'aurai un peu plus de temps libre la semaine prochaine et je vais m'y attaquer juste pour voir. De toute faÇon, Ça va ressembler beaucoup a ta méthode, finalement. Pas sûr que Ça serve à quelqu'un d'autre qu'à moi-même. ;-)

#29 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 28 February 2013 - 18:31 PM

Merci Didier ;-)

Si tu veux dès que j'aurai un peu nettoyé je te file la source, de toute façon ça va devenir le prochain exercice sur le Wiki, c'est loin d'être parfait mais ça répond à mes besoins c'est l'essentiel.

Pour générer le labyrinthe essayes cette méthode : http://fr.wikipedia....ki/Backtracking

Et pour répartir les clés je part de l'idée d'envoyer un liquide qui se répand dans le donjon dans toutes les directions à partir d'un point de départ, bloque à chaque porte, ouvre la porte et jette la clé correspondante sur le chemin déjà parcouru (le "liquide" quoi).

#30 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 28 February 2013 - 19:20 PM

pas sûre que tu sois si seul, ce sont les feux de la rampe qui t'empêchent de voir la salle et les spectateurs ;)
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#31 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 02 March 2013 - 01:45 AM

Yop,

Voilà première partie tutorialisée, j'attaque la suite : http://forums.mediab...uelike_partie_1

#32 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 03 March 2013 - 13:47 PM

Bon, donc ça se confirme, j'arrive après la bataille :-D

Mais je vais me faire plaisir quand même, si ça ne gène pas.
J'ai laissé partir ma progéniture ce matin vers les vallons cantaliens et je suis délicieusement tiraillé entre la solitude triste et la solitude sereine…

Le début commence bien : faut dire que j'avais eu pas mal de temps pour réfléchir et j'avais survolé ton travail et quelques liens.
Je parle là juste de la création du labyrinthe.

J'ai tenté pour m'amuser de le faire à ma sauce plutôt que de reproduire une méthode ayant fait ces preuves.
Au final, ça ressemble à ta version, et pourtant ça me semble différent.

Le code est largement commenté, je pense que ça devrait aller :


// constantes et variables
const L:uint    = 16;     // Largeur
const H:uint    = 16;     // Hauteur
const E:uint    = 20;     // Echelle
const chemins:Array  = [];        // Chemins
const cellules:Array = [];        // Cellules
const sprite:Sprite  = new Sprite();  // Afficheur
const vue:Graphics  = sprite.graphics; // Dessin
var possibles:Array =[];          // Possibilités de départ de chemin
var depart:Point, arrivee:Point;        // Point de départ et d'arrivée
var i:uint, j:uint, chemin:Array, voisines:Array; // itérateurs

/*
* CODE PRINCIPAL
*
* Position, échelle et affichage du sprite
* Création d'un nouveau labyrinthe
* Ecoute de l'événement CLICK pour créer un nouveau labyrinthe
*/

sprite.x = (stage.stageWidth - E * L)/2;
sprite.y = (stage.stageHeight - E * H)/2;
sprite.scaleX = sprite.scaleY = E;
addChild(sprite);
nouveau_labyrinthe();
stage.addEventListener(MouseEvent.CLICK,nouveau_labyrinthe);

/*
* CREATION DU LABYRINTHE
*
* NB : les chemins et leurs points sont stockés en ordre inverse (via unshift)
* pour accéder en [0] au dernier élément stocké.
* Cela évite de recalculter la longueur du tableau sans arrêt.
*
* On crée un premier chemin possible, partant d'un point au hasard
* Tant qu'il y a un chemin possible :
  // On liste les voisines de la première case de ce chemin
   // Il n'y a pas de voisines ?
        // On mémorise le chemin (s'il fait plus d'une case)
   // Il y a plus d'une voisine ? Il en restera quand on va partir !
        // On mémorise donc un nouveau chemin possible partant de cette case
   // Il y a au moins une voisine ?
        // On en ajoute une devant le chemin, on valorise sa cellule
        // Et on ajoute le chemin aux possibles
* Le dernier point stocké sera notre point d'arrivée
*/

function creer_labyrinthe():void
{
  depart=new Point(alea(L),alea(H));
  possibles[0] = [depart];
  cellules[valeur(depart)] = 0;
  while (chemin = parmi_les(possibles))
  {
   voisines = voisinage(chemin[0]);
   switch(i = voisines.length)
   {
        case 0 :
         if(chemin.length>1) chemins.unshift(chemin);
         break;
        case 2 :
        case 3 :
        case 4 :
         ajouter([chemin[0]],possibles);
        case 1 :
         chemin.unshift(parmi_les(voisines));
         cellules[valeur(chemin[0])] = 0;
         ajouter(chemin,possibles);
   }
  }
  arrivee = chemins[0][0];
}
/*
* DESSIN DU LABYRINTHE
*
* On dispose de tous les chemins dans la variable chemins, on les dessine 1 par 1…
* On dessine ensuite le point de départ et le point d'arrivée
*/

function afficher_labyrinthe():void
{
  vue.clear();
  vue.lineStyle (E*.75, 0xFFFFFF, 1, true, LineScaleMode.NONE, CapsStyle.SQUARE,JointStyle.MITER);
  for each(var chemin:Array in chemins)
  {
   vue.moveTo(chemin[0].x,chemin[0].y);
   for each(var _p:Point in chemin)
   {
        vue.lineTo(_p.x,_p.y);
   }
  }
  vue.lineStyle(undefined);
  vue.beginFill(0xFF0000,1);
  vue.drawCircle(depart.x,depart.y,.3);
  vue.endFill();
  vue.beginFill(0x00FF00,1);
  vue.drawCircle(arrivee.x,arrivee.y,.3);
  vue.endFill();
}
/*
* FONCTIONS SECONDAIRES
*/

function nouveau_labyrinthe(event:Event=null):void
{
  // Nettoyage, puis création et affichage
  chemins.length = cellules.length = possibles.length = 0;
  creer_labyrinthe();
  afficher_labyrinthe();
}
function voisinage (_p:Point):Array
{
  // Gestion des bords pour limiter le labyrinthe
  // Et vérification de la vacuité de la cellule
  var reponse:Array=[];
  var _c:uint=valeur(_p);
  if(_p.x!=0 && cellules[_c-1]==undefined) reponse.push(new Point(_p.x-1,_p.y));
  if(_p.x!=L-1 && cellules[_c+1]==undefined) reponse.push(new Point(_p.x+1,_p.y));
  if(_p.y!=0 && cellules[_c-L]==undefined) reponse.push(new Point(_p.x,_p.y-1));
  if(_p.y!=H-1 && cellules[_c+L]==undefined) reponse.push(new Point(_p.x,_p.y+1));
  return reponse;
}
/*
* SIMPLIFICATIONS D'éCRITURE
*/

// Obtenir un entier non signé aléatoire
function alea (value:uint):uint  { return Math.random() * value }
// Obtenir un élément au hasard dans un tableau
function parmi_les (value:Array):*      { return value.splice(alea(value.length),1)[0] }
// Ajouter un élément n'importe ou dans un tableau
function ajouter(value:*,array:Array):void { array.splice(alea(array.length),0,value) }
// La position dans le vecteur d'un point(x,y)
function valeur (value:Point):uint      { return value.x + value.y * L }
 

Le code fait tout, du coup, vous pouvez copier coller dans un nouveau doc. (je n'ai pas pu repartir de tes fichiers MrSpi, mais de toute façon il faut m'oublier, je suis encore en CS3).

Au résultat : ça me semble juste et varié.
J'ai à ma disposition :
- une liste des chemins (je ne sais pas encore si je peux l'utiliser pour me déplacer, mais elle est bien pratique déjà pour dessiner le labyrinthe, et je vais creuser dans ce sens pour la suite)
- une map qui fait la taille des chemins (pas de murs)
(pour l'instant elle est juste pleine de zéros mais ça ne va pas durer)



si vous avez des questions, sinon, je continue tout seul :)



PS : si quelqu'un qui peut utiliser les sources de Mr Spi pouvait faire un test de rapidité entre sa fonction et la mienne (juste la création du labyrinthe) j'aimerais bien connaître le résultat parce que ma version est assez lente chez moi. On ne peut pas vraiment comparer puisque j'en fait beaucoup moins que lui, mais si je suis déjà dans les choux niveau perfs, ça ne va pas me motiver :-(

Fichier(s) joint(s)



#33 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 03 March 2013 - 14:15 PM

Voir le messagedldler, le 03 March 2013 - 13:47 PM, dit :

Mais je vais me faire plaisir quand même, si ça ne gène pas.

Certes non ! Je dirais même plus : au contraire :Hola:

Toutes ces contributions constituent un bel enrichissement à l'exercice proposé par M. Spi, je trouve :)
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#34 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 14:22 PM

Yop,

Houla tu t'y colle ;-)

Voici la version nettoyée où j'ai pioché une partie de ce qu'a fait Lilive sur ses propres tests :

Inistialisation :

const C:uint = 48;
const L:uint = 48;
const T:uint = 10;
const tailleGrille:uint = C*L;

var i:int;
var j:int;

var grille:Array;
var entree:Point;
var sortie:Point;
var rendu:Sprite;

init();

function init():void{
        entree =                 new Point(1,1);
        sortie =                 new Point(L-2,C-1);
        rendu =          new Sprite();
        addChild(rendu);
        genere();
}

function genere(choix:int):void{
        while(rendu.numChildren>0) rendu.removeChildAt(0);
        grille = [];
        for (i=0;i<C*L;i++) grille.push(1);
}
 

Création du layrinthe :

function creeLabyrinthe():void{
       
        var X:int =                     entree.x;
        var Y:int =                     entree.y;
        var pas:int =           3;
        var retour:int =                0;
        var directions:Array[];
        var mouvements:Array[X+Y*C];
        grille[X+Y*C] =         0;
       
        while(mouvements.length){
                directions = [];
                if (X+pas<C && grille[X+pas+Y*C])        directions.push(new Point( 1,  0));
                if (Y+pas<L && grille[X+(Y+pas)*C]) directions.push(new Point( 0,  1));
                if (X-pas>0 && grille[X-pas+Y*C])        directions.push(new Point(-1,  0));
                if (Y-pas>0 && grille[X+(Y-pas)*C]) directions.push(new Point( 0, -1));
                if(directions.length)   {
                        var dir:Point = directions[int(Math.random()*directions.length)];
                        for (i=0; i<pas; i++) {
                                X += dir.x;
                                Y += dir.y;
                                grille[X+Y*C] = 0;
                        }
                        mouvements.push(X+Y*C);
                } else {
                        retour = mouvements.pop();
                        X = retour%C;
                        Y = retour/C;
                }
        }
}

Rendu graphique :

function renderLabyrinthe():void{
        for (i=0; i<tailleGrille; i++){
                renduTuile(i%C,int(i/C),grille[i]+1,"");
        }
}

Je te laisses faire des tests par contre car je dois avancer sur la suite du générateur, je vais essayer de finir la partie qui concerne la répartition des objets pour ce soir sinon je sent que ça va me bouffer toute ma semaine et je peux pas me le permettre.




EDIT : et je vais te piquer quelques raccourcis pratiques auquel j'avais même pas pensé dans les petites fonctions annexes, merci. Comme dit Nat, c'est cool que chacun y aille de ses tests, ça enrichi la chose et ça donne un terrain de jeux ;-)

#35 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 14:57 PM

Pour le moment de mon côté j'en suis là :



- Afficher le SWF -
Fichier joint  generateurs et répartition_v3.swf   158.71 Ko   12 téléchargement(s)

Téléchargez le swf pour un affichage en 960*960.
Utilisez les 3 boutons pour passer d'un environnement à l'autre
Utilisez les fléches pour déplacer le curseur du joueur
Utilisez la barre espace pour effectuer une action (prendre un objet, une clé, ouvrir une porte, ouvrir une porte dérobée, entrer dans un magasin).
Les clés sont en rouge avec un chiffre dessus, les objets sont des tuiles plus petites, les magasins sont en orange, et les portes dérobées sont en bleu ciel.

Si tout va bien c'est jouable sans trop de bugs, sauf pour la caverne où le point d'entrée peut se trouver dans un mur pour le moment.

Il me reste encore à faire :
  • Générer des entrées et sorties cohérentes pour chaque environnement.
  • Poser des téléporteurs ou creuser des couloirs entre les différentes parties isolées des cavernes (je préfères ça au remplissage, pour le moment j'en suis à détecter et colorer différemment les salles des cavernes.
  • Changer automatiquement de terrain quand le joueur à atteint la sortie.
  • Pouvoir enregistrer un terrain quand on le souhaite pour y revenir plus tard.
  • Affiner la détection des objets
  • Réfléchir pour faire des classes qui ne renverraient que les infos utiles (grilles) pour le moteur


#36 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 03 March 2013 - 15:12 PM

Bon,

de toute façon, je ne peux pas utiliser ton code sans une version CS3 pour récupérer le MovieClip des tuiles et je suis bloqué pour comparer.
En même temps, tu avances très, très vite, donc mes élucubrations n'ont pas vraiment d'intérêt.
Au rythme ou je vais, je ne suis pas près d'avoir une participation intéressante.

Je pense que je vais continuer tranquillement mon bonhomme de chemin sans déranger personne.

#37 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 15:21 PM

Citation

de toute façon, je ne peux pas utiliser ton code sans une version CS3 pour récupérer le MovieClip des tuiles et je suis bloqué pour comparer.

Le Clip des tuiles est un simple clip exporté pour AS avec pour nom "Tuiles" et comprenant 4 frames :

1 - sols
2 - murs
3 - entrée
4 - sortie

;-)

Citation

En même temps, tu avances très, très vite, donc mes élucubrations n'ont pas vraiment d'intérêt.
Pas forcément, je pense que c'est très bien d'avoir différentes approches et mon code est loin d'être parfait, donc ce n'est pas du temps perdu, la preuve puisque je vais te piquer deux ou trois raccourcis ;-)

Citation

Je pense que je vais continuer tranquillement mon bonhomme de chemin sans déranger personne.
Bah tu dérange pas au contraire.
C'est juste que là je dois faire un choix, je viens de passer la semaine sur ce générateur et j'ai 1000 autres trucs à faire, je ne peux pas, bosser dessus, rédiger les exercices correspondants et faire des tests annexes sinon je repart pour une semaine non stop et je ne peux pas me le permettre, du coup j’essaye d'avancer vite, mais comme la semaine prochaine je ne vais pratiquement pas me coller dessus ça va laisser le temps pour faire des tests de votre côté.

En tout cas moi je suis intéressé par tes résultats, si on peut faire plus simple et plus rapide c'est toujours bon à prendre, et puis il suffira de linker ce sujet pour expliquer les modifs effectuées le cas échéant.

Citation

Au rythme ou je vais, je ne suis pas près d'avoir une participation intéressante.
Détrompe toi, tu viens avec ton test d'aborder une autre version du labyrinthe dont je n'ai pas parlé, c'est à dire avec des murs et non des tuiles qui servent de murs. Quand on abordera les différentes vues possibles la tienne sera mieux adaptée par exemple à une vue 3D (genre FPS).

#38 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 03 March 2013 - 15:34 PM

Salut,

C'est sympa de voir une autre façon de faire.

Voir le messagedldler, le 03 March 2013 - 13:47 PM, dit :

PS : si quelqu'un qui peut utiliser les sources de Mr Spi pouvait faire un test de rapidité entre sa fonction et la mienne (juste la création du labyrinthe) j'aimerais bien connaître le résultat parce que ma version est assez lente chez moi. On ne peut pas vraiment comparer puisque j'en fait beaucoup moins que lui, mais si je suis déjà dans les choux niveau perfs, ça ne va pas me motiver :-(

J'ai fait un test de vitesse en comparaison avec la version de m.spi donnée dans le wiki.
Pour 1000 générations de labyrinthe (sans affichage) ça donne chez moi 800ms pour le code de m.spi et 2600ms pour celui de dldler.

Je ne suis pas sûr que ça veuille dire grand chose. Par exemple l'usage des petites fonctions raccourcies doit certainement augmenter beaucoup le temps d'exécution. Et peut-être que l'usage de unshift aussi.

Je mets les sources en simple fichier texte.

Fichier(s) joint(s)



#39 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 15:45 PM

Merci Lilive,

Par contre Didier, plus j'y réfléchis et plus ta solution avec juste des murs et pas des tuiles est intéressante, faut voir comment gérer les collisions par la suite, et poser les magasins et les portes dérobées, mais mais ça me semble un bon point de départ pour les différentes vues graphiques finales, le gros problème des tuiles c'est que ça fait des murs super épais quand on passe en 3D (ou vue subjective), alors qu'avec de simples murs c'est tout de suite plus agréable. Si tu me le permet je pense que je vais te récupérer ta version quand tu l'aura avancée, pour proposer une alternative quand j'en serait à gérer le rendu graphique (top down, iso, 3D).

Ha et pour info, dans toutes les sources que je file en CS6 ou CS5 le seul point bloquant sur une CS3 c'est la blblio, or en biblio il n'y a qu'un seul clip "Tuiles" qui regroupe toutes les tuiles, donc tu peux réutiliser les codes sans problème, il te suffit juste de te refaire un clip "Tuiles" avec les couleurs que tu veux par frame, il n'y a rien d'autre dedans qu'un Shape de couleur et un champ texte pour afficher les numéro des salles et portes. Pour le reste je n'utilise rien dans le code qui ne passerait pas sur une version CS3 (pas de Vector etc....)

#40 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 16:00 PM

Ha oui autre chose, histoire de cette fois prendre un peu d'avance, si quelqu'un qui passe par la et nous lis, sait aborder la notion de multijoueurs dans un jeu, qu'il se présente et nous cause ;-)

Je suis en train de me dire que ce serait sympa d'en proposer une version où plusieurs joueurs pourraient se rejoindre sur une carte, mais ce sera pas pour tout de suite......

L'idée générale serait :

Le serveur génère une map avec les objets, portes dérobées, magasins, portes et salles.
Chaque client réparti les clés en fonction de la position de départ du joueur dans l'environnement, ce qui veut dire que les clés sont réparties différemment en fonction de chaque joueur, c'est la seule partie qui n'est pas commune.
Chaque joueur joue sa partie mais peut croiser les autres, les combattre, s'associer avec eux ou juste échanger.
Quand deux joueurs s'associent, les clés des portes déjà découvertes sont mises en commun, et le nombre d'ennemis rencontrés sur leur chemin est doublé (pour rappel pour le moment les ennemis sont des petites tuiles rouges plus petites que la taille d'une tuile normale, ils sont répartis aléatoirement et constitueront des groupes et non des ennemis seuls, du coup on peut en changer le nombre à volonté au sein d'un même groupe).
Les combats se feront à l'ancienne en tour par tour.

Pour l'instant ce n'est qu'une idée, qui si ça se trouve ne verra jamais le jour, faut déjà finir la version solo, mais si quelqu'un veut y réfléchir avec un peu d'avance c'est le moment, la partie multijoueur est quelque chose que je maîtrise encore mal donc toute aide sera la bienvenue au moment où je vais m'y coller.

#41 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 20:41 PM

Voilà la toute dernière version, je pense que je vais arrêter là pour ce soir, et même cette semaine ;-)



- Afficher le SWF -
Fichier joint  generateurs et répartition_v3.swf   159.2 Ko   18 téléchargement(s)

Commandes :

Utiliser les flèches pour se déplacer
Utiliser la barre espace pour faire une action

Le joueur doit se trouver sur la même tuile pour ramasser les objets, agir avec les personnages et passer les téléporteurs.
Le joueur doit se trouver sur un tuile voisine pour ouvrir une porte, une porte dérobée, un magasin ou la sortie

Légende :

Joueur : carré vert
Sortie : carré jaune barré d'une croix
Porte : carré rose
Clé : carré rouge
Magasin : carré orange
Porte dérobée : carré bleu ciel
Téléporteur : carré noir avec un cercle gris dedans

Ennemi : petit carré rouge
Pnj : petit carré vert
Coffre : petit carré jaune
Nid de monstes : petit carré bleu
Objet de quête : petit carré multicolore

Etat d'avancement :

Il n'y a pas d'entrée car le joueur ne peut pas faire demi tour.
Sa position de départ est donc considérée comme l'entrée.

A présent à peu près tout est fonctionnel, sauf que je ne met pas à jour le rendu graphique quand on interagit avec les objets.

- le joueur prévient quand il fait une action
- le joueur peut ramasser les objets et les identifier
- le joueur peut ouvrir les portes dérobées et frapper à la porte des magasins
- le joueur ne peut ouvrir une porte que si il a la clé de la salle correspondante
- les clés sont réparties de manière cohérente dans le donjon
- les objets sont répartis aléatoirement en proportions variables selon l'environnement
- les cavernes à multiples salles sont reliées par des téléporteurs fonctionnels
- les entrées et sorties sont ajoutés parfois à des positions différentes selon l'environnement
- si le joueur passe la sortie il change aléatoirement d'environnement

- on peu forcer le changement d'environnement avec les trois boutons (L,C,D) situés en haut de l'écran

Todo :

Gros nettoyage puis rédaction de l'exercice avant d'attaquer la partie 3.

N'hésitez pas si vous voyez des bugs, que ça plante, que ça rame ou que sais-je encore.

#42 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 03 March 2013 - 20:59 PM

Hello.

Merci pour vos encouragements :
- MrSpi pour son positivisme (et pas de souci, je peux maintenant tester tes codes)
- lilive pour les tests.

J'ai avancé sur 2 points cet aprem :
- simplification des formules pour essayer de gagner un peu de temps de traitement.
J'ai réduit environ à 1/4 selon mes tests, du coup, assez proche des pefs du code de MrSpi. Comme le supposait lilive, étaient en cause les splices et unshift (impressionnant). Un peu moins les fonctions de simplification d'écriture et du coup, j'ai laissé celles qui me semblaient les plus utiles.
- gestion des salles

J'ai perdu du temps sur 2 points :D :
- l'optimisation : la simplification me coûte beaucoup en compréhension du code. J'avoue que j'aime bien mes petites fonctions qui me servent d'avantage à traduire mon code du français vers l'actionscript et vice/versa
- la création des salles
Là, j'aime bien le dernier lien cité par Mr spi, mais je n'ai pas réussi à l'implémenter. Je me suis rabattu sur un tout bête découpage en grille et je crée une salle dans chaque zone de la grille.

Passé ces 2 points le reste est simple et je me réjouis de penser que je suis sur une voie qui a de l'avenir :
- je crée les salles avant le labyrinthe
- pour que les salles soient reliées au labyrinthe, je laisse juste une case du pourtour de la salle sur la valeur "non visitée" (pour l'instant, c'est undefined mais ça va changer pour ma prochaine étape)
Et le truc magic, c'est que c'est tout. Ma version précédente de génération du labyrinthe fonctionne à l'identique avec ou sans les salles. :-)

- J'obtiens un labyrinthe "parfait (un seul cheminement possible)
- quand j'arrive dans une salle, je sais quelles cases j'ai parcourues, donc je peux déposer la clef d'entrée sur l'une d'elles

Le truc reste très linéaire, mais, j'entrevois déjà la logique sur les principes (non codés ici mais assez clairs dans mon esprit) suivants :
- quand j'arrive dans une salle, je peux "ouvrir" un nouveau chemin qui sort de la salle en ajoutant simplement une des cases du contour de la salle (non visitée) aux chemins possibles.
- je peux créer une nouvelle entrée si je veux, parmi les cases du contour non visités, en la remettant à undefined.


  // constantes et variables
  const L:uint  = 60;     // Largeur
  const H:uint  = 22;     // Hauteur
  const E:uint  = 12;     // Echelle
  const chemins:Array  = [];      // Chemins
  const cellules:Array = [];      // Cellules
  const salles:Array = [];        // salles
  const sprite:Sprite  = new Sprite();  // Afficheur
  const vue:Graphics  = sprite.graphics; // Dessin
  var possibles:Array = [];       // Possibilités de départ de chemin
  var depart:Point, arrivee:Point;      // Point de départ et d'arrivée
  var point:Point;
  var i:uint, j:uint, chemin:Array, voisines:Array; // itérateurs

  /*
  * CODE PRINCIPAL
  *
  * Position, échelle et affichage du sprite
  * Création d'un nouveau labyrinthe
  * Ecoute de l'événement CLICK pour créer un nouveau labyrinthe
  */

  sprite.x = (stage.stageWidth - E * (L-1))/2;
  sprite.y = (stage.stageHeight - E * (H-1))/2;
  sprite.scaleX = sprite.scaleY = E;
  addChild(sprite);
  nouveau_labyrinthe();
  stage.addEventListener(MouseEvent.CLICK,nouveau_labyrinthe);

  /*
  * CREATION DES SALLES
  * La fonction creer_salles découpe le labyrinthe en une grille _a x _b
  * Dans chaque secteur, on crée une salle (en retrait dans la zone)
  * Toutes les cellules de la zone prennent la valeur 0
  * Une cellule du contour de la zone est remise à undefined
  * afin que la création des chemins puisse y pénétrer
  */

  function creer_salles(_l:uint,_h:uint):void
  {
   var l_secteur:int = L/_l;
   var h_secteur:int = H/_h;
   var x_secteur:int;
   var y_secteur:int;
        for(x_secteur = 0; x_secteur<_l; x_secteur++)
        {
         for(y_secteur = 0; y_secteur<_h; y_secteur++)
         {
          var l_salle:int = (Math.random()*.5 + .4) * l_secteur - 2;
          var h_salle:int = (Math.random()*.5 + .4) * h_secteur - 2;
          if (l_salle < 2 || h_salle < 2) break; // Pas de salle plus petite que 2 x 2
          var x_salle:int = x_secteur * l_secteur + Math.random() * (l_secteur-l_salle-2) + 1;
          var y_salle:int = y_secteur * h_secteur + Math.random() * (h_secteur-h_salle-2) + 1;
          // On remplit les cellules de la salle de zéros
          for (var ii:int = x_salle; ii < x_salle + l_salle; ii++)
          {
           for (var jj:int = y_salle; jj < y_salle + h_salle; jj++)
           {
                cellules[ii + jj * L] = 0;
           }
          }
          // On mémorise la salle
          salles.push([x_salle,y_salle,l_salle - 1, h_salle - 1]);
          // On choisit un point d'entrée sur le pourtour de la salle
          if(Math.random()>.5)
          {
           x_salle += Math.random() > .5 ? 0 : l_salle -1;
           y_salle += Math.random() * h_salle;
          }
          else
          {
           x_salle += Math.random() * l_salle;
           y_salle += Math.random() > .5 ? 0 : h_salle - 1;
          }
          cellules[x_salle + y_salle * L] = undefined;
         }
        }
  }
  /*
  * CREATION DES CHEMINS
  *
  * On crée un premier chemin possible, partant d'un point au hasard
  * Tant qu'il y a un chemin possible :
   // On liste les voisines de la première case de ce chemin
        // Il n'y a pas de voisines ?
         // On mémorise le chemin (s'il fait plus d'une case)
        // Il y a plus d'une voisine ? Il en restera quand on va partir !
         // On mémorise donc un nouveau chemin possible partant de cette case
        // Il y a au moins une voisine ?
         // On en ajoute une devant le chemin, on valorise sa cellule
         // Et on ajoute le chemin aux possibles
  * Le dernier point stocké sera notre point d'arrivée
  */

  function creer_chemins():void
  {
 
   depart=new Point(0,0);
   possibles[0] = [depart];
   cellules[valeur(depart)] = 0;
        while(chemin = possibles.shift())
        {
         point=chemin[chemin.length-1];
         while(chemin)
         {
          voisines = voisinage(point);
          switch(i = voisines.length)
          {
           case 0 :
                if(chemin.length>1) chemins.push(chemin);
                chemin=null;
                break;
           case 2 :
           case 3 :
           case 4 :
                possibles.push([point]);
           case 1 :
                point = voisines[alea(voisines.length)];
                chemin.push(point);
                cellules[valeur(point)] = 0;
          }
        }
   }
   arrivee = chemins[chemins.length-1][chemins[chemins.length-1].length-1];
  }
  /*
  * DESSIN DU LABYRINTHE
  *
  * On dispose de tous les chemins dans la variable chemins, on les dessine 1 par 1…
  * On dessine ensuite le point de départ et le point d'arrivée
  */

  function afficher_labyrinthe():void
  {
   vue.clear();
   vue.lineStyle (E*.75, 0x00FFFF, 1, true, LineScaleMode.NONE, CapsStyle.SQUARE,JointStyle.MITER);
   for each(var salle:Array in salles)
   {
        vue.beginFill(0x00FFFF,1);
        vue.drawRect(salle[0],salle[1],salle[2],salle[3]);
        vue.endFill();
   }
   vue.lineStyle (E*.75, 0xFFFFFF, 1, true, LineScaleMode.NONE, CapsStyle.SQUARE,JointStyle.MITER);
   for each(var chemin:Array in chemins)
   {
        vue.moveTo(chemin[0].x,chemin[0].y);
        for each(var _p:Point in chemin)
        {
         vue.lineTo(_p.x,_p.y);
        }
   }
   vue.lineStyle(undefined);
   vue.beginFill(0xFF0000,1);
   vue.drawCircle(depart.x,depart.y,.3);
   vue.endFill();
   vue.beginFill(0x00FF00,1);
   vue.drawCircle(arrivee.x,arrivee.y,.3);
   vue.endFill();
  }
  /*
  * FONCTIONS SECONDAIRES
  */

  function nouveau_labyrinthe(event:Event=null):void
  {
   // Nettoyage, puis création et affichage
   chemins.length = cellules.length = possibles.length = salles.length = 0;
   creer_salles(4,2);
   creer_chemins();
   afficher_labyrinthe();
  }
  function voisinage (_p:Point):Array
  {
   // Gestion des bords pour limiter le labyrinthe
   // Et vérification de la vacuité de la cellule
   var reponse:Array=[];
   var _c:uint=valeur(_p);
   if(_p.x!=0 && cellules[_c-1]==undefined) reponse.push(new Point(_p.x-1,_p.y));
   if(_p.x!=L-1 && cellules[_c+1]==undefined) reponse.push(new Point(_p.x+1,_p.y));
   if(_p.y!=0 && cellules[_c-L]==undefined) reponse.push(new Point(_p.x,_p.y-1));
   if(_p.y!=H-1 && cellules[_c+L]==undefined) reponse.push(new Point(_p.x,_p.y+1));
   return reponse;
  }
  /*
  * SIMPLIFICATIONS D'éCRITURE
  */

  // Obtenir un entier non signé aléatoire
  function alea (value:uint):uint        { return Math.random() * value }
  // La position dans le vecteur d'un point(x,y)
  function valeur (value:Point):uint    { return value.x + value.y * L }
 

Fichier(s) joint(s)



#43 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 03 March 2013 - 21:08 PM

Petit bug avec une coupure dans mon message précédant sans doute trop long…

Je termine en disant que maintenant, pour avancer, je dois stocker les infos dans mes cellules, et du coup je n'ai pas trop le choix.
Je vais devoir gérer le stockage binaire des infos dans un uint…
… ça va être un gros morceau. Mais après, ça pourrait bien avancer assez vite.

#44 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 03 March 2013 - 22:15 PM

Je ne sais pas si ça va t'aider ou te donner des idées, mais voilà comment je suis parti pour la répartition des clés :

J'utilise 5 grilles dans le jeu :
  • grille : la grille principale qui servira à la déco et à certaines détections
  • grilleTests : une grille temporaire qui me sert à faire toutes les manips que je veux
  • grilleObjets : la grille où je stocke les objets (les portes sont considérées comme des objets avec un numéro)
  • grilleInfosObjets : une grille qui stocke uniquement les infos complémentaires des objets (numéro de clé, ...)
  • grilleCollisions : une grille qui ne recense que les murs (les portes dérobées et les portes en sont tant qu'on les as pas ouvertes)
Toutes les grilles sont de taille identique, ce qui me permet de pointer directement un index dans n'importe quelle grille sans avoir à faire de recherches supplémentaires, c'est pratique mais carrément lourd, au final je vais réduire leur nombre en stockant directement des objets et plus des chiffres, il me restera peut être trois grilles : décor, collisions, objets

Mon donjon est tracé et nettoyé avec ses pièces, ses couloirs et ses portes.

Je part de l'entrée et de cette première tuile je lance un algorithme de remplissage (http://fr.wikipedia....e_par_diffusion) pour tracer le chemin jusqu'aux portes.

Quand mon remplissage tombe sur une porte, il continue mais note la porte et jette la clé sur la partie déjà remplie.
J'enregistre la clé dans une liste, si le remplissage retombe sur une porte avec le numéro d'une clé déjà ramassée il n'en tient pas compte et continue tout simplement son chemin.

Pour éviter que les clés ne puissent être jetées trop proches les unes des autres, je fais une recherche des cases voisines de la case sur laquelle je veux jeter la clé, si l'une d'entre elle est déjà une clé je refais un tirage.

Si la case sur laquelle je jette une clé est une porte ou un une autre clé, je refais un tirage.

Quand le remplissage est terminé, toutes les tuiles ont été parcourues, je lance le rendu du donjon.

// point de départ de la répartition des clés
function repartirCles(X,Y):void{
    for(i=0; i<tailleGrille; i++) grilleTests[i] = 0;
    testeTuile(X,Y);
    addEventListener(Event.ENTER_FRAME, sortieDonjon);
}


function testeTuile(X,Y):void{
    i = X+Y*C;
    if(grilleTests[i]==0) {
        grilleTests[i] = 1;
        voisines(X,Y);
    }
}

// trouve les cases voisines libres
function voisines(X,Y):void{
    testSortie = false;
    i = X+Y*C;
    var libres:Array = [];
    var portes:Array = [];
   
    // cherche les voisines libres (portes = libre) et enregistre les portes des salles découvertes
    for(x=-1; x<=1; x++){
        for(y=-1; y<=1; y++){
            j = x+X+(y+Y)*C;                
            if (Math.abs(x+y)==1 && grille[j]!=1 && grilleTests[j]==0)  libres.push([X+x,Y+y]);
            if (grilleObjets[j]>0 && portes.indexOf(grilleObjets[j])==-1) portes.push(grilleObjets[j]);
        }
    }
   
    // ouvre les portes et jette la clé
    while(portes.length){
        for (j=0; j<portes.length; j++){
            if(listeCles.indexOf(portes[j])==-1){
                i = Math.random()*tailleGrille;
                while(grilleTests[i]==0 || grilleObjets[i]==4 || grille[i]==5){        
                    i = Math.random()*tailleGrille;
                    // cherche si une voisine est une clé
                    if(grilleObjets[i-1]==4) i = Math.random()*tailleGrille;
                    if(grilleObjets[i+1]==4) i = Math.random()*tailleGrille;
                    if(grilleObjets[i-C]==4) i = Math.random()*tailleGrille;
                    if(grilleObjets[i+C]==4) i = Math.random()*tailleGrille;
                }
                grilleInfosObjets[i] = portes[j];
                grilleObjets[i] = 4;
                listeCles.push(portes[j]);
            }
            portes.splice(j,1);                                    
        }
    }

    // lance un nouveau test à chaque emplacement libre
    while(libres.length){
        testeTuile(libres[0][0],libres[0][1]);
        libres.splice(0,1);
    }
    testSortie = true;
}

// la recherche est terminée
function sortieDonjon(e:Event):void{
    if(testSortie==true) {
        removeEventListener(Event.ENTER_FRAME,sortieDonjon);
        renderDonjon();
    }
}


#45 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 04 March 2013 - 18:30 PM

Bon…
… petit point de la journée avant de rentrer vers ma solitude et ma CS3…

J'ai fini par implémenter la fabrication des salles du lien cité par MrSpi. Le résultat est plus intéressant.

J'ai voulu commencer l'intégration binaire des données mais j'étais trop curieux. :-P Du coup, j'ai bricolé un truc.
Je laisse tester la validité des labyrinthes aux plus courageux, moi, j'ai les yeux qui commencent à piquer. Je crois quand même que ça marche.

Les clefs sont rondes, les portes carrés.
Il est possible, si le programme ne trouve pas de cachette à sa convenance que la porte menant à une salle reste ouverte… je l'ai vu passer une fois et je n'ai pas trop compris. Mais c'est possible.
Ce qu'il y a de bien, c'est que les clés sont cachées dans des fins de couloirs. Il faut parfois passer par une salle pour aller dans une autre, ou pas…

Du coup, je vais peut-être juste faire un nettoyage pour rendre le code plus compréhensible…
ça reste quand même proche de la première version, toujours en un seul passage :
- je fais la création des salles en premier
- je génère le labyrinthe tout en posant les clés.

Je mets le code mais c'est plus pour moi. Sans commentaires et noms de variables bien choisis je pense que c'est dur à suivre.

Spoiler

Fichier(s) joint(s)





1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)