Bonne idée de défi, mais donne moi UNE seule bonne raison de le faire en PHP et pas en C ?

bah tu peux le faire en C mais seuls les scripts en PHP seront pris en compte et noté.

Plus sérieusement, il n'y a aucune raison de le faire en PHP plutot qu'en C, mais et puis ? Des codeurs PHP organisent des défis, et c'est cool. Si les codeurs C du forum n'en font pas on n'y peut rien

Une bonne raison ?

C'est dans la rubrique PHP

Ok, je sors []

Strucky -> pas mal chez moi le temps d'execution est de 0.06185507774353 sec

Sinon donne nous une bonne raison de le faire en C et pas en php Webanix

bon courage aux participants

++

Oui, 0.06 pour un 10*10, mais pour un 40*40, c'est un peu plus long

Mais en fait le temps de génération dans mon script est en rapport avec le nombre de case du départ vers l'arrivée du labyrinthe, plus le chemin est court, plus ça va vite.

Citation : Cdams

Alors comment peut-on créer une structure d'arbre avec des tableaux ? Je ne vois pas trop comment on peut faire ça ?

Autant créer une structure de Pile, c'est facile, mais un arbre, je ne vois pas trop

En fait, j'étais comme toi au départ, mais en ayant bien étudié le problème sur papier, il s'avère que la solution est extrêmement simple

Ca y'est j'ai finis. Et il est facile de modifier la taille des case, le nombre de case en largeur et en hauteur dans le script, j'ai mis des variables. Je les metterais peut-être par des GET si y'en a qui veulent faire des teste dessus.

En attendant, voici une grille résolvable généré aléatoirement :



Pour info, j'utilise l'idée que selon moi (dans ce cas de figure seulement parcompte) , si on garde la main droite sur le mur le temps que l'on avance, on finira toujours par passer par l'arrivé. Sinon, on reviendra au point de départ à un moment ou à un autre, dans ce cas, on regénère un grille jusqu'a ce que l'on en trouve qui soit résolvable.

Sinon, au niveau des performances, je n'ai pas trouver d'autre moyen de générer des labyrinthe résolvable que de les tester. D'où la lenteur lorsque la grille à générer est trop grande, surtout que j'ai l'impression qu'il est plus rare de tomber sur une grille résolvable lorsque celle-ci est grande. (A vérifier)

Si quelqu'un à trouver une autre méthode ca m'intérresserait.

Et une méthode pour trouver le plus cours chemin aussi (sans tout tester).
D'ailleur, comment font les personnage de Age of Empires pour trouver le plus court chemin ?

Personellement avec mon algorithme de résolution, je suis limité quant à la taille de ma grille...

Je ne peux pas faire plus de 44*44 case.

Et vous, vous pouvez résoudre les grilles de n'importe quelle taille, ou vous connaissez aussi des limites ?

Citation : Cdams

Et vous, vous pouvez résoudre les grilles de n'importe quelle taille, ou vous connaissez aussi des limites ?

Pour moi la seule limite c'est la taille de la RAM xD

bah PHP ne me sort pas d'erreur... Il ne fait rien, je ne comprends pas pourquoi

Récursivité ?

Davidlouiz, tu as des pièces fermées dans ton labyrinthe

Ouais, j'ai des appels récursifs.

Tu penses que c'est à cause de ça que mon script "s'arrête" ?

Je pense que oui, car j'ai eu ce problème en passant par une génération par une fonction récursive, lors d'une 1ère tentative.

D'après le texte du défi, les codes seront testés sur des grilles 10*10 et 40*40, donc a priori, pas la peine de se prendre la tête avec ça

Enfin j'espère que c'est ça :-)

Pour ce qui est de la résolution, j'ai trouvé un trus pour prendre des chemins plus cours.
Là où je bloc encore c'est sur l'estétisme du labyrinthe. Quelqu'un e une idée ?

Voilà le résultat sur Free :
http://cameronfrance.free.fr/Labyrinthe/fct_recu.php

Citation : winzou

Si les codeurs C du forum n'en font pas on n'y peut rien

Il y a un défi C en cours. Faut suivre

Citation : Cdams

Alors comment peut-on créer une structure d'arbre avec des tableaux ? Je ne vois pas trop comment on peut faire ça ?

Pour avoir tenté d'implémenter ça dans ma version delta, je peux te dire que c'est d'une lourdeur monstre!

En fait, le problème est qu'il n'existe pas de structure en php. La clarté fournit par une structure est absente une fois que tu as crées une pseudo structure PHP que tu mets dans un tableau (multidimentionnel) ou dans une class.

