Forums Développement Multimédia

Aller au contenu

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

CODE

80 réponses à ce sujet

#46 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 04 March 2013 - 18:35 PM

(( pour les plus torturés, un labyrinthe plus étendu ))

Fichier(s) joint(s)



#47 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 04 March 2013 - 18:42 PM

Cool tu avance bien, on va avoir deux méthodes complétement différentes pour obtenir la même chose ou presque, c'est cool.
Dès que j'ai un petit moment, entre deux recherches de taf, je regarde ton code, si tu as réussi à implémenter la création de salles avec le BSP ça m'intéresse de voir comment tu as fait ça ;-)

J'ai regardé vite fait deux ou trois labyrinthes, ça a l'air d'être cohérent, ce serait plus pratique avec un mini moteur pour déplacer un curseur et ouvrir les portes avec les clés trouvées, de toute façon il en faudra un pour tes tests au fur et a mesure.

#48 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 18 March 2013 - 19:52 PM

Bonsoir,

Pour ne pas ouvrir un autre sujet sur les labyrinthes, je mets ici mon package de création de Labyrinthe (dossier lab).
Il permet de créer des labyrinthes de formes différentes, ça se passe ainsi:

- Il faut d'abord créer des cellules (classe LabCell). Ce sont les unités de base du labyrinthe. L'explorateur qui parcourt le labyrinthe se déplacera de cellule en cellule. Les cellules peuvent être de formes différentes, régulières ou pas, en 2D comme en 3D.

- Il faut ensuite créer des bords (classe LabEdge). Il faut indiquer à chaque bord les cellules qui le touche avec sa méthode addCell(). En effet chaque cellule est entourée de plusieurs bords. Par exemple des cellules carrées ont 4 bords, des hexagonales en ont 6, des cubiques en ont 6 aussi, etc. Un bord peut être commun à deux cellules. Dans ce cas il sera susceptible de devenir une porte reliant ces 2 cellules.

- Il faut finalement appeler LabBuilder.createLab() en lui passant les bords en paramètres.
A partir de là le labyrinthe est créé, et on peut consulter chaque bord pour savoir s'il est un mur ou une porte. On peut également consulter chaque cellule pour connaitre ses murs, ses portes, et les cellules qu'on peut atteindre en la quittant par une porte.

Il sera souvent utile d'étendre les classes LabCell et LabEdge pour que ces objets contiennent d'autres informations. Par exemple des informations sur leur emplacement géométrique, leur aspect, etc.



Je mettrai ceci dans les petites contributions, mais j'attends d'abord un peu d'éventuels retours ;)

Fichier(s) joint(s)



#49 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 18 March 2013 - 20:52 PM

lol délire, ça te plait les labyrinthes ;-)
Merci pour cette contribution, veux-tu ajouter un petit mot aux deux tutos sur le roguelike sur le wiki ?
Je pense que ça ferait un addon pour avoir un générateur facilement réutilisable, le mien étant un peu fermé.

#50 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 18 March 2013 - 20:59 PM

Voir le messageMonsieur Spi, le 18 March 2013 - 20:52 PM, dit :

lol délire, ça te plait les labyrinthes ;-)
Merci pour cette contribution, veux-tu ajouter un petit mot aux deux tutos sur le roguelike sur le wiki ?
Je pense que ça ferait un addon pour avoir un générateur facilement réutilisable, le mien étant un peu fermé.
Tant qu'à avoir codé ça pour moi, et étant tout prêt d'un truc générique, j'ai franchi le pas. ça m'a plu oui d'implémenter l'algo de wikipedia, ça m'a fait découvrir ce truc de l'union-find que je ne connaissais pas (cf commentaires dans le code).

J'attends un peu et pis oui, je pourrai rajouter ça au tuto.

#51 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 20 March 2013 - 23:15 PM

Ding-Dong… C'est le retardataire :-)

Je progresse lentement et à mon rythme.
Je me suis un peu égaré vers le binaire et je n'ai pas débouché sur grand chose.
Je suis reparti, cette fois avec des classes et la méthode de fusion aléatoire de chemins.
Je crois que c'est la première fois que je fais un ensemble d'autant de classes aussi petites… c'est peut-être bon signe… :-)
Pour éviter de taper les murs au hasard, j'ai eu l'idée de mélanger le tableau des murs, puis de les ouvrir dans l'ordre. J'ai peu de pertes en Math.random() de cette façon…
Sinon, j'ai utilisé une classe Zone pour identifier mes chemins, qui est une liste chaînée (le truc avec lequel j'ai toujours eu des bons résultats)…

Au final; c'est vrai que l'algo de fusion donne des labyrinthes plus complexes avec des fausses routes longues.
Le temps de réponse à la création est bon, il me semble.
Quand je lis la description de ce que lilive a fait, je trouve qu'il y a pas mal de points communs, dans les classes et l'usage. Aprsè, je n'ai pas été voir beaucoup plus loi, vu que je suis privé de vector :-(

