JeuWeb - Crée ton jeu par navigateur
Génération d'un donjons aléatoire - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Génération d'un donjons aléatoire (/showthread.php?tid=4162)

Pages : 1 2 3


Génération d'un donjons aléatoire - kilhom - 08-07-2009

Bonjour à tous !

Voila je me suis lancé dans la création d'un générateur de donjons aléatoire.
Je n'ai jamais fait de script dans ce genre avant et j'ai besoin d'un petit coup de main Smile.

Le donjon se compose de salles, que voici :

[Image: salles36r.png]
Les mur sont représentés par des traits noir.

Voila mon idée pour générer mon donjons :

On génère chaque case les unes après les autres en commençant par en haut à gauche.
A chaque génération de case on regarde les cases adjacentes du haut et de gauche (car celle du bas et de droite ne sont pas encore générées, logique).
Si l'une ou plusieurs de ces cases adjacentes comportes des "entrées" (des portes vers la case générée) on les prends en compte et on trouve une case qui respecte ces entrées.

et on fait ce système en boucle jusqu'à la fin de la carte.

Seulement voila je sèche un peu.

J'aimerais pouvoir faire :
$sql = 'SELECT id FROM pieces WHERE haut = 1 bas = 1';
Ce qui me retournerais toutes les ID des pièces ou le haut et le bas sont fermés et la gauche et la droite ouvertes ou fermés.

Ensuite je n'aurais plus qu'à piocher dedans pour prendre aléatoirement une piece qui répond à ces critères...

Mais le problème est là : je n'utilise pas de SQL pour ce script, les informations de mes pièces sont stockés dans des variables associatives... (voir infos_cases.php).

Ci contre mes deux pages commentés :
index.php
Code PHP :
<?
$image
= 'images/';
// Infos (mur ou pas mur) sur chaque case
include('infos_cases.php');
?>
<form action="" method="post">
Largeur :<br>
<input name="x_max" type="text" value="<?=$_POST['x_max']?>" ><br>
Longueur :<br>
<input name="y_max" type="text" value="<?=$_POST['y_max']?>" ><br>
(Option Case :)<br>
<input name="case" type="text" value="<?=$_POST['case']?>" >
<input type="submit" value="G&eacute;nerer">
</form>
<br>
<hr>
<br>
<?
if(isset($_POST['x_max']) AND is_numeric($_POST['x_max']) AND isset($_POST['y_max']) AND is_numeric($_POST['y_max']) AND $_POST['x_max'] <= 30 AND $_POST['y_max'] <= 30){

// On calcul la largeur en pixel du div qui va contenir les div "case"
$largeur_px = $_POST['x_max']*90;

$carte .= '<div id="limite_largeur" style="width:'.$largeur_px.'px;">';

// $num_c représente le numero de la case
$num_c = 0;
for (
$nb_y = 0; $nb_y < $_POST['y_max']; $nb_y++)
{
for (
$nb_x = 0; $nb_x < $_POST['x_max']; $nb_x++)
{

$num_c++;

// On rajoute +1 pour ne pas avoir pour origine x=0/y=0 mais x=1/y=1 (confort)
// Les variables si dessous sont faites pour pouvoir retrouver facilement l'id d'une case à partir de son X et Y et inversement
$cases[$nb_x + 1][$nb_y + 1] = $num_c;
$cases[$num_c]['x'] = $nb_x + 1;
$cases[$num_c]['y'] = $nb_y + 1;

// Récupération de l'ID cases du dessus et de gauche
$case_dessus = $cases[$cases[$num_c]['x']][$cases[$num_c]['y']-1];
$case_gauche = $cases[$cases[$num_c]['x']-1][$cases[$num_c]['y']];

// Si il n'y a pas de case en haut ou à gauche on considère ça comme un mur
if($cases[$case_dessus]['piece'] == ''){$cases[$case_dessus]['piece'] = 0;}
if(
$cases[$case_gauche]['piece'] == ''){$cases[$case_gauche]['piece'] = 0;}

// ICI : toutes les rêgles de passage (mur/ouverture)


//$cases[$num_c]['image'] = $piece[$cases[$num_c]['piece']]['image'];

$carte .= '<div style="background-image:url('.$cases[$num_c]['image'].'); background-color:#FFFFFF; color:#000000; height:90px; width:90px; float:left; display:inline; text-align:center;">';

if(
$_POST['case'] == $num_c){
$carte .= '<b>'.$num_c.'</b>';
//$carte .= '<br>( x:'.$cases[$num_c]['x'].' y:'.$cases[$num_c]['y'].' )';
$carte .= '<br>ID Case du dessus : '.$case_dessus;
$carte .= '<br>ID Case de gauche : '.$case_gauche;
} else {
$carte .= $num_c;
}

$carte .= '</div>';


}
$carte .= '<div style="clear: both;"></div>';
}

$carte .= '</div>';

echo
$carte;
}
?>

