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

**Mindiell** · 09/05/2008, 15h42

Envoyé par nicodn02

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 ...

Bah moi je te dirais bien de partir directement vers la zone de sortie, et si tu rencontres un mur (une tour), tu le contournes, puis tu reprends ton chemin.

Ce qui m'étonne c'est que ta map ne correspond pas du tout à un tableau. Qu'as-tu déjà fait ?

**acx01b** · 09/05/2008, 19h25

salut j'avais fait un dijkstra dans un tableau (en 4-connexité):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void calc_chemin (Int i1, Int j1, Int i2, Int j2, Int v) {
    // si on est en dehors du tableau
    if (i1 == 0 || (i1 == maxi-1) || j1 == 0 || j1 == maxj-1) return ;
    // on met en (i1,j1) le poids v
    _matrice[j1][i1] = v;    
    v++; // on incrémente directement le poids
    if (i1 == i2 && j1 == j2) return ; // on est arrivé ! départ = arrivée
    // si le poids déja dans la case d'à côté est plus grand que le poids avec lequel on va y arriver, alors on y va
    if (v < _matrice[j1+1][i1] || _matrice[j1+1][i1] == 0) 
        calc_chemin (i1, j1+1, i2, j2, v);
    if (v < _matrice[j1-1][i1] || _matrice[j1-1][i1] == 0)
        calc_chemin (i1, j1-1, i2, j2, v);
    if (v < _matrice[j1][i1+1] || _matrice[j1][i1+1] == 0)
        calc_chemin (i1+1, j1, i2, j2, v);
    if (v < _matrice[j1][i1-1] || _matrice[j1][i1-1] == 0)
        calc_chemin (i1-1, j1, i2, j2, v);
}
 
/* on initialise à +infini toutes les cases vides du labyrinthe
on met -1 pour les murs 
puis on appelle dijkstra
*/
calc_chemin (xdepart,ydepart,xarrivee,yarrivee, 1);

**nicodn02** · 09/05/2008, 20h33

ba en fait .. pour le calcul du chemin:
je pars d'une des zones d'entrées .. et je trouve un chemin (le plus court si possible) jsuqu'à une des zones de sorties, en évitant les murs
Autrement dit, sur la map :
_lieux de départ
_murs
_lieux d'arrivée

**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