Discussion :

[Davidbrcz]

Bonjour a tous.
J'ai bien compris le principe du pathfinding.
Mais un problème se pose a moi.
Comment coordonner un groupe d'unité qui souhaite arriver dans une même zone pour éviter les interblocages et minimiser le temps passé sur le chemin ?

J'ai beau me creuser la tête , je ne vois pas comment faire.

Merci.

[Jedai]

Tu peux les gérer comme s'il s'agissait d'une seule unité et parallèlement agir sur leur formation pour qu'ils ne se rentrent pas dedans (sans considération de pathfinding).

--
Jedaï

[Davidbrcz]

Le seul problème étant que je ne peut pas les mettre en groupe ou en formation
( et oui je suis chiant ).

[FrancisSourd]

Tu peux éventuellement regarder du côté des algorithmes de flots car un flot peut être vus comme un ensemble de chemins simultanés et il est possible de mettre une capacité sur chaque arc (nombre maximal de chemins traversant l'arc).

[Jean-Marc.Bourguet]

Francis, il me semble qu'il y a un aspect temporel dans le probleme des congestions pour du pathfinding qui n'est pas pris en compte dans les algo de flot.

[Davidbrcz]

Francis, il me semble qu'il y a un aspect temporel dans le probleme des congestions pour du pathfinding qui n'est pas pris en compte dans les algo de flot.

Ah.
L'aspect temporel est important car durant leur trajet , les unités qui vont suivre le chemin trouvé par l'algo vont se faire canarder .
D'où le besoin de minimiser le temps passé dessue .

[FrancisSourd]

Francis, il me semble qu'il y a un aspect temporel dans le probleme des congestions pour du pathfinding qui n'est pas pris en compte dans les algo de flot.

Je n'avais pas vu l'aspect temporel du pathfinding.

En revanche, on peut toujours introduire cette aspect temporel dans les flots en développant le graphe: pour chaque nœud i, on crée des nœuds (i,1) (i,2) (i,3)... pour chaque instant.

Une réf en anglais:
http://www.math.tu-berlin.de/coga/pu...-752-2002.html

[Davidbrcz]

Imaginez que je fasse pour chaque noeud i et durant toute la durée du trajet (décomposé en une serie d'instants t ) un noeud j(i,j).
Cela revient il a refaire un graphe entier a chaque instant t ?

Si oui(je pense que c'est le cas ) mon problème est résolue du coté temporel et pas loin de l'être pour éviter les interblocages.

[PRomu@ld]

Imaginez que je fasse pour chaque noeud i et durant toute la durée du trajet (décomposé en une serie d'instants t ) un noeud j(i,j).
Cela revient il a refaire un graphe entier a chaque instant t ?

Oui, ça peut marcher comme ça, une modélisation de la bataille de la marne (problème d'approvisionnement temporel) est faite ainsi, chacun des noeud est démultiplié. Ca densifie le graphe mais si ça passe en mémoire c'est bon.

[FrancisSourd]

Tu peux regarder la figure 3 dans le lien que j'ai mis dans mon précédent message. Elle illustre bien la construction du "gros" graphe temporel.

[Davidbrcz]

J'ai regarde le PDF d ton lein précedant et j'ai rien compis
Les intégrales et autres joyeuseté mathématique , j'ai pas encore vue ca (Je suis rentré en Ts aujourd'hui )

[FrancisSourd]

A 15 ans, respect!

Laisse tombé les intégrales (enfin pour l'instant, cela sera utile pour le bac;-) Je voulais juste juste t'indiquer la figure. Si, tu peux aller d'un point i à un point j en un temps d(i,j), l'idée est simplement de relier les nœuds (i,t) à (j,t+d(i,j)).

[Davidbrcz]

Enfin 15 ans , j'ai 16 en février prochain et puis le lycée c'est pas la mort.

Si, tu peux aller d'un point i à un point j en un temps d(i,j), l'idée est simplement de relier les nœuds (i,t) à (j,t+d(i,j)).

temps d(i,j) ?
Un temps construit avec des points ?
Ca représente le temps pour aller du point i au point j ?
Je pense que oui vu ca (j,t+d(i,j)) mais je souhaite confirmation .

Merci.

Edit : ce truc va faire exploser la mémoire .

[FrancisSourd]

Je pense que oui vu ca (j,t+d(i,j)) mais je souhaite confirmation

Oui c'est bien cela.

Edit : ce truc va faire exploser la mémoire .

Effectivement, c'est le problème, comme le signalait PRomu@ld.

[Davidbrcz]

Pas keul.
Je sens que je fais faire un pathfinding tout simple par unité puis verifier si la case suivante est libre.
Si oui on y va.
Sinon on attend.