L'union-find m'a beaucoup intrigué mais malgré 2 lectures attentives de l'article je n'ai rien pigé. Je pense que ça devrait permettre d'accélérer l'addition de mes listes chaînées, mais je ne vois pas le début de comment (ni pourquoi, ce qui est plus grave) l'implémenter.
Du coup, j'aurais bien été curieux de comparer les perfs de l'un et de l'autre, même si cela n'a aucun intérêt. Parce qu'un labyrinthe de 500 x 500 cases, franchement, c'est infaisable :D
Sinon, lilive, ça se situe dans quelle classe dans ton package (si c'est isolable ?)



Si vous voulez regarder ou faire des tests, un simple fichier Fla avec la class App ajouté au dossier des sources suffira.
ça n'a pas l'ambition de ce qu'a fait lilive, ça a plus un intérêt pou rles curieux que pour un usage réel.


Prochaine étape (oui, je persiste même si je prends le temps) ajouter des salles et des clefs.

Fichier(s) joint(s)



#52 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 21 March 2013 - 11:15 AM

Salut Dldler,

J'ai jeté un oeil rapidement, et oui, j'ai bien l'impression que ça se ressemble nos 2 versions.

Quand je compile j'ai une erreur de syntaxe ligne 25 de Rectangle.as
C'est peut-être une différence entre Flash Pro et le compilateur du Flex SDK, allié à ton usage exotique de la boucle for :D

L'union-find est implémenté dans lab/LabCell.as de mon package lab. C'est les 2 dernières méthodes de la classe.
J'ai recopié en AS le code donné par wikipedia.
L'idée me semble être, si on compare avec les listes chainées:
Plutôt que de raccorder une liste à la fin de la queue d'une autre, on raccorde une liste à la tête d'une autre. Une tête à donc plusieurs queues.
Ceci crée donc des arbres au fur et à mesure qu'on raccorde les listes.
L'optimisation finale conseillé par wikipedia, la compression de chemin, consiste à faire redescendre chaque branche pour qu'elles soient toutes attachées à la même racine.

[EDIT] En relisant mon code je vois que je n'ai pas fait attention, en reliant deux listes, à relier la plus courte à la plus longue. J'ai fait mon fainéant :)

#53 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 21 March 2013 - 11:29 AM

Je vois une différence entre nos codes:
Tu as choisi d'identifier la zone des cellules via une autre classe Zone, alors que j'ai intégré le chainage à la classe Cellule (LabCell dans mon cas).

#54 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 21 March 2013 - 11:48 AM

Merci pour ton retour lilive.

Pour la ligne 25 :

j=i++*_l--/_l++

Bah quoi :D. Je trouve ça joli :-)
C'est un 'raccourci' pour :

i++, j=i*_l/(_l-1)

Si tu veux tester si ça marche mieux…
C'est une valeur que je pourrais calculer et stocker… normalement. Sauf que sur les grands labyrinthes ça crée un chevauchement des bords. Je n'ai pas trouvé pourquoi, je suppose un problème d'arrondi…
Du coup, j'ai choisi de "cacher" le calcul ici, mais si ça pose souci, je ferai taire mon esthète et le ressortirai. :-P


Voir le messagelilive, le 21 March 2013 - 11:15 AM, dit :

Ceci crée donc des arbres au fur et à mesure qu'on raccorde les listes.
L'optimisation finale conseillé par wikipedia, la compression de chemin, consiste à faire redescendre chaque branche pour qu'elles soient toutes attachées à la même racine.
C'est ça. Mais je bloque sur 2 points :
- 1 - imbriquer des chaînes en arbres, ça me semble compliquer la chose (mais je vais aller voir ton code, si ça me fait tilter)
- 2 - et ça avance a quoi d'avoir un arbre puisque je ne fais jamais de recherche dans cette liste ?
En fait, je passe directement à l'étape "optimisation finale" : je change la racine des cellules de la liste la plus courte.
La seule chose que je fais en plus, c'est de "brancher" le premier de la dernière petite liste sur le dernier de la grande (je ne la parcourres pas)…





Voir le messagelilive, le 21 March 2013 - 11:15 AM, dit :

En relisant mon code je vois que je n'ai pas fait attention, en reliant deux listes, à relier la plus courte à la plus longue

C'est bien dommage. ;-)
Je m'en suis aperçu en traçant les longueurs… la plupart du temps il y en a une "très" petite (1 ou 2 éléments…)

#55 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 21 March 2013 - 12:00 PM

Voir le messagelilive, le 21 March 2013 - 11:29 AM, dit :

Tu as choisi d'identifier la zone des cellules via une autre classe Zone, alors que j'ai intégré le chainage à la classe Cellule (LabCell dans mon cas).

Ça, c'est une habitude pour la gestion des listes chaînées.
Je ne testes plus maintenant, mais au début, j'ai vérifié que 50% du gain venait de cette petite classe qui gère la tête de la liste.
Peut-être même que je devrais sortir la boucle "ajouter"… Je crois que plus la classe est légère plus elle est efficace.

#56 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 21 March 2013 - 20:47 PM

Vous me faites halluciner, je ne comprend même plus le code lol.....

Juste pour vous dire en passant que j'ai testé plusieurs possibilités pour le rendu graphique du rogue like, ça a donné lieu à une fiche pratique (voir ici : http://forums.mediab.../fiche_rendus2d ). J'opte définitivement pour le rendu Iso en case par case qui me semble de loin le plus adapté à ce style de jeu ;-)

