Chemin Tableau ou Graphe

**nicodn02** · 06/05/2008, 13h14

Bonjour,

J'ai une "map" en entrée sous forme d'un tableau, par exemple 20*20.
Le but étant de trouver le plus court chemin d'une zone d'entrée ( variant de une à plusieurs cases ) à une zone de sortie ( de même, variant de une a plusieurs cases ).
Sachant que je pourrais réeffectuer une recherche d'un nouveau parcours selon les modifications de la map...

J'ai réfléchis à plusieurs possibilités:
_ propagation d'un liquide :
on pour des la zone de sortie ( par exemple ) et on attribue ValeurAncienneCase+1 aux cases adjacentes (8 directions); et ainsi de suite jusqu'à trouver une case appartenant à la zone d'entrée.
On remonte cette itinéraire de la case de départ jusqu'à la sortie en faisant attention à que un déplacement en diagonal est plus coûteux qu'un en horizontale-verticale

_ transformer le tableau en graphe, effectuer une recherche de plus court chemin dessus ( pb. zone d'entrée, zone de sortie = plusieurs cases ... ) et effectué par exemple le A-Star dessus

Car après je voudrais pouvoir réeffectuer un calcul de parcours ( par exemple pour contourner un obstacle mis par l'utilisateur sur le chemin départ-arrivée )

Qu'en pensez-vous ?
Améliorations?

Merci.

**knarf87** · 07/05/2008, 10h33

J'ai une petite question qui pourrait m'aider à te répondre.
Est-ce que ton tableau peut s'apparenté à un labyrinthe dans lequel on ai plusieurs entrées et sorties?
Si c'est le cas je ne saurais que trop te conseiller de prévoir un automate avec un "champ" de vision. C'est à dire que, si tu souhaite optimiser les chemins pour aller vers chaque sorties, ton automate partira d'une entrée et regardera autour de lui sur un certain nombre de cases pour y découvrir un obstacle ou une sortie. Un système de notation des cases (par exemple si la direction ou il y a un obstacle sera moin bien noté que celle ou il n'y en a pas) te permettra d'accélérer le processus et de ne repasser que par les cases non visités.
Voili, Voilou
FX

**nicodn02** · 07/05/2008, 12h44

On pourrait oui l'apparenter à un certain labyrinthe
Sujet : Tower Defense

Map :
_ map vide
_ zone entree - zone sortie
_ murs sur la map ( zones constructibles pour les tours)

Donc en fait, c'est pas vraiment un labyrinthe .. juste qu'il y a des murs où je n'est pas le droit de passer dessus pour trouver mon chemin ...

Il peut y avoir modification du chemin ( par exemple quand il y a présence d'un amas de tours sur une zone de la map où les créatures passent ... le but serait de détecter cet amas et donc de retracer un nouveau chemin ) Sachant que refaire tout en entier un calcul d'iténaire peut être long.

Et c'est quoi cet automate?
Je ne comprends pas trop son système?

NB: implémentation en C

**Veovis** · 07/05/2008, 13h48

Pourquoi n'utilises tu pas les parcours en profondeur, ou largeur ???

**nicodn02** · 07/05/2008, 13h56

Car beaucoup de temps de recherche, sachant qu'une map peut-être très grande...

Notre prof' nous a dit de faire comme cela:
attribuer 0 a toutes zones d'entrées
chaques cases ( 8 directions et en évitant les murs ) ayant un contact avec une zone d'entrée : poids de la zone + 1
et ainsi de suite .. jusqu'a remplir le tableau
Refaire le chemin inverse en partant de la zone de sortie .. prendre le poids le plus faible et remonter sur une case poids - 1 .. jusqu'à trouver une zone d'entrée.
( algo plus ou moins similaire à une propagation d'un liquide sur la map )

Mais ce que je voudrais savoir est :
est-ce que avec cet algo, je peus refaire un calcul de chemin sans tout refaire ?

**Mindiell** · 07/05/2008, 14h50

Si ton algo demande de tout remplir, et que ton "labyrinthe" a changé, i lfaudra tout recalculer à priori...
Ton prof a donné un algo "bête et méchant" mais qui fonctionne.

**nicodn02** · 07/05/2008, 15h38

en effet, c'est un algo béta et méchant ... c'est pour cela que je vous demande vos avis ^^ sur le comment faire !

**knarf87** · 07/05/2008, 16h06

Pour répondre a ta question, j'ai eu un problème similaire à celui-ci à la différence près que notre "labyrinthe" était fermé et qu'il n'y avait qu'un seul point d'entrée et plusieurs sorties.

Notre automate fonctionnait sur un principe de parcours en profondeur limité. En d'autre terme on affectait un certain champs de vision à notre robot parcourant le labyrinthe. Avant de choisir une direction ce denier faisait un parcours en profondeur sur les cases qu'il était autorisé à voir en affectant un poids à chacune d'entre elle lors de la remonté récursive.
Pour faire son choix de direction parmi les huit, il prenait celle qui, par exemple, avait une sortie dans son champs de vision ou celle qui rencontrait le moins d'obstacles ou celle qui n'avait pas encore été évaluée etc....

L'avantage de cette technique est qu'elle ne nécessité pas forcément un parcours complet de tous le labyrinthe pour trouver un chemin. Maintenant si le but est de trouver LE chemin le plus cours de chaque sortie à chaque entrée (si j'ai bien compris) la problématique n'est pas la même.

Je préconiserais un système multi-agent (un sur chaque entrée et sortie) qui effectuent un truc dans le style de ce que t'ai décris de sorte que chacun sache ou se trouve les autres pour que dés que deux d'entre eux se rencontre il puisse convenir d'un chemin pour rejoindre leur sortie et entrée respective.

Je ne sais pas si je suis bien clair

Donc si besoin hésite pas à me harceler, le we arrive et je me fait chier au boulot

FX

**nicodn02** · 07/05/2008, 16h09

Et tu faisais comment?

**acx01b** · 07/05/2008, 19h03

salut ton algo nicodn02 c'est dijkstra

D 1 2 3
1 X 7 X
2 X 6 X
3 4 5 X

devient:

D X 8 9
1 X 7 X
2 X 6 X
3 4 5 X

en rajoutant un mur (on a modifié les valeurs que sur 3 cases, on n'a pas tout recalculé)

je pense que pour un labyrinthe pas trop long c'est comme ça qu'il faut faire, pour ne recalculer qu'une partie du dijkstra (de manière récursive toujours) à chaque fois qu'un obstacle est ajouté
si tu vois le labyrinthe comme un graphe alors le poids des arrêtes n'est pas forcément 1, tu peux mettre le poids que tu veux (4.66 pour 10 monstres sur une case, 1.33 pour 5 monstres sur une même case...)

**nicodn02** · 07/05/2008, 19h15

Mais cela me force à passer mon tableau [][] en graphe pour faire l'algo de dijskra dessus .. non?
A* ne serait-il pas mieux? Car je sais que ce dernier est beaucoup utilisé pour les jeux vidéo

**acx01b** · 07/05/2008, 19h18

avec A* tu ne pourras pas te resservir des calculs déja fait

non dijkstra s'adapte très bien à un [][], mais il faut que tu prévois une astuce si le poids n'est pas forcément de 1 (si avancer en diagonale fait 1.414 par exemple, ou s'il y a des cases avec des objets qui augmentent ou diminuent le poids)

dans un jeu vidéo j'utiliserais plutôt dijkstra sur un graphe simplifié de la map, avec des heuristiques pour supprimer des parties du graphe, de toute façon avec A* il doit falloir faire le même genre de trucs

**nicodn02** · 07/05/2008, 19h35

En effet..
Déplacement horizontale verticale.. poids = 1
Déplacement diagonal.. poids = racine(2) = 1.4

Comment faire?

**acx01b** · 07/05/2008, 19h45

tu as 2 tableaux, un avec tes murs, l'autre avec tes poids (flottants) d'abord tous à 0

tu fais dijkstra en 8 connexité:

si vers horizontale ou verticale alors poids + 1
si vers diagonale alors poids + 1.4

tu repasses par une case si le poids que tu y as trouvé est inférieur à celui qui t'avais amené auparavant donc tu initialies tous les poids à +inf sauf le départ = 0

dijkstra c'est juste basé sur
si A->B->C plus court A->D->C alors on conserve A->B->C et le poids qui mène à C est: poids (AB) + poids(BC)
c'est la méthode "naïve" pour trouver son chemin

**nicodn02** · 07/05/2008, 20h03

Ok je vois !
Est-il assez rapide pour des map assez grande ?

Et concernant un recalcul ? ( c'est juste pour info pour le moment .. non prévu )

**Alikendarfen** · 07/05/2008, 20h28

Une possibilité (si la map est grande et si ça ressemble plus à un extérieur qu'à un labyrinthe) est la suivante :

Considérer une droite D de l'entrée à la sortie.

Parcourir la droite depuis l'entrée.

Si un obstacle, le contourner, à gauche et à droite par rapport D.

Depuis les points trouvés (à gauche et à droite) tracer de nouveau une droite vers la sortie (donc deux droites). Les points trouvés sont ceux qui sont à gauche et à droite, par parcours inverse, non déjà traversés par D.

Puis recommencer en prenant au final la meilleure des deux droites (récursion).

(Si c'est vraiment un labyrinthe, ce n'est pas le plus efficace).

**nicodn02** · 07/05/2008, 22h31

mais jpense que je vais rester sur dijshkra ou bien A*
mais c'était pour le comment faire .. comme commencait acx01b

**benDelphic** · 08/05/2008, 06h39

salut
moi je trouve que le graphe et la recherche de plus court chemin est plus adaptée ... pas besoin d'aller voir des metaheuristiques comme le A star , et pour le problème que tu soulève ( multi sources multi puits ) est un problème classique dans la theorie des graphe il suffit d'ajouter un sommet fictif ( super source ) et le relier avec toutes les entrees de distance nulle . ainsi de meme pour les sorties ( un sommet relié a toutes les sortie de distance nulle )... l algorithme dikjstra résoudra ainsi le problème ...

edit je vois que tu te soucis du calcul dans ce cas la utilise l algorithme de ford car il es t dynamique donc toute modification entraine juste une réactualisation a partir du sommet changé ...

**nicodn02** · 08/05/2008, 09h10

Ce dernier est un algo que je ne connais pas
Mais moi je voudrais eviter de perdre du temps à transformer mon tableau en graphe.. surtout si le tableau est de grande taille
Et puis pour l'instant, c'est juste un algo me permettant dans un 1er temps de calculer le plus court chemin..
Suivant mon avancement dans le projet.. et si j'ai le temps.. je metterais en place une AI qui changerait de chemin selon la position des tours sur le niveau..