Discussion :

[carton99]

bonjour,
je réalise un site dynamique mi Flash mi HTML sur le thème de Klotski.
voir cette page google si vous ne connaisez pas: [ame="http://www.google.fr/search?hl=fr&safe=off&client=safari&rls=en&q=klotski+game&bav=on.2,or.r_gc.r_pw.&biw=1279&bih=680&um=1&ie=UTF-8&tbm=isch&source=og&sa=N&tab=wi"]klotski game - Recherche Google[/ame]

Mon objectif et de laisser la liberté au joueur de créer leur propre puzzle et de le partager au autre.
Mon projet personnel en et à 90% j'ai donc presque terminé.


Je bloque sur la partie détermination pour savoir si un Puzzle est possible ou non.

J'ai commencé par un algorithme de résolution simple , avec un choix aléatoire des pièces puis un déplacement semi-aléatoire de ses pièce ,jusqu'à la situation final désiré.
Avec surprise cette technique fonctionne et j'arrive à résoudre un puzzle en quelque million de coup pour les puzzles les plus difficile.
Mais cette technique présente deux inconvénient elle est trop longue(surtout pour du flash) et elle ne détermine pas si le puzzle est réalisable ou non.

Ensuite j'ai essayer la même technique mais avec du backtraking , mais le résultat est décevant.

J'ai donc décidé de réaliser un vrai algorithme de résolution.
Mais je bloque . L'idée de départ que je me suis fixé était de pousser le bloc qui me gène pour déplacer un bloc choisit au bon endroit. Principe réalisé grace à la récurrence.
Sa fonctionne moyen , donc certaine situation on bloc dans des boucles infini ou un bloc ira d'une position successif et tournera en rond.
De plus Je me suis rendu compte que sa marche pas ,si jamais je doit déplacer deux blocs pour pouvoir déplacer la pièce voulut.


J'ai déjà beaucoup travaillé dessus , mais je pense qu'il me faudrait un autre point de vu pour crée l'algorithme.


Je cherche quelqu'un pour m'expliquer le principe (vu que j'ai pas trouvé seul) à utiliser pour résoudre ces type de puzzle informatiquement.

[Franck Dernoncourt]

Je ne me suis jamais penché sur l'algorithme pour résoudre ce jeu par manque de temps, voici 2 liens peut-être (ou pas) intéressants au cas où tu ne les aurais pas déjà croisés :

• http://klotskisolver.sourceforge.net/
• http://www.sciencedirect.com/science...47563202000134 (je peux t'envoyer le contenu de l'article si tu n'y as pas accès)

[carton99]

bonjour,Franck Dernoncourt
effectivement je n'ai pas accès au dossier du deuxième lien.
Par rapport au premier lien j'ai regardé les fichiers sources , et sa m'a l'air plus compliqué que je pensais .

De plus j'ai encore un peu de temps libre sa me dérange pas de réaliser moi même l'algorithme , c'est très intéressent d'un point de vu programmation je trouve.

Donc si je pourrais avoir accès au dossier sa sera pas mal , je suis pas un pro en anglais mais je devrais pouvoir me débrouiller.

[Franck Dernoncourt]

cf MP

[carton99]

bonjour,
aujourd'hui j'ai essayé un pseudo algorithme évolutionnisme pour résoudre le puzzle mais le résultat est décevant l'utilisation du cpu est énorme est le résultat dépend fortement du calcul euristique que j'ai du mal à bien calculer.
De plus j'ai pas encore fait un algo de trie efficace en AS3.


Par contre j'ai finit par trouver une technique qui marche à tous les coup il suffit de parcourir l'ensemble des possibilités . La représentation se fait sous la forme d'un arbre et chaque branche représente une possibilité de déplacement, il faut reconnaître des noeuds déjà traité afin de ne pas les retraiter. Si jamais tous les noeuds possible sont parcourut sans gagner alors le puzzle est impossible.

Avec cette technique simple je suis sur d'avoir le résultat voulut. La surprise sera de savoir si Flash supportera la charge de données et si il sera assez rapide.
Et il y aura un effort pour représenter un puzzle afin que la reconnaissantes entre deux puzzle se fasse instantanément

[carton99]

Bonjour,
j'ai bien avancer, j'ai donc essayer l'algorithme qui parcourt toute les possibilités.

Le résultat final est excellent avec le nombre de coup exact pour résoudre un puzzle ou la possibilité de savoir si un puzzle est impossible .

Par contre de temps de calcul est beaucoup trop lent il faut 1 min pour résoudre un puzzle évident de quelques pièces.La cause du au nombre de puzzle déjà traité à parcourir pour vérifier si on retraite ou non.
Je vais essayer d'optimiser du coté la.

Donc c'est pas terrible par rapport à mon projet final . Mon objectif est d'avoir une réponse pour un puzzle très dur réduit à 5-10 sec.