infos_cases.php
Code PHP :
<?
// 1 = Fermé 0 = Ouvert (1=mur/0=pas de mur)
$piece[0]['haut'] = '1';
$piece[0]['bas'] = '1';
$piece[0]['droite'] = '1';
$piece[0]['gauche'] = '1';
$piece[0]['image'] = $image.'00.png';

$piece[1]['haut'] = '1';
$piece[1]['bas'] = '0';
$piece[1]['droite'] = '0';
$piece[1]['gauche'] = '1';
$piece[1]['image'] = $image.'01.png';

$piece[2]['haut'] = '1';
$piece[2]['bas'] = '0';
$piece[2]['droite'] = '1';
$piece[2]['gauche'] = '0';
$piece[2]['image'] = $image.'02.png';

$piece[3]['haut'] = '0';
$piece[3]['bas'] = '1';
$piece[3]['droite'] = '1';
$piece[3]['gauche'] = '0';
$piece[3]['image'] = $image.'03.png';

[...]
Vous avez compris le principe ;)

Et le lien vers une démo :
http://kilhom.free.fr/manoir/

Voila voila, une idée ? Wink

Merci de m'avoir lu, et @+ !


RE: Génération d'un donjons aléatoire - My Hotel - 08-07-2009

Franchement, moi je prendrais plutôt 4 images (murs dans les 4 sens possibles) et je les positionnerai en PHP. Ça s'approche un peu d'un générateur de labyrinthe, où il doit y avoir au moins un chemin, donc regarde ça sur le web, et sur le SdZ, où il y avait eu un concours, il me semble Wink

Sinon, pourquoi ne pas utiliser SQL? C'est quand même plus simple, non? Pour imiter ça : "$sql = 'SELECT id FROM pieces WHERE haut = 1 bas = 1';" avec des array, tu peux parcourir l'array et stocker à chaque fois les cases qui répondent à tes conditions. Puis, il y a sûrement des fonctions pour les array bien pratiques pour cette situation.

P.S : met ton code en mode PHP, c'est plus simple à lire.

Désolé, c'est vite répondu, je dois partir en vacances Wink


RE: Génération d'un donjons aléatoire - kilhom - 08-07-2009

(08-07-2009, 07:28 PM)My Hotel a écrit : Franchement, moi je prendrais plutôt 4 images (murs dans les 4 sens possibles) et je les positionnerai en PHP. Ça s'approche un peu d'un générateur de labyrinthe, où il doit y avoir au moins un chemin, donc regarde ça sur le web, et sur le SdZ, où il y avait eu un concours, il me semble Wink
Non justement le but c'est de ne pas le faire en GD ^^
Je cherche pas à faire une image mais bien un donjons totalement exploitable par la suite.
(08-07-2009, 07:28 PM)My Hotel a écrit : Sinon, pourquoi ne pas utiliser SQL? C'est quand même plus simple, non? Pour imiter ça : "$sql = 'SELECT id FROM pieces WHERE haut = 1 bas = 1';" avec des array, tu peux parcourir l'array et stocker à chaque fois les cases qui répondent à tes conditions.
Oui peut être que c'est plus simple en SQL mais j'aimerais justement faire sans, c'est tout le but de ma question Wink
Et puis faire une requête par case, c'est un peu gourmand tout ça !

(08-07-2009, 07:28 PM)My Hotel a écrit : Puis, il y a sûrement des fonctions pour les array bien pratiques pour cette situation.
Justement je cherche ces fonctions Smile

(08-07-2009, 07:28 PM)My Hotel a écrit : P.S : met ton code en mode PHP, c'est plus simple à lire.
Oups, j'avais rater le bbcode !


Merci de ta réponse en tout cas Wink


RE: Génération d'un donjons aléatoire - Arius Vistoon - 08-07-2009

euh, ca me parait compliqué pour pas grand chose....

perso je vois 2 solutions (a vue de nez, je n'y ai pas réfléchi depuis plusieurs années).

1) un systeme simple qui génère chaque case INDEPENDAMMENT des autres cases

