GENERATION ET RECHERCHE DE SORTIE D'UN LABYRINTHE
defis91
Messages postés
65
Date d'inscription
samedi 29 octobre 2005
Statut
Membre
Dernière intervention
8 août 2011
-
5 juin 2010 à 15:05
timmalos Messages postés 7 Date d'inscription mercredi 28 septembre 2005 Statut Membre Dernière intervention 7 août 2011 - 14 juin 2010 à 19:34
timmalos Messages postés 7 Date d'inscription mercredi 28 septembre 2005 Statut Membre Dernière intervention 7 août 2011 - 14 juin 2010 à 19:34
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/51844-generation-et-recherche-de-sortie-d-un-labyrinthe
https://codes-sources.commentcamarche.net/source/51844-generation-et-recherche-de-sortie-d-un-labyrinthe
14 juin 2010 à 19:34
Mais pour l'instant je reste sous Autoit qui reste beaucoup plus simple tout en offrant des possibilités infinies (Labyrinthe en Autoit ici si vous voulez voir à quoi ca ressemble http://www.siteduzero.com/concours-657-595-laby-etages.html)
La fonction de generation du labyrinthe a été adaptée directement à partir de ce programme.
8 juin 2010 à 00:33
c'est un programme fait en pascal avec FreePascal.
Pour pouvoir le compiler sous Delphi, il faudra eventuellement le transformer: d'oú ma proposition ci-dessus.
T'inquiète, je travaille dessus pour montrer à Timmalos à quoi ca pourrait ressembler!
7 juin 2010 à 20:22
Si tu es sous Windows et que tu cherches juste a te faire une idée tu peux utiliser le lien que j'ai mis dans la presentation (http://malossane.fr/usb-file-474.html)
Il contient un exécutable certifié sans virus de mon coté, et le site de dépôt m'appartient donc pas de soucis ;), qui peut te permettre de voir à quoi ressemble le programme.
7 juin 2010 à 19:53
Chuis bête ou flemmard ?
Comment compiler tout ça sous Delphi 7 perso ?
6 juin 2010 à 22:39
J'essaierai de continuer ce programme après mes partiels, puisque vous y tenez tant !
6 juin 2010 à 21:21
je pense que l'organisation de ton code(lisibilité du commentaire et du code) permettra une bonne compréhension de tous et motiveras aussi les consultants à mieux scruter ton idée sans se "fatigué".
sinon Bravo!!
NB: ce serrais encore meilleur si tu élargissais ton projet en permettant à un utilisateur de trouver(avec les flèches de directions) la sortie.
PROPOSITION:
1) permettre de créer un labyrinthe de dimmension XY plutôt que de limiter;
2) Ajout d'un timer pour relever le record de résolution (et pouvoir sauvegarder si possible);
3)Permettre a l'utilisateur de trouver la sortie avec les touches fléchées;
Je sais que c'est pas le but, mais juste un complement!!
Et avec Delphi (par exemple), ce serait nettement intéressant (utilisation de Canvas).
je noterais un 7/10
6 juin 2010 à 15:56
@cirec
Passons sur la majuscule des Begin (en effet ce n'est pas un nom propre !)
Merci pour les liens sur la normalisation.
mais quand je lis ceci :
for I := 0 to 10 do begin // Incorrect, begin on same line as for
for I := 0 to 10 do // Correct, begin appears on a separate line
begin
..je n'accepte pas cette norme.
Ce qui m'importe c'est la portée du "for", et mon "end" sera indenté sur ce "for" ce qui ferme la boucle sans ambiguïté.
Dans mon esprit, c'est un "do-begin" en un seul mot. idem pour "then-begin"
Sinon on se retrouve avec des blocs bancales qui s'ils font plus d'une page demandent de l'attention pour voir leur portée.
Amicalement
Dom
6 juin 2010 à 14:49
Merci pour tes explications.
Si jamais on te reprochait l'absence de récursivité, tu pourras toujours répondre que la récursivité est l'ennemi de l'optimisation.
Bien que parfois très utile dans un raisonnement mathématique, je trouve qu'en programmation la récursivité ne sert qu'à ennoblir le code et ne devrait jamais être utilisée, surtout dans ce type de programme où les problèmes de temps de calcul sont cruciaux.
En effet, la dérécursification des procédures récursives aide grandement à gagner de la vitesse.
Exemple de Florenth, la fonction de Fibonacci :
function Fibo(X: Integer): Integer;
begin
if (X 0) or (X 1) then
Result := 1
else
Result := Fibo(X - 1) + Fibo(X - 2);
end;
Elle s'optimise largement ainsi :
function Fibo2(X: Integer): Integer;
var
I: Integer;
Pred, PredPred: Integer;
begin
Pred := 1;
PredPred := 1;
for I := 2 to X do
begin
Result := Pred + PredPred;
PredPred := Pred;
Pred := Result;
end;
end;
Cette dernière fonction est infiniment plus rapide que l'autre. (pour calculer le 40 ème terme, il lui faut 0ms contre 400ms pour la version récursive).
Donc, en particulier, fuir comme la peste les fonctions de tri rapides récursives !
J'ai toujours été étonné de trouver majoritairement des QuickSort récursives sur Internet. C'est un non-sens.
QuickSort sans récursivité très bien commenté et expliqué, pour comparer :
http://delphi.developpez.com/sources/?page=sec_math_algo#JFS_Quicksort
@Cirec
Il m'arrive souvent d'imprimer des parties de mon code pour pouvoir y travailler quand je suis en déplacement. Je trouve que les 'begin' à la ligne n'apportent rien en lisibilité et allongent inutilement les listings dans ce cas.
Mais, en général, je suis pour un maximum de normalisation.
D'ailleurs, il serait souhaitable que désormais tous les programmeurs dans le monde commentent leur code en langue française. La langue des Droits de l'Homme. :p
6 juin 2010 à 13:38
"Je n'ai pas encore analysé ton programme, mais je voudrais en profiter pour lancer un grand mouvement de protestation.
"Non au saut à la ligne avant les begin !""
Pour information:
il y a des conventions pour l'écriture de code. voir le lien ci-dessous:
http://www.econos.de/delphi/cs.html
Ce ne sont pas des préférences personnelle.
Si vous trouvez que le code en est plus lisible .. ce n'est qu'une impression (c'est un tout petit bout de code) j'ai eu à un moment la même impression que vous et je l'ai appliqué .... mais je suis très vite revenu à la norme.
En effet sur un code plus consistent on perd la faculté de repérer les débuts et fins de bloc d'un coup d'oeil ... ils ne sont plus alignés voir même en dehors de vue.
http://www.econos.de/delphi/cs.html#GeneralRules_BeginEnd
Petite précision encore: tous les mots réservés (ceux qui sont en gras tel que: begin end string const ...) doivent être en minuscule :
Begin // incorrect
begin // correct
String // incorrect
string // correct
il suffit de regarder le code du source ... "begin" est reconnu par le colorateur syntaxique et mis en gras/bleu alors que "Begin" plus loin dans le code ne l'est pas.
@++
6 juin 2010 à 09:14
Si vous voulez, à la base notre problème devait s'effectuer sur des labyrinthes de 10x10 maximum, donc A* était amplement suffisant pour trouver la sortie la plus courte, et je dois aussi avouer que devant faire ce programme en 6 jours, je n'ai pas eu enormement de temps pour coder et après quelques echecs avec Djikstra j'ai changé de direction.
Si vous voulez, l'algorithme, bien que codé itérativement (plus facile pour moi, mais je pense moins comprehensible pour ceux qui lisent que si je l'avais fait recursivement) vérifie à chaque étape :
1: Le nombre de cases ou il peut aller autour de lui.
A chaque fois qu'il va sur une case, il change cette dernière avec un '-' pour se dire : J'y suis déja allé.
Donc si il y a une possibilité, il avance, change les nouvelles valeurs de x et y pour le prochain tour, et c'est tout ;)
Si il y a 2 ou 3 possibilités, il choisit un chemin grace à une fonction heuristique très simple.
Si il y a 0 possibiltiés (cul de sac), il retourne au dernier noeud, part dans un autre coté (si la fonction heuristique s'est plantée :) ) et si ce noeud a lui meme été entierement exploré, il revient au noeud precedant et ainsi de suite.
Ainsi il trouve obligatoirement une sortie, mais comme tu l'as soulevé, ce n'est pas forcement la plus courte dans certains cas ou le labyrinthe est construit avec 2 sorties possibles.
Voila, à la base je voulais explorer tous les chemins, additionner une valeur, pour etre sur de toujours choisir le plus court, mais ca ne s'est pas fait par manque de temps.
Cordialement,
Tim
5 juin 2010 à 23:08
« c'est le seul et unique programme que j'ai fait en pascal, et je pense que ca restera le seul »
- C'est bien dommage pour nous ( et pour toi aussi ;)
Hélas, je n'ai pas le temps de regarder de près en ce moment, mais j'aimerais savoir (si ça ne te gonfle pas trop car je regarderai de près dès que possible de toute façon) si la recherche de sortie, dérivée de l'algorithme A* et Djikstra dis-tu, donne bien LE PLUS court chemin et quel avantage avez-vous eu à utiliser aussi le A* qui n'est pas des plus fiables, bien que rapide.
Pour les begin [et non pas Begin (lol)], ce n'est que préférence personnelle. Mais je suis d'accord avec vous.
Pour les blocs de commentaires, je suis 100% d'accord avec toi quand il s'agit de commenter un bloc de code. Quant aux commentaires de bout de ligne, je préfère les réserver aux commentaires de ligne.
Tout ceci pour dire que ça vaut bien un 10/10 et un merci. :)
5 juin 2010 à 20:51
Je suis d'accord avec les Begin, ma mauvaise habitude vient du fait que c'est le seul et unique programmet que j'ai fait en pascal, et je pense que ca restera le seul et mes langages de predilections ne fonctionnent pas avec des Begin.
Par contre, je suispour les sauts de lignes avant les blocs de commentaires, ils permettent d'expliquer la procédure complète. Mais en effet il faut preferer les commentaires à chaque instruction, mais comme mon programme devait etre comprehensible pour quelqu'un qui n'a jamais programmé en Pascal, j'ai préféré commenter par bloc chaque procédure.
5 juin 2010 à 15:05
Je n'ai pas encore analysé ton programme, mais je voudrais en profiter pour lancer un grand mouvement de protestation.
"Non au saut à la ligne avant les begin !"
Regarde ton bout de code :
For i := 0 To dim_x-1 do
Begin
For j := 0 To dim_y-2 do
If (MH[i,j] = 1) Then
Begin
rendu[i*2+1,(j+1)*2+1]:= 'M';
rendu[i*2+2,(j+1)*2+1]:= 'M';
rendu[i*2+3,(j+1)*2+1]:= 'M';
End;
End;
... et celui-ci :
For i := 0 To dim_x-1 do Begin
For j := 0 To dim_y-2 do Begin
If (MH[i,j] = 1) Then Begin
for k:=1 to 3 do rendu[i*2+k,(j+1)*2+1]:= 'M';
End;
End;
End;
On y gagne en compréhension à première lecture.
On voit mieux où commence et où se termine un bloc fonctionnel.
On a plus de chance d'avoir un bloc fonctionnel complet dans la même page.
Non à la tyrannie des codes aérés !
Non au saut de ligne avant et après un commentaires !
Oui au commentaire en bout d'instruction !
Ouf ça va mieux.
Je regarde ton code...
A+
Dom