Le topic de Lapintade sur "création de jeux" sur les laby m´a inspiré. Voici un petit générateur de laby, qui genere un laby, et sa solution (sous forme de BMP)
Je fournis aussi les sources

http://perso.numericable.fr/~fvirtman/progs/makelaby.zip

Le programme génere 2 BMP dans le repertoire courant, nosol.bmp (laby sans solution), sol.bmp : le meme avec sa solution.
Je vous conseille de mettre une taille petite dans un premier temps (<100 pour x et y)

peu importe les tailles que je rentre (50, 50; 75, 80; 150, 125) ca marque "mauvaise taille"

yeaah la classe. C´est terrible comme programme.

J´ai fait il y a qq mois un prog pour JOUER dans un labyrinthe mais ça me fesait suer de les construire. Je pense que je vais en faire qq un avec ton programme et bidouiller une fonction de chargement dans le mien...

nickel merci

et aussi merci pour les sources, sinon j´aurais pas pu

m-2 c´est aussi marqué nombre IMPAIR (pour les 2 valeurs)

sympa (en tout cas, ça marche bien).

le seul truc que j´ai à dire c´est que tu devrait générer des bitmaps 4 couleurs, ce qui permettrait de produire des fichiers 16 fois plus petits (ou à la limite 256 couleurs, si tu ne veux pas t´emmerder avec les décalage d´octets).

(Ou même 2 couleurs pour nosol.bmp)

m-2 > oui, nombres impairs, important !
en effet, pour X routes verticales, il y a X+1 murs verticaux, ce qui te fait une largeur de 2X+1 (-> Impair)

guyver2 > oui, tu peux récupérer les sources : le laby est une classe assez simple d´acces avec des données membres assez simples a prendre en main
Apres, tu en fais ce que tu veux !

dnob700 > oui, je pense que je ferai un ecrire BMP light
En fait, j´ai fait ça rapidos : j´ai pris le générateur de laby que j´avais fait pour le Klostro Laby (en le ramenant a 2 dimensions)
Et un vieux ecrire BMP que j´avais
Il faut que j´en fasse un plus light

Exellent
Par contre j´ai demandé du 1001 par 1001, et ca fait 5mn qu´il a ecrit Generation et rien d´autre.

forcement, la complexité doit etre exponentielle, et si FVirtman dit qu´il faut pas voir trop haut (100*100) c´est qu´il y a une raison... enfin si tu n´a rien d´autre a faire tu peux le laisser courrir...

mm, j´ai pas lu le code, mais je ne vois pas de raison que ca soit exponentielle...
la recherche de plus court chemin doit se faire en O(nombre de case).
La génération je ne sais pas trop quel algorithme il a choisit, mais il n´y a pas de raison qu´il soit exponentiel.

J´ai trouvé ca dans ton code...
j´ai peur de ne pas comprendre.

1. ifdef _DEBUG

if (i<0 || j<0 || i>=x || j>=y)
while(0);

1. endif

pourquoi pas un assert (i<0...) ?

Je ne sais pas comment est compiler le bianire de JYY, mais l´optimisation peut changer beaucoup de chose :

j´ai compilé le programme avec juste g++ makelaby.cpp et j´ai testé en 1001*1001, au bout de 20 minutes, il n´avait toujours pas finis.

Je l´ai recompilé avec -O3 -march=nocona et là, en moins de 3 minutes il avait terminé.

godrik:
j´ai pas vraiment suivit les cours sur la complexité mais une complexité en O(nombre de case) revient a une complexité en O(n²) en suposant qu´on demande un carré de n par n