2) un systemes complexe qui génère en fonction des cases voisines
--------------
ton algo pourrait correspondre a la 2eme solution mais n'est pas du tout assez poussé (selon moi, j'ai pas regardé ton code juste ton explication).

Hors je suis persuadé que la solution 1 ferait beaucoup mieux que ce que tu propose en plus simple et moins lourd en traitement

Pour info, il y a de cela environ 20ans (merde, ca fait un baille :non:, amiga powaa), j'avais fait un un jeux de labyrinthe en 3d totalement aléatoire (le but était que j'e puisse y jouer sans connaitre mon propre jeu)

Je m'était inspiré de jeux de l'époque a laquelle je jouais souvent ("dungeons master", "la vallée de kyrandia" et "sorcery 1-2-3") et d'un magasine "jeux et stratégie" qui proposait un algo hyper simple (genre 4 ou 5 lignes de code max) pour générer un labyrinthe aléatoire sur calculatrice (solution 1).

Donc j'ai améliorer l'algo et fait mon labyrinthe aléatoire en 3D (enfin en fausse 3D, juste de la 2D avec un sentiment de profondeur comme dit ce je ne sais quel sujet de ce forum).

De mémoire lalgo reposer sur une formule mathémathique a base de sinus et cosinus qui permettait d'avoir un nombre pseudo aléatoire qui garantissait un chemin plus ou moins long vers la "sortie" en remplacant ces nombres par ce que l'on souhaiter (ex: 1=porte 2=chemin 3=passage secret 4=monstre a endroit fixe 5= element scénaristique etc...) j'avais obtenu un jeu "vivant".

j'espere t'avoir aidé


RE: Génération d'un donjons aléatoire - My Hotel - 08-07-2009

(08-07-2009, 08:35 PM)kilhom a écrit :
(08-07-2009, 07:28 PM)My Hotel a écrit : Franchement, moi je prendrais plutôt 4 images (murs dans les 4 sens possibles) et je les positionnerai en PHP. Ça s'approche un peu d'un générateur de labyrinthe, où il doit y avoir au moins un chemin, donc regarde ça sur le web, et sur le SdZ, où il y avait eu un concours, il me semble Wink
Non justement le but c'est de ne pas le faire en GD ^^
Je cherche pas à faire une image mais bien un donjons totalement exploitable par la suite.
(08-07-2009, 07:28 PM)My Hotel a écrit : Sinon, pourquoi ne pas utiliser SQL? C'est quand même plus simple, non? Pour imiter ça : "$sql = 'SELECT id FROM pieces WHERE haut = 1 bas = 1';" avec des array, tu peux parcourir l'array et stocker à chaque fois les cases qui répondent à tes conditions.
Oui peut être que c'est plus simple en SQL mais j'aimerais justement faire sans, c'est tout le but de ma question Wink
Et puis faire une requête par case, c'est un peu gourmand tout ça !

(08-07-2009, 07:28 PM)My Hotel a écrit : Puis, il y a sûrement des fonctions pour les array bien pratiques pour cette situation.
Justement je cherche ces fonctions Smile

(08-07-2009, 07:28 PM)My Hotel a écrit : P.S : met ton code en mode PHP, c'est plus simple à lire.
Oups, j'avais rater le bbcode !


Merci de ta réponse en tout cas Wink

T'as pas compris : je te propose 2 images _ et | que tu positionne avec des divs générés par PHP, t'as donc bien une carte utilisable indépendamment par la suite. Comme pour les maps, en fait, tu place des images dans les divs aux positions gérées par PHP.

Pour le SQL, je te proposai de stocker tes infos dans la BDD, de faire une requête pour tout récupérer et mettre ça dans un array, et là, t'as ton script normal.

Pour les fonctions des arrays : ici

Et regarde les générateurs de labyrinthe, y'as des trucs intéressants pour faire des chemins cohérents (début, fin, et au moins 1 passage).

Bye


RE: Génération d'un donjons aléatoire - kilhom - 08-07-2009

(08-07-2009, 08:50 PM)Arius Vistoon a écrit : euh, ca me parait compliqué pour pas grand chose....

perso je vois 2 solutions (a vue de nez, je n'y ai pas réfléchi depuis plusieurs années).

1) un systeme simple qui génère chaque case INDEPENDAMMENT des autres cases

Sauf que ça donne... ça :
http://data.nimages.fr/1247080167552mz8.png

et oui forcément, si on prend pas la peine de gérer les cases adjacentes et bien on se retrouve avec un tas de salles "bloquées".
Et puis attention, je rappel que je ne cherche pas à faire un labyrinthe (entré/sortie) mais bel et bien un enchainement de salles aléatoires et reliés.
De plus toutes les salles doivent être accessibles.
Merci quand même !

Je continue mes recherches...


RE: Génération d'un donjons aléatoire - wild-D - 08-07-2009

+1 pr Arius Vistoon; il existe des algos de création de labyrinthe relativement "simple" mais très efficace.

genre pour le générateur tu te contente des pieces 07, 08, 09, 10 (si tu colle 2 pièce 07 une à coté de lautre tu te retrouve avec un couloir,... pas besoin de 05 à ce niveau là - tu pourra toujours la reprendre pour le rendu final )

de cette manière tu allège lourdement la complexité de ton problème topologique (en gros derrière t'as plus qu'un "petit" nettoyage à faire -petit c'est parce que je me souviens plus du truc Tongue - )

sinon si tu aime shakespeare, fait une recherche "maze generator".


RE: Génération d'un donjons aléatoire - kilhom - 08-07-2009

Hop
merci à tous de vos réponse mais j'ai trouver la solution grâce à une fonction php. (merci pour le lien My Hotel, c'est vrai qu'il ne faut jamais sous estimer le manuel !)

Pour ça j'utilise array_filter(); qui me permet de trouver la liste de toutes les cases qui sont ouvertes en haut, à gauche ou les deux.


RE: Génération d'un donjons aléatoire - Arius Vistoon - 08-07-2009

(08-07-2009, 09:17 PM)kilhom a écrit : Sauf que ça donne... ça :
http://data.nimages.fr/1247080167552mz8.png

et oui forcément, si on prend pas la peine de gérer les cases adjacentes et bien on se retrouve avec un tas de salles "bloquées".
Et puis attention, je rappel que je ne cherche pas à faire un labyrinthe (entré/sortie) mais bel et bien un enchainement de salles aléatoires et reliés.
De plus toutes les salles doivent être accessibles.
ehehehe, et non, c'est la magie des math (j'suis un matheux à la base). tu auras toutes les salles "aléatoire" et NON-BLOQUE (pour peu que tu décide d'une clé de génération assez grande).

Mais tu peux si tu n'as pas confiance au math (honte à toi, car j'ai vraiment l'impression que cela est amplement suffisant. maintenant je ne connait pas ton cahier des charges), t'impliquer dans la solution 2 qui elle demande beaucoup plus de boulot (genre enormement plus..pour obtenir quelquechose de correcte) et nécessite d'en avoir vraiment besoin, je te conseille de regarder dans la génération d'effet plasma et de terrain. (mais je dois reconnaitre que pour cette solution 2, je m'y suis pas vraiment penché mais de souvenir lors de génération aléatoire de paysage avec propagation du terrain voisin, cela devait vaguement ressembler a ce ca -je parle de l'algo, pas du résultat-)

(08-07-2009, 09:17 PM)kilhom a écrit : Merci quand même !

Je continue mes recherches...
no soucaille, bonne continuation
(08-07-2009, 09:55 PM)kilhom a écrit : Hop
merci à tous de vos réponse mais j'ai trouver la solution grâce à une fonction php. (merci pour le lien My Hotel, c'est vrai qu'il ne faut jamais sous estimer le manuel !)

Pour ça j'utilise array_filter(); qui me permet de trouver la liste de toutes les cases qui sont ouvertes en haut, à gauche ou les deux.

comme quoi, je n'avais pas compris ce que tu recherchais.
cool que tu es trouvé ton bonheur


RE: Génération d'un donjons aléatoire - kilhom - 12-07-2009

Re-bonjour à tous !
A peine sortit d'un problème voila qu'un nouveau s'oppose à moi =/

Alors la par contre c'est un peu différent.
Enfaite le script fait exactement ce que je lui demande (il respecte les règles cités plus haut) cependant il y a quelques fois des pièces isolés (qui n'ont pas de lien avec les autres).
Exemple :

[Image: SanstitrePNG8c9.png]

Hors je voudrais que toutes les pièces puissent être visitables !

Est ce que quelqu'un a une idée pour contrer ça ?

(même lien pour la version de test : http://kilhom.free.fr/manoir/ )

Merci d'avance Smile