Je me servirai de ce topic pour y coller mes avancées, car je pense que ce sera mon prochain gros jeu perso.
Je vous propose que ce sujet devienne notre déversoir à tests lorsqu'on s'attaque à du labyrinthe, je vais essayer de relire vos codes pour voir si je peux optimiser le mien et trouver de nouvelles astuces, mais le binaire et moi ça fait deux.............

[Edit] Pour le moment j'en suis là : Fichier joint  SPI ROGUE LIKE ISO.rar   19.7 Ko   14 téléchargement(s)

J'ai commencé tout à l'heure sur la base que j'ai donné dans la fiche sur les rendus, c'est à dire très très peu de code. J'arrive à gérer plusieurs hauteurs de tuiles, et à permettre à mon personnage de sauter dans repasser derrière le décor. Toute la partie map et objets sera sur la base du rogue like.

#57 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 21 March 2013 - 21:17 PM

Hello.
Je suis OK pour le "déversoir". :-)

Sinon, il y a très peu de binaire dans mon code.
je ne m'en sers que pour les directions, ce qui demande un peu de gymnastique binaire, mais je peux l'expliquer, et si ce n'est pas compréhensible, je pense que c'est au moins "acceptable" en pratique.

J'ai donc 4 constantes binaires pour les directions (je devrais en avoir 5 pour être cohérent).
Pour les différencier dans un tableau, j'aurais donc : 0, 1, 2 et 3 comme accès.

J'ai attribué 0 à Nord,
1 à Est,
2 à Ouest,
et 3 à Sud.

Pourquoi dans cet ordre ?

Il faut regarder les valeurs en binaires

Spoiler

On a donc :
Nord :0b00; //0
Sud: 0b11; // 3
Est : 0b01; // 1
Ouest : 0b10: // 2

J'ai rapproché Sud et Nord d'un côté, ouest et est de l'autre, pour mettre en évidence qu'en choisissant ces valeurs,
on a un effet remarquable : la direction opposé est l'opposé en binaire. Là ou il y a des zéros, il y a des 1 et inversement.

Ceci permet de passer d'une dorection a son contraire sans if.
On a :
Nord == ^Sud & 3;
Est == ^Ouest & 3;

Pratique pour retenir un sens de passage dans un mur et retrouver son sens inverse.

Pourquoi le & 3 ?
Parce que 3 c'est 0x11, tous les bits sont positifs et il sert de masque pour que les bits supérieurs au second ne soient pas inversés.
Pour mieux comprendre, il faut se rappeler que pour Flash, 0b11 c'est en fait 0b00000000000…*00000000011;

(*Oui, je n'ai pas compté si j'en avais réellement 32…).
Du coup, l'inverse de 0b00000000000…*00000000011 serait 0b1111111111…*1111111111100;
Le 3 sert à masquer tous les 1 précédant les bits qui nous intéressent.

A noter que pour que àa fonctionne avec 6 ou 8 directions, il faut utiliser plus de bits et prendre les valeurs opposées. Elles sont différentes que celles pour 4 directions.
En fait, c'est de ça dont je voulais parler en disant que je devrais avoir 5 constantes. Le 3 devrait être une constante "MASQUE_DES_DIRECTIONS".

Voili, voilà.

Sinon, que tu sois perdu, je le comprends un peu.
J'ai de mon côté beaucoup de mal à suivre un code procédural, si ça te rassure. ;-)
J'ai respirer plus sereinement en revenant à mes petites classes.

Mon cerveau est mieux adapté à découper de petites tranches de code et à conceptualiser leur ensemble.
ça ne m'empêche pas de beaucoup apprendre à suivre tes articles.

#58 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 22 March 2013 - 13:41 PM

Yop,

Ok je vois mieux avec quelques explications, merci ;-)
Effectivement ça demande un peu de "gymnastique" ... lol

Je ne suis pas totalement perdu, je passe assez facilement du procédural aux classes et vice et versa, c'est juste que lorsque je tombe sur du binaire ça me refroidit un peu, les maths c'est ma bête noire lol.

Citation

Mon cerveau est mieux adapté à découper de petites tranches de code et à conceptualiser leur ensemble.
Moi aussi quand ce sont de gros trucs, sinon je trouve le procédural plus rapide pour faire un brouillon, question d'habitude. Là pour le générateur c'était une erreur j'aurai du partir sur des classes tout ce suite, je viens de tout refaire au propre ça m'a pris une bonne partie de la nuit...

Citation

ça ne m'empêche pas de beaucoup apprendre à suivre tes articles.
Merci, content que ça serve, en tout cas ça m'amuse de les faire, j’apprends tout autant que vous en les rédigeant et de vous aussi quand on en cause ;-)



Sinon de mon côté j'avance, voilà où j'en suis pour le moment : http://spi4.free.fr/...guelike_01.html

Pour l'exemple je ne génère qu'un donjon (cavernes et labyrinthes sont prêts mais je n'ai pas encore refait tout le moteur, on ne peut donc pas encore changer d'environnement). Tout est fonctionnel, malgré qu'on ne ramasse pas les objets et que les portes soient ouvertes pour permettre de tester. J'expérimente actuellement les hauteurs de murs en vue Iso, tout le rendu Iso tient en 6 lignes de code sans aucun z-sorting, ce n'est que du traçage de texture de base au bon moment pour l'affichage, tout le reste se passe dans la grille 2D envoyée par le générateur.

