Bonjour,

Voilà, j'ai un projet de Sokoban déjà bien avancé mais je bute sur l'implémentation pour HB++ d'un algorithme en C dont j'ai les sources et les explications en clair. Mais à chaque fois que j'essaye de comprendre le fonctionnement du dit algorithme je grille la moitié des neurones qu'il me reste. :-?

L'algoritme en question consiste à trouver le meilleur chemin pour pousser une caisse sur une case vide et accessible, le chemin devant être dégagé. Il s'agit du déplacement d'une caisse et non du pousseur ; ça c'est fait. La gestion des scores est faite, l'interface et toute la partie graphique aussi.
Me manque plus que cet algorithme. Aucun autre Sokoban sur Palm, me semble-t-il, ne propose cette fonction qui rend le jeu très agréable.

Je recherche donc une personne de bonne volonté pour me donner un coup de main.
Je pense diffuser ce programme en shareware. Toutes les possibilités sont envisageables.

Voili, voilà. Si ça intéresse quelqu'un...
J'envoie des snapshot, voir la version actuelle à qui me les demandera.
Merci. Philippe.

salut,

quand tu dis le meilleur chemin, est le plus court chemin ?
si c'est le cas, l'algo a implemente est celui de djisktra qui est simple a comprendre en plus.

etant curieux, je veux bien voir les snapshot.

merci

Mais qui peut malheureusement poser quelques problèmes sur un Palm car il est assez vite gourmand en ressources. Mais cela dépend de la plate-forme visée (par exemple sur PalmOS 2, il y a vraiment très peu de mémoire dynamique) ou de la complexité maximale du problème envisagé...

Il n'ai pas question de résoudre le tableau mais de faire ceci :
1. le joueur clique sur une caisse
2. puis clique une case de destination
3. le programme cherche le chemin le plus court pour pousser la caisse sur cette case
4. si le chemin existe (et est donc dégagé et qu'il n'y a pas de caisse sur le chemin)
5. le programme pousse la boule jusqu'à la case d'arrivée.

Le plus court chemin pour emmener le "poussoir" d'une case à une autre, ça je sais faire ?
Le programme est destiné à Palm OS 5. Il est en haute définition.

Des snapshot ce soir...

Dans ce cas, il n'y a pas de problème de ressources à craindre (à moins que tu ne prévoies des tableaux gigantesques).

En revanche, en y réfléchissant, je pense que Djikstra ne répond pas au problème (si on parle d'un vrai Sokoban) : non seulement il faut que la caisse puisse arriver au point de destination, mais il faut aussi que le "pousseur" puisse la pousser dans la bonne direction pour y arriver (il y a des problèmes pour prendre les virages...).

Effectivement, je pense que c'est tout à fait faisable sur Palm.

Voilà des snapshots et le fameux algorithme en C commenté.
Mais je n'arrive pas à mettre à plat ce que fait cet algo, malgré les explications.
De plus, j'ai beaucoup de mal à lire le C...
Autant, je me débrouille pour tout ce qui est "bête" mais dès qu'un peu d'AI entre en jeu, je ne suis plus. Me manquent les bases de la programmation.
Je n'ai pas non plus envie qu'on le fasse à ma place. J'aimerai comprendre le processus.
Mais il doit me manquer une case. A un moment, je pars en vrille. :smile:

peux tu preciser quelle partir tu ne comprends pas?

par contre, pourquoi as tu besoin d'un calcul de plus court chemin alors que le depalcement par le joueur se fait de case en case (desole pour la question, je ne suis pas un chef en sokoban ) ?

Il est aussi possible de pousser en ligne droite jusqu'a la derniere case vide. Mais bon je ne comprends pas non plus le probleme, le joueur pousse normalement dans la direction qui est la sienne. Genre s'il va vers le haut la caisse ira vers le haut, s'il va vers le bas la caisse ira vers la bas, etc... Il suffirait donc de tester la case suivante pour savoir s'il peut pousser la caisse. A moins que tu puisses choisir de pousser une caisse vers n'importe quel emplacement du tableau d'un seul pointage, la c'est sur il faut bosser un peu au niveau de l'algo.

Les déplacements simples, c'est bon, j'y arrive.
Il s'agit bien de pousser une caisse d'une case à une autre, quelque soit l'endroit, pourvu qu'il soit accessible. C'est bien utile une fois que l'on a débloqué le tableau et qu'il ne reste plus qu'à ranger les caisses, ce qui est fastidieux dans les grands tableaux. Parceque pousser les caisses case après case au stylet ou avec les boutons, à la longue, c'est saoulant. :smile: