Bonjour et merci de vous interesser a mon probleme .
Voila je compte avec l'aides de plusieurs autres patenaire developper un jeu de strategie en langage java .. menfin bref ..
Dans ce jeu il y aura un carte ( genre carte Heroes ) et des unités ( genre Heroes )  tout ca pour faire deplacer des unités sur la carte ( genre Heroes ) .. peut etre que je devrais acheter heroes ??
Bref j'aimerais pouvoir faire un algorithme permettant de trouver le chemin le plus court en 2 points de la carte ( chaque case a un coefficient de difficulté ) .. mais pour trouver un algo je seche et mes recherche sur le net ne sont pas tres ( pas du tout ) concluante .
J'ai dans mes recherches eu la presentations des algo de Dijkstra .. suis sur la bonne voie ?  
connaissez vous un moteur open source qui uilise ce type de calcul en java ?
 
Merci de l'aide que vous pourrez me fournir ...  
sur ce je vous souhate de joyeuses fetes ..

Dijkstra te donne un des chemins le plus court, pas LE plus court, mais
ca marche bien. Ca utilise des graphes.
 
En tappant "Dijkstra java" sur google la premiere page c'est :
 
http://www.cs.rpi.edu/~puninj/XMLJ [...] kstra.java

Fait une recherche à "heuristique" pour trouver des algos "simples".
 
Les "méta heuristiques" permettront d'affiner les résultats donnés par les heuristiques mais les solutions données ne sont jamais certifiées comme étant les plus courtes si ton problème possède un facteur n assez elevé.
J'ai sur mon dd un fichier excel (en VBA) qui permet d'effectuer un "plus proche voisin" (heuristique) ainsi qu'une descente stochastique et un recuit simulé (metaheuristique).  
Ce fichier permet de calculer des tournées de véhicule, c'est à dire calculer la distance la plus courte en répartissant au mieux le volume des colis à charger.  
 
Si tu es interessé, viens en MP, tu n'aura qu'à t'aider de la partie optimisation de la distance et laisser de côté le problème de volume.

en général, on fait plutôt du A* ou un de ses dérivés, pour les pathfinders, non ?
 
Edit : enfin, ca doit être compris dans la réponse de jeoff, vu que ca se sert d'une heuristique pour le parcours

vos reponses ont l'air tres interessante merci pour elle ...
"http://www.cs.rpi.edu/~puninj/XMLJ [...] kstra.java"
ce lien est mort chez moi a l'heure ou je parle ...
si tu as pu effectuer une rcherche de chemin le plus court jeoff je serais interessé par ton code vba ... jeoff.
J'aimerais savoir ce qu'est A*
 
Mais les algorithmes que j'ai pu voir s'appliquais sur de graph avec au plus 10 "cases" et seulement 2 chemins possibles par case ... et la je suis dans le cas d'un graph a plusieurs centaines de cases ( la carte est immense )
et chaque case offre 6 (ou 5 si on enleve la case source ) possiblités ( map basé sur des hexagones ).
voila je vais continuer mes recherches .. mais ce probleme necessite un niveau assez elevé de mathématique ?

Tiens, le problème est intéressant.
 
Bon, je n'y connais rien du tout, raison pour laquelle je me permets d'intervenir : est-ce que dans ton cas ce ne serait pas plus simple de découper le chemin en n noeuds, des points de passage ?
Tu disposes les noeuds en utilisant une version grossière de l'algorithme, puis entre chaque noeud tu affines ?

le A* est effectivement une bonne solution, tiens ya un tut sympa là
 
EDIT : un autre article, en français cette fois : ici

Il faut aussi que tu puisses modéliser ton problème.
 
Il y a deux grandes manières de la faire :
- faire un distancier à la main  
- fournir les coordonnées de chaque point de passage (distancier alors généré automatiquement)
 
Mais tu introduis une notion supplémentaire il me semble, le "coût" du chemin. Et dans ce cas là, soit tu fait le distancier à la main, soit tu ajoute une colonne supplémentaire à côté des tes coordonées et lors de la génération du distancier, tu appliquera ce facteur de difficulté au résultat. (je sais pas si je suis bien clair)
 
Comment calcule-tu la distance entre deux cases ? car tu mentionnes un coefficient de difficulté.
Pour le trouver il faut faire un calcul entre la valeur de la case de départ et celle d'arrivée ?
 
P.S.  
distancier : c'est un tableau à deux dimensions dans lequel tu indiques le "coût" du chemin
Par exemple pour des villes pour lesquelles l'aller n'est aps forcèment aussi long que le retour et invèrsement (distance au hasard):
                Paris    Bordeaux   Caen
Paris            0           936km   532km
Bordeaux     890km       0         472km
Caen           489km     511km      0
 
EDIT : on peux aussi modéliser ce genre de problème à la main.
un cercle représente un point de passage, un arc entre deux cercles représente un chemin possible.
Chaque arc porte un chiffre, le coût du chemin (en km par ex) mais plus il y a de places et de possibilités et plus c'est long à réaliser et illisible.

dans le cas mentionné, qui est un cas classique pour du jeu vidéo, c'est un coût de passage par un noeud et non pas un coût de passage par une branche ... mais je me permets d'insister sur le A*, qui est très adapté pour ce genre de problématique et est facile à implémenter

http://www-cs-students.stanford.ed [...] html#paths
 
Très bien fait, avec tout plein d'images.

bonsoir jeoff;
 
j'ai lu sur votre commentaire que vous aves un fichier excel (en VBA) qui permet d'effectuer un "plus proche voisin" (heuristique) ainsi qu'une descente stochastique et un recuit simulé (metaheuristique). est ce que vous pouvez le partager ici car je prépare un projet sur ce sujet .
merci d'avance