Désolé pour les graphismes, c'est loin d'être parfait car ce n'est qu'un test, si vous voulez vous amuser vous pouvez modifier la feuille de sprites pour changer le décor.

Pour le moment le jeu fait 8 Ko tout compris et la feuille de sprites 60 Ko, il est réglé à 24 fps.
Il tourne nickel en plein écran sur mon notebook.

Si vous avez des idées ou des remarques n'hésitez pas.


EDIT : maintenant c'est jouable, il faut appuyer sur la touche espace pour ouvrir les portes et avant il faut avoir ramassé la clé.

Fichier(s) joint(s)



#59 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 23 March 2013 - 12:07 PM

Bonjour,

Dldler :

Merci pour la traduction de la boucle for qui ne passait pas à la compilation. Ça marche maintenant.

J'ai testé en modifiant ton code pour implémenter l'union-find selon wikipedia. C'est genre 20% plus lent.
Effectivement ce que tu fais est le même genre d'idée que l'optimisation finale de l'union-find. Je crois qu'une différence réside dans le fait que tu fais cette optimisation systématiquement à chaque union(), alors que wikipedia le fait seulement lors du find(). J'aurais donc pensé que wikipedia serait plus rapide, puisque ne le faisant qu'en cas utile. Mais en chronométrant je me rend compte que non. Soit parce-que quelque chose m'échappe, soit parce-qu'en AS une boucle (ce que tu fais) prend l'avantage sur une récursion (ce que fait wikipedia).

J'ai du mal à avoir clair en tête ce que fait ton code, car je dois lutter avec la référence croisée entre Zone Et Cellule. Je le comprends en lisant ton code, puis Ça fait comme si je devais lutter pour maintenir ma vision à jour au fur et à mesure que je pense au reste.

J'ai aussi fait un test en gardant ton approche et en me débarrassant de Zone. Là c'est un peu plus rapide.
Fichier joint  laby.zip   3.19 Ko   12 téléchargement(s)





M.Spi :

OK pour moi aussi pour l'utilisation de ce sujet.

Ça marche bien ton truc, bravo.
En remarque: peut-être qu'on s'y habitue, mais je n'aime pas trop l'apparition / disparition du 2eme étage. Je comprends que tu l'as fait pour dégager la vue sur le sprite du joueur, mais Ça me fait comme une animation qui brouille la vision.

Je sais pas si tu as été voir mon package lab. J'ai essayé dans les commentaires de montrer que c'est simple comme code et comme utilisation. Le seul truc plus tordu c'est cette histoire d'union-find en arbres, dont on pourrait se débarrasser puisque mes derniers tests montrent que Ça va moins vite.

#60 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 23 March 2013 - 17:03 PM

Citation

Ça marche bien ton truc, bravo.
En remarque: peut-être qu'on s'y habitue, mais je n'aime pas trop l'apparition / disparition du 2eme étage. Je comprends que tu l'as fait pour dégager la vue sur le sprite du joueur, mais ca me fait comme une animation qui brouille la vision.

Merci, je viens de faire des modifs pour que les murs des salles soient texturés en fonction du sol de la salle, il reste quelques bugs mais c'est un brouillon, je corrigerai après.

Pour l'effet d'apparition des murs, je cherche encore comment avoir un rendu qui prenne de la hauteur sans géner la visibilité, je pense que trois murs de haut c'est trop, je viens de les passer à deux ca rend un effet moins clostro et plus léger.

J'ai mis à jour la version en ligne pour les tests (penser à vider son cache) : http://spi4.free.fr/...guelike_01.html

Citation

Je sais pas si tu as été voir mon package lab. J'ai essayé dans les commentaires de montrer que c'est simple comme code et comme utilisation. Le seul truc plus tordu c'est cette histoire d'union-find en arbres, dont on pourrait se débarrasser puisque mes derniers tests montrent que Ça va moins vite.

J'avoue que non, j'ai téléchargé vos versions, jeté un oeil rapide au code, mais j'essaye d'avancer sur l'ensemble du jeu car les idées se bousculent à un rythme effrayant. Du coup je dois faire un choix entre améliorer l'existant et avancer sur les 120548 autres choses à penser/gérer/coder/dessinner rapidement avant que j'oublie ou que ca me lasse.

Pour le moment j'ai bien séparé la génération des environnements, le moteur, et le rendu graphique, du coup je pense que je pourrai assez facilement me remplonger sur vos codes et optimiser le mien voire reprendre les votres par la suite, pour cette partie j'ai juste à récupérer le contenu de quelques maps.

A première vue chacun s'amuse bien sur la partie qu'il à choisie et c'est ce qui compte, ce que vous êtes en train de faire avec les labyrinthes va beaucoup me servir quand j'en serai à la partie "optimisation/nettoyage" en tout cas, merci à vous.



Si vous vous lassez du labyrinthe et que vous avez envie de réfléchir ou avez des idées ou algos à propos du dernier environnement que je vais devoir travailler, ne vous génez pas..., je m'explique :

Je réfléchi en parallèle à la manière d'organiser un jeu aléatoire en un tout cohérent afin que le joueur évolule dans un milieu structuré au sein d'environnements toujours différents, et n'enchaîne pas bêtement des donjons aléatoires.