tests de vitesses (avec les optimisation de dnob700:
101*101 -> 2 secondes (5000 cases/secondes)
501*501 -> 18 secondes (13944 cases/secondes)
701*701 -> 78 secondes (6300 cases/secondes)
1001*1001 -> 300 secondes (3340 cases/secondes)

Donc la supere conclusion : ?? ?
Je pense que la complexité moyenne est uniquement dépendante de la taille du laby (de quoi d´autre me direz vous) donc en O(n²) avec n la taille d´un coté mais cela ne donne qu´un ordre de grandeure moyen et il est possible que la complexité "au pire" soit bien superieure. Je ne me suis pas penché sur le code mais il doit y avoir un truc de "chance" la dedans (si les choses se goupilles bien alors ça va vite).

Si quelqu´un s´y connait je suis tout ouïe. Et je vais me pencher plus conséquement sur le code.

en fait la 1ere mesure est fausse ce qui serait logique...

je rajoute un petit compteur sdl et je revient avec de vraies valeurs

alors voila un peu de précision
cps = cases par seconde

101*101 -> 48 ms
-> 21252 cps
501*501 -> 20022 ms
-> 12536 cps
701*701 -> 82198 ms
-> 5978
1001*1001 -> 346237 ms
-> 2893 cps

ce qui semble plus logique et nous donne
http://img501.imageshack.ack.us/img501/628/graphrj0.jpg
donc la complexité semble bien en O(n²)

Je ne comprend pas ta conclusions.

Pour tes cps, tu considère bien n*n comme nombre de case ?

si c´était en O(n²), les cps seraient quasi constant. Hors ça ne semble pas être le cas ici.

Par contre, en O(n²) ce n´est pas exponentiel mais polynomial (tout cequi est de la forme O(n^a)). Une complexité exponentielle est de la forme O(a^n).

"Pour tes cps, tu considère bien n*n comme nombre de case"

oui

"Par contre, en O(n²) ce n´est pas exponentiel mais polynomial"

oui oui je me suis planté (j´ai tjs eu du mal avec ça)

"si c´était en O(n²), les cps seraient quasi constant"

les cps diminuent d´autant plus qu´il y a beaucoup case a calculer. donc ça fait bien un temps de calcul par case qui augmente avec le nombre de case (non ?)

Et bien, je vois que ça souleve beaucoup de questions !
Alors j´explique l´algo de génération :
3 parties :
- l´autogenere : (méthode AutoGenere_amorce)
Ici, je crée une grille, un peu comme un sudoku
http://www.sos-cadeaux.coom/sudoku-images/sudoku-01.gif
c´est a dire que j´alterne les murs et les trous une rangée sur deux. Ainsi, a la sortie de cette étape, le laby n´est qu´un tableau ou chaque trou ne fait qu´un seul pixel. Et l´ensemble est régulier.
Note : les nombres entrés soivent etre impairs pour obtenir une telle forme : il y a toujours 1 trait (mur) de + que les cases. (pour un sudoku, il y a 9 cases horizontalement, et pourtant, 10 traits verticaux sont nécessaires pours les séparer (et les englober)
- l´assignation (le systeme de double for dans la méthode Autogenere)
Je vais numéroter chaque zone évidée, chaque trou. Ce sera des numéros de zone. Je stocke tous les numéros de zone dans un "set"
(un set est une structure qui garde des éléments uniques, et accede a ceci en O(ln2(n)), en interne, c´est un binaire de recherche)
- le creusement : (le while de AutoGenere) et fonction Creuse
le but maintenant est de creuser au hasard des murs jusqu´a ce que le laby devienne connexe.
Pour cela, je choisis une positionx,y au random. Si c´est un mur, je ne creuse pas, et je passe a la suite.
Si c´est un mur, je regarde les 4 voisins de ce mur, et surtout, le numéro de leur zone.
Si il y a 2 voisins a zones différentes, ça veut dire que le mur que je casse va rassembler 2 zones.
Donc dans ce cas, je casse le mur, puis je paints (avec l´algo du pot de peinture (Laby::Fill) ) l´une des 2 zones avec le numéro de l´autre zone. En d´autres termes, si je rassemble la zone 10 et la zone 23, je paints la zone 10 en 23 : en gros, la nouvelle zone s´appellera entierement 23, et la zone 10 disparait. Je retire la zone 10 de l´ensemble (le set)
Et je recommence le creusement jusqu´a ce que je n´ai plus qu´une seule zone : cela signifiera alors que le laby est connexe, et donc possible.

Il est a noter que j´ai fait un algo de pot de peinture par itération : en effet, certains compilos ne tolerent pas qu´on empile des appels de fonction a l´infini : si j´avais fait cet algo récursivement, alors ça aurait pu planter pour les gros laby, ce qui n´est pas le cas avec un algo itératif qui utilise une pile (std::stack)

Voila, et pour l´algo de résolution du laby, c´est la meme chose, un algo de pot de peinture itératif modifié : des que la "peinture" touche l´arrivée, ça veut dire que ma pile contient la bonne route -> que je note.

Sinon, j´ai donc relevé des remarques auquelles je voudrais répondre :
--> Par contre j´ai demandé du 1001 par 1001, et ca fait 5mn qu´il a ecrit Generation et rien d´autre.
Oui, y´a un certain temps de calcul.

--> la complexité doit etre exponentielle
A mon avis, elle n´est pas linéaire, mais pas exponentielle non plus. ça doit venir des algos de pot de peinture frequemment appelés.
Il ne faut pas oublier que pour un laby de 100*100, tu as 10 000 cases, mais pour 1000*1000, tu en as 1 million.
Quoiqu´il en soit, l´algo reste glouton. (il ne revient jamais en arriere)

-->

1. ifdef _DEBUG

if (i<0 || j<0 || i>=x || j>=y)
while(0);

1. endif

pourquoi pas un assert (i<0...) ?

En fait, les "while(0);" sont des signatures pour moi : c´est une instruction qui ne fait rien du tout. Par contre, on peut mettre un breakpoint dessus en debug : comme ça, je passe dans le break en debug
J´ai pas mis assert pour éviter une messagebox mais bon !

--> Je l´ai recompilé avec -O3 -march=nocona et là, en moins de 3 minutes il avait terminé.
ça c´est un truc qui m´échappe !
Si quelqu´un, en lisant mon algo plus haut, sait me dire quelle optimisations ont du etre faites avec cette option de compilation, je suis preneur.
Si ça se trouve, j´ai fait une opération idiote qui fait perdre beaucoup de temps, et que le -O3 "corrige"

--> guyver2 > pour ton graph, tu t´es déchiré, lol !!

Petite mise a jour !
Un compteur de progression pendant la génération.
Et puis j´écris maintenant des BMP monochromes, et 16 couleurs pour que ce soit + compact !

Meme lien.

"Si quelqu´un, en lisant mon algo plus haut, sait me dire quelle optimisations ont du etre faites avec cette option de compilation, je suis preneur."

super facile: STL POWAH!!
A partir de -O2, le compilateur inline les appels de fonctions quand elles sont petite!

On ne se rends pas compte a quel point -O3 est intelligent. Mais d´ailleurs dès fois, il est tellement intéligent qu´il est plus lent que -O2. Ils essaye trop d´optimiser la localité des tableaux et si tu as plusieurs degré d´indirection. Il se foire completement.

Ah. aussi. Quand tu fais ton voisinage. Une case n´a pas 6 voisins comme en 3D mais 4 comme en 2D. Un bon tiers de perf a gagner...

Ah Sinon pour ton fill. On ne fait pas ca en théorie des graphes. On ne fait les calculs que quand on en a besoin.
On a des représentants de composante connexe qui est un noeud. Chaque noeud a un label "mon chef c´est numéro machine".
Mais peut etre que le chef a un chef alors tu récurse jusqu´a trouver le VRAI chef: celui qui pointe sur lui meme.

Bien sur je penses que quand tu accède au chef de machin il faut mettre la chaine entre lui et le chef a jour.

Je penses que dnas le pire des cas tu fais autant de mise a jour avec cette technique. Mais je penses que tu en fais moins en moyenne.

"Si il y a 2 voisins a zones différentes, ça veut dire que le mur que je casse va rassembler 2 zones. "
C´est bien ce que je me disais, tu construis un arbre et pas un graphe! C´est peut etre plus marrant avec des cycles...

J´ai enlevé les 6, remplacé par des 4
Comme je le disais plus haut, j´ai repris mon code de génération de mon "Klostro Laby", en le passant en 2D. Donc les 6 restants étaient des oublis

Sinon, en effet, mon laby est un arbre
Y´a qu´une route qui mene a l´arrivée.
Je pourrais facilement faire une rustine qui, une fois la génération finie, casse N murs en plus : ainsi, possibilité de créer des boucles.
Avec N a déterminer, ce ne serait pas trop dur a faire.

Sous Visual C++, j´ai pas remarqué de différence flagrante entre -O2 et -O3.
Peut etre que VC6.0 vieillit un peu aussi