Déterminer un chemin sur un plan

Bonjour a tous,

Je met ma question ici car l'interface se fera certainement sur un borne utilisant AIR, mais je cherche comment faire de manière très ouverte...

Partant du plan des locaux, pouvant être assez complexe, avec étages, donc ascenseurs et escaliers, parfois plusieurs bâtiments, parkings, existe t'il un outils permettant de trouver les chemins possible pour se rendre d'un lieu a l'autre, et de proposer le bon chemin aux visiteurs.

Naturellement les lieux sont susceptibles de changements réguliers (les services se déplacent) et tracer tous les cas possibles me semble bien fastidieux. :calim2:

Des idées ?

Merci d'avance !
Jacques

Ta problématique est algorithmique, et aurait donc plutôt sa place dans le forum dédié : http://www.developpez.net/forums/f60...s/algorithmes/.

Tu auras besoin d'un algorithme de path-finding, qui se base généralement (exclusivement?) sur des graphes;
c'est très standard, et notamment très utilisé dans les jeux pour gérer le déplacement des PNJs.

Citation:

---

Envoyé par seriousme

Tu auras besoin d'un algorithme de path-finding

---

Merci, c'est la piste que je n'avais pas !...

Bon, je vais creuser dans cette direction, il y a effectivement beaucoup d'informations en ligne. J'ai bon espoir de trouver des solutions utilisant php et pouvant alimenter mon client Air.

Je reste à l'écoute !

c'est tres classique comme problématique ... le plus court chemin entre deux points ... bellman , Djikstra ,Ford... c'est pas les algorithmes qui manquent...

Oui, A*, etc

En fait je ne posait pas correctement la question dans les moteurs de recherche.

Maintenant il faut que j'étudie comment décrire l'ensemble des points, je pense qu'une grille de carrés n'est pas très utilisables sur un ensemble immobilier, par contre un arbre de lieu de croisement ou de destination me semble possible....

Les contraintes sont assez légères, surement une notion de niveau d'accès, mais a première vue pas de sens unique. Il faut que je réfléchisse aussi aux escaliers, que tout le monde ne peut pas prendre...

Ayant lu quelques algo trouver le chemin ne m'inquiète plus trop, c'est plus l'interface d'enregistrement des nœuds qui risque d'être coton !

Merci encore !

C’est très sympathique comme problème, une idée juste comme ça :
La représentation en graphe et possible, il est claire que les ascenseurs escaliers et autres moyens de transite ne changent pas, au niveau d’un étage les couloires ne changent pas aussi donc on peu supposer que les arrêtes seront les couloirs, et les sommets les éventuels emplacements de stand.
On procède de la même manière pour touts les étages, maintenant le lient entre les étages sera les différent moyen de transite (assainisseurs, escaliers, …) ceux là débouche sur un couloir théoriquement donc cela nous créera d’autres sommets.
Une fois le graphe établi, il suffit de numéroté les sommets et de donner un numéro de sommet à chaque stand, s’il y a un changement il suffira juste de faire une réaffectation des stands aux numéros des sommets.

Oui, c'est tout a fait comme ça que je le voie, les couloirs étant pondérés par leur temps de parcours, de manière à pouvoir déterminer le meilleur chemin.

Les escaliers et ascenseurs ne sont effectivement que des couloirs verticaux, avec des temps spécifiques !

La question se résumera toujours à aller d'un sommet ou d'un nœud à un autre, généralement d'un lieu d'accueil à un bureau. C'est vrai que le bâti ne change pas tous les jours, mais les cloisons peuvent bouger bien plus souvent qu'on ne le pense...

Il me faut donc une interface qui permet de situer les sommets, les nœuds et les parcours sur des plans; une base ou enregistrer tout ça, et enfin une interface d'accueil qui propose le bon parcours.

Je sens que je vais bien m'amuser ! :?

D’un point de vu purement théorique, c’est vrai que le problème peut facilement atteindre une complexité de l’ordre de nn, cela étant dans un cas concret à moins d’avoir cent étages et autant de combinaison ou plus, le plus plausible serai de les répertorier, ou bien si on peut envisager que un sommet est une cellule et que celle si ne débouche que sur un ensemble arrêtes « A », les cellules pouvant être fusionnées, ça ne serai plus vraiment contraignant.
On admettant bien évidemment comme première hypothèse qu’il faut plus de temps à faire bouger une cloison qu’a appuyer sur un bouton :?, le plus difficile sera « si c’est pas toi concepteur qui va l’utiliser, comment crée une interface facile à utiliser ».