La solution qui m'est venue c'est de créer une très grande map, elle aussi générée aléatoirement, qui représente l'extérieur (région) et dans laquelle sont répartis les points d'entrées vers les environnements clos (cavernes, donjons, labyrinthes), et un village où le joueur peut centraliser les actions principales :
  • se soigner (temple)
  • acheter/vendre (magasins)
  • obtenir des informations (taverne)
  • passer des niveaux (salle d'entrainement)
  • obtenir des quêtes (mairie)
  • obtenir et valider la quête principale (retrouver des objets perdus dans les différents environnements de la région).
  • apprendre de nouvelles compétences (guildes)
Pour que Ça marche à chaque fois que le joueur entre pour la première fois dans un lieu, je génére la map et je l'enregristre pour qu'il puisse y revenir, ainsi la zone de jeu se crée aléatoirement mais se construit aussi de manière cohérente au fil de la partie. Il me faut donc réfléchir à comment générer cette map de région et y répartir un décor.

Pour le moment je cherches l'inspiration par ici : http://donjon.bin.sh/fantasy/world/






EDIT : c'est moi ou le forum premplace automatiquement le c cédille par un c cédille majuscule ?

#61 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 23 March 2013 - 18:43 PM

Voir le messageMonsieur Spi, le 23 March 2013 - 17:03 PM, dit :


EDIT : c'est moi ou le forum premplace automatiquement le c cédille par un c cédille majuscule ?

C'est pas toi !


Ayé j'ai pu participer de façon constructive :eusa_doh:





:jesors:
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#62 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 26 March 2013 - 13:36 PM

Voir le messagelilive, le 23 March 2013 - 12:07 PM, dit :

J'ai testé en modifiant ton code pour implémenter l'union-find selon wikipedia. C'est genre 20% plus lent.
[…]
J'ai du mal à avoir clair en tête ce que fait ton code, car je dois lutter avec la référence croisée entre Zone Et Cellule. Je le comprends en lisant ton code, puis Ça fait comme si je devais lutter pour maintenir ma vision à jour au fur et à mesure que je pense au reste.
[…]
J'ai aussi fait un test en gardant ton approche et en me débarrassant de Zone. Là c'est un peu plus rapide.
UP

Je suis assez occupé cette semaine, du coup, je fais juste un petit up pour ne pas laisser tomber le topic dans l'oubli.

@lilive : merci pour les tests…
J'ai tenté aussi la suppression de zone et j'ai aussi un bon résultat.
J'ai vu après qu'on avait fait pratiquement pareil :-)
J'ai vu aussi une ligne de commentaire qui me fait voir à peu près là ou c'est embrouillé…
J'ai conÇu zone comme un objet pour remplacer l'indice des chemins (méthode de réunion des chemins- wikipedia).
Je voulais avoir un objet plutôt que juste un indice pour la zone/chemin justement pour éviter de repartir à chaque fois de l'indice et de me farcir toutes les cellules. En ayant une classe dédiée, j'avais un objet et je pouvais modifier l'objet directement, donc pour toutes les cellules référenÇant l'objet (c'est ce qui se passe lors de la jonction : je n'ai pas besoin de m'occuper des cellules du chemin le plus long, puisque je modifie leur "zone", et j'ai juste à valoriser la zone des cellules du chemin le plus court…

Avec l'intégration des first, next et last directement dans la classe Cellule, la propriété first rempli le rôle de la zone de la même faÇon…

J'ai supprimé également mon tableau "ouvert" qui me disait si une cellule voisine était accessible ou pas. C'était un reste devenu inutile puisque je ne renseigne plus les voisines. Je le fais uniquement lors de l'ouverture d'une porte. Du coup, s'il y a une cellule, c'est qu'il y a un accès… j'ai encore gagné un petit peu.

J'ai simplifié aussi le dessin du labyrinthe dans la class App, en ne dessinant que les chemins au lieu de dessiner les murs.

Depuis, je ne vois rien que je peux encore simplifier.

Je cogite pour l'implémentation des zones, et Ça prend forme mais je ne suis pas encore prêt à le coder et je manque de temps (trop d'enfants à charge cette semaine ;-) ).


Je vous remets les classes au plus propre. Quelques noms de variables ont changé pour essayer d'être plus clair. Si Ça a vraiment un intérêt que je m'explique d'avantage, dites)le, et je commenterai un peu plus.


Sinon, j'ai vu Ça ce matin :
http://adsoftheworld...rinth_nietzsche

et je me disais que c'était tout à fait faisable de faÇon automatique (même si sûreùent moins souple, en tous cas avec mon niveau) sur le principe suivant :

- si on part d'une photo, détection des contours (méthode photo, je peux fournir un peu d'explications si Ça intéresse quelqu'un)
- sinon, partir d'une illustration au trait.
- découpage en pixels (là, c'est un peu flou pour moi)
- attribution d'une valeur aux murs en fonction de la densité de contour à cet emplacement
- tri des murs selon cette valeur au lieu de faire un tri aléatoire
- ouverture des murs sur le même principe qu'actuellement…

Si je trouve le temps j'irai voir ce que Ça donne comme rendu.
Sinon, si quelqu'un d'autre de plus rapide veux se le tenter, l'idée est libre de tous droits :-)

A plus.

Fichier(s) joint(s)

  • Fichier joint  laby.zip   4.32 Ko   13 téléchargement(s)


#63 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 26 March 2013 - 13:56 PM

Yop,

Tant que j'y suis j'y vais aussi de mon petit up sur ma partie ;-)
J'ai mis à jour mon petit test ici : http://spi4.free.fr/...guelike_01.html