D'ailleurs, je pense que ce qui manque le plus à PHP, c'est la notion d'adressage car faire des listes chainés sur ce défi serait le top.

pour trouver le chemin le plus court, comme le font les persos (joués par le CPU) des jeux vidéos, il faut utiliser la méthode A* (prononcez "A étoile" ou "A star").

http://www.vieartificielle.com/index2.php?action=article&id=161

Voilà deux versions :

HTML :
http://cameronfrance.free.fr/Labyrinthe/fct_recu.php?HTML

GD :
http://cameronfrance.free.fr/Labyrinthe/fct_recu.php

Tu as des allées beaucoup trop longues dans tes labyrinthes, tu devrais essayer d'améliorer ce point

Voui, c'est le principe de mon algorithme qui veut ça

Mais il est rapide
Après faut faire ds choix...

La rapidité n'est pas le critère majeur du défi, à moins que je n'ai pas tout saisi, enfin c'est toi qui voit

Si le critère est le point le plus important alors je peux me vanter avec mes laby rapide mais peu aléatoire
Avec cette méthode (et une méthode de résolution particulière ), j'obtiens :

Labyrinthe de 100x100
Génération + Résolution : 58 ms
Affichage (GD) : 61 ms

C'est pas mal


Mais on notera que le chemin est systèmatiquement l'équivalent d'une diagonale, et que les côtés externes (bas et droite) n'ont pas de trait sur leur dernière ligne pour pouvoir avoir un labyrinthe résolvable !
Et enfin le labyrinthe n'est pas si aléatoire que ça ... mais il est simple à générer / analyser (suffit de voir les temps pour s'en rendre compte )

En gros ma rapidité à un désavantage : c'est pas un super labyrinthe
mais bon, j'ai fais cette méthode dans le seul but d'avoir un script ultra rapide, pas de faire de superbes labyrinthes !


EDIT : je vais changer de stratégie et essayer de faire un labyrinthe parfait tout en optimisant le temps d'exécution parce que le coup du labyrinthe peu aléatoire devient du raffistolage pour combler les côté
Et puis c'est plus amusant de relever le defis de façon plus "honnête"

Dis voir jérémie, t'aurais pas oublié des +1 quelque part dans ton script, parce que la dernière ligne et la dernière colonne sont vides...

Citation : Davidlouiz

Ca y'est j'ai finis. Et il est facile de modifier la taille des case, le nombre de case en largeur et en hauteur dans le script, j'ai mis des variables. Je les metterais peut-être par des GET si y'en a qui veulent faire des teste dessus.

En attendant, voici une grille résolvable généré aléatoirement :



Pour info, j'utilise l'idée que selon moi (dans ce cas de figure seulement parcompte) , si on garde la main droite sur le mur le temps que l'on avance, on finira toujours par passer par l'arrivé. Sinon, on reviendra au point de départ à un moment ou à un autre, dans ce cas, on regénère un grille jusqu'a ce que l'on en trouve qui soit résolvable.

Sinon, au niveau des performances, je n'ai pas trouver d'autre moyen de générer des labyrinthe résolvable que de les tester. D'où la lenteur lorsque la grille à générer est trop grande, surtout que j'ai l'impression qu'il est plus rare de tomber sur une grille résolvable lorsque celle-ci est grande. (A vérifier)

Si quelqu'un à trouver une autre méthode ca m'intérresserait.

Et une méthode pour trouver le plus cours chemin aussi (sans tout tester).
D'ailleur, comment font les personnage de Age of Empires pour trouver le plus court chemin ?

Pour voir si une grille est résolvable il faut attribuer à chaque case un id unique, si l'on coupe une liaison entre deux case on remplace l'id de la deuxième case par celui de la première.
(on fait ca avec toute les cases qui ont le meme id que la deuxième) si le départ à le même id que la dernière, c'est résolvable.

Citation : savageman

Dis voir jérémie, t'aurais pas oublié des +1 quelque part dans ton script, parce que la dernière ligne et la dernière colonne sont vides...

Non non, j'ai pas oublié, c'est fait exprès
Si je remplis les dernières lignes je m'expose à une grille non résolvable
Mais comme je l'ai dit (tu n'as pas lu tout mon post !) cette méthode ne produit pas de labyrinthe parfait!

Quelqu'un aurait-il une classe pour les gifs annimés ?

oui
google est ton ami

http://www.phpclasses.org/browse/package/3163.html

Il faut s'inscrire.

J'ai essayé avec un 40*40 et le temps de génération est énorme
Un peu normal, puisque ça tourne entre 300 et 500 images à créer.

le gif c'est long à générer
en plus cette classe est pas super rapide ... elle est bourrée de trucs inutiles

Ben donnes en une autre