Utilisez la touche C du clavier pour changer aléatoirement d'environnement.
Pour le moment il y a 4 environnements générés : région, caverne, labyrinthe, donjon
La région est une map de 256*256, les autres sont de 64*64, c'est un environnment général où le joueur revient à chaque sortie de donjon ou autre, pour vendre, acheter, se soigner, évoluer, .... L'échelle de la map des régions est également réduite (personnages) afin de donner l'impression de parcourir de grandes distances. Pour les graphismes rien n'est défini pour le moment, ce sont des feuilles de sprites de brouillon pour faire des tests.

Je bosse actuellement sur la "région", je réfléchit à la manière de faire des rivières (tracés aléatoires entre deux points de la map), puis tracer des chemins entre les différents points importants de la map (magasins, donjons, labyrinthes, cavernes).

Désolé je ne participe pas trop aux optimisations que vous faites sur la génération des labyrinthes, mais je pense que tous les deux êtes bien plus forts que moi sur ces parties, et j'ai encore énormément à faire pour obtenir un résultat propre avec mon jeu. En revanche votre boulot me sera des plus utiles lorsque je devrais me mettre à optimiser la génération de mes maps, donc merci à vous pour ce partage, je m'y colle dès que j'ai suffisament avancé pour prendre un peu de marge et étudier vos codes. ;-)

#64 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 27 March 2013 - 14:31 PM

Yop,

J'ai besoin de l'aide des matheux que vous êtes :mrgreen:

Je suis sur la génération auto de la map "régions", pour bien faire je cherche à créer tout d'abord deux rivières qui traversent la map (chemin aléatoire mais bien tordu), puis relier tous les points importants de la map (structures, donjons, magasins, ...) par des chemins (si un chemin coupe une rivière je colle un pont).

Je pensait partir sur un truc simple, genre pathfinding pour les chemins et tirage aléatoire pour la rivière, mais ça ne colle pas, je me suis donc lancé dans une petite recherche d'algos et je suis tombé là dessus :

Tout d'abord pour les labyrinthes (partie qui vous intéresse surement) :
http://www.olivierpons.fr/labyrinthes/ (voir le menu latéral droit pour un résumé de tous les algos de créa de labyrinthes)
C'est globalement une traduction française de cette page : http://www.astrolog....th/algrithm.htm

Puis pour la rivière :
http://fr.wikipedia....C3%AAt_maximale
http://fr.wikipedia....K%C3%B6nigsberg
http://fr.wikipedia....rie_des_graphes

Les algos :
http://fr.wikipedia....orithme_de_Prim
http://fr.wikipedia....thme_de_Kruskal
http://fr.wikipedia....de_Bor%C5%AFvka

Ca semble se rapprocher beaucoup du pathfinding et de l'algorithme de Dijkstra (http://fr.wikipedia....hme_de_Dijkstra), mais niveau en maths étant ce qu'il est, j'ai un peu de mal à déterminer si c'est bien ce dont j'ai besoin, si ça se trouve je suis totalement à côté de la plaque.

Si vous avez des idées là dessus je suis preneur, l'objectif étant de faire un tracé torturé mais qui ne repasse jamais par le même point (principe d'une rivière qui ne remonte pas la pente, elle peut en revanche se scinder en plusieurs chemins qui peuvent se rejoindre ou non). Je pense que je vais finir par trouver en cherchant, mais j'essaye d'avancer sur 200 autres trucs en même temps et j'avoue avoir la tête un peu farcie depuis une semaine, donc si vous avez du temps et l'envie de jouer, quelques pistes seraient les bienvenues ;-)

Merki.



EDIT : pour le moment voici la solution la plus simple que j'ai trouvé :

riviere(0, int(Math.random()*L), C, int(Math.random()*L),350);

function riviere(x1:int, y1:int, x2:int, y2:int, f:int):void {
        if (f==0) {
                while(x2>x1) decor[(x1++)+y1*L] = 2;
                while(x1>x2) decor[(x1--)+y1*L] = 2;
                while(y2>y1) decor[x1+(y1++)*L] = 2;
                while(y1>y2) decor[x1+(y1--)*L] = 2;
                decor[x1+y1*L] = 2;
    } else {
                var X:Number = (x2+x1)*.5;
                var Y:Number = (y2+y1)*.5;
                X += (Math.random()-.5)*f;
                Y += (Math.random()-.5)*f;
                riviere(x1, y1, X, Y, f/2);
                riviere(x2, y2, X, Y, f/2);
        }
}

C'est pas parfait mais ça donne au moins un résultat correct.

#65 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 27 March 2013 - 15:40 PM

Voir le messageMonsieur Spi, le 27 March 2013 - 14:31 PM, dit :

J'ai besoin de l'aide des matheux que vous êtes :mrgreen:

On me parle ? :jesors:




EDIT SPI : je répond directement là lol

Voir le messageNataly, le 27 March 2013 - 14:31 PM, dit :

On me parle ?

Oui on te parles, parce que toi tu pourrait intervenir sur l'interface et la gestion clavier/souris, SharedObject, ......
Allez zou, je met tout le monde à contribution pour mon jeu ! :mrgreen:
Je plaisante, mais si tu te sent des ailes sur un truc n'hésites pas, j'ai tellement de taf sur le feu avec ce petit jeu que n'importe quel point qui me permet d'avancer plus vite est un gros bonus
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#66 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 27 March 2013 - 21:35 PM

Petite question : ça représente une carte de combien de "pixels/unités/sprites" environ ?
Parce que j'ai déjà bossé un peu sur de la génération de terrain mais dans un esprit géologie à grande échelle. Je ne suis pas sur que ça puisse servir à petite échelle…

Sinon à grand échelle :
  • générer du relief
  • rechercher les lignes d'écoulement des eaux
  • rechercher les lignes de crête
  • rechercher les tracés d'altitudes
  • après faut voir à mailler…
Les rivières passent par les lignes d'écoulement à partir d'une source
Les chemins sont plus complexes. Ils suivent plutôt les lignes de crête en terrain vallonné, les tracés d'altitude en montagne (tout droit en plaine)… ça me semble être un trop gros boulot, non ?

#67 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 27 March 2013 - 22:07 PM

Yop,

Alors pour le moment ça va avec le petit code que j'ai trouvé (cf l'edit de mon dernier message) mais si tu as mieux ou plus simple n'hésites pas.

Citation

Petite question : ça représente une carte de combien de "pixels/unités/sprites" environ ?

Pour le moment j'ai limité la map à 256*256 cases
graphiquement chaque tuile fait 64*64 mais n'a pas d'importance ici puisque je trace chaque case entière.

Citation

Sinon à grand échelle :
  • générer du relief
  • rechercher les lignes d'écoulement des eaux
  • rechercher les lignes de crête
  • rechercher les tracés d'altitudes
  • après faut voir à mailler…

Ca va etre trop compliqué de gérer un relief aléatoire en iso sur une si petite map, à l'affichage mon perso va se retrouver derrière des hauteurs et le joueur ne saura plus où il va. C'est le facteur aléatoire qui me bloque à chaque fois, je ne maîtrise pas du tout le look final des environnements, du moins je ne le connais pas à l'avance. Du coup ça me semble beaucoup trop précis/complexe pour ce que je veux faire ;-)

En fait ce qui me bloquait c'était que je voulais un tracé cohérent et que j'ai pensé au fait qu'une rivière ne repasse jamais deux fois au même endroit, mais en fait on s'en fout puis que ma map est à plat..... du coup j'arrive à m'en sortir avec un peu de récursivité, ça me donne un tracé pas mal torturé et sans coupures, avec même des petits lacs quand le tracé fait des boucles. Je tranche comme un sagouin dans les murs (qui sont en fait des fôrets pour les extérieurs) sans tenir compte du "relief" et ma rivière traverse la map tranquille. Il me reste à voir comment parcourir tous les bords de la rivière pour dessinner les rives mais ça c'est assez simple.

Prochaine étape, tracer les chemins qui relient tous les points importants de la carte (maisons, magasins, donjons, labyrinthes, cavernes).

#68 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 27 March 2013 - 22:33 PM

OK.

Alors j'oublie (au moins pour le moment).

Sinon, j'étais en train de regarder avec la méthode des cavernes.
- En jouant sur le seuil de ta fonction choisirTuile (par ex. 0.65)
- En traçant des "lignes" de zéros dans le tableau, on obtient des trucs qui peuvent ressembler à des cours d'eau… (de loin… et pas tout le temps).

Je crois que je vais un peu me pencher sur cette méthode pour voir ce qu'elle peut générer d'autre… :-)

#69 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 27 March 2013 - 22:48 PM

C'est marrant, moi les cavernes ça me faisait plus penser à des fleuves ou à des lacs avec un relief.

En tout cas c'est bien fun de voir les environnements se générer tout seuls, j'ai pensé à créer plusieurs feuilles de sprites pour chaque décor, histoire de varier, il suffit de tirer la feuille aléatoirement, mais il va falloir que je trouve un graphiste pour m'aider, je passe trop de temps à essayer de dessinner des trucs corrects....

#70 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 27 March 2013 - 23:08 PM

Ça cogite grave dans ce topic !

M.Spi, ton code m'a fait penser au motif fractal qu'on nous avait fait faire au lycée.
Du coup j'ai googlé "fractal river algorithm" quelques minutes, et c'est plein d'exemples. Bien sûr la plupart sont dans l'optique de créer des terrains plus détaillés que le tien.
Exemple: http://www.graphicsi...ewiczHammel.pdf

Et sinon, rien à voir, prévois-tu une animation du déplacement qui soit plus douce, qui ne saute pas de tuile en tuile ? J'ai l'impression que ce serait bien plus agréable au rendu.

#71 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 27 March 2013 - 23:27 PM

Ha oui c'est sympa aussi ça, merci.

Citation

Et sinon, rien à voir, prévois-tu une animation du déplacement qui soit plus douce, qui ne saute pas de tuile en tuile ? J'ai l'impression que ce serait bien plus agréable au rendu.

Oui :-)

C'est une partie que je ferait après, il y a juste à faire quelques modifs dans le moteur de rendu iso pour éviter que la map se décale quand on est à moitié sur deux tuiles, mais je ferait ça après pour le moment ce n'est pas important, il y a plein de petits trucs que j'ai laissé en suspend, mais ça avance pas mal, je suis content.


EDIT : il y aura même le choix de jouer à la souris (pathfinding) ou clavier, et en mode tour par tour (case par case) ou temps réel (fluide)

#72 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 28 March 2013 - 13:37 PM

Voir le messageNataly, le 27 March 2013 - 15:40 PM, dit :

On me parle ? :jesors:

SPI dit :

Oui on te parles, parce que toi tu pourrait intervenir sur l'interface et la gestion clavier/souris, SharedObject, ......
Allez zou, je met tout le monde à contribution pour mon jeu ! :mrgreen:

Si ce n'est que ça : boulonner un pov cookie et une gestion de préférences… je peux m'y coller, ça me permettra de frimer sur le mode : j'en étais ! :mrgreen: (pas obligé de préciser le champ d'intervention :cool: )
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#73 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 29 March 2013 - 14:20 PM

Alors bienvenue ;-)

Je donne une formation et donc je ne suis pas dispo jusqu'à lundi, mais dès lundi je te fais un brief de ce qui pourrait être utile.
Attention, l'enregistrement par cookie va peut être aller bien plus loin que ce que tu ne crois, en effet je vais avoir besoin de sauvegarder aussi (en plus des préférences clavier) les maps en cours (grilles) et les paramètres du joueur (feuille de personnage) pour que le joueur puisse couper le jeu et reprendre sa partie à n'importe quel moment. Il faudrait aussi réfléchir à crypter les infos dans le cookie (ce qui ferait un bon complément à ton tuto sur le sujet), afin que le joueur ne puisse pas modifier les maps et sa feuille de perso facilement en ouvrant le cookie (puisque tu as donné l'endroit où il faut aller le chercher).

#74 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 29 March 2013 - 15:15 PM

Voir le messageMonsieur Spi, le 29 March 2013 - 14:20 PM, dit :

Je donne une formation et donc je ne suis pas dispo jusqu'à lundi
Une formation sur la fabrication de cloches volantes ? Coooool !
Comment ? Je sors ? Bon, ok, ok, si on peut rien dire alors ici rhaaa...

:jesors:

#75 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 29 March 2013 - 16:29 PM

Citation

Une formation sur la fabrication de cloches volantes ?

lol je ne sais pas comment prendre cette remarque ;-)

Je retourne a mes élèves ;-)

#76 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 29 March 2013 - 17:25 PM

Voir le messageMonsieur Spi, le 29 March 2013 - 14:20 PM, dit :


Attention, l'enregistrement par cookie va peut être aller bien plus loin que ce que tu ne crois,[…]

Et voilà ! on donne ça (une phalange) il prend ça (le bras) !

Je verrai ce que je peux faire. Choper les infos et les enregistrer, voir les "crypter" (je peux toujours appliquer un coef aux valeurs), ça devrait ne pas être trop difficile, les récupérer pour initialiser le jeu, ça je ne garantis pas de m'y retrouver ;) mais ça te fera déjà un début :P
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#77 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 29 March 2013 - 19:29 PM

Voir le messageMonsieur Spi, le 29 March 2013 - 16:29 PM, dit :

lol je ne sais pas comment prendre cette remarque ;-)
Haha. Je t'imagine t'interrogeant sur un sens caché, dans l'hypothèse où tu n'aurais pas vu la référence à pâques :mrgreen:
Mais non, pas de sens caché, j'ai hésité entre ça, les oeufs et les lapins. Mais fabriquer des oeufs ou des lapins, j'ai trouvé que c'était vraiment trop n'importe quoi, ya des limites quand même !

#78 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 29 March 2013 - 20:15 PM

Citation

Et voilà ! on donne ça (une phalange) il prend ça (le bras) !

Et la tête, et la tête, alouette, alouette, alalalalalaaaaa.....

Désolé chuis fatigué.......

Citation

Je verrai ce que je peux faire. Choper les infos et les enregistrer, voir les "crypter" (je peux toujours appliquer un coef aux valeurs), ça devrait ne pas être trop difficile, les récupérer pour initialiser le jeu, ça je ne garantis pas de m'y retrouver ;) mais ça te fera déjà un début

Yep, de toute façon je n'ai pas encore le modèle définitif des grilles et aucune idée du volume d'infos à stocker (attention à la limite de taille du cookie... 100 Ko je crois)

Citation

j'ai hésité entre ça, les oeufs et les lapins. Mais fabriquer des oeufs ou des lapins, j'ai trouvé que c'était vraiment trop n'importe quoi, ya des limites quand même !

Moi j'aime bien les lapins, les lapins... crétins ;-)

#79 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 13 April 2013 - 01:18 AM

Hello,

Je déterre un peu, j'ai trouvé ça qui pourrait vous intéresser pour les labyrinthes : http://weblog.jamisb...ap#article_body

#80 lilive

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 2993 messages

Posté 13 April 2013 - 09:11 AM

Salut M.Spi,
Merci pour le partage, ça m'a intéressé.

#81 Urban angel

    Ceinture Verte

  • Members
  • PipPipPipPip
  • 50 messages

Posté 21 October 2013 - 18:08 PM

Rha, je découvre ce topic après la guerre, super intéressant les gars bravos !



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

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