LOCODUINO
Parlons Arduino => Modélisation, Architectures logicielles et matérielles => Discussion démarrée par: Jean-Luc le mars 07, 2016, 05:58:11 pm
-
Bonjour,
Ma petite contribution à la modélisation.
Ayant travaillé sur l'approche objet pour la gestion d'un gare cachée, les articles sont en attente de publication, j'ai fait des classes pour chaque type de voie : aiguille, voie d'extrémité de la gare et voie en gare. Les classes en question sont instanciées et les objets sont connectés pour former un graphe. Une recherche de chemin est ensuite faite pour trouver une voie libre ou pour relier l'entrée à une voie ou bien une voie à la sortie. Le défaut est que le graphe est orienté ce qui fait qu'un aiguillage va connaître les voies en aval mais pas en amont. Donc partant de l'entrée, on trouve une voie en gare, idem partant de la sortie mais on ne trouve pas un chemin de l'entrée vers la sortie par exemple.
Titillé par DDEFF, j'ai généralisé l'idée à un graphe où chaque nœud (bout de voie) connaît ses voisins. Comme exemple, j'ai choisi la gare de DDEFF que j'ai re-dessinnée en PECO code 55 (gare dont on peut déduire deux choses d'ailleurs : 1) Ça va coûté un bras à DDEFF, rien qu'en appareils de voie, il y en a pour 1300€, 2) DDEFF a de la place, la gare fait 4,2m de long. Bref je suis jaloux ! ;D)
Je vous mets le lien vers le PDF : La gare de DDEFF en PDF (http://www.locoduino.org/pic/GareDenis/gareDenis.pdf)
J'ai donc défini une classe abstraite de base, Voie :
class Voie
{
private:
byte mIdentifiant;
byte mDirection;
protected:
void fixeDirection(byte dir);
public:
Voie(byte identifiant) { mIdentifiant = identifiant; mDirection = AUCUNE_DIRECTION; }
byte idVoie() { return mIdentifiant; }
byte direction() { return mDirection; }
virtual void connecteDeVoie(Voie *voie, byte connecteur) = 0;
virtual bool creeCheminVers(byte identifiant, byte dir, Voie *venantDe = NULL) = 0;
};
Une voie a : 1) un identifiant, 2) une direction. On l'instancie en lui donnant un identifiant et par défaut il n'y a pas de direction fixée. La direction est fixée plus tard lorsque le graphe est construit.
connecteDeVoie permet d'établir une connexion entre deux voies, j'explique ci-dessous. creeCheminVers permet de trouver un chemin entre deux nœuds du graphe (entre deux bout de voies) en suivant une direction.
Ensuite, j'ai 5 classes :
1) les voies de garage qui n'ont qu'un seul connecteur : SORTANT
(http://www.locoduino.org/pic/GareDenis/voiegarage.png)
2) les voies normales qui ont 2 connecteurs : ENTRANT et SORTANT
(http://www.locoduino.org/pic/GareDenis/voienormale.png)
3) les aiguillages qui ont 3 connecteurs : ENTRANT, SORTANT_DROIT et SORTANT_DEVIE
(http://www.locoduino.org/pic/GareDenis/aiguillage.png)
4) les traversées de jonction double (on peut ajouter également les simples) qui ont 4 connecteurs : ENTRANT, SORTANT, ENTRANT_BIS et SORTANT_BIS
5) les croisement qui ont également 4 connecteurs
(http://www.locoduino.org/pic/GareDenis/croisementtjd.png)
Un sens normal de parcours est également défini : de entrant vers sortant.
-
Effectivement, le réseau est impressionnant...
-
Merci Jean-Luc,
Sur le bras que ça va me coûter, c'est sûr. Je m'y suis déjà préparé psychologiquement :( :(
Tu comprends aussi pourquoi je suis particulièrement motivé pour que ce soit commandé par du tout-Arduino, très bon marché ;D
Sur la longueur, en employant des éléments Peco classiques, je vais sur les 4,20m, c'est vrai aussi. :( :(
En fait, le problème vient des 3 croisements.
Comme ils sont reliés aux TJD, si on les laisse tels quels, cela définit un écart de voie qui se répercute sur les autres écarts de voie, même sans croisements.
Il faut donc, pour raccourcir la gare, quasiment ne laisser du croisement que le croisement lui même (sans les petits bouts de droite qui l'accompagnent) et faire de même pour les TJD.
Comme je n'ai pas les 4,20 m (on s'en doutait), je pense ainsi réduire la longueur totale de la gare.
Y'a du boulot, du charcutage, mais je tiens à la caser quelque part.
A priori, j'ai une pièce de 3,42 m x 2,57 m et j'aurais bien tort de me plaindre.
Ta démarche m'intéresse au plus haut point, évidemment.
D'autant que je vais pouvoir comparer avec ma solution SGDD qui a été inventée pour cette gare. Et qui fonctionne.
Mais elle utilise une méthode vraiment ... non-conventionnelle (voir SGDD (1) et (2) )
J'ai le programme, pour les curieux.
J'appelle le sens "normal" sens "horaire", mais c'est un détail.
On peut peut-être s'éviter les zones genre "voie 0" en disant que ce n'est jamais que la partie de rails qui fait partie de l'aiquille 0 ? (quand la zone est très courte)
Bon courage !
Et merci pour le plan à l'échelle ;D ;D
-
La solution pour caser les 4m dans ta pièce est de courber la gare. Note que j'ai mis des voies de garage très généreuses :)
Concernant les voies intermédiaires, du point de vu du graphe on peut effectivement les omettre mais je pense étendre le système au delà de la détermination des itinéraires.
Je continue.
Chaque classe dispose de fonction de connexion. Ainsi une voie de garage possède une unique fonction de connexion :
void connecteAVoie(Voie &voie, byte connecteur);
qui va connecter SORTANT à la voie et au connecteur passés en argument.
Une voie normale possède 2 fonctions de connexion :
void connecteSortantAVoie(Voie &voie, byte connecteur);
void connecteEntrantAVoie(Voie &voie, byte connecteur);
qui vont connecter respectivement SORTANT et ENTRANT à la voie et au connecteur passés en argument. Si on utilise connecteSortantAVoie, une voie normale est connecté dans le sens normal (DIRECTION_AVANT) si on utilise connecteEntrantAVoie, elle est connectée dans le sens inverse (DIRECTION_ARRIERE).
Un aiguillage possède 3 fonctions de connexion :
void connecteSortantDroitAVoie(Voie &voie, byte connecteur);
void connecteSortantDevieAVoie(Voie &voie, byte connecteur);
void connecteEntrantAVoie(Voie &voie, byte connecteur);
De la même manière, si on utilise connecteSortantDroitAVoie ou connecteSortantDevieAVoie, l'aiguillage est connecté en DIRECTION_AVANT et si on utilise connecteEntrantAVoie, il est connectée en DIRECTION_ARRIERE.
Idem pour les croisement et TJD :
void connecteSortantAVoie(Voie &voie, byte connecteur);
void connecteSortantBisAVoie(Voie &voie, byte connecteur);
void connecteEntrantAVoie(Voie &voie, byte connecteur);
void connecteEntrantBisAVoie(Voie &voie, byte connecteur);
Les connexions doivent être réalisées de manière compatible. C'est à dire qu'un élément de voie ne peut pas être connecté de telle sorte qu'il soit à la fois en DIRECTION_AVANT et DIRECTION_ARRIERE. Pour cela il faut connecter en parcourant les éléments dans une direction.
Je ne traite donc pas les boucles de retournement pour l'instant.
Les objets sont instanciés simplement. Par exemple, si on prend en bas à gauche VoieLibre0, Aiguille0, Voie0 et Voie1, on a
VoieNormale voieLibre0(VOIE_LIBRE_0);
Aiguillage aiguille0(AIGUILLE_0);
VoieNormale voie0(VOIE_0);
VoieNormale voie1(VOIE_1);
Une fois instanciés les objets, on les connecte. Il faut décider d'un direction de connexion, de la gauche vers la droite dans notre cas :
voieLibre0.connecteSortantAVoie(aiguille0, ENTRANT);
aiguille0.connecteSortantDevieAVoie(voie0, ENTRANT);
aiguille0.connecteSortantDroitAVoie(voie1, ENTRANT);
Ici tous les objets sont en DIRECTION_AVANT. Mais, par exemple, en connectant de gauche à droite, l'aiguillage Aiguille3 sera en DIRECTION_ARRIERE.
On a donc une ligne par connecteur dans la gare. Pour la gare de DDEFF nous avons 110 connexions :
/*
* Connexion des voies de bas en haut et de gauche à droite
*/
voieLibre0.connecteSortantAVoie(aiguille0, ENTRANT);
aiguille0.connecteSortantDevieAVoie(voie0, ENTRANT);
aiguille0.connecteSortantDroitAVoie(voie1, ENTRANT);
voie0.connecteSortantAVoie(tjd0, ENTRANT_BIS);
voie1.connecteSortantAVoie(tjd8, ENTRANT_BIS);
voieLibre1.connecteSortantAVoie(tjd0, ENTRANT);
tjd0.connecteSortantAVoie(voie3, ENTRANT);
tjd0.connecteSortantBisAVoie(voie2, ENTRANT);
voie3.connecteSortantAVoie(tjd8, ENTRANT);
tjd8.connecteSortantAVoie(voie22, ENTRANT);
tjd8.connecteSortantBisAVoie(voie21, ENTRANT);
voie22.connecteSortantAVoie(aiguille12, SORTANT_DEVIE);
aiguille12.connecteEntrantAVoie(voieGarage2, SORTANT);
voie32.connecteSortantAVoie(aiguille12, SORTANT_DROIT);
voieLibre2.connecteSortantAVoie(tjd1, ENTRANT);
voie2.connecteSortantAVoie(tjd1, ENTRANT_BIS);
tjd1.connecteSortantAVoie(voie8, ENTRANT);
tjd1.connecteSortantBisAVoie(voie6, ENTRANT);
voie8.connecteSortantAVoie(tjd12, ENTRANT);
voie21.connecteSortantAVoie(tjd12, ENTRANT_BIS);
tjd12.connecteSortantAVoie(voie27, ENTRANT);
tjd12.connecteSortantBisAVoie(croisement2, ENTRANT_BIS);
voie27.connecteSortantAVoie(tjd15, ENTRANT_BIS);
croisement2.connecteSortantAVoie(tjd15, ENTRANT);
tjd15.connecteSortantBisAVoie(voie31, ENTRANT);
tjd15.connecteSortantAVoie(voie32, ENTRANT);
voie31.connecteSortantAVoie(aiguille11, ENTRANT);
aiguille11.connecteSortantDevieAVoie(voieGarage3, SORTANT);
aiguille11.connecteSortantDroitAVoie(voieGarage4, SORTANT);
voieLibre3.connecteSortantAVoie(tjd2, ENTRANT);
voie6.connecteSortantAVoie(tjd2, ENTRANT_BIS);
tjd2.connecteSortantAVoie(voie12, ENTRANT);
tjd2.connecteSortantBisAVoie(voie11, ENTRANT);
voie12.connecteSortantAVoie(tjd11, ENTRANT_BIS);
voie20.connecteSortantAVoie(tjd11, ENTRANT);
tjd11.connecteSortantBisAVoie(voie26, ENTRANT);
tjd11.connecteSortantAVoie(croisement2, ENTRANT);
voie26.connecteSortantAVoie(tjd14, ENTRANT);
croisement2.connecteSortantBisAVoie(tjd14, ENTRANT_BIS);
tjd14.connecteSortantAVoie(voie30, ENTRANT);
tjd14.connecteSortantBisAVoie(voie29, ENTRANT);
voie30.connecteSortantAVoie(aiguille10, ENTRANT);
aiguille10.connecteSortantDroitAVoie(voieGarage5, SORTANT);
aiguille10.connecteSortantDevieAVoie(voie34, ENTRANT);
voie34.connecteSortantAVoie(aiguille14, SORTANT_DROIT);
voie33.connecteSortantAVoie(aiguille14, SORTANT_DEVIE);
aiguille14.connecteEntrantAVoie(voieGarage6, SORTANT);
voieLibre4.connecteSortantAVoie(tjd4, ENTRANT);
voie11.connecteSortantAVoie(tjd4, ENTRANT_BIS);
tjd4.connecteSortantAVoie(voie16, ENTRANT);
tjd4.connecteSortantBisAVoie(croisement0, ENTRANT_BIS);
voie16.connecteSortantAVoie(tjd7, ENTRANT_BIS);
croisement0.connecteSortantAVoie(tjd7, ENTRANT);
tjd7.connecteSortantAVoie(voie20, ENTRANT);
tjd7.connecteSortantBisAVoie(voie19, ENTRANT);
voie19.connecteSortantAVoie(aiguille8, SORTANT_DROIT);
voie25.connecteSortantAVoie(aiguille8, SORTANT_DEVIE);
aiguille8.connecteEntrantAVoie(voie28, ENTRANT);
voie28.connecteSortantAVoie(tjd16, ENTRANT);
voie29.connecteSortantAVoie(tjd16, ENTRANT_BIS);
tjd16.connecteSortantAVoie(voie33, ENTRANT);
tjd16.connecteSortantBisAVoie(voieGarage7, SORTANT);
voieLibre5.connecteSortantAVoie(tjd3, ENTRANT_BIS);
voie10.connecteSortantAVoie(tjd3, ENTRANT);
tjd3.connecteSortantAVoie(croisement0, ENTRANT);
tjd3.connecteSortantBisAVoie(voie15, ENTRANT);
voie15.connecteSortantAVoie(tjd6, ENTRANT);
croisement0.connecteSortantBisAVoie(tjd6, ENTRANT_BIS);
tjd6.connecteSortantAVoie(voie18, ENTRANT);
tjd6.connecteSortantBisAVoie(croisement1, ENTRANT_BIS);
voie18.connecteSortantAVoie(tjd10, ENTRANT_BIS);
croisement1.connecteSortantAVoie(tjd10, ENTRANT);
tjd10.connecteSortantAVoie(voie25, ENTRANT);
tjd10.connecteSortantBisAVoie(voieGarage8, SORTANT);
voieLibre6.connecteSortantAVoie(aiguille3, SORTANT_DROIT);
voie5.connecteSortantAVoie(aiguille3, SORTANT_DEVIE);
aiguille3.connecteEntrantAVoie(aiguille4, ENTRANT);
aiguille4.connecteSortantDroitAVoie(voie9, ENTRANT);
aiguille4.connecteSortantDevieAVoie(voie10, ENTRANT);
voie9.connecteSortantAVoie(tjd5, ENTRANT_BIS);
voie14.connecteSortantAVoie(tjd5, ENTRANT);
tjd5.connecteSortantAVoie(croisement1, ENTRANT);
tjd5.connecteSortantBisAVoie(voie17, ENTRANT);
voie17.connecteSortantAVoie(tjd9, ENTRANT);
croisement1.connecteSortantBisAVoie(tjd9, ENTRANT_BIS);
tjd9.connecteSortantAVoie(voie24, ENTRANT);
tjd9.connecteSortantBisAVoie(voie23, ENTRANT);
voie24.connecteSortantAVoie(aiguille9, SORTANT_DROIT);
voie36.connecteSortantAVoie(aiguille9, SORTANT_DEVIE);
aiguille9.connecteEntrantAVoie(voieGarage9, SORTANT);
voieGarage0.connecteAVoie(aiguille1, ENTRANT);
aiguille1.connecteSortantDroitAVoie(voie5, ENTRANT);
aiguille1.connecteSortantDevieAVoie(voie4, ENTRANT);
voieGarage1.connecteAVoie(aiguille2, SORTANT_DEVIE);
voie4.connecteSortantAVoie(aiguille2, SORTANT_DROIT);
aiguille2.connecteEntrantAVoie(voie7, ENTRANT);
voie7.connecteSortantAVoie(aiguille5, ENTRANT);
aiguille5.connecteSortantDevieAVoie(voieLibre9, ENTRANT);
aiguille5.connecteSortantDroitAVoie(aiguille6, ENTRANT);
aiguille6.connecteSortantDroitAVoie(voieLibre8, ENTRANT);
aiguille6.connecteSortantDevieAVoie(aiguille7, ENTRANT);
aiguille7.connecteSortantDroitAVoie(voie14, ENTRANT);
aiguille7.connecteSortantDevieAVoie(voie13, ENTRANT);
voie13.connecteSortantAVoie(tjd13, ENTRANT);
voie23.connecteSortantAVoie(tjd13, ENTRANT_BIS);
tjd13.connecteSortantAVoie(voie36, ENTRANT);
tjd13.connecteSortantBisAVoie(voie35, ENTRANT);
voie35.connecteSortantAVoie(aiguille13, ENTRANT);
aiguille13.connecteSortantDroitAVoie(voieGarage10, SORTANT);
aiguille13.connecteSortantDevieAVoie(voieLibre7, ENTRANT);
Je vous livre le sketch complet avec la recherche de deux chemins. Je n'ai pas tout testé, je viens de le terminer. Il peut être modifié pour ajouter des requêtes de chemin. Pour l'instant l'algorithme ne cherche qu'un seul chemin. Je vais rajouter la recherche de tous les chemins possibles, le calcul de l'intersection des chemins et donc l'établissement de plusieurs chemins simultanément.
Ça tourne sur un Uno en bouffant 33% de la flash et 52% de la SRAM
-
C'est d'une limpidité de cristal ! ;D
Et tu utilises des noms en clair pour les voies, pas des bytes. C'est un progrès aussi. C'est beaucoup plus parlant ;D
Quelques bugs en lançant, mais c'est un programme non déverminé. Donc, rien de grave.
Pour mes 4 m, je ne suis pas inquiet. Il y a plein de solutions. Mais je vais essayer sans la tordre (j'aime bien les 2 x 2 diagonales bien droites).
Merci de t'en soucier. ;)
-
J'ai bien conscience que ça va "polluer" ton exposé, mais je me pose quelques questions :
#ifdef __AVR__
#include <avr/pgmspace.h>
#endif
#ifndef __AVR__
#include <iostream>
#define F(string) string
#define PROGMEMJe ne connais pas ___AVR__ ?
Le simple fait de mettre #define DEBUG au début suffit pour pouvoir afficher les essais ?
Tu mets les sorties Serial.print() entre #ifdef DEBUG .... #endif et elles sont affichées et si tu dévalides le #define DEBUG pour ne plus les afficher.
C'est sympa, ça.
J'ai adoré le :
void afficheLigne(byte nb)
{
while(nb--) {
Serial.print('-');
}
Serial.println();
}C'est tout bête, mais marrant.
Et, dans mes efforts pour comprendre les pointeurs, je choisis "venantDe". Exemple :
bool Aiguillage::creeCheminVers(byte identifiant, byte dir, Voie *venantDe)
{
if (idVoie() == identifiant) return true;
else {
if (direction() == dir) {
if (mVoieSortantDroit != NULL) {
if (mVoieSortantDroit->creeCheminVers(identifiant, dir, this)) {
afficheNomVoie(idVoie());
Serial.println(F(": droit"));
return true;
}
else if (mVoieSortantDevie != NULL) {
if (mVoieSortantDevie->creeCheminVers(identifiant, dir, this)) {
afficheNomVoie(idVoie());
Serial.println(F(": devie"));
return true;
}
else return false;
}
else return false;
}
else return false;
}
else {
if (mVoieEntrant != NULL) {
if (mVoieEntrant->creeCheminVers(identifiant, dir, this)) {
afficheNomVoie(idVoie());
if (venantDe == mVoieSortantDroit) {
Serial.println(F(": droit"));
}
else {
Serial.println(F(": devie"));
}
return true;
}
else return false;
}
else return false;
}
}
}
Au début, il y a une étoile : Voie *venantDe
J'en déduis que c'est un pointeur ?
Puis, un peu plus loin dans un test, tu as : if (venantDe == mVoieSortantDroit)
Et là, c'est le contenu de la variable ?
Peux-tu m'expliquer la nuance ? C'est là que je bute.
Dommage, c'est une notion fondamentale.
Pour moi, si *venantDe est un pointeur, pour avoir le contenu, tu mets &venantDe...
D'avance, merci :D
-
Si je peux me permettre, je m'insinue...
Le test vérifie que l'argument venantDe et la donnée membre de la classe mVoieSortantDroit pointent vers la même voie. Si les pointeurs sont égaux, alors évidemment les contenus aussi ! Mais là on veut absolument s'assurer qu'on ne parle pas de choses différentes mais exactement de la même voie, donc on compare les pointeurs.
Et non, si venantDe est un pointeur, alors *venantDe est son contenu, et &venantDe est le pointeur contenant la valeur du pointeur venantDe !
-
Je complète la réponse de Thierry avec un petit dessin que j'ai fait en parallèle :)
J'ai bien conscience que ça va "polluer" ton exposé, mais je me pose quelques questions :
Pas du tout, ça ne pollue rien, un forum c'est fait pour discuter :)
#ifdef __AVR__
#include <avr/pgmspace.h>
#endif
#ifndef __AVR__
#include <iostream>
#define F(string) string
#define PROGMEMJe ne connais pas ___AVR__ ?
__AVR__ est un symbole défini par le compilateur quand il compile pour AVR et donc pour Arduino Uno/Nano. Sinon il ne l'est pas. J'utilise ça pour émuler des macros et des classes Arduino sur mon Mac. Ça me permet de compiler et exécuter le programme sur mon Mac, sans Arduino, et de mettre au point dans un environnement plus confortable.
Le simple fait de mettre #define DEBUG au début suffit pour pouvoir afficher les essais ?
Tu mets les sorties Serial.print() entre #ifdef DEBUG .... #endif et elles sont affichées et si tu dévalides le #define DEBUG pour ne plus les afficher.
C'est sympa, ça.
C'est ça
Et, dans mes efforts pour comprendre les pointeurs, je choisis "venantDe". Exemple :
bool Aiguillage::creeCheminVers(byte identifiant, byte dir, Voie *venantDe)
{
if (idVoie() == identifiant) return true;
else {
if (direction() == dir) {
if (mVoieSortantDroit != NULL) {
if (mVoieSortantDroit->creeCheminVers(identifiant, dir, this)) {
afficheNomVoie(idVoie());
Serial.println(F(": droit"));
return true;
}
else if (mVoieSortantDevie != NULL) {
if (mVoieSortantDevie->creeCheminVers(identifiant, dir, this)) {
afficheNomVoie(idVoie());
Serial.println(F(": devie"));
return true;
}
else return false;
}
else return false;
}
else return false;
}
else {
if (mVoieEntrant != NULL) {
if (mVoieEntrant->creeCheminVers(identifiant, dir, this)) {
afficheNomVoie(idVoie());
if (venantDe == mVoieSortantDroit) {
Serial.println(F(": droit"));
}
else {
Serial.println(F(": devie"));
}
return true;
}
else return false;
}
else return false;
}
}
}
Au début, il y a une étoile : Voie *venantDe
J'en déduis que c'est un pointeur ?
C'est ça.
Puis, un peu plus loin dans un test, tu as : if (venantDe == mVoieSortantDroit)
Et là, c'est le contenu de la variable ?
Non, je compare les pointeurs.
En effet, chaque voie connaît ses voisines via des pointeurs. Par exemple quand on écrit :
voie8.connecteSortantAVoie(tjd12, ENTRANT);
voie21.connecteSortantAVoie(tjd12, ENTRANT_BIS);
ça donne ça
(http://www.locoduino.org/pic/GareDenis/connexions.png)
Quand creeCheminVers de la TJD est appelée, venantDe sert à savoir de où on vient, voie8 ou voie21 ? En le comparant avec les deux pointeurs arrière, on détermine la position de l'aiguille d'entrée de le TJD. Idem quand on entre dans une aiguille par la branche déviée ou la branche droite
-
Donc, pour voir ce que j'ai compris :
Sur ton schéma, Jean-Luc, chaque flèche est un pointeur.
Pour tjd12, pointeur de mVoieEntrant = voie8 et pointeur de mVoieEntrantBis = voie21
De même pour voie8, pointeur de mVoieSortant = tjd12 et pour voie21, pointeur de mVoieSortant = tjd12
Maintenant, il faut l'écrire en code compilable.
Dans le test if (venantDe == mVoieSortantDroit) {..},
mVoieSortantDroit est un élément de la classe Voie et donc ce n'est pas un pointeur.
Il s'ensuit que venantDe n'est pas non plus un pointeur pour qu'on compare des choses de même nature.
Il y a deux mVoieSortantDroit : celui de la voie8 et celui de la voie21 et il faut donc choisir.
Tu es dans bool traverseeJonctionDouble(...), donc tu es sur la tjd12 et tu recherches les antécédents pour pouvoir créer un chemin qui va venir soit de la voie8, soit de la voie21.
Quand tu rentres comme argument de bool(...) Voie *venantDe, tu veux préciser en entrée que tu viens de la voie8 ou que tu viens de la voie21.
Admettons qu'on vienne de la voie8.
Est-ce que je peux dire, dans tjd12, que Voie *venantDe = voie8 ?
Par ailleurs, dans voie8, mSortantDroit, pointe vers tjd12.
Est-ce que je peux dire, dans voie8 cette fois, que *mSortantDroit = tjd12 ?
Et là, je bloque. Que valent venantDe et mSortantDroit ? ???
-
Salut Jean-Luc,
Il y a un truc qui m'intéresserait : comment mettre des images dans le dossier www.locoduino.org/pic ?
C'est peut-être réservé à l'admin ?
En tout cas c'est mieux de pouvoir mettre les images au bon endroit dans le texte
Danke !
Dominique
-
Sur ton schéma, Jean-Luc, chaque flèche est un pointeur.
Oui
Pour tjd12, pointeur de mVoieEntrant = voie8 et pointeur de mVoieEntrantBis = voie21
De même pour voie8, pointeur de mVoieSortant = tjd12 et pour voie21, pointeur de mVoieSortant = tjd12
Oui
Dans le test if (venantDe == mVoieSortantDroit) {..},
mVoieSortantDroit est un élément de la classe Voie et donc ce n'est pas un pointeur.
Non, mVoieSortantDroit est un pointeur vers un objet de type Voie. Regarde dans la déclaration de la classe Aiguille :
Voie *mVoieSortantDroit;
Il y a deux mVoieSortantDroit : celui de la voie8 et celui de la voie21 et il faut donc choisir.
Non, mVoieSortantDroit est une donnée membre de la classe Aiguille.
Tu es dans bool traverseeJonctionDouble(...), donc tu es sur la tjd12 et tu recherches les antécédents pour pouvoir créer un chemin qui va venir soit de la voie8, soit de la voie21.
Quand tu rentres comme argument de bool(...) Voie *venantDe, tu veux préciser en entrée que tu viens de la voie8 ou que tu viens de la voie21.
Admettons qu'on vienne de la voie8.
Est-ce que je peux dire, dans tjd12, que Voie *venantDe = voie8 ?
Non. Comme voie8 a passé this dans l'argument venantDe, venantDe est un pointeur vers voie8, c'est à dire &voie8. On compare chacun des pointeurs vers les voies précédentes : mVoieEntrant et mVoieEntrantBis à venantDe. L'un d'entre eux étant un pointeur vers voie8, il est égal à venantDe et de cette manière tu sais d'où on vient et tu connais la position de l'aiguille d'entrée de la TJD
Par ailleurs, dans voie8, mSortantDroit, pointe vers tjd12.
Est-ce que je peux dire, dans voie8 cette fois, que *mSortantDroit = tjd12 ?
Je ne suis pas sûr de comprendre ce que tu veux écrire. Ton égal est le égal mathématique ou l'affectation ?
-
Salut Dominique
Il y a un truc qui m'intéresserait : comment mettre des images dans le dossier www.locoduino.org/pic ?
C'est peut-être réservé à l'admin ?
C'est réservé à l'admin effectivement.
Eventuellement vous pouvez vous faire un article bidon dont vous ne demandez pas la publication et vous chargez vos images dans cet article. Il suffit ensuite de récupérer l'URL de l'image pour pouvoir l'insérer dans le forum. Comme ceci :
(http://www.locoduino.org/IMG/png/croisementtjd.png)
-
Merci Jean-Luc pour ta patience...
Mais je crois avoir compris.
Dans la class Voie, ligne 222 tu définis :
virtual bool creeCheminVers(byte identifiant, byte dir, Voie *venantDe = NULL) = 0;
Donc venantDe est un pointeur et tu l'initialises à NULL.
Également dans la class Aiguille, ligne 452, tu définis :
virtual bool creeCheminVers(byte identifiant, byte dir, Voie *venantDe = NULL);
Donc il y a des venantDe qui servent quand on est sur une voie et d'autres qui servent quand on est sur une aiguille.
En fait, ce pointeur est crée et initialisé à NULL dans tous les creeCheminVers(...), comme donnée d'entrée.
Dans la class Aiguille, ligne 441, tu définis :
Voie *mVoieSortantDroit;Donc mVoieSortant droit est un pointeur.
Quelques lignes plus bas, ligne 458, tu lui affectes la valeur :
mVoieSortantDroit = &voie;
Là, l'affectation est claire pour moi.
Mais pour venantDe, c'est plus complexe et je ne la trouvais pas.
En fait, tu la passe avec le this ligne 295 :
if (mVoie->creeCheminVers(identifiant, dir, this))
Là, c'est pour VoieEnImpasse, mais il y en a pour tous les éléments.
Et après, effectivement, tu compares les deux pointeurs pour la TJD ligne 792 :
if (venantDe == mVoieEntrant && mVoieSortant != NULL)Et comparer des pointeurs, c'est comme comparer les contenus.
C'est bon ? ???
J'ai relu la prose de Thierry et ça m'a aussi aidé.
J'avais cru comprendre ses articles, mais finalement pas complètement...
Autre chose :
On démarre par la class Voie.
class VoieEnImpasse hérite de Voie
class VoieNormale hérite de Voie
Puis class VoieMuli
class Aiguille hérite de VoieMulti
class Croisement hérite de VoieMulti
class TraverseeJonctionDouble hérite de Croisement
C'est quand même très souple
-
Tout bon :)
-
Yes !!!! ;D ;D ;D ;D
A bientôt 60 balais (le 26/04, le jour de Tchernobyl :D), c'est quand même plus dur.
-
A part ça, la compil ne marche pas... :(
Message :
Arduino : 1.6.7 (Windows 10), Carte : "Arduino Due (Programming Port)"
GrapheReseauDDEFF:23: error: conflicting declaration 'SerialEmulation Serial'
SerialEmulation Serial;
^
In file included from C:\Users\PARENTS1\AppData\Local\Arduino15\packages\arduino\hardware\sam\1.6.6\cores\arduino/Arduino.h:189:0,
from sketch\GrapheReseauDDEFF.ino.cpp:1:
C:\Users\PARENTS1\AppData\Local\Arduino15\packages\arduino\hardware\sam\1.6.6\variants\arduino_due_x/variant.h:245:18: error: 'Serial' has a previous declaration as 'UARTClass Serial'
extern UARTClass Serial;
^
exit status 1
conflicting declaration 'SerialEmulation Serial'
-
Ça compile bien sur un Mega !
Pour le Due, je l'ai vu aussi. C'est probablement parce que ce n'est plus un AVR, mais un Sam, non ?
La classe Serial est différente.
-
Et ça marche sur un UNO (je n'ai pas de MEGA). Tu dois avoir raison.
-
Effectivement, mon émulation pour Mac (et Unix en général, ça compilera sous Linux et sans doute sous Windows) casse la compilation pour un Arduino à base d'ARM
Voici une version à jour qui compile sur Due. Hier soir j'ai également commencé à travailler sur les itinéraires et les ensembles d'itinéraires. il y a donc de nouvelles classes qui ne sont pas utilisées pour le moment. Le sketch actuel fait la même chose que celui que j'ai déjà posté.
J'ai également commencé à mettre le code en plusieurs fichiers de manière à ne laisser dans le sketch que ce qui est propre au réseau.
-
Si je voulais être caustique, je dirais qu'il fait la même chose que l'ancien : il n'affiche toujours rien ... :D :D
Mais il compile sur DUE, effectivement, et sur un UNO.
J'ai dû oublier quelque chose ???
-
Tu as connecté le DUE via le programming port ?
-
Arduino DUE connecté en USB sur le programming port, comme je l'ai toujours fait...
Je suis en version 1.6.7
La compil se passe bien, le téléversement aussi.
Dans "outils", je suis sur programmateur : "arduinoISP".
Voir copie écran jointe.
Et quand je clique sur la loupe à droite (moniteur série), il ne se passe rien.
Tu as mis le DEBUG en Debug.h.
J'ai essayé de mettre #include "debug.h" dans GrapheReseau, mais le compilateur me parle mal :)
Arduino : 1.6.7 (Windows 10), Carte : "Arduino Due (Programming Port)"
In file included from R:\Documents publics\_Trains\Locoduino\Jean-Luc\GrapheReseau\GrapheReseau\GrapheReseau.ino:3:0:
Debug.h:6: error: default argument given for parameter 2 of 'void afficheNomVoie(byte, bool)' [-fpermissive]
extern void afficheNomVoie(byte id, bool aLaLigne = false);
^
In file included from sketch\Voie.h:7:0,
from R:\Documents publics\_Trains\Locoduino\Jean-Luc\GrapheReseau\GrapheReseau\GrapheReseau.ino:1:
Debug.h:6: error: after previous specification in 'void afficheNomVoie(byte, bool)' [-fpermissive]
extern void afficheNomVoie(byte id, bool aLaLigne = false);
^
exit status 1
default argument given for parameter 2 of 'void afficheNomVoie(byte, bool)' [-fpermissive]
-
Encore mon histoire d'émulation qui joue des tours. Du coup j'ai tout viré. L'archive mise à jour est à télécharger ci-dessous.
-
PEBCAK...
Maintenant, fonctionnement parfait.
Merci Jean-Luc
-
La nuit porte conseil... :P
La chose la plus difficile à comprendre dans SGDD, c'est cette histoire de niveaux. En plus, saisie manuelle.
D'un autre côté, la saisie manuelle permet d'influencer les choix de l'Arduino.
Comment optimiser et surtout automatiser ?
Pour optimiser les itinéraires, il faut faire comme en réalité, avec un maître mot : fluidité
Il faut donc arriver à donner un "poids" aux itinéraires. C'est la phase d'analyse. On ne la fait qu'une fois.
Soit on la fait à part en on inscrit les résultats "en dur" dans la programme d'exploitation, soit on la met dans le setup() et c'est automatique.
1°) Il faut trouver tous les itinéraires.
Combien y en a-t-il ?
Dans ma gare, 9 origines (à gauche) et 12 extrémités (à droite).
Donc 9 x 12 = 108 itinéraires. Deux sens => 216 itinéraires.
Une bonne partie des itinéraires ont 2 solutions à cause des doubles diagonales => 432 est une borne supérieure.
C'est beaucoup pour un humain, mais pas trop pour un Arduino. Et, là dedans, 180 itinéraires utiles.
En "largeur" de la matrice, on a un maxi de 11 (itinéraire voieLibre0 -> voieLibre7)
2°) Il faut donner un poids à chaque aiguille.
A chaque fois qu'une aiguille est utilisée dans un itinéraire, on lui ajoute 1, en faisant le tour de tous les itinéraires.
On a donc un mini de 4 pour une aiguille donnée (aiguille = 2 itinéraires mini, dans les 2 sens) et un maxi de ... on ne sait pas.
Je ne serais pas surpris qu'on atteigne les 25-30.
Un poids de 20 indique que cette aiguille est impliquée dans 0 itinéraires.
3°) En ayant le poids de chaque aiguille, on va pouvoir donner le poids de chaque itinéraire en additionnant.
Et plus un itinéraire est "lourd", plus il bloque d'autres itinéraires et plus il contrarie la fluidité.
Et donc plus il faut le faire tard ! ;)
On a ainsi une donnée supplémentaire dans l'objet "itinéraire" : son poids, calculé une fois pour toute dans le setup().
Maintenant, on va élaguer cette liste en ne gardant que les itinéraires de plus faible poids quand il y en a deux pour un même coupe origine-extrémité.
Et c'est là qu'on arrive à "seulement" 180 itinéraires. ;)
Une autre variable des itinéraires est "l'heure" à laquelle il va être demandé, heure qui va servir à savoir quand on va pouvoir le lancer.
Le principe du "time sharing" me paraît la méthode la plus adaptée à notre problème.
C'est une méthode qui sert dans les serveurs. Vieille méthode et donc éprouvée.
Le principe est le suivant :
Plusieurs itinéraires doivent être exécutés en même temps.
Comme on ne peux pas les faire vraiment en même temps, on va leur donner une priorité dynamique.
1°) On note l'heure de la demande.
2°) On note le poids de l'itinéraire. On effectue en priorité les itinéraires courts, ce qui réduit la liste (fluidité toujours)
3°) Au bout d'un "certain temps", on effectue des itinéraires plus lourds, même s'ils bloquent tout (ex : voieLibre0 -> voieLibre7) parce qu'il faut aussi que ces itinéraires soient faits.
Voilà.
Y'a plus qu'à ... ;D ;D
-
Oui mais moi je ne veux pas faire cette phase d'analyse à la main. En fait je ne veux pas faire d'analyse du tout.
1) c'est fastidieux
2) tu peux te tromper (c'est même une garantie si c'est gros)
Comment sais tu que tu as trouvé tous les itinéraires de ton réseau ? 432 est faux il y en a plus car tu as plusieurs chemins intermédiaires entre les doubles diagonales. Par exemple, entre VoieLibre0 et VoieGarage7, tu as 5 itinéraires si mon compte est bon.
108 est également faux car tu ne peux pas aller de VoieLibre0 à VoieLibre9 sans changer de sens.
Enfin il n'y a pas que les extrémités qui nous intéressent. Il faut également construire les itinéraires permettant d'amener à une voie en particulier, à quai par exemple, qui n'est pas une voie extrême.
-
Comment sais tu que tu as trouvé tous les itinéraires de ton réseau ? 432 est faux il y en a plus car tu as plusieurs chemins intermédiaires entre les doubles diagonales. Par exemple, entre VoieLibre0 et VoieGarage7, tu as 5 itinéraires si mon compte est bon.
Tu as raison : c'est plus que 432, car tu as effectivement tu as des fois plus de 2 itinéraires pour 2 extrémités données.
Donc, le nombre d'itinéraires possibles est plus élevé.
108 est également faux car tu ne peux pas aller de VoieLibre0 à VoieLibre9 sans changer de sens.
108, c'était un maximum.
En fait, il y a 36 couples origine-extémité qui sont carrément impossibles.
Je veux bien ne pas faire d'analyse (surtout à la main, ce que je n'ai jamais fait), mais il faut quand même prioriser des choses, avoir des critères ?
-
C'est quand même un sacré site que LOCODUINO : on en est quand même à la troisième (!!) possibilité de modéliser un réseau... ;D
Pour un seul site, c'est bien une preuve de vitalité !
Comme ils disent dans la pub : le plus dur, c'est de choisir...
-
Blouge. C'est bien, blouge...
-
J'ai avancé hier soir.
J'ai ajouté la méthode tousLesCheminsVers aux voies. Il s'utilise comme creeCheminVers mais prend un argument supplémentaire : un ensemble d'itinéraires. Au retour cet ensemble contient tous les itinéraires possible pour aller de A à B.
Un itinéraire est un ensemble de voies (du point de vue ensembliste, c'est à dire qu'il n'y a pas d'ordre). Côté implémentation, un Itinéraire est un vecteur de bits implémenté sous la forme d'un tableau de N octets ou N est le nombre de voies / 8 + 1 quand la division ne tombe pas juste. Quand le bit de rang identifiant de la voie est à 1, la voie est présente dans l'itinéraire et absente sinon. Cela permet une représentation compacte d'une part et des opérations efficaces. Par exemple, des itinéraires sont compatibles si l'intersection des ensembles de voies qui les représente est vide. Il suffit de faire un & pour le savoir.
J'ai donc l'objet Itineraire et EnsembleItineraires.
Exemple:
EnsembleItineraires iti3;
voieLibre6.tousLesCheminsVers(VOIE_GARAGE_4, DIRECTION_AVANT, iti3);
iti3.print();
crée un ensemble d'itinéraires iti3 qui est pour l'instant vide puis le remplit et enfin l'affiche. Il n'y a qu'un seul itinéraire possible entre voieLibre6 et voieGarage4. L'affichage est :
VOIE_LIBRE_6 VOIE_10 VOIE_20 VOIE_31 VOIE_GARAGE_4 AIGUILLE_3 AIGUILLE_4 AIGUILLE_11 TJD_3 TJD_7 TJD_11 TJD_15 CROISEMENT_0 CROISEMENT_2
EnsembleItineraires iti4;
voieLibre0.tousLesCheminsVers(VOIE_GARAGE_7, DIRECTION_AVANT, iti4);
iti4.print();
produit :
VOIE_LIBRE_0 VOIE_0 VOIE_3 VOIE_21 VOIE_29 VOIE_GARAGE_7 AIGUILLE_0 TJD_0 TJD_8 TJD_12 TJD_14 TJD_16 CROISEMENT_2
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_12 VOIE_26 VOIE_29 VOIE_GARAGE_7 AIGUILLE_0 TJD_0 TJD_1 TJD_2 TJD_11 TJD_14 TJD_16
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_18 VOIE_25 VOIE_28 VOIE_GARAGE_7 AIGUILLE_0 AIGUILLE_8 TJD_0 TJD_1 TJD_2 TJD_4 TJD_6 TJD_10 TJD_16 CROISEMENT_0
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_19 VOIE_28 VOIE_GARAGE_7 AIGUILLE_0 AIGUILLE_8 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_16
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_20 VOIE_26 VOIE_29 VOIE_GARAGE_7 AIGUILLE_0 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_11 TJD_14 TJD_16
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_8 VOIE_29 VOIE_GARAGE_7 AIGUILLE_0 TJD_0 TJD_1 TJD_12 TJD_14 TJD_16 CROISEMENT_2
VOIE_LIBRE_0 VOIE_1 VOIE_21 VOIE_29 VOIE_GARAGE_7 AIGUILLE_0 TJD_8 TJD_12 TJD_14 TJD_16 CROISEMENT_2
7 itinéraires possibles
et enfin :
EnsembleItineraires iti5;
voieLibre1.tousLesCheminsVers(VOIE_GARAGE_2, DIRECTION_AVANT, iti5);
iti5.print();
produit :
VOIE_LIBRE_1 VOIE_2 VOIE_8 VOIE_27 VOIE_32 VOIE_GARAGE_2 AIGUILLE_12 TJD_0 TJD_1 TJD_12 TJD_15
VOIE_LIBRE_1 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_20 VOIE_32 VOIE_GARAGE_2 AIGUILLE_12 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_11 TJD_15 CROISEMENT_2
VOIE_LIBRE_1 VOIE_2 VOIE_6 VOIE_12 VOIE_32 VOIE_GARAGE_2 AIGUILLE_12 TJD_0 TJD_1 TJD_2 TJD_11 TJD_15 CROISEMENT_2
VOIE_LIBRE_1 VOIE_3 VOIE_21 VOIE_27 VOIE_32 VOIE_GARAGE_2 AIGUILLE_12 TJD_0 TJD_8 TJD_12 TJD_15
VOIE_LIBRE_1 VOIE_3 VOIE_22 VOIE_GARAGE_2 AIGUILLE_12 TJD_0 TJD_8
5 itinéraires possibles
J'ai laissé la trace de recherche dans le programme pour voir le cheminement.
Ça ne tourne plus sur le Uno par manque de SRAM (le tas vient télescoper la pile)
J'ai mis le code sur le dépôt git : https://git.framasoft.org/locoduino.org/GestionnaireReseau/tree/master
Téléchargement direct : https://git.framasoft.org/locoduino.org/GestionnaireReseau/repository/archive.zip?ref=master
Vous pouvez vous amuser avec.
La suite : étant donné N ensembles d'itinéraires former si possible des itinéraires compatibles.
-
Génial !!! ;D ;D ;D
Je vais essayer de décortiquer
-
Je viens de pousser de nouvelles choses sur le repository :
1 - Le programme calcule tous les itinéraires de la gare de DDEFF, il y en a 241 (x2 si on compte le même en sens inverse).
2 - Il y 18 couples source, destination qui n'ont pas d'itinéraire possible.
3 - Le programme mesure le temps de calcul de tous les itinéraires : 77ms sachant qu'il y a du code de comptage la dedans (si si je pensais que ça ferait plus, je suis épaté par les perfs du Due).
L'affichage des dits itinéraires est commenté. Pour les afficher, il faut décommenter les lignes 288 à 293 de GestionnaireReseau.ino
-
Questions :
- Est-ce ces itinéraires tiennent compte des positions des aiguilles ?
- Sinon, pour en parcourir un faut-il positionner les aiguilles avant le départ du train ?
- Quid des autres itinéraires pendant les mouvements des trains ?
-
Questions :
- Est-ce ces itinéraires tiennent compte des positions des aiguilles ?
- Sinon, pour en parcourir un faut-il positionner les aiguilles avant le départ du train ?
- Quid des autres itinéraires pendant les mouvements des trains ?
Dans l'ordre :
- Non, les itinéraires ne tiennent pas compte de la position des aiguilles. En fait il s'agit ici du problème inverse de celui que tu exposes plus haut. Il s'agit, à partir d'un couple d'emplacements (A,B) sur le réseau, de déterminer les itinéraires possibles et donc la position des aiguilles à appliquer.
- Oui
- Ce n'est pas traité pour l'instant mais c'est facilement faisable.
-
Tu vois, calculer tous les itinéraires, ça n'est pas si long.
Et pourtant, il y en a plein.
Evidemment, j'ai quelques questions
1°) Je passe sur le :
static Voie **sVoies;
Je comprends (enfin, je crois), mais ça se complique.
Un pointeur de pointeur…
2°) je ne comprends pas pourquoi tu dois avoir un creeCheminVers (…) et un tousLesCheminsVers(…) dans chaque classe.
Quand on hérite, on n'hérite pas de tout ?
3°) Là, je décroche :
static const byte taille() {
return ((sNombre >> 3) + ((sNombre & 7) != 0));
Je comprends (grosso-modo) la syntaxe, mais pourquoi tu fais ça ?
4°) Et ailleurs, encore mieux (mais je ne comprends plus la syntaxe) :
void EnsembleDeVoies::ajouteVoie(byte identifiant)
{
mEnsemble[identifiant >> 3] |= 1 << (identifiant & 7);
}
void EnsembleDeVoies::enleveVoie(byte identifiant)
{
mEnsemble[identifiant >> 3] &= ~(1 << (identifiant & 7));
}
bool EnsembleDeVoies::contientVoie(byte identifiant)
{
return (mEnsemble[identifiant >> 3] & 1 << (identifiant & 7)) != 0;
}
5°) Tu as marqué un commentaire, c'est vrai, mais pour comprendre, là, c'est costaud :
/* Si sVoies n'est pas alloue, alloue arbitrairement 256 emplacements */
if (sVoies == NULL) {
sVoies = (Voie **)malloc(sTailleTableau * sizeof(Voie **));
}
Et, la plus drôle pour la fin : le loop() est ... vide !
-
Tu vois, calculer tous les itinéraires, ça n'est pas si long.
Et pourtant, il y en a plein.
Je n'aurais pas dit plein. Ça reste très raisonnable.
1°) Je passe sur le :
static Voie **sVoies;
Je comprends (enfin, je crois), mais ça se complique.
Un pointeur de pointeur…
Oui, je maintiens une table de pointeurs, des Voie* où chaque objet Voie, ou dérivé de Voie vient inscrire son pointeur à l'index de son identifiant. De cette manière, je peux retrouver un objet Voie par son identifiant. Comme je ne sais pas à priori combien d'éléments de voie je vais avoir. Je pars sur 256 et une fois que j'ai tout, je retaille le tableau au nombre d'élément effectif.
2°) je ne comprends pas pourquoi tu dois avoir un creeCheminVers (…) et un tousLesCheminsVers(…) dans chaque classe.
Quand on hérite, on n'hérite pas de tout ?
J'ai laissé creeCheminVers et ajouté tousLesCheminsVers à côté mais à terme, creeCheminVers disparaîtra car tousLesCheminsVers fait mieux.
3°) Là, je décroche :
static const byte taille() {
return ((sNombre >> 3) + ((sNombre & 7) != 0));
Je comprends (grosso-modo) la syntaxe, mais pourquoi tu fais ça ?
Ok. Comme je l'ai dit, je gère un vecteur de bits. Là je calcule la taille en nombre d'octets du tableau nécessaire au stockage de ce vecteur. sNombre est le nombre de bits nécessaires, sNombre >> 3 correspond à une division par 8 (2^3 = 8)et donc au nombre d'octets. Mais c'est une division entière. Si sNombre n'est pas divisible par 8 j'ai un reste et j'ai besoin d'un octet de plus. sNombre & 7 est le reste de la division. Si il est différent de 0, je dois avoir un octet de plus et c'est çe que je calcule puisque le != 0 me renvoie 1 si il y a un reste et 0 sinon.
4°) Et ailleurs, encore mieux (mais je ne comprends plus la syntaxe) :
void EnsembleDeVoies::ajouteVoie(byte identifiant)
{
mEnsemble[identifiant >> 3] |= 1 << (identifiant & 7);
}
Pareil. Je veux mettre à 1 le bit de rang identifiant. Je divise identifiant par 8 pour avoir l'octet puis sur cet octet je fais un ou avec un 1 décalé du reste.
void EnsembleDeVoies::enleveVoie(byte identifiant)
{
mEnsemble[identifiant >> 3] &= ~(1 << (identifiant & 7));
}
bool EnsembleDeVoies::contientVoie(byte identifiant)
{
return (mEnsemble[identifiant >> 3] & 1 << (identifiant & 7)) != 0;
}
Et là auss, je mets le bit a 0 et je le teste.
5°) Tu as marqué un commentaire, c'est vrai, mais pour comprendre, là, c'est costaud :
/* Si sVoies n'est pas alloue, alloue arbitrairement 256 emplacements */
if (sVoies == NULL) {
sVoies = (Voie **)malloc(sTailleTableau * sizeof(Voie **));
}
malloc alloue une zone mémoire comptée en nombre d'octets. Ici je veux allouer sTailleTableau pointeurs. Un pointeur a une taille de sizeof(Voie **) octets. Je caste le resultat qui est un void * en Voie **
Et, la plus drôle pour la fin : le loop() est ... vide !
Tout est fait dans setup :-)
-
Je continue sur le programme (et incidemment la bibliothèque associée).
Actuellement il n'est pas possible d'avoir un réseau bouclé (c'est ballot hein ? ;D). En effet, la recherche d'itinéraires ne termine pas car il n'existe pas de moyen de savoir que l'on est déjà passé par un élément de voie (nœud du graphe). En fait ça finirait par planter par manque de mémoire car lorsque la recherche du but est faite sur un mauvais chemin et que ce mauvais chemin ramène à un élément déjà parcouru sur ce chemin, on tourne en rond et l'appel récursif des fonctions conduit à une pile qui ne fait que croître.
La solution est bien connue en algorithmique sur les graphes : il faut jouer au petit poucet et marquer les endroits où on est déjà passé. Il ne faut pas les marquer globalement en marquant les éléments de voie car cela empêcherait la découverte des chemins qui partagent un sous ensemble d'éléments de voie. Il faut donc un historique de parcours que l'algo emmène avec lui (c'est la version petit poucet avec un GPS). J'ai déjà la classe permettant de faire ça : les ensembles de voies. Je suis en train d'ajouter ça dans l'algo existant.
Il y a le problème des croisements. En effet, c'est le seul élément de voie que l'on peut parcourir deux fois sans emprunter le même chemin. Il doit être considérer comme unique en terme d'occupation d'itinéraire mais permet deux chemins disjoints. La solution est simple, on n'ajoute pas les croisements dans l'ensemble des éléments de voies parcourus dans l'algorithme d'exploration. On pourra donc passer par un croisement autant de fois qu'on le veut sans savoir que l'on y est déjà passé. À moins d'avoir un réseau exclusivement constitué de croisements ;D ça ne pose pas de problème.
Denis, as-tu le reste de ton futur réseau ?
-
Et pourquoi on ne ferait pas un réseau composé uniquement de croisements ? ;D ;D
J'ai déjà cherché pour la suite du réseau, mais je pense que ça va t'embêter :
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=291;image)
1°) Si tu sors par l'une des VoieLibre0 ... VoisLibre9 et que tu reviens par une autre de ces voies, tu fais une boucle de retournement :(
Je n'y avais pas pensé au début, mais c'est logique.
2°) La seule voie bouclable "normalement", c'est VoieLibre0 <-> VoieLibre7. C'est ce que je fais.
La voieLibre7 longe la gare et passe dessous pour rejoindre la VoieLIbre0.
Comme ce circuit passe au travers de toute la gare, j'en profite pour mettre une gare cachée, du type "biceps" (appellation perso pour 1 tendon, plusieurs fibres et un tendon), comme la quasi totalité des gares cachées.
La facture chez Peco s'alourdit :(
Comme ça, la gare cachée donne accès à toutes les voies. :D
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=271;image)
3°) VoieLibre6 <-> VoieLibre5
VoieLibre4 <-> VoieLibre1
VoieLibre3 <-> VoieLibre2.
4°) Et j'aurais quelques bifurcations pour passer d'un circuit à l'autre.
Le but est simple : quand un train sort par une voie, on ne doit pas savoir par laquelle il reviendra.
Il me reste à caser tout ça dans 3.42 x 2,57 ;D
Donc, M. Peco m'attend au coin du bois...
-
Et pourquoi on ne ferait pas un réseau composé uniquement de croisements ? ;D ;D
Faire un réseau exclusivement composé de croisement est un des droits fondamentaux du modéliste ferroviaire ;D mais il s'expose à être la risée de ses confrères :P
1°) Si tu sors par l'une des VoieLibre0 ... VoisLibre9 et que tu reviens par une autre de ces voies, tu fais une boucle de retournement :(
Je n'y avais pas pensé au début, mais c'est logique.
J'ai réfléchi aux boucles de retournement et je pense avoir trouvé une solution élégante et simple. J'ajoute une classe d'élément de voie : BoucleDeRetournement. Dans un parcours qui est une boucle de retournement, un élément de ce type doit être inséré. L'un des connecteurs est dans le sens normal mais l'autre doit être connecté à contresens.
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=289;image)
Par exemple voici une boucle simple. On commence la construction par E. On connecte le SORTANT de E à l'ENTRANT de l'aiguillage A. On connecte le SORTANT_DROIT de A à l'ENTRANT de B. On connecte le SORTANT_GAUCHE de A à l'ENTRANT de C. On connecte le SORTANT de B sur l'ENTRANT de D et on connecte le SORTANT de C sur le SORTANT de D. Comme D est une instance de BoucleDeRetournement, cette dernière connexion doit être faite à contresens.
Ensuite pour le parcours des éléments, comme je l'ai dit, on décide d'un sens de parcours. Ainsi si on cherche E depuis A dans le sens normal, que va-t-il se passer ? On commence par explorer côté SORTANT_DROIT, on arrive sur B, on continue sur D. Là on a un probléme, si on continue sur C, on arrive dans C avec le sens normal et en faisant ça, C va continuer sur D et on part en boucle infinie (ou bien si l'algo joue au petit poucet, il stoppe car il passe deux fois par un élément et il ne trouve pas. Comment faire ? c'est assez simple, il suffit d'inverser le sens de parcours quand on traverse un élément BoucleDeRetournement (ça servira aussi à commuter l'alim d'ailleurs :-)). Donc avant que D appelle C, il retourne le sens. C continuera donc avec A qui continuera avec E et E est trouvé. Du côté de la branche SORTANT_DEVIE, on arrive sur C qui appelle D, qui inverse le sens et appelle B qui appelle A et E est également trouvé. Deux chemins possibles, donc, selon le sens de parcours de la boucle de retournement.
On a maintenant un nouveau problème. Si on joue au petit poucet en notant les éléments parcourus pour ne pas passer deux fois par les mêmes éléments et permettre à l'algorithme de terminer, on va arrêter sur A. Comment faire ? C'est pas compliqué non plus, il ne faut pas marquer seulement les éléments mais le couple élément/sens de parcours. ainsi quand on parcoure A dans le sens normal, on marque A/normal. Quand on le reparcoure dans le sens inverse, on marque A/inverse. Donc deux marquages différents qui font qu'on ne va pas reconnaître A en le parcourant en sens inverse.
Donc, M. Peco m'attend au coin du bois...
My model train reseller is rich 8)
PS: on peut insérer une image de la pièce jointe dans le texte : clic sur la pièce jointe pour l'agrandir, clic droit « copier l'adresse de l'image », puis coller l'adresse dans une balise BBCode img
-
J'ai programmé et testé la recherche d'itinéraires avec marquage des nœuds visités. Ça fonctionne mais ca n'est pas satisfaisant.
En effet, l'algorithme actuel n'est pas très économe. Quand un aiguillage ou une TJD est rencontré (une divergence), l'exploration est faite dans la branche droite et déviée. Si on rencontre N aiguillages/TJD, on fait donc 2^N explorations. Ça, on n'y peut pas grand chose.
Par contre, si lors de l'exploration, on a une convergence des chemins, on n'y voit que du feu et la suite du chemin est explorée plusieurs fois et l'algorithme travaille donc de manière redondante.
Avec le marquage, ça engendre beaucoup de copies. En effet, comme, en cas de convergence, le chemin est exploré plusieurs fois, on ne peut pas le marquer de manière globale, en posant des cailloux sur le chemin car en, cas de convergence, l'algorithme échouerait. Il est donc marqué via un carnet que l'explorateur emmène avec lui. Lors d'une divergence, le carnet est copié et l'original est emmené sur la branche droite, la copie sur la branche déviée et ainsi de suite. On fait donc 2^N copies.
Évidemment sur mon Mac, ça s'exécute en un clin d'œil mais sur l'Arduino ca posera problème.
Je vais donc refaire l'algorithme pour tenir compte des convergences et ne pas dupliquer du travail. L'avantage est qu'un marquage global, donc beaucoup plus simple et rapide, est utilisable dans ce cas.
-
Merci pour l'info permettant (enfin !) de mettre des images dans le texte. Yeaahh. ;D ;D
Progressivement, à force de décortiquer, je me pose des questions.
Je proposerais bien de n'en avoir que deux classes :
Une classe arc et une classe nœud.
Dans la classe arc, on garde la tienne pour les cantons et pour une voie sans issue, on dit que le suivant, c'est 0 (zéro).
Dans la classe nœud, on définit 4 entrées sorties, systématiquement.
- pour une aiguille, l'une des entrées-sorties est à zéro, simplement.
- pour un croisement, une TJS, une TJD, un triple, on définit les 4.
Ordre proposé : 1 2
4 3
Par ailleurs, on définit quels sont les aboutements INTERNES sont possibles dans les nœuds :
- pour une aiguille, on aura 1,2,3,0 et 1-2, 1-3, 0, 0
- pour un croisement, on aura 1,2,3,4 et 1-3, 2-4, 0, 0
- pour une TJS, on aura 1,2,3,4 et 1-2, 1-3, 3-4, 0
- pour une TJD, on aura 1,2,3,4 et 1-2, 1-3, 2-4, 3-4
- pour un triple, on aura 1,2,3,4 et 1-2, 1-3, 1-4, 0
Les aboutements sont ordonnés (A<B). Quand on l’interrogera, on ordonnera aussi la demande.
Une autre remarque : quand on cherche à aller d'un point à un autre, c'est toujours d'un canton à un autre, jamais d'un nœud à un autre nœud.
Je sais qu'en théorie des graphes, on va d'un nœud à un autre...
Et, d'ailleurs, pour sortir des labyrinthes (ce qui est un peu notre cas), on met une croix à côté de l'entrée du tunnel qu'on choisit.
Donc, ce qu'on marque, ce n'est pas le nœud lui-même, mais l'une de ses extrémité.
Je ne me rappelle pas avoir déjà vu de méthode qui tenait compte du sens de parcours d'un arc (ce qui est différent du problème des arcs orientés dès la départ).
Dans ton exemple et ce que tu disais auparavant sur les circuits complets qui seraient impossibles, je dirai que :
Je sais aller de E à B, de E à D, de B à D, de D à B, de D à E, de E à C, de C à E. Mais ni de D à C ou de C à D.
Et tu t'occuperas du problème de l'inversion dans le loop{}
De cette manière, on ne retourne pas sur ses pas.
Dernière remarque :
J'ai l'impression que tu veux faire deux choses à la fois :
1°) Trouver toutes les façons d'aller de A à B. Là, je comprends bien.
2°) Gérer les incompatibilités en même temps.
J'aurais mieux compris, surtout dans le setup{}, que tu cherches tous les itinéraires possibles (quelques ms).
Tu les ranges (A<B).
Dans le setup{}, on peut perdre une seconde...
Et, dans le loop{}, tu géreras le fait que tel itinéraire ne peux pas être fait en même temps que tel autre, en testant parmi ceux que tu as trouvé auparavant.
J'espère avoir été constructif ;)
-
Je proposerais bien de n'en avoir que deux :
Une classe arc et une classe nœud.
Dans la classe arc, on garde la tienne pour les cantons et pour une voie sans issue, on dit que le suivant, c'est 0 (zéro).
Dans la classe nœud, on définit 4 entrées sorties, systématiquement.
- pour une aiguille, l'une des entrées-sorties est à zéro, simplement.
- pour un croisement, une TJS, une TJD, un triple, on définit les 4.
Par ailleurs, on définit quels sont les aboutements INTERNES sont possibles dans les nœuds :
- pour une aiguille, on aura 1,2,3,0 et 1-2,1-3, 0, 0
- pour un croisement, on aura 1,2,3,4 et 1-3,2-4, 0, 0
- pour une TJS, on aura 1,2,3,4 et 1-2,1-3,3-4, 0
- pour une TJD, on aura 1,2,3,4 et 1-2,1-3,2-4,3-4
- pour un triple, on aura 1,2,3,4 et 1-2,1-3,1-4, 0
Les aboutements sont ordonnés (A<B). Quand on l’interrogera, on ordonnera aussi la demande.
Oh non non non.
Pas de remplacement du graphe d'objets utilisant le polymorphisme par deux types d'objets (en fait un seul car je ne vois pas l'avantage de faire des arcs puisqu'un arc n'est rien de plus que le pointeur que l'on suit ici) est à l'encontre de la programmation objet. Tu vas, au lieu d'avoir un code spécifique à chaque type d'objet, avoir un code générique ou tu vas retrouver le code actuel dans une seule fonction enrobé de test pour savoir dans quel type de voie on est. Donc un truc énorme et moins conpréhensible. C'est pas du tout le principe. C'est clairement remplacer la programmation objet par de la programmation classique. On repart en arrière de 20 ans.
Une autre remarque : quand on cherche à aller d'un point à un autre, c'est toujours d'un canton à un autre, jamais d'un nœud à un autre nœud.
Je sais qu'en théorie des graphes, on va d'un nœud à un autre...
Les cantons ne sont pas le problème pour l'instant, ce n'est tout simplement pas traité. Par la suite, on peut regrouper les nœuds du graphe en cantons. Ça reste à faire mais je ne vois pas de difficultés. Pour mon réseau j'ai besoin du graphe car mes cantons contiennent 0 ou plusieurs aiguillages. Par ailleurs je pense ajouter la longueur des éléments de voie. pour calculer les distances.
Et, d'ailleurs, pour sortir des labyrinthes (ce qui est un peu notre cas), on met une croix à côté de l'entrée du tunnel qu'on choisit.
Donc, ce qu'on marque, ce n'est pas le nœud lui-même, mais l'une de ses extrémité.
Je ne me rappelle pas avoir déjà vu de méthode qui tenait compte du sens de parcours d'un arc (ce qui est différent du problème des arcs orientés dès la départ).
C'est équivalent à marquer le nœud où on arrive.
Dernière remarque :
J'ai l'impression que tu veux faire deux choses à la fois :
1°) Trouver toutes les façons d'aller de A à B. Là, je comprends bien.
2°) Gérer les incompatibilités en même temps.
Non, pour l'instant je ne fait que 1). Je construis une liste d'ensembles de nœuds liant un point de départ à un point d'arrivée.
Une fois que tu as fait 1), faire 2) n'est pas compliqué, savoir si deux itinéraires sont incompatibles consiste à faire une intersection des deux ensembles de chemins. Si l'intersection est vide, les itinéraires sont compatibles.
J'aurais mieux compris, surtout dans le setup{}, que tu cherches tous les itinéraires possibles (quelques ms).
Tu les ranges (A<B).
Dans le setup{}, on peut perdre une seconde...
Et, dans le loop{}, tu géreras le fait que tel itinéraire ne peux pas être fait en même temps que tel autre, en testant parmi ceux que tu as trouvé auparavant.
En informatique, on échange de la mémoire contre du temps de calcul et inversement. Il faut doser entre les deux. Dans ta gare, il y a 93 éléments de voies, il faut donc 12 octets pour stocker un itinéraire. Il suffit de reboucler voieLibre0 sur voirLibre7 pour avoir plus de 600 itinéraires entre les extrémités (7,2ko). Et on n'a pas traité le cas des voie en gares. En fait c'est exponentiel et sur un réseau complet, ça fait un sacré paquet d'itinéraires si on considère tous ceux possibles entre 2 paires de cantons. Je crains donc que la mémoire disponible ne suffise pas (mais alors pas du tout). Il faut donc les calculer au vol. Avec le nouvel algorithme que je fais ça sera encore plus rapide et le temps de calcul ne sera pas un problème.
J'espère avoir été constructif ;)
Tout à fait !
-
On repart en arrière de 20 ans
Et pan sur le bec ! ;D ;D ;D
Mais c'est dit gentiment et c'est parfaitement vrai.
J'avoue avoir un peu de mal avec la programmation objet complète comme celle que tu utilises. Il y a encore un aspect "magique"...
Mais je suis forcé de constater que c'est redoutablement efficace. Et ça me plait.
J'ajouterais que la croissance exponentielle dont tu parles (l'idée de calculer tous les couples) pourrait ne pas avoir lieu.
En effet, il y a énormément de couples qui ne servent à rien.
Il y a deux types de trains : les trains gérés en automatique et LE train géré en manuel.
On peut changer à tout moment de train suivi en manuel.
L'ancien devient un train automatique et le nouveau sélectionné est le train manuel.
Pour que l'ancien train sache où il va, il faut qu'on lui donne une destination.
Il y a trois types de destinations possibles :
1°) Une voie précise d'une gare visible
2°) N'importe quelle voie d'une gare cachée
3°) Un circuit qui boucle indéfiniment qu'on choisit dans une liste.
Les circuits peuvent être mémorisé fois pour toute : ils sont peu nombreux.
Un circuit, c'est une suite définie d'itinéraires A-B.
Un itinéraire A-B, tu as montré qu'on peut en avoir jusqu'à 11 pour un couple donné de ma gare. Et l'exponentielle peut être monstrueuse si on cherche toutes les façons de boucler un circuit.
Par contre, si on définit un circuit qui boucle de A -> A, on peut dire que c'est de (A->A1) + (A1->A2) + (A2->A3) + .... + (An->A) et là, plus de croissance exponentielle.
En fonction des occupations, le train automatique qui suit un circuit adaptera chaque partie à l'état du terrain.
Et on n'a plus à gérer que 1°) et 2°), sachant qu'à chaque fois, on ne va que d'une gare à la gare suivante.
-
J'ajouterais que la croissance exponentielle dont tu parles (l'idée de calculer tous les couples) pourrait ne pas avoir lieu.
En effet, il y a énormément de couples qui ne servent à rien.
Il y a deux types de trains : les trains gérés en automatique et LE train géré en manuel.
On peut changer à tout moment de train suivi en manuel.
L'ancien devient un train automatique et le nouveau sélectionné est le train manuel.
Pour que l'ancien train sache où il va, il faut qu'on lui donne une destination.
Il y a trois types de destinations possibles :
1°) Une voie précise d'une gare visible
2°) N'importe quelle voie d'une gare cachée
3°) Un circuit qui boucle indéfiniment qu'on choisit dans une liste.
Justement, le cas que tu cites fait que tous les nœuds peuvent être, au moins, point de départ. Si l'opérateur prend le contrôle d'un train géré en automatique, il peut le faire à n'importe quel moment et donc alors que que le train est à n'importe quelle position dans le réseau. Par ailleurs il peut y avoir plusieurs opérateurs.
Les circuits peuvent être mémorisé fois pour toute : ils sont peu nombreux.
Un circuit, c'est une suite définie d'itinéraires A-B.
Un itinéraire A-B, tu as montré qu'on peut en avoir jusqu'à 11 pour un couple donné de ma gare. Et l'exponentielle peut être monstrueuse si on cherche toutes les façons de boucler un circuit.
Par contre, si on définit un circuit qui boucle de A -> A, on peut dire que c'est de (A->A1) + (A1->A2) + (A2->A3) + .... + (An->A) et là, plus de croissance exponentielle.
En fonction des occupations, le train automatique qui suit un circuit adaptera chaque partie à l'état du terrain.
Oui, on peut construire des itinéraires en faisant l'union de sous itinéraires. On économisera de la mémoire mais on en perdra car il faudra mettre en place des structures de données pour construire les circuits comme des listes de sous itinéraire, ce qui aura un coût en mémoire. Ça sera plus compliqué à exploiter et je crains que l'on ne soit en fait perdant au niveau mémoire.
Et on n'a plus à gérer que 1°) et 2°), sachant qu'à chaque fois, on ne va que d'une gare à la gare suivante.
Mais la construction des itinéraires sera rapide, ce n'est pas la peine de les stocker.
-
Bonsoir,
Je viens de pousser une nouvelle version avec le nouvel algorithme.
Le temps de calcul des 603 itinéraires de la version bouclée est de 170ms.
Certains itinéraires bouclés peuvent ne pas être trouvés quand un itinéraire possible est inclus. Ca n'est pas très grave. J'ai l'idée d'une variante pour les inclure tous mais je me pose la question de l'intérêt.
-
Bonjour Jean-Luc
Sujet très intéressant, après avoir décortiqué le SGDD de Denis (merci Denis) et avant de me décider sur la méthode que je vais utiliser pour gérer mon réseau (encore virtuel :'() je vais essayé de comprendre ta méthode qui me plait bien au premier survol. Maintenant il faut approfondir et je me pose quelques petites questions.
Sur tes schémas de présentation tu parles du "sens normal" et dans ton code tu définis dans voie.h
enum { DIRECTION_AVANT = 0, DIRECTION_ARRIERE = 1, AUCUNE_DIRECTION = 2 };
puis dans voie.cpp
void afficheSens(byte sens)
{
switch (sens) {
case DIRECTION_AVANT: Serial.print("AV"); break;
case DIRECTION_ARRIERE: Serial.print("AR"); break;
case AUCUNE_DIRECTION: Serial.print("*"); break;
}
}
C'est quoi exactement le "Sens normal" y-a-t-il une relation avec les "DIRECTION" par exemple sens normal = DIRECTION_AVANT, ou bien pour faire un // avec le SGDD de Denis sens normal = sens HORAIRE ?
D'autre part est-ce que la définition du canton est la même que celle de Denis à savoir : une zone STOP, une Zone pleine voie, une zone STOP ?
J'aurai sûrement d'autres questions par la suite (j'ai aperçu des pointeurs dans ton code :P), car je n'en suis qu'au début de l'analyse de ton code. Mais pour le moment cette question de "sens" m'interpelle.
Merci d'avance pour ta réponse.
-
Bonjour Jack
Ce n'est pas tout à fait équivalent. Ce que je définis comme le sens normal c'est le parcours d'une voie dans la même direction que sa direction de connexion. Ainsi dans la gare de Denis, l'aiguillage Aiguille1 est connecté en DIRECTION_AVANT, le sens normal pour cet aiguillage est donc DIRECTION_AVANT. L'aiguillage Aiguille3 est connecté en DIRECTION_ARRIERE, le sens normal est donc DIRECTION_ARRIERE.
Pour l'instant je n'ai pas encore de notion de canton mais ça va venir. C'est un peu différent en analogique et en numérique. En analogique un canton = une alimentation indépendante, la détection de présence peut être unique ou multiple. En numérique un canton = une détection de présence.
-
C'est vrai que sur la façon de raisonner, il y a quelques subtilités dans la description du réseau :
Mes cantons sont tous décris dans le sens horaire (cw = Clockwise).
Par contre, les aiguilles sont toutes orientées de la pointe vers le talon.
Le raisonnement de Jean-Luc est très légèrement différent, comme il l'a indiqué dans son précédent post.
Le principal est de définir une règle et de s'y tenir strictement. ;)
Mais la grosse différence entre ma façon de raisonner et celle de Jean-Luc tient au fait que sa méthode cherche tous les itinéraires possibles (sans reculer, quand même :D ) et c'est même élargi à tout le réseau (moi, je reste en gare...).
Évidemment, le type de programmation est, lui aussi, très différent car il exploite à fond la programmation objets, héritage et pointeurs.
A ce propos, j'ai une question :
Certains itinéraires bouclés peuvent ne pas être trouvés quand un itinéraire possible est inclus. Ça n'est pas très grave. J'ai l'idée d'une variante pour les inclure tous mais je me pose la question de l'intérêt.
Pas compris...
-
Voici un exemple.
On cherche les chemins de A à B. quand on arrive sur la TJD0, les chemins que l'on va trouver dépendent de l'ordre d'exploration.
Si on commence du côté de la flèche rouge, on trouve la cible et la TJD mémorise un chemin partiel (B). Quand on explore côté flèche bleue, on retombe sur la TJD et on découvre le chemin partiel. Il est donc recopié et le chemin via la boucle est ajouté. On termine avec deux chemins, le direct (flèche rouge) et le bouclé (flèche bleue).
Si on commence côté flèche bleue, on retombe sur la TJD sans chemin partiel et on ne retourne pas de chemin. On explore côté flèche rouge et on trouve la cible. On termine avec un seul chemin.
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=311;image)
-
L'une des joies de l'informatique, c'est qu'on se rend compte que, nous, on raisonne de manière analogique (dans le sens pas complètement logique).
L'ordinateur raisonne, lui, de manière particulièrement logique, jusqu'à l'absurde dans ce cas.
La bonne nouvelle, c'est que le bon itinéraire est trouvé dans les deux cas, avec du rab pour l'une des solutions.
On a même de la "chance" qu'il ne fasse pas deux fois le tour ;D ;D
Non, ça n'est pas possible avec les marquages.
J'avais dit en rigolant "sans reculer, quand même", mais plus j'y réfléchis, plus je me demande si l'Arduino, en cherchant toutes les possibilités, ne va pas utiliser une boucle de retournement pour trouver un itinéraire "en reculant".
Exemple :
Il nous parait à tous évident qu'on ne peux pas aller de la VoieGarage8 à la VoieGarage9.
Mais si en cherchant, il trouve qu'en sortant VoieLibre5 on suit les rails jusqu'à revenir VoieLibre6, il va trouver que c'est possible !!
Parce qu'en fait, quand j'avais dit que VoieLibre6 <-> VoieLibre5 est une boucle de retournement, je ne pensais qu'au cas où on revenait vraiment sur ses pas.
Et, là, ça n'est pas le cas.
D'ailleurs quelque chose m'a choqué quand tu as fait ta deuxième version :
Dans la première, tu trouvais 18 itinéraires impossibles.
Moi qui compte les deux sens, j'en trouve 36. Donc on est d'accord.
Et dans ta deuxième version, tu noteras qu'il ne trouve plus que 14 impossibilités.
Il a dû trouver des machins comme ça.
-
L'une des joies de l'informatique, c'est qu'on se rend compte que, nous, on raisonne de manière analogique (dans le sens pas complètement logique).
L'ordinateur raisonne, lui, de manière particulièrement logique, jusqu'à l'absurde dans ce cas.
Je voie plutôt ça comme une force :D
La bonne nouvelle, c'est que le bon itinéraire est trouvé dans les deux cas, avec du rab pour l'une des solutions.
On a même de la "chance" qu'il ne fasse pas deux fois le tour ;D ;D
Mais tous ces itinéraires sont valables, celui avec 1 tour, celui avec 2 tours, ... ceux avec N tours. Le seul qui n'est pas valable est celui avec une infinité de tours :P
Non, ça n'est pas possible avec les marquages.
Eh oui car sans marquage, comme c'est un algorithme breadth-first (en profondeur d'abord), on commencerait par chercher si par hasard, celui avec une infinité de tours ne conviendrait pas :o
En pratique, il faudra couper des itinéraires. En effet, si on veut des itinéraires pour manœuvrer en gare, il ne s'agit pas de permettre ceux qui quittent la gare. Par exemple sur mon réseau j'ai un pont tournant et une gare terminus (le dépôt est à côté de la gare). Je voudrais automatiser la remise en tête de la locomotive via le pont tournant. Comme j'ai également des boucles de retournement, plusieurs itinéraires possibles sortent de la zone dépôt/gare pour aller se balader.
Avec le marquage, c'est facile d'interdire des voies, il suffit de les marquer comme déjà vues avant de lancer l'algorithme. Ça servira à enlever de la recherche les voies des cantons occupés et les voies menant à des parties non désirées.
-
Bonjour Jean-Luc
Je suis en train de décortiquer ton code, afin de bien comprendre. ;)
Je me pose une question par rapport à la fonction tousLesCheminsVers(). Dans l'objet "TraverseeJonctionDouble" tu as déclaré cette fonction comme protected alors que pour tous les autres objets "Voie" elle est déclarée en public. Y-a-t-il une raison particulière ?
Comme cette fonction (pour le moment) n'est appelée que par les objets "voie" en interne elle devrait peut-être être déclarée comme protected par tous les objets "Voie" ?
Dans le même ordre d'idée la fonction connecteDeVoie() qui n'est appelée (toujours pour le moment) que par les objets "Voie" pourrait (devrait ?) être déclarée comme protected ?
Clairement cela ne change rien pour le fonctionnement du code dans son état actuel, mais quand je me pose une question j'aime bien aller au bout, cela m'aide à progresser en C++ qui n'est pas mon langage de prédilection. ???
-
Bonjour Jack
Non, il n'y a pas de raison particulière. Je pense qu'à terme tousLesCheminsVers sera protected et appelée via une interface publique dans Voie (c'est déjà le cas avec cheminVers). C'est en développement, tout les petits tas de poussière ne sont pas nettoyés :)
-
Grand nouveauté sur Locoduino : un programme qui écrit … un programme Arduino !
Dès le début, j'ai bien aimé ce programme de Jean-Luc.
D'abord, il s'intéressait à une gare que je connaissais bien : la mienne … ;D ;D
(http://www.locoduino.org/IMG/jpg/gare_complete2.jpg)
Ensuite, comme expliqué, ce programme trouve tous les itinéraires, sans autre préalable que de décrire le réseau dans le .ino.
C'est-à-dire qu'il cherche tout seul tous les itinéraires possibles : on n'a pas besoin de les décrire un par un. Tant mieux, il y en a 241 ! :o
Cependant, cette description du grill de la gare, bien que d'une grande logique, n'est pas aussi simple qu'on le penserait de prime abord.
Aussi, je me suis dit que j'allais la faire écrire par l'ordi, sans intervenir directement. ;)
Je commence par du très simple : mettre tout ce qui concerne le réseau dans le même onglet.
Donc, je crée un onglet "Specifs" (sans accent).
Je mets dedans :
enum { … }
La création des objets (voies, aiguilles, TJD, …)
La table des sources
La table des destinations
Le void afficheNomVoie { … }
Jusque là, ce sont de simples copier-coller. On démarre cool.
Je mets tout au début du .ino un #include "Specifs.h" pour que l'Arduino s'y retrouve.
Pour les connexions des voie, cette fois dans le setup(), il faut créer un void()
Je crée donc void export_setup() { … } dans Specifs, que j'appelle depuis le setup().
Un dernier copier coller des connexions de voies et c'est fini.
Une vérification pour voir qu'on n'a rien oublié ni raté une ligne et le programme fonctionne comme avant. C'était bien la peine… :P
Mais, avez-vous remarqué que pour créer l'onglet dans l'IDE de l'Arduino, il ne vous a pas demandé le nom de l'onglet, mais le nom du fichier correspondant. Et c'est là qu'est la première astuce : tout ce que je dois créer, c'est un simple fichier texte : Specifs.h !
Si je veux changer de réseau, j'ai juste à changer de Specifs.h. C'est dur de faire plus simple.
Reste un "détail" : générer ce fichier…
C'est là que j'utilise mon programme de TCO en Processing.
En deux mots :
1°) Je dessine mon réseau, en positionnant des petits cubes.
(http://www.locoduino.org/IMG/jpg/gare_tco_sans_etiquettes.jpg)
2°) Je regroupe les cubes en cantons en leur affectant un numéro (de 101 à 255) et je numérote de la même façon les aiguilles (de 1 à 100). J'utilise la touche CTRL et la touche M (pour "memorize").
(http://www.locoduino.org/IMG/jpg/gare_tco_avec_etiquettes.jpg)
3°) Une petite analyse, pour voir s'il reste des erreurs (cubes isolés, …) et mise en forme des cantons.
Un simple appui sur A (pour "analysis"). Corrections des erreurs trouvées.
4°) Je sélectionne les voies entrantes de la gare, avec CTRL et quand je les ai toutes, j'appuie sur I (pour "in")
5°) Je sélectionne les voies sortantes de la gare, avec CTRL et quand je les ai toutes, j'appuie sur O (pour "out")
6°) J'appuie sur R (pour "Route", faux ami pour itinéraire).
Et c'est fini.
J'ai, non seulement un TCO sur mesure à l'écran, mais aussi un fichier Specifs.h !
L'affichage du TCO serait presque accessoire (alors que c'est quand même l'essentiel)…
Maintenant, je copie ce fichier Specifs.h pour remplacer celui existant dans la directory du programme Arduino. Et ça marche. ;D ;D
Quelques précisions :
1°) Le programme de Jean-Luc utilise des "voies libres", c'est-à-dire des voies qui sont bien reliées côté gare et "en l'air" vers l'extérieur.
Je n'ai pas retenu cette notion qui n'existe pas dans la réalité, mais dont je comprends parfaitement l'utilité dans ce programme, dans son état actuel.
Les curieux auront remarqué que j'ai donc mis des voies de garage à chaque entrée sortie. Pas très réaliste non plus… ???
C'est donc un point à creuser dans l'avenir.
2°) J'ai donc un peu modifié le programme de Jean-Luc en retirant les tests de debug au départ (qui font allusion aux voies libres). Mais qui ne sont pas nécessaires au fonctionnement.
3°) Evidemment, j'ai essayé avec le réseau de Dominique que j'utilise dans mes articles.
Le fichier Specifs.h est bien créé, mais il ne fonctionne pas avec l'Arduino.
Est-ce parce qu'il est bouclé ?? Je ne sais pas. :-[ :-[
4°) J'ai aussi changé le mot "aiguillage" que j'ai remplacé par "aiguille" (on n'est pas pinailleur pour rien :D). Je vais essayer d'ajouter les TJS et les triples, mais c'est plus sournois qu'il y paraît.
Et maintenant ?
"Que vais-je faire ?", disait Becaud.
Moi, rien.
Mais j'aimerais bien que Jean-Luc puisse trouver un peu de temps libre pour continuer son magnifique programme.
Parce qu'en l'état actuel, il trouve en un temps record tous les itinéraires d'une gare (et, j'en suis sûr, d'un réseau complet). Mais d'un point A à un point B, il en trouve "trop". Lequel choisir ?
Donc, à suivre. :P
En PJ : mon TCO en Processing, version 3.8 et le fichier de Jean-Luc avec les quelques modifs décrites et qui marche avec mon Specifs.h
-
Finalement, j'ai continué ;D
Parce que le réseau de Dominique ne marchait pas et que ça n'était pas dû au programme de Jean-Luc, mais au mien ... :(
J'ai donc retroussé mes manches et j'ai revu l'onglet Analysis qui a connu une simplification drastique.
Maintenant, c'est beaucoup plus simple, plus facile à comprendre et plus carré.
J'ai revu l'onglet routes et, là, seulement quelques bricoles.
C'est quand même sympa, la récursivité... 8)
Et maintenant, les deux fonctionnent parfaitement ;D ;D
J'ai volontairement retiré les // devant la trace de l'onglet debug => c'est plus long. Soyez patients : ça s'arrête bien à la fin dans la fenêtre du moniteur.
Vous pourrez toujours remettre les //, bien sûr.
Ce qui veut dire, entre autres, que le programme de Jean-Luc fonctionne avec un réseau bouclé.
A suivre :P
-
Bravo Denis,
Heureusement que tu peux faire les questions et les réponses, en ce qui concerne mon réseau, car je ne peux pas faire tourner Processing à cause de la version de Java que je ne peux (et veux) pas mettre à jour.
Alors tu peux me dire combien d'itinéraires sont possibles sur mon réseau ?
Amicalement
Dominique
-
Il en trouve 26 et 2 impossibles.
Mais je n'ai pas compris lesquels ... ???
Je m'explique :
1°) je te fournis le plan de ton réseau avec ma numérotation (celle du programme TCO et de SGDD).
2°) Je te fournis aussi le programme Arduino de Jean-Luc, avec la version ton réseau.
Celui-là, tu peux le téléverser sur un Arduino DUE et voir ce qu'il donne.
L'onglet Specifs.h est la description, "comme Jean-Luc" cette fois, de ton réseau.
Pour t'aider je te joins aussi le fichier tansform.txt qui est la traduction numérotation DD -> numérotation JLB.
(numérotation DD = 1000+numérotation DD du plan pour que tout soit bien aligné)
Ce fichier ne sert à rien d'autre qu'à nous aider, pauvres humains :)
Il est quand même généré par l'ordi, sans intervention humaine.
En retirant les // pour voir les tâches, tu verras comment travaille le programme de Jean-Luc.
Et tu comprendras ma réponse du début ;D
-
Trouvé les 25 :
(http://www.locoduino.org/IMG/jpg/tableau1.jpg)
Ce qui correspond à ce que je lui ai demandé :
Origine : VOIE_GARAGE_1, VOIE_GARAGE_5 et VOIE_GARAGE_6
Extrémité : VOIE_GARAGE_0, VOIE_GARAGE_2, VOIE_GARAGE_3 et VOIE_GARAGE_4
Et les deux impossibilités sont donc : VOIE_GARAGE_5 vers VOIE_GARAGE_0 ou VOIE_GARAGE_1, ainsi que VOIE_GARAGE_6 vers VOIE_GARAGE_0 ou VOIE_GARAGE_1
On peut demander individuellement ce qu'on veut (un peu plus haut dans le programme).
Ex VOIE_21 -> VOIE_20
Il trouve les 4 solutions :
Via la VOIE_2, la VOIE_3, la VOIE_4 ou la VOIE_5, prenant le périphérique intérieur ou le périphérique extérieur :D
Je savais que ce programme était génial ! Bravo Jean-Luc !
Pour transformer les numéros de voie DD -> nom des voies JLB, utiliser le fichier Transform.txt (post précédent).
Je conseille d'imprimer le plan avec mes numéros et d'écrire dessus les noms de Jean-Luc.
Comme ça, c'est plus facile à suivre.
Moyennant quelques modifs simples, je vais l'adapter au port série et lui faire échanger avec mon programme de commandes, cette fois.
Je lui demanderai sur le TCO par où je démarre (CTRL, clic souris sur le canton puis I (= in) et où je veux aller (CTRL, clic souris sur le canton puis O (= out))
Et il me sortira la liste des itinéraires.
Reste une question à la quelle on ne sait pas répondre : lequel choisir ? ???
"A que" on est bien embêtés :-\, d'autant que cette réponse doit être dynamique, en fonction des itinéraires demandés et des présences des autres trains...
A suivre :-*
-
Je prends un autre exemple :
Faire un circuit 107, 110, 112, 114, 115, 117, 124, 131.
On indique à la ligne 115 ce qu'on veut :
testItineraire(VOIE_4, VOIE_23);(en suivant bien ce que le fichier Transform.txt a dit)
Réponse dans la fenêtre du moniteur :
Gestionnaire reseau
Nombre de voies : 50
**** Test des ensembles ****
VOIE_4
AIGUILLE_10
VOIE_23
================
*vide*
================
Ajout de VOIE_23
================
VOIE_23
================
Ajout de AIGUILLE_10
================
VOIE_23 AIGUILLE_10
================
Ajout de VOIE_4
Qui se lit comme suit :
VOIE_4
AIGUILLE_10 = AIGUILLE_1 (les numéros d'aiguille sont multipliés par 10. Je ne sais pas quelle est la raison)
VOIE_23.
Puis la construction :
Ajout de VOIE_23
Ajout de AIGUILLE_10
Ajout de VOIE_4
C'est dans le sens DIRECTION AVANT.
Pour l'autre sens, il faut aller modifier la ligne 31 en DIRECTION_ARRIERE.
Et téléverser.
Ce qui donne dans le moniteur série, en vous faisant grêce du début :
================
VOIE_7 VOIE_9 VOIE_11 VOIE_12 VOIE_14 VOIE_19 VOIE_23 AIGUILLE_40 AIGUILLE_50 AIGUILLE_70 AIGUILLE_80 AIGUILLE_90 AIGUILLE_150 AIGUILLE_160
VOIE_7 VOIE_9 VOIE_11 VOIE_12 VOIE_14 VOIE_20 VOIE_23 AIGUILLE_40 AIGUILLE_50 AIGUILLE_70 AIGUILLE_80 AIGUILLE_90 AIGUILLE_150 AIGUILLE_160 TJD_0 TJD_1
VOIE_7 VOIE_9 VOIE_11 VOIE_12 VOIE_14 VOIE_17 VOIE_23 AIGUILLE_40 AIGUILLE_50 AIGUILLE_60 AIGUILLE_100 AIGUILLE_110 AIGUILLE_150
VOIE_7 VOIE_9 VOIE_11 VOIE_12 VOIE_14 VOIE_18 VOIE_23 AIGUILLE_40 AIGUILLE_50 AIGUILLE_60 AIGUILLE_110 AIGUILLE_150
================
Ajout de VOIE_4
Il y a cette fois 4 façons d'aller de la VOIE_4 à la VOIE_23.
On peut passer par la VOIE_17, la VOIE_18, la VOIE_19 et la VOIE_20
N'oubliez pas, les numéros d'aiguilles sont multipliés par 10...
Ce que je retiens, c'est que ce magnifique programme résout de façon entièrement automatique la problématique d'aller d'un point A à un point B, sur absolument n'importe quel réseau.
Il donne toutes les solutions.
S'agissant d'un cœur de programme, la partie intelligente si vous voulez, la partie communication avec l'extérieur, aussi bien en entrée qu'en sortie n'a pas été développée. Mais, justement, chacun peut développer la sienne.
J'ai apporté ma pierre en simplifiant l'entrée des données, elle aussi automatisée. On a juste à "jouer aux cubes"... ;D
Je vais m'attacher maintenant à communiquer avec ce programme Arduino via le bus série et mon programme "Commande.pde" écrit en Processing.
La suite sur mon post http://forum.locoduino.org/index.php?topic=211.0 (http://forum.locoduino.org/index.php?topic=211.0) :P
-
"Houston ?
We have a problem"... :(
J'ai progressé dans ma compréhension du fonctionnement du programme de Jean-Luc.
Je pense même que j'ai trouvé comment choisir le meilleur itinéraire parmi ceux trouvés.
Mais je bloque sur la façon de programmer cette fonction.
Le point aujourd'hui :
Il y a 93 éléments dans ma gare :
- 37 voies normales (ou de liaisons).
- 10 "voies libres", selon la dénomination de Jean-Luc, qui sont vouées, à terme, à devenir des voies normales.
Mais qui, en l'état actuel du programme, sont nécessaires car elles évitent d'avoir à décrire le reste du réseau.
- 11 voies de garage
- 15 aiguilles
- 17 TJD
- 3 croisements
Comme on donne en clair les éléments au départ (maintenant dans Specifs.h), le programme n'a aucun mal à les dénombrer.
Il crée une matrice uniligne pour marquer ces éléments.
Au départ, un peu trop grande (il ne sait pas combien d'éléments il va trouver), puis retaillée au bon format, à savoir 24 octets ici.
(Au passage : Excellente idée, à réutiliser sans modération).
En effet, à 2 bits par élément, il faut au moins 93*2 bits, soit un peu moins de 24 octets.
Les bits d'ordre pair marquent le fait qu'on utilise un élément en y mettant un 1.
Les bits d'ordre impair marquent le sens dans lequel on parcoure l'élément.
Si vous voulez voir ça, il faut ajouter dans l'onglet Debug :
#define TRACE2
Comme cette matrice est triée dans l'ordre donné plus haut (voies, voies libres, voies de garage, aiguilles, TJD, croisements), il s'ensuit que quand on donne la liste des éléments formant l'itinéraire, cette liste est triée de cette façon.
Mais il manque d'autres notions si on veut utiliser mon idée.
Un bon schéma valant plus qu'un discours, je (re)prends l'exemple de ma gare.
(http://www.locoduino.org/IMG/jpg/gare_complete2.jpg)
Je veux aller de la voieLibre0 vers la voieGarage6 sur ce schéma.
L'Arduino me trouve quand même pas moins de 12 (!!) façons de réaliser cet itinéraire.
################
De VOIE_LIBRE_0 a VOIE_GARAGE_6
================
VOIE_LIBRE_0 VOIE_0 VOIE_3 VOIE_21 VOIE_30 VOIE_34 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_10 AIGUILLE_14 TJD_0 TJD_8 TJD_12 TJD_14 CROISEMENT_2
VOIE_LIBRE_0 VOIE_0 VOIE_3 VOIE_21 VOIE_29 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_14 TJD_0 TJD_8 TJD_12 TJD_14 TJD_16 CROISEMENT_2
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_12 VOIE_26 VOIE_30 VOIE_34 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_10 AIGUILLE_14 TJD_0 TJD_1 TJD_2 TJD_11 TJD_14
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_12 VOIE_26 VOIE_29 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_14 TJD_0 TJD_1 TJD_2 TJD_11 TJD_14 TJD_16
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_18 VOIE_25 VOIE_28 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_8 AIGUILLE_14 TJD_0 TJD_1 TJD_2 TJD_4 TJD_6 TJD_10 TJD_16 CROISEMENT_0
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_19 VOIE_28 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_8 AIGUILLE_14 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_16
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_20 VOIE_26 VOIE_29 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_14 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_11 TJD_14 TJD_16
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_20 VOIE_26 VOIE_30 VOIE_34 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_10 AIGUILLE_14 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_11 TJD_14
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_8 VOIE_29 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_14 TJD_0 TJD_1 TJD_12 TJD_14 TJD_16 CROISEMENT_2
VOIE_LIBRE_0 VOIE_0 VOIE_2 VOIE_8 VOIE_30 VOIE_34 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_10 AIGUILLE_14 TJD_0 TJD_1 TJD_12 TJD_14 CROISEMENT_2
VOIE_LIBRE_0 VOIE_1 VOIE_21 VOIE_29 VOIE_33 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_14 TJD_8 TJD_12 TJD_14 TJD_16 CROISEMENT_2
VOIE_LIBRE_0 VOIE_1 VOIE_21 VOIE_30 VOIE_34 VOIE_GARAGE_6 AIGUILLE_0 AIGUILLE_10 AIGUILLE_14 TJD_8 TJD_12 TJD_14 CROISEMENT_2
================
J'affirme que l'itinéraire suivant, venant de la gauche, est le meilleur :
VoieLibre0 -> Aiguille0 (droite) -> Voie1 -> TJD8 (tout droit) -> Voie21 -> Croisement2 -> TJD13 (droite) -> Voie30 -> Aiguille10 (gauche) -> Voie34 -> Aiguille14 (talon) -> VoieGarage6.
Et pourquoi est-ce le meilleur ?
Parce qu'il réserve le maximum de place aux autres itinéraires. Il améliore donc grandement la fluidité des déplacements.
Donc, le raisonnement est le suivant :
Quand on vient de la gauche, il faut tourner le plus rapidement possible à droite (pour dégager la première diagonale) et ainsi de suite.
Evidemment, quand on vient de la droite, il faut tourner le plus rapidement possible à gauche. ;D ;D
Ce qui suppose d'amener ces deux notions dans le programme de Jean-Luc :
- sortie d'un élément multiple (aiguille, TJD, croisement) par la gauche ou la droite
- ordre dans lequel les éléments sont abordés par le train
Il y a en effet dans mon raisonnement une notion d'ordre. Il ne suffit pas de compter le nombre de fois où on tourne à droite, par exemple. Il faut aussi savoir si c'est au début, ou pas, de l'itinéraire.
Tourner à droite est d'autant plus efficace qu'on le fait tôt.
Donc, j'ai modifié les dessins du début de ce fil, pour tenir compte de la gauche et de la droite.
Voici mes nouveaux schémas (moins beaux, OK) :(
(http://www.locoduino.org/IMG/jpg/entrees-sorties_dd.jpg)
On remarque que, maintenant, je distingue les aiguilles gauches des aiguilles droites.
Dans le programme, on garde aussi Droit et Dévié pour tenir compte des longueurs des branches.
J'ai donc une nouvelle version de TCO qui génère le nouveau fichier Specif.h et, bien sûr, la nouvelle version de Gestionnaire_JLB_DD.ino.
Par exemple, de la voie de garage 0 (dans ma notation) à la voie de garage 16 (dans ma notation), ça donne :
###################################################
De VOIE_GARAGE_0 a VOIE_GARAGE_16
================
VOIE_0 VOIE_3 VOIE_21 VOIE_30 VOIE_34 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_2 AIGUILLE_D_70 AIGUILLE_G_00 AIGUILLE_G_40 TJD_0 TJD_8 TJD_12 TJD_14
VOIE_0 VOIE_3 VOIE_21 VOIE_29 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_2 AIGUILLE_D_70 AIGUILLE_G_00 TJD_0 TJD_8 TJD_12 TJD_14 TJD_16
VOIE_0 VOIE_2 VOIE_6 VOIE_12 VOIE_26 VOIE_30 VOIE_34 VOIE_GARAGE_0 VOIE_GARAGE_16 AIGUILLE_D_70 AIGUILLE_G_00 AIGUILLE_G_40 TJD_0 TJD_1 TJD_2 TJD_11 TJD_14
VOIE_0 VOIE_2 VOIE_6 VOIE_12 VOIE_26 VOIE_29 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 AIGUILLE_D_70 AIGUILLE_G_00 TJD_0 TJD_1 TJD_2 TJD_11 TJD_14 TJD_16
VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_18 VOIE_25 VOIE_28 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_0 AIGUILLE_D_40 AIGUILLE_D_70 AIGUILLE_G_00 TJD_0 TJD_1 TJD_2 TJD_4 TJD_6 TJD_10 TJD_16
VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_19 VOIE_28 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 AIGUILLE_D_40 AIGUILLE_D_70 AIGUILLE_G_00 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_16
VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_20 VOIE_26 VOIE_29 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 AIGUILLE_D_70 AIGUILLE_G_00 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_11 TJD_14 TJD_16
VOIE_0 VOIE_2 VOIE_6 VOIE_11 VOIE_16 VOIE_20 VOIE_26 VOIE_30 VOIE_34 VOIE_GARAGE_0 VOIE_GARAGE_16 AIGUILLE_D_70 AIGUILLE_G_00 AIGUILLE_G_40 TJD_0 TJD_1 TJD_2 TJD_4 TJD_7 TJD_11 TJD_14
VOIE_0 VOIE_2 VOIE_8 VOIE_29 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_2 AIGUILLE_D_70 AIGUILLE_G_00 TJD_0 TJD_1 TJD_12 TJD_14 TJD_16
VOIE_0 VOIE_2 VOIE_8 VOIE_30 VOIE_34 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_2 AIGUILLE_D_70 AIGUILLE_G_00 AIGUILLE_G_40 TJD_0 TJD_1 TJD_12 TJD_14
VOIE_1 VOIE_21 VOIE_29 VOIE_33 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_2 AIGUILLE_D_70 AIGUILLE_G_00 TJD_8 TJD_12 TJD_14 TJD_16
VOIE_1 VOIE_21 VOIE_30 VOIE_34 VOIE_GARAGE_0 VOIE_GARAGE_16 CROISEMENT_2 AIGUILLE_D_70 AIGUILLE_G_00 AIGUILLE_G_40 TJD_8 TJD_12 TJD_14
================
Information importante :
Le choix d'un itinéraire ne peut pas être fixe, à partir d'une liste qu'on donnerait dès le départ.
Dans le cas précédent, on a trouvé qu'il fallait passer par la voie 1. Et décrit l'itinéraire qui passe par là.
Supposons qu'on ait perdu un wagon justement voie 1. Si le choix de l'itinéraire est fixé, il faudra attendre d'avoir dégagé le wagon de la voie 1 pour pouvoir faire l'itinéraire de la voie de garage 0 à la voie de garage 16.
Si l'allocation d'itinéraire est dynamique, le programme va passer par la voie 3 et le tour est joué.
Il s'ensuit que la définition des itinéraires va devoir tenir compte des occupations de zones…
Et voilà
Je suis donc dans une situation où j'ai une idée très précise de ce qu'il faudrait faire … sans savoir le faire !
"Houston ?
We have a problem"… :(
-
Jean-Luc étant bien occupé, j'ai continué de mon côté. :D
J'ai employé l'artillerie lourde en mettant des Serial.print partout.
J'arrive maintenant à suivre le cheminement de manière plus précise.
Dans ce que j'ai dit dans mon précédent post, il y a des erreurs.
En fait c'est beaucoup plus "Siouxe" que ça. Mais il fallait comprendre… ???
Il y a, entre autres, deux ensembles de voies :
EnsemblesDeVoies et EnsembleDeVoiesOrientées
Le premier enregistre les voies qui ont été sélectionnées par identifiant
Le deuxième enregistre les voies qui ont été sélectionnées par identifiant et par sens.
La place utilisée est réduite à sa plus simple expression 1 bit par voie et 1 bit par sens.
EnsembleDeVoies :
J'ai dans ma gare 93 éléments, ce qui correspond à 93/8 = 11,625 soit 12 octets.
L'élément d'identifiant 0 (VOIE_LIBRE_0) est en octet 0, bit 0.
L'élément d'identifiant 1 (VOIE_LIBRE_1) est en octet 0, bit 1.
…
L'élément d'identifiant 10 (VOIE_0) est en octet 1, bit 2.
…
L'élément d'identifiant 59 (AIGUILLE_0) est en octet 7, bit 2.
…
Mais comment s'y retrouver ?
Pour trouver l'octet, c'est assez simple :
identifiant >> 3 correspond à une division par 8 (= 2^3).
Par exemple 59/8 = 7,375 : on est bien octet 7.
En fait, c'est comme prendre la partie entière.
Pour le rang du bit, ça commence à se compliquer :
mEnsemble[identifiant >> 3] |= 1 << (identifiant & 7);
On commence par identifiant & 7 :
(http://www.locoduino.org/IMG/jpg/identifiant_7.jpg)
On remarque que le résultat varie périodiquement de 0 à 7
Donc 1 << (identifiant & 7) place un 1 dans la bonne colonne correspondant à l'identifiant
Par exemple 59 donne colonne 3, soit le bit 2.
En fait, c'est comme prendre la partie décimale.
Et mEnsemble[identifiant >> 3] |= 1 << (identifiant & 7); veut dire :
mEnsemble[identifiant >> 3] = (mEnsemble[identifiant >> 3]) | (1 << (identifiant & 7));
On place un 1 dans l'octet 7, bit 2.
Très efficace, mais, comment dire, "pas immédiat". :o
EnsembleDeVoiesOrientees :
Beaucoup de ressemblances, mais on a cette fois 2 bits à mettre.
On aurait pu croire que le sens allait se mettre sur 1 bit (AVANT/ARRIERE), mais il faut tenir compte du fait qu'on va chercher le sens et l'identification d'un élément.
On a donc :
00 : pas d'élément défini et donc pas de sens défini
01 : un élément défini et DIRECTION_AVANT
10 : un élément défini et DIRECTION_ARRIERE
Au lieu de mettre 8 identifiants par octet, on ne pourra en mettre que 4 (2 bits/identifiant).
La taille de l'ensemble va donc être 2 fois plus grande.
Donc les Voie::taille() de l'ensemble des voies va devenir 2 * Voie::taille().
taille() valant toujours 12, on a cette fois 24 octets.
Et on a mEnsemble[(identifiant >> 2)] |= 1 << (((identifiant & 3) << 1) + sens );
Pour l'octet, on passe de [identifiant >> 3] à [identifiant >> 2] puisqu'on divise maintenant par 4.
Pour le bit, & 3 donne comme résultat 0, 1, 2, 3, 0, 1, 2, 3, 0…
Et on ajoute le bit de sens.
Petit exercice inverse : afficher, dans l'EnsembleDeVoiesOrientees, tous les identifiants et leur sens à partir du tableau :
void EnsembleDeVoiesOrientees::print()
{
bool ensembleVide = true;
for (byte i = 0; i < 2 * Voie::taille(); i++) {
byte sousVecteur = mEnsemble[i];
for (byte j = 0; j < 4; j++) {
byte identifiant = (i << 2) + j;
if (sousVecteur & (1 << (2 * j))) {
ensembleVide = false;
afficheNomVoie(identifiant);
Serial.print('/');
afficheSens(DIRECTION_AVANT);
Serial.print(' ');
}
if (sousVecteur & (1 << ((2 * j) +1))) {
ensembleVide = false;
afficheNomVoie(identifiant);
Serial.print('/');
afficheSens(DIRECTION_ARRIERE);
Serial.print(' ');
}
}
}
if (ensembleVide) {
Serial.print("*vide*");
}
}
Analyse :
Pour les octets, on va de i = 0 à i = 2 * Voie::taille().
On définit un sousVecteur mEnsemble[ i ]
Les infos vont de j = 0 à j = 4 (soit 4 infos par octet)
L'identifiant est donc égal à (i << 2) + j;
i << 2 pour le rang de l'octet : normal car on divise par 4.
On ajoute j pour être dans le bon "double bit".
Pour le sens, c'est un peu plus compliqué :
1 << (2*j) donne :
00000001 pour j = 0
00000100 pour j = 1
00010000 pour j = 2
01000000 pour j = 3
sousVecteur & (1 << (2 * j)) va donc récupérer le bit de droite du double bit, soit DIRECTION_AVANT
Et 1 << (2 j) + 1 donne :
00000010 pour j = 0
00001000 pour j = 1
00100000 pour j = 2
10000000 pour j = 4
sousVecteur & (1 << ((2 * j) +1)) va donc récupérer le bit de gauche du double bit, soit DIRECTION_ARRIERE
Bien content d'avoir compris ça … ;D ;D
Je vais donc pouvoir créer EnsembleDeVoiesSorties sur ce modèle, avec :
00 : pas d'élément défini et donc pas de sortie définie
01 : un élément défini et SORTIE_DROITE
10 : un élément défini et SORTIE_GAUCHE
11 : un élément défini et SORTIE_MILIEU pour les voies normales et le triple
Au boulot ! :P
-
Une étape a été franchie ! ;D ;D ;D ;D
Je me suis plongé dans le programme de Jean-Luc :
Une programmation objet avec polymorphisme, des récurrences et même des récurrences imbriquées…
Le résultat est un programme compact et efficace, mais, comme dire, … pas immédiat. :o
La place occupée en mémoire est limitée en deux temps :
Dans le cas de ma gare, il y a 93 éléments :
- 8 aiguilles droites
- 7 aiguilles gauches
- 17 TJD
- 3 croisements
- 37 voies de liaison
- 21 voies de garage
Conseil d'ami : Je ne saurais trop vous conseiller d'imprimer le schéma des voies, sinon, vous allez avoir du mal à suivre les exemples. ;)
(http://www.locoduino.org/IMG/jpg/gare_denis_numerotee.jpg)
Ils sont décris en seulement 12 octets (8 x 12 = 96) dans un "EnsembleDeVoies" et, en tenant compte du sens de déplacement, dans 24 octets (12 x 2) d'un "EnsembleDeVoiesOrientees".
Donc, au départ, Jean-Luc réserve par défaut 256 bits.
Puis, dans le enum{…}, on compte 93 éléments et via malloc et realloc, on le retaille à 96 bits dans la classe Voie(). On ne peut pas prendre moins de place. :D
Le classement dans le enum{…} n'est pas, ici, anodin. C'est lui qui va donner l'ordre d'affichage des éléments dans la description des itinéraires de Jean-Luc. J'expliquerai plus loin pourquoi je l'ai modifié.
Par manque de temps, ce programme n'a pas été terminé.
J'ai donc cherché à avancer, mais avec des méthodes moins sophistiquées, en utilisant les résultats du programme de Jean-Luc.
Il faut, en effet, ajouter deux notions fondamentales :
1°) Donner l'orientation des aiguilles. C'est indispensable si on veut leur envoyer l'ordre d'aiguillage. ::) ::)
2°) Afficher les itinéraires dans l'ordre du parcours. Deux raisons à cela :
- Donner une note aux itinéraires pour savoir quel est le meilleur choix.
- Un peu moins nécessaire, mais ça fera plus joli quand on déclenchera les aiguilles les unes après les autres.
Si on suit bien le programme, on constate qu'à aucun moment la liste des itinéraires pour aller d'un point A à un point B n'est mémorisée.
Une seule ligne est calculée et mémorisée (c'est element[ i ]), affichée et effacée pour afficher la ligne suivante.
J'ai donc créé une matrice qui mémorise 15 itinéraires de 25 éléments, soit 375 bytes.
En faisant ça, j'ai eu l'impression de finir un lustre en cristal de Baccarat avec des pièces en plastique ! :P :P
Pour information, le couple qui donne le plus grand nombre d'itinéraires est de VOIE_GARAGE_0 vers VOIE_GARAGE_16, avec 12 (!) solutions.
Et le plus grand, toujours pour ce couple, compte 21 éléments.
Ces deux informations expliquent la taille de la matrice.
Via malloc et realloc, je pourrais la retailler à 252 octets, mais ça n'est pas fait pour l'instant.
Cette fois, il va falloir conserver le numéro de l'élément et sa position pour les aiguilles, dans un seul byte.
J'ai trouvé les principes suivants pour indexer 50 aiguilles et 100 voies (c'est déjà pas mal) :
1°) Je construis le enum{…] en commençant par les aiguilles. Je rappelle qu'il est généré automatiquement par le programme TCO en Processing.
Dans ma gare, 8 + 7 + 17 + 3 = 35, qui est bien < 50.
2°) Je mets les voies à la suite, en commençant donc à 36 jusqu'à 93.
Et 93 - 35 = 58 est bien < 100. On est donc dans les clous.
3°) Quand on sort d'une aiguille par la gauche, on ajoute 150 au numéro de l'élément
Quand on sort d'une aiguille par la droite, on ajoute 200 au numéro de l'élément.
Par exemple, la première aiguille gauche sera notée 9 quand on en sort par la pointe, 159 quand on en sort par la branche déviée et 209 quand on en sort par la voie directe.
On peut même indexer de cette façon les aiguilles triples, non traitées dans le programme jusqu'à maintenant. ;)
Vous pourrez ainsi tester et vous verrez qu'aucun nombre n'est ambigu. Et vous voyez aussi pourquoi j'ai mis les aiguilles dans les 50 premiers dans le enum{...}.
Pour zéro, c'est vide dans l'impression.
Passons à l'analyse du programme de Jean-Luc :
Avec 9 entrées pour 12 sorties, on s'attend à 9 x 12 = 108 itinéraires.
Comme il y en a 18 d'impossibles (ex VOIE_GARAGE_0 vers VOIE_GARAGE_9), il reste 90 couples origine - extrémité, chacun pouvant avoir plusieurs solutions.
Première bonne nouvelle :
Pour chaque couple (parmi 90 couples), le "meilleur itinéraire" (voir post précédent) est le dernier de la liste. Hasard ?
Deuxième bonne nouvelle :
Le meilleur itinéraire est le premier calculé ! Hasard ?
Vous avez tous été faire des courses dans un hyper et vous êtes forcément déjà tombé sur un caddie dont une roue est plus ou moins bloquée et vous tombez sur un "tourne à droite" ou un "tourne à gauche".
Et bien, le programme de Jean-Luc est un "tourne à droite" !
Ce qui explique la deuxième bonne nouvelle, étant donné la définition du meilleur itinéraire.
Et aussi la première puisqu'ils sont affichés dans l'ordre inverse.
Je sens déjà poindre une objection : mais pourquoi une matrice, alors ?
Si tourner à droite est une bonne idée en allant de la gauche vers la droite, ce n'est pas forcément une bonne idée quand on va dans l'autre sens…
Et il me fallait comparer mes sorties avec celles de Jean-Luc.
Dernière raison : au moment où j'écris, je ne suis pas sûr que les bonnes nouvelles soient toujours vraies quand il faudra y intégrer les occupations de cantons. On verra.
Analyse du programme :
Pour voir comment fonctionne le programme version Jean-Luc, il faut afficher, dans l'onglet Debug, DEBUG, TRACE et TRACE2.
Mais uniquement sur un seul couple A - B sous peine d'engorgement.
J'ai évidemment choisi VOIE_GARAGE_O vers VOIE_GARAGE_16 et ses 12 solutions.
On voit tout le déroulement, chaque élément choisi est affiché, avec une indentation croissante, que Jean-Luc appelle "profondeur" de l'itinéraire.
La première phase est donc simple : la profondeur va donner l'indice des colonnes dans la matrice.
Quand le cheminement arrive dans un cul de sac, le système repart du dernier de direction choix fait.
Et, donc, chaque nouveau cheminement efface l'ancien.
Voir le programme "GestionnaireReseau_JLB-DD_V2_1_AV_TR3.ino"
Pour être précis, deux choses sont à prendre en compte :
1°) On n'efface pas tout depuis le début (surtout pas !), mais juste le nouveau cheminement.
2°) Il faut penser à changer la position des aiguilles quand on avance à nouveau.
Exemple du début :
On part de la VOIE_GARAGE_0 et on finit VOIE_GARAGE_12. Il faut reculer.
On avait pris la VOIE_22 et, maintenant, on prendra la VOIE_21 qui va effacer la VOIE_22, puisque c'est la même profondeur (=> même colonne dans la matrice).
Mais TJD_8/D, vers la voie 22, donc doit devenir TJD_8/G vers la VOIE_21.
Ce qui se fait simplement en retirant 50 à TJD_8 qui vaut 24 au départ (d'après le enum{…}).
Il passe donc de 224 à 174.
Le cheminement bute ensuite sur l'AIGUILLE_G_50.
Pourquoi ? Ce n'est pas une voie de garage !?
Parce que ce programme démoniaque remarque qu'il est déjà passé par l'AIGUILLE_G_50 et que ça ne menait à rien !! ;)
Le cheminement bute ensuite sur la VOIE_GARAGE_13, VOIE_GARAGE_14.
Là, on recule un grand coup jusqu'au CROISEMENT_2.
Puis on bute sur VOIE_GARAGE_15.
Et, enfin, via la VOIE_34, on arrive à VOIE_GARAGE_16.
Donc, les bons cheminements ont effacé petit à petit les mauvais choix et il a fallu modifier les orientations de TJD_8, TJD_12.
Normalement, on a fini, c'est le meilleur itinéraire.
J'ai expliqué plus haut pourquoi on cherchait tous les itinéraires.
Et, là, ça se corse, comme disait Napoléon !
D'abord, il fallait trouver où la machine sortait les bons éléments, au fil de l'eau.
C'est au moment du marquage, dans chaque classe, là où j'ai ajouté mon traitement "noteAjoutBonneAiguille(0, sortie, profondeur, idVoie());", ligne 440 dans Voie.cpp.
0 : on va dans le sens gauche -> droite
sortie : donné une ligne au dessus. C'est là qu'on garde l'info de direction de sortie, elle même fonction du connecteur utilisé.
profondeur : indice de la colonne
idVoie() : indice de la voie
Il en faut un à chaque marquage et aussi quand on est arrivé au bout (ligne 433).
Maintenant que je vous l'ai expliqué, vous allez croire que c'était facile…
Et a suite ?
C'est un peu plus loin, quand il y a "Serial.println(F("$$$$ Chemin partiel"));" (ligne 790).
Là, on ajoute une ligne dans la matrice par "ajouteItineraireMatrice();"
Il faut ajouter une ligne, mais elle ne va pas jusqu'au bout.
Pourquoi ?
Parce qu'on arrive sur des éléments déjà visités.
Il va falloir compléter. Et avec quoi ?
Avec la fin de ligne qu'on a déjà créée ! ;)
En effet, on est maintenant avec un itinéraire déjà trouvé.
Il suffit de prendre l'élément terminal, là où on a bloqué, comme pivot.
Facile ! Et on continue…
Que nenni !
Parce que maintenant, on a deux itinéraires complets et donc deux façons de terminer !
Dans le premier exemple, on a le choix en passant par la VOIE_29 et TJD_16 ou la VOIE_30 et AIGUILLE_G_40.
Donc, pour la VOIE_1, on a ces deux solutions (on vient de les construire).
Et, quand on va trouver via la VOIE_3, on va avoir ces deux solutions aussi.
En fait, on doit rechercher le pivot qu'on vient de trouver dans toutes les propositions précédentes pour ne pas oublier de possibilités de finir un début d'itinéraire.
Résumé jusqu'à présent :
VOIE_1 … TJD_14/D VOIE_30 AIGUILLE_G_40/G VOIE_34 AIGUILLE_D_70/M VOIE_GARAGE_16
VOIE_1 … TJD_14/G VOIE_29 TJD_16/D VOIE_33 AIGUILLE_D_70/M VOIE_GARAGE_16
VOIE_3 … TJD_14/D VOIE_30 AIGUILLE_G_40/G VOIE_34 AIGUILLE_D_70/M VOIE_GARAGE_16
= début VOIE_3 + 1ere fin VOIE_1
VOIE_3 … TJD_14/G VOIE_29 TJD_16/D VOIE_33 AIGUILLE_D_70/M VOIE_GARAGE_16
= début VOIE_3 + 2eme fin VOIE_1
Et, si je continuais, j'aurais :
VOIE_3 … TJD_14/D VOIE_30 AIGUILLE_G_40/G VOIE_34 AIGUILLE_D_70/M VOIE_GARAGE_16
= début VOIE_3 + 1ere fin VOIE_3 !!
Mais on l'a déjà…
Et il faut donc l'effacer.
Cela se fait avec "ligneIdentique(byte ligneCourante)"
Quand je vous disais que ça n'était pas si facile que ça !
Et on remarquera que pour tous ces itinéraires, au début, on a deux solutions (VOIE_29 et VOIE_30) et puis, soudain, on a autre chose :
… VOIE_28 TJD16/D VOIE_33 AIGUILLE_D_7 VOIE_GARAGE_16.
Nous voilà maintenant avec 3 fins possibles.
Et voilà le résultat :
----------------------------------------------------------------------------------------------------------------------------------------------------------------
VOIE_GARAGE_0/M AIGUILLE_G_00/D VOIE_1/M TJD_8/G VOIE_21/M TJD_12/G CROISEMENT_2/G TJD_14/D VOIE_30/M AIGUILLE_G_40/G VOIE_34/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/D VOIE_1/M TJD_8/G VOIE_21/M TJD_12/G CROISEMENT_2/G TJD_14/G VOIE_29/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/D VOIE_3/M TJD_8/G VOIE_21/M TJD_12/G CROISEMENT_2/G TJD_14/D VOIE_30/M AIGUILLE_G_40/G VOIE_34/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/D VOIE_3/M TJD_8/G VOIE_21/M TJD_12/G CROISEMENT_2/G TJD_14/G VOIE_29/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/D VOIE_8/M TJD_12/G CROISEMENT_2/G TJD_14/D VOIE_30/M AIGUILLE_G_40/G VOIE_34/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/D VOIE_8/M TJD_12/G CROISEMENT_2/G TJD_14/G VOIE_29/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/G VOIE_6/M TJD_2/D VOIE_12/M TJD_11/G VOIE_26/M TJD_14/D VOIE_30/M AIGUILLE_G_40/G VOIE_34/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/G VOIE_6/M TJD_2/D VOIE_12/M TJD_11/G VOIE_26/M TJD_14/G VOIE_29/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/G VOIE_6/M TJD_2/G VOIE_11/M TJD_4/D VOIE_16/M TJD_7/D VOIE_20/M TJD_11/G VOIE_26/M TJD_14/D VOIE_30/M AIGUILLE_G_40/G VOIE_34/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/G VOIE_6/M TJD_2/G VOIE_11/M TJD_4/D VOIE_16/M TJD_7/D VOIE_20/M TJD_11/G VOIE_26/M TJD_14/G VOIE_29/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/G VOIE_6/M TJD_2/G VOIE_11/M TJD_4/D VOIE_16/M TJD_7/G VOIE_19/M AIGUILLE_D_40/M VOIE_28/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
VOIE_GARAGE_0/M AIGUILLE_G_00/G VOIE_0/M TJD_0/G VOIE_2/M TJD_1/G VOIE_6/M TJD_2/G VOIE_11/M TJD_4/G CROISEMENT_0/G TJD_6/D VOIE_18/M TJD_10/D VOIE_25/M AIGUILLE_D_40/M VOIE_28/M TJD_16/D VOIE_33/M AIGUILLE_D_70/M VOIE_GARAGE_16/M
----------------------------------------------------------------------------------------------------------------------------------------------------------------
Les 12 itinéraires y sont bien, dans l'ordre du calcul.
Ils sont décrits dans l'ordre de cheminement du train qui va les parcourir, en précisant, à chaque aiguille, si on sort par la gauche ou la droite !
Tout est prêt pour envoyer les ordres aux aiguilles !!
Mais on n'a pas fini.
Si on teste sur tous les itinéraires (faites tourner GestionnaireReseau_JLB-DD_V2_3_AV_TR3.ino), on va trouver les 239 itinéraires de la gare…
Sur ces 239, seuls 90 sont utiles (il n'y a que 90 couples entrée-sortie). Dans le sens gauche vers droite. Parce qu'il y a aussi l'autre sens !
En fait, à priori, il y a 180 itinéraires utiles parmi les 239.
Fort bien. Mais j'entends déjà des réflexions … ???
Maintenant qu'on a trouvé les 90 meilleurs itinéraires, on pourrait se passer du programme et les affecter chacun à un bouton (méthode Märklin).
Outre le fait qu'il faudrait 180 (!!) boutons, il reste un énorme problème :
Un wagon s'est détaché et reste sur la VOIE_1.
Si on a des itinéraires dont la définition est fixée une fois pour toutes, on ne peut plus aller de la VOIE_GARAGE_0 à la VOIE_GARAGE_16 !!
Et c'est là que l'affectation dynamique est formidable :
Un wagon décroché VOIE_1 ? Pas de problème : on va passer par la VOIE_3 !!
Mieux :
Pour aller chercher ce fameux wagon, je ne vais pas demander VOIE_GARAGE_0 vers une autre voie de garage, comme on aurait dû le faire avec des itinéraires fixés.
Je vais demander VOIE_GARAGE_0 vers … VOIE_1, tout simplement.
Et, ainsi, TJD_8 pourra servir à un autre itinéraire. On pourra aller chercher ce wagon perdu sans désorganiser toute la gare.
C'est quand même souple, non ?
J'aimerais qu'un spécialiste d'un célèbre logiciel en version Silver ou Gold me dise comment ils gèrent ce cas.
Je vais vous laisser ingurgiter tout ça.
Et je suis sûr que, maintenant, vous penserez à Locoduino en poussant le caddie… :P
-
On continue !
Gestion des occupations.
Il y a, dans le programme de Jean-Luc, deux types de "matrices" uniligne :
1°) EnsembleDeVoies qui compte 12 octets pour ma gare et qui ne sert plus, pour l'instant. On verra pourquoi plus loin.
2°) EnsembleDevoiesOrientees qui compte le double, soit 24 octets.
Cet EnsembleDeVoiesOrientees est marqué à l'aide de pointeurs, au fur et à mesure de la construction des itinéraires.
Ainsi, on ne peut pas passer plusieurs fois au même endroit.
Le moins que l'on puisse dire, c'est qu'on est économe en place mémoire pour cette importante fonction de gestion des itinéraires !
On a vu, dans le post de Jean-Luc le 26 mars un passage clé :
J'ai réfléchi aux boucles de retournement et je pense avoir trouvé une solution élégante et simple. J'ajoute une classe d'élément de voie : BoucleDeRetournement. Dans un parcours qui est une boucle de retournement, un élément de ce type doit être inséré. L'un des connecteurs est dans le sens normal mais l'autre doit être connecté à contresens.
Par exemple voici une boucle simple. On commence la construction par E. On connecte le SORTANT de E à l'ENTRANT de l'aiguillage A. On connecte le SORTANT_DROIT de A à l'ENTRANT de B. On connecte le SORTANT_GAUCHE de A à l'ENTRANT de C. On connecte le SORTANT de B sur l'ENTRANT de D et on connecte le SORTANT de C sur le SORTANT de D. Comme D est une instance de BoucleDeRetournement, cette dernière connexion doit être faite à contresens.
Ensuite pour le parcours des éléments, comme je l'ai dit, on décide d'un sens de parcours. Ainsi si on cherche E depuis A dans le sens normal, que va-t-il se passer ? On commence par explorer côté SORTANT_DROIT, on arrive sur B, on continue sur D. Là on a un probléme, si on continue sur C, on arrive dans C avec le sens normal et en faisant ça, C va continuer sur D et on part en boucle infinie (ou bien si l'algo joue au petit poucet, il stoppe car il passe deux fois par un élément et il ne trouve pas. Comment faire ? c'est assez simple, il suffit d'inverser le sens de parcours quand on traverse un élément BoucleDeRetournement (ça servira aussi à commuter l'alim d'ailleurs :-)). Donc avant que D appelle C, il retourne le sens. C continuera donc avec A qui continuera avec E et E est trouvé. Du côté de la branche SORTANT_DEVIE, on arrive sur C qui appelle D, qui inverse le sens et appelle B qui appelle A et E est également trouvé. Deux chemins possibles, donc, selon le sens de parcours de la boucle de retournement.
On a maintenant un nouveau problème. Si on joue au petit poucet en notant les éléments parcourus pour ne pas passer deux fois par les mêmes éléments et permettre à l'algorithme de terminer, on va arrêter sur A. Comment faire ? C'est pas compliqué non plus, il ne faut pas marquer seulement les éléments mais le couple élément/sens de parcours. ainsi quand on parcoure A dans le sens normal, on marque A/normal. Quand on le reparcoure dans le sens inverse, on marque A/inverse. Donc deux marquages différents qui font qu'on ne va pas reconnaître A en le parcourant en sens inverse.
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=289;image)
C'est pour cela que les pointeurs sont orientés : c'est le seul moyen de marquer correctement les éléments d'une boucle de retournement.
Ce qui explique aussi pourquoi EnsembleDeVoies ne sert plus : on ne pouvait pas marquer les boucles de retournement.
Mais il va me resservir à gérer les occupations et mettre des limites aux zones d'itinéraires.
J'utilise, là aussi, une remarque fondamentale de Jean-Luc, dans son post du 04 avril :
Avec le marquage, c'est facile d'interdire des voies, il suffit de les marquer comme déjà vues avant de lancer l'algorithme. Ça servira à enlever de la recherche les voies des cantons occupés et les voies menant à des parties non désirées.
En marquant certains éléments, la recherche d'itinéraires va les "oublier".
Je vais donc utiliser cette importante fonction pour :
1°) Délimiter la zone d'action de la recherche et lui éviter d'aller se perdre dans tout le réseau.
On a ainsi une seule description du réseau total et on "zoome" dessus pour trouver les itinéraires qui nous intéressent.
Au début, parce que je n'avais pas compris comment ça marchait, j'avais mis des voies de garage à toutes les extrémités de la zone d'itinéraire. Je contenais ainsi la recherche. Mais, maintenant, ça n'est plus nécessaire : je pourrais délimiter la zone en ajoutant tel ou tel élément dans cette "matrice" uniligne.
2°) On va pouvoir aussi utiliser cette "matrice" pour gérer les occupations. Si un élément est occupé, l'itinéraire ne passera pas par là.
Application :
Comme vous l'avez remarqué depuis l'origine, tout se passe dans le setup(). Et donc, une seule fois, au début. Pour les explications, c'est parfait, mais plus en temps normal.
Passons donc dans la loop() pour suivre les occupations.
La fonction essentielle est :
void testItineraire(byte source, byte destination, byte voiesOccupees[16]){…}
Qui va de "source" à "destination" en ignorant les "voiesOccupees".
On a besoin d'une matrice supplémentaire : matriceOccupations[16].
Etant donné le soin pris à ne pas utiliser trop de mémoire pour la gestion, j'ai conservé le système de Jean-Luc.
J'ai pris [16] pour pouvoir gérer 128 éléments (= 16 octets, soit 128 éléments gérables).
Je ne me suis pas encore penché suffisamment sur malloc/realloc pour qu'on n'ait que 12 octets pour les 93 éléments de ma gare. Mais c'est faisable.
J'imagine que certains se demandent : "pourquoi utiliser une autre matrice ?"
Parce qu'il n'est pas question de modifier les éléments occupés pendant qu'on calcule les itinéraires, sous peine de gabegie !
Donc, la matriceOccupation[16] récupère les infos au fil de l'eau (via le bus CAN) et on prend une "photo" de la matrice AVANT de calculer les itinéraires.
void testItineraire(…){…} utilise une méthode essentielle :
Voie::voirParIdentifiant(source).cheminsVers(destination, DIRECTION_AVANT, iti, occ);
On la retrouve en méthode liée à la classe Voie, en "static" parce qu'un peu spéciale.
J'avoue que la méthode employée n'est pas du tout simple à comprendre.
J'ai mis "un certain temps", comme dirait le regretté Fernand Reynaud.
Mais ça marche.
Pour tester (et uniquement pour tester !) j'ai mis en exemple 3 x ajouteVoie(…) qu'on peut valider ou dévalider pour voir les impacts de telle ou telle occupation.
On utilisera évidemment les infos du bus CAN pour "ajouter" les occupations à la matriceOccupations[16].
De même, enleveVoie(…) pour la fin d'occupation.
Je vous laisse apprécier la méthode employée (copiée tout bêtement sur celle de Jean-Luc, dans l'onglet "EnsembleDeVoies") :
void ajouteVoieOccupee(byte voieOccupee)
{
matriceOccupations[voieOccupee >> 3] |= 1 << (voieOccupee & 7);
}
Temps d'exécution :
Sans rien afficher : calcul des 12 itinéraires en 5,2 millisecondes !!
On verra dans un prochain post une méthode pour trouver le meilleur itinéraire, celui qui amène le maximum de fluidité dans une grande gare, en calculant le plus souvent un itinéraire, voire 2 ou 3 au maximum.
Maintenant, il va falloir tenir compte aussi des fonctions évoluées (enclenchements et des autorisations). :-*
-
Trouver le meilleur itinéraire…
Vaste question ! :o
Pour moi, le meilleur itinéraire est celui qui bloque le moins un grill de gare.
C'est à dire que quand on programme un itinéraire, on doit laisser de la place aux autres, au cas où…
Notez que je j'ai dit "grill de gare" et pas "gare".
Pour moi, et par la suite, dans ce post, je ne parlerai que de grills de gare, c'est-à-dire d'un point A EXTERIEUR à une gare à un point B DANS la gare. Et réciproquement.
Dans la gare qui suit, j'ai UNE gare et DEUX grills :
(http://www.locoduino.org/IMG/jpg/p1030044_coupee.jpg)
Je ne gère donc pas le cas d'un point A à un point B à n'importe quels endroits du réseau.
Ce sera l'objet d'un post suivant.
On va régler d'un coup 80 % des cas en traitant des gares "biceps" (de par leur forme), de loin les plus nombreuses, comme sur la photo ci-dessus.
Et de 100 % des gares cachées !
Là, c'est très simple : on n'a qu'un seul moyen d'aller d'un point A à un point B.
Comme il n'y en a qu'un, c'est le meilleur !
A noter que le nombre de voies ne change rien à l'affaire : il y a seulement plus d'itinéraires quand il y a plus de voies, mais la complexité reste la même. C'est toujours aussi simple.
Là où ça se complique, c'est quand il y a deux diagonales. Parce qu'il y a plusieurs façons d'aller de A en B.
La première idée, quand il y a deux diagonales, c'est d'en "spécialiser" une dans le sens gauche -> droite et l'autre droite -> gauche.
Le programme de Jean-Luc permet justement cette spécialisation, en étant "tourne à droite".
En "tournant à droite", vous allez prendre à chaque fois la deuxième diagonale, de votre point de vue.
Il faut que vous imprimiez le schéma de ma gare pour pouvoir suivre. Voir mon post du 06/12 pour la trouver.
Commençons simplement, de gauche -> droite, de VoieGarage1 -> VoieGarage16.
Le premier itinéraire calculé passe par Voie3, Voie21, Voie30 et Voie34.
C'est, à la fois le premier calculé, le meilleur et le plus court. Que demander de mieux ?
Disons que ça tombe bien, dans ce cas là. On verra plus loin pourquoi.
Tordons déjà le cou à une idée communément répandue :
"Non, le meilleur itinéraire N'EST PAS FORCEMENT le plus court".
Une première raison est que si on va, cette fois, de droite -> gauche, on va tomber sur le même puisqu'il n'y a qu'UN SEUL plus court. Et la deuxième diagonale ne servirait à rien? Dommage !
Alors que si on "tourne à droite", on va utiliser la deuxième diagonale.
Pour aller de VoieGarage16 -> VoieGarage1, on va aller via Voie33, Voie28, Voie19, Voie16, Voie11, Voie6 et Voie2.
Et un itinéraire VoieGarage0 -> VoieGarage12 (via Voie1, Voie22) va pouvoir passer, contrairement à la solution la plus courte qui bloque tout vers le bas (de VoieGarage12 à VoieGarage15) … mais qui libère VoieGarage7, VoieGarage18 à VoieGarage20 !
Et voilà le dilemme : on ne peut pas donner une règle simple qui marcherait dans tous les cas, dans toutes les gares.
Enfin, si : Il faut trouver l'itinéraire qui bloque le moins possible la gare. C'est le point clé.
Autre remarque : dès qu'un itinéraire est réellement réalisé, le nombre de possibilités chute pour les suivants, ce qui veut dire que la notion de "meilleur" est volatile. Cela ne simplifie pas les choses.
Donc, mauvaise piste.
Je me suis amusé à faire des tests complets donnant le nombre d'itinéraires bloqués par un itinéraire donné. En plus de prendre un temps considérable et occuper plein de mémoire, je n'ai rien décelé de très simple, sauf une piste prometteuse :
Il y a une diagonale montante (y = x) principale puisqu'elle donne accès à toutes les voies.
De même, il y a une diagonale descendante (y = -x) principale qui, elle aussi, donne accès à toutes les voies.
C'est parfaitement normal et, j'ajouterai, nécessaire au fonctionnement !
Comme il s'agit du plan d'une vraie gare (mais je ne sais malheureusement pas laquelle), la deuxième diagonale montante et la deuxième descendante on été créées pour soulager les diagonales principales, particulièrement pour les destinations les plus fréquentes.
Donc, quand le premier train arrive dans la gare, on l'aiguille vers les deuxièmes diagonales, ce qui laisse toute latitude aux trains suivants.
On a bien minimisé les blocages de la gare, but qu'on cherchait à atteindre.
Donc :
1°) Il suffit de noter quelles sont les deux diagonales principales (dans le TCO en Processing) via la fonction appropriée (à développer, mais très simple).
Cela mettra à jour une matrice FIXE, dans le setup(), de 16 octets.
Un 1 pour dire que cet élément fait partie d'une diagonale principale, un 0 sinon.
2°) Quand les itinéraires sont définis par le programme de Jean-Luc, on leur met une note qui correspond simplement à la somme des poids des éléments.
Plus on utilise une diagonale principale, plus on est pénalisé.
A noter qu'on ne pourra pas faire un score inférieur à 1, puisque, quel que soit l'itinéraire choisi, on coupe au moins une fois une diagonale, le plus souvent 2 fois.
3°) On construit l'itinéraire le mieux noté, celui qui a la note la plus faible.
Cette façon de raisonner conduit à laisser libres les diagonales principales le plus longtemps possible, ce qui promet un maximum de fluidité, lié au fait qu'elles permettent d'aller partout.
Bien que la matrice soit fixe, elle permet de noter les itinéraires en tenant compte de ceux déjà existants et des occupations. C'est-à-dire à tout moment.
Moyennant un temps de calcul minime (une fois dans le setup() et en mettant les notes au fil de l'eau) et une occupation minime de mémoire (16 octets pour la matrice fixe et 15 octets pour les notes), on a le résultat souhaité.
Plus qu'à développer et tester … :-*
-
Bonjour
Suite à ce que j’ai fait pour les TCOs en Processing et les articles ("Un gestionnaire en C++ pour votre réseau 1 2 "), je suis en train de réécrire complètement le gestionnaire de mon réseau.
J’ai commencé par la partie TCO qui en avait le plus besoin, à force de modifications pour ajouter plein de choses ce n’était plus très propre et puis les courbes de Béziers c’est quand même plus joli.
Comme pour le Locodrome je fais circuler des trains (composés de plusieurs véhicules), mais pour l’instant sans gestionnaire (j’ai juste ajouté quelques informations sur le réseau dans le TCO, avec des méthodes " suivant…() " ).
C’est très pratique car je peux peaufiner le TCO et faire pas mal d’essais pour éliminer les bugs dans la gestion du TCO.
Comme je n’ai pas pour l’instant d'itinéraires, et pour le plaisir, j’ai expérimenté la méthode de Jean-Luc, je cherche les itinéraires entre une origine et une destination. Pour cela j’ai une méthode RECURSIVE qui fait une dizaine de lignes de code qui marche très bien, quand il y a plusieurs possibilités je prend la plus courte (ce n'est pas la meilleure façon, mais c'est la plus simple et il faut bien choisir !) et je trace l’itinéraire sur le TCO comme pour le Locodrome.
Par contre pour annuler ou mémoriser un itinéraire c’est plus délicat, et puis il il a l’enclenchement d’approche à réaliser et la prise en compte des autorisations, mais c'est faisable. Inversement j’économise l’écriture d’une centaine d’itinéraires.
La base de mon réseau est la ZONE, une zone est un ensemble de voies et/ou d'appareils de voie pour lequel il ne peut y avoir qu'un seul train à la fois
Pour la recherche des itinéraires j'ajoute dans les classes zones deux méthodes qui renvoient la liste des zones suivantes paires et la liste des suivantes impaires, et dans la classe zone deux méthodes pour la recherche des itinéraires (dont une récursive) ainsi que quelques variables. Comme les classes zones ont beaucoup de références croisées entre elles, on ne peut pas tout faire dans le constructeur et il faut attendre que tous les objets zones soient construits pour établir ces références, c'est le rôle de la méthode liens() de zone qui est appelée dans le setup().
J'ai choisi de séparer la recherche des itinéraires dans le sens pair de celle du sens impair, car en pratique, pour optimiser, je marque les zones avec les marques suivantes : origine-paire, origine-impaire, destination-paire et/ou destination-impaire. Comme je clique sur le TCO sur une zone d'origine puis sur une zone de destination, cela me permet d'éliminer d'emblée les itinéraires impossibles et dans certains cas de limiter la recherche (pair/impair).
Concrètement on trouvera ci dessous le programme de la recherche récursive automatique des itinéraires appliquée au Locodrome, écrit en Processing puis en C++. Le programme a été optimisé pour qu'il y ai le moins de choses possibles sur la pile d"exécution.
L'image du Locodrome pour l'identification des zones :
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=632;image)
Le programme en Processing :
void setup() { // programme de test
for (Zone z : zones) z.liens(); // etablissement des liens entre zones (suivants)
print("Z3 vers z4 "); z3.itineraireVers(z4);
print("Z4 vers z3 "); z4.itineraireVers(z3);
z0.occupee=true; println("occupation de la zone Z0");
print("Z3 vers z4 "); z3.itineraireVers(z4);
print("Z4 vers z3 "); z4.itineraireVers(z3);
}
static Zone z0=new Z0(),z1=new Z1(),z2=new Z2(),z3=new Z3(),z4=new Z4(),z5=new Z5();
static Zone[] zones={z0,z1,z2,z3,z4,z5};
static abstract class Zone {
static Zone[] VIDE={};
boolean occupee=false; // la zone est occupee par un train
boolean utilisee=false; // la zone est utilisee par un autre itineraire
abstract Zone[] suivantesPair();
abstract Zone[] suivantesImpair();
Zone[] suivantesPair;
Zone[] suivantesImpair;
static Zone destination;
static Zone suivante;
static boolean sensRecherche;
static Zone[] itineraire=new Zone[10]; static int index; // itineraire courant
static Zone[] itineraireLePlusCourt=new Zone[10]; static int longueur; // itineraire le plus court
void liens() { suivantesPair=suivantesPair(); suivantesImpair=suivantesImpair(); }
void copie() { // copie de l'itineraire vers le plus court
for (longueur=0; longueur<index; longueur++) itineraireLePlusCourt[longueur]=itineraire[longueur];
}
void affichage() { // affichage de l'itineraire le plus court
println(); print("itineraire ");
for (int i=0; i<longueur; i++) print(itineraireLePlusCourt[i].getNom()+" "); println();
}
void itineraireVers(Zone d) { // methode preparatoire (non recursive)
destination=d;
itineraire[0]=this; index=1; // origine
longueur=0; // remise a zero de l'itineraire le plus court
sensRecherche=false; itineraire(); // recherche sens pair
sensRecherche=true; itineraire(); // recherche sens impair
if (longueur!=0) affichage(); // on a trouve un des itineraires les plus courts
}
void itineraire() { // vers destination (methode recursive)
if (occupee) return; // la zone est occupee (donc pas utilisable)
if (utilisee) return; // la zone est utilisee (par un autre itineraire)
if (this==destination) { // on est arrivé à destination donc on a trouvé un itineraire
if (longueur==0) copie(); // premier itineraire de la recherche (copie)
if (longueur>index) copie(); // itineraire plus court que le precedent (copie)
} else { // on continue a chercher
Zone[] suivantes=sensRecherche?suivantesPair:suivantesImpair; // suivant le sens de recherche
for (int i=0; i<suivantes.length; i++) { // pour tous les suivantes paires ou impaires
suivante=suivantes[i];
itineraire[index++]=suivante; // on ajoute une des zones suivantes a l'itineraire
suivante.itineraire(); // RECURSIVITE
index--; // on supprime la zone de l'itineraire
}
}
}
final String getNom() { return getClass().toString().substring(25) ; } // nom de zone
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
static class Z3 extends Zone {
Zone[] suivantesPair() { return VIDE; }
Zone[] suivantesImpair() { return new Zone[] {z2}; }
}
static class Z2 extends Zone {
Zone[] suivantesPair() { return new Zone[] {z3}; }
Zone[] suivantesImpair() { return new Zone[] {z0,z1}; }
}
static class Z0 extends Zone {
Zone[] suivantesPair() { return new Zone[] {z2}; }
Zone[] suivantesImpair() { return new Zone[] {z5}; }
}
static class Z1 extends Zone {
Zone[] suivantesPair() { return new Zone[] {z2}; }
Zone[] suivantesImpair() { return new Zone[] {z5}; }
}
static class Z5 extends Zone {
Zone[] suivantesPair() { return new Zone[] {z0,z1}; }
Zone[] suivantesImpair() { return new Zone[] {z4}; }
}
static class Z4 extends Zone {
Zone[] suivantesPair() { return new Zone[] {z5}; }
Zone[] suivantesImpair() { return VIDE; }
}
class Zone;
static Zone* destination;
static Zone* suivante;
static boolean sensRecherche;
static Zone* itineraireCourant[10]; static int index; // itineraire courant
static Zone* itineraireLePlusCourt[10]; static int longueur; // itineraire le plus court
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Zone {
public:
boolean occupee=false; // la zone est occupee par un train
boolean utilisee=false; // la zone est utilisee par un autre itineraire
Zone** suivsPair;
Zone** suivsImpair;
int nbPair;
int nbImpair;
virtual Zone** suivantesPair()=0;
virtual Zone** suivantesImpair()=0;
Zone(int np,int ni) { // constructeur
nbPair=np; nbImpair=ni;
}
void liens() { suivsPair=suivantesPair(); suivsImpair=suivantesImpair(); }
void copie() { // copie de l'itineraire vers le plus court
for (longueur=0; longueur<index; longueur++) itineraireLePlusCourt[longueur]=itineraireCourant[longueur];
}
void affichage() { // affichage de l'itineraire le plus court
Serial.println(); Serial.print("itineraire ");
for (int i=0; i<longueur; i++) Serial.print(itineraireLePlusCourt[i]->getNom()+" "); Serial.println();
}
void itineraireVers(Zone* d) { // methode preparatoire (non recursive)
destination=d;
itineraireCourant[0]=this; index=1; // origine
longueur=0; // remise a zero de l'itineraire le plus court
sensRecherche=false; itineraire(); // recherche sens pair
sensRecherche=true; itineraire(); // recherche sens impair
if (longueur!=0) affichage(); // on a trouve un des itineraires les plus courts
}
void itineraire() { // vers destination (methode recursive)
if (occupee) return; // la zone est occupee (donc pas utilisable)
if (utilisee) return; // la zone est utilisee (par un autre itineraire)
if (this==destination) { // on est arrivé à destination donc on a trouvé un itineraire
if (longueur==0) copie(); // premier itineraire de la recherche (copie)
if (longueur>index) copie(); // itineraire plus court que le precedent (copie)
} else { // on continue a chercher
Zone** suivantes=sensRecherche?suivsPair:suivsImpair; // suivant le sens de recherche
int nb=sensRecherche?nbPair:nbImpair;
for (int i=0; i<nb; i++) { // pour tous les suivantes paires ou impaires
suivante=suivantes[i];
itineraireCourant[index++]=suivante; // on ajoute une des zones suivantes a l'itineraire
suivante->itineraire(); // RECURSIVITE
index--; // on supprime la zone de l'itineraire
}
}
}
virtual String getNom(); // nom de zone
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Z3:public Zone {
public:
Z3():Zone(0,1) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z3"; }
};
class Z2:public Zone {
public:
Z2():Zone(1,2) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z2"; }
};
class Z0:public Zone {
public:
Z0():Zone(1,1) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z0"; }
};
class Z1:public Zone {
public:
Z1():Zone(1,1) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z1"; }
};
class Z5:public Zone {
public:
Z5():Zone(2,1) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z5"; }
};
class Z4:public Zone {
public:
Z4():Zone(1,0) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z4"; }
};
static Zone *z0=new Z0(),*z1=new Z1(),*z2=new Z2(),*z3=new Z3(),*z4=new Z4(),*z5=new Z5();
static Zone* zones[]={z0,z1,z2,z3,z4,z5};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void setup() {
for (int i=0; i<6; i++) zones[i]->liens(); // etablissement des liens entre zones (suivants)
Serial.begin(9600);
Serial.print("Z3 vers z4 "); z3->itineraireVers(z4);
Serial.print("Z4 vers z3 "); z4->itineraireVers(z3);
z0->occupee=true; Serial.println("occupation de la zone Z0");
Serial.print("Z3 vers z4 "); z3->itineraireVers(z4);
Serial.print("Z4 vers z3 "); z4->itineraireVers(z3);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
static Zone** VIDE=new Zone*[0]{};
Zone** Z3::suivantesPair() { return VIDE; }
Zone** Z3::suivantesImpair() { return new Zone*[1] {z2}; }
Zone** Z2::suivantesPair() { return new Zone*[1] {z3}; }
Zone** Z2::suivantesImpair() { return new Zone*[2] {z0,z1}; }
Zone** Z0::suivantesPair() { return new Zone*[1] {z2}; }
Zone** Z0::suivantesImpair() { return new Zone*[1] {z5}; }
Zone** Z1::suivantesPair() { return new Zone*[1] {z2}; }
Zone** Z1::suivantesImpair() { return new Zone*[1] {z5}; }
Zone** Z5::suivantesPair() { return new Zone*[2] {z0,z1}; }
Zone** Z5::suivantesImpair() { return new Zone*[1] {z4}; }
Zone** Z4::suivantesPair() { return new Zone*[1] {z5}; }
Zone** Z4::suivantesImpair() { return VIDE; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void loop() {}
Affichages des deux programmes (c'est le même pour les deux) :
Z3 vers z4
itineraire Z3 Z2 Z0 Z5 Z4
Z4 vers z3
itineraire Z4 Z5 Z0 Z2 Z3
occupation de la zone Z0
Z3 vers z4
itineraire Z3 Z2 Z1 Z5 Z4
Z4 vers z3
itineraire Z4 Z5 Z1 Z2 Z3
Et pour finir ce que cela donne avec la grande gare de mon réseau :
(http://www.locoduino.org/IMG/png/imageprs.png)
Pierre
-
Merci Pierre : contribution passionnante, comme d'habitude. ;)
J'ai hâte de pouvoir faire avec mon TCO réseau ce que tu fais avec le tien. C'est vraiment un look d'enfer !
Il y a même des trains complets... ;D ;D ;D
Ceci dit, on est bien obligé de comparer au programme de Jean-Luc (avec mes quelques compléments).
La grosse différence, c'est, qu'effectivement, tu ne raisonnes pas par identifiant. Je vois mieux maintenant ce que tu voulais dire.
C'est apparemment plus simple. A voir à la description de ma gare et comparer les temps d'exécution.
J'ai pas mal de questions :
1°) C'est bien d'avoir la liste des zones correspondant à un itinéraire, mais ça ne donne pas la position des aiguilles pour passer d'une zone à l'autre. On aura pourtant besoin de cette info pour orienter les aiguilles.
2°) En marquant comme utilisée une zone, sans tenir compte du sens où tu prends la zone, il va y a voir un problème dans les boucles de retournement.
Je pense qu'on est obligé de noter qu'une zone est utilisée et dans quel sens, dans la même action.
3°) Les croisements seuls sont particuliers au niveau marquage.
4°) Je vois bien que la recherche de l'itinéraire le plus court amène une grosse simplification du programme. Mais je ne suis pas convaincu du tout par cette méthode pour une gare comme la mienne (voir mon post précédent).
Enfin, deux questions sur la technique de programmation :
En Processing :
static Zone z0=new Z0(),z1=new Z1(),z2=new Z2(),z3=new Z3(),z4=new Z4(),z5=new Z5();
static Zone[] zones={z0,z1,z2,z3,z4,z5};
Peut-on faire plus compact (j'ai 93 zones !) ?
En C++ :
class Z3:public Zone {
public:
Z3():Zone(0,1) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z3"; }
};
class Z2:public Zone {
public:
Z2():Zone(1,2) {}
Zone** suivantesPair();
Zone** suivantesImpair();
String getNom() { return "Z2"; }
};
1°) Faut-il vraiment écrire 93 fois (dans chaque classe) :
Zone** suivantesPair();
Zone** suivantesImpair();
ça ne pourrait pas faire partie de l'héritage ?
2°) A quoi correspondent les nombres dans : Z3():Zone(0,1) {}
, Z2():Zone(1,2) {}
A bientôt.
PS : c'est quand même agréable de ne pas être seul sur ce fil. Merci Pierre. ;D
-
Bonjour
Pour les trains complets, j'aime beaucoup aussi surtout quand ils se tortillent dans les successions d'aiguilles, mais concrètement c'est le premier pas pour pouvoir mettre en tête d'une rame une machine ou vice versa. C'est nécessaire pour pour tester le gestionnaire qui est plus compliqué dans ces cas là.
Le but était bien de comparer avec le programme de Jean-Luc. Je ne pense pas que l'absence d'identifiants change grand chose, la différence est plutôt au niveau conceptuel.
Avec la liste des zones d'un itinéraire, je peux l'établir à savoir positionner les aiguilles (ce n'est pas le plus facile) ouvrir les signaux et faire le tracé sur le TCO. Mais aussi le détruire, juste fermer les signaux et le détracer. Pour positionner les aiguilles j'ai ajouté, dans la classe zone, une méthode qui fait le travail dans les cas simples (une seule aiguille ou TJD), cette méthode étant redéfinie dans les zones particulières pour les cas compliqués (plusieurs aiguilles ou TJD).
Pour l'instant je ne prends pas en compte les boucles de retournement. De toute façon un itinéraire avec une boucle de retournement c'est pas très réaliste. N'ayant pas de croisements sur mon réseau j'ai pas encore envisagé le problème.
Pour l'itinéraire le plus court, cela marche bien sur mon réseau, mais il est clair que ce n'est pas le cas du tien. Il faut trouver un critère pour choisir, après la programmation ce n'est pas trop le problème.
La déclaration des zones et de la liste des zones est assez fastidieuse, mais je ne vois pas de solutions à par écrire un programme annexe (en Processing par exemple) qui sort sur la console un bout de programme idoine, il ne reste plus qu'a faire un copier/coller !
Pour les déclarations des différentes zones, on ne peut pas simplifier non plus (le C++ est assez bavard), mais ici aussi la technique précédente peux être avantageusement utilisée utilisée. J'avais essayé, lors de l'écriture de mon premier article sur le gestionnaire, des macros C (pour le préprocesseur) cela marchait pas mal, mais ce n'était pas publiable et il n'y avait aucune détection d'erreurs.
Les deux entiers dans les constructeurs des différentes zones, ce sont les tailles des tableaux des suivantes-paires et des suivantes-impaires, j'en ai besoin pour les parcourir (problème classique avec le C/C++).
Pierre
-
Bonjour,
Moi aussi, j'aime bien les trains qui se tortillent dans les gares. Avec la mienne, je vais être servi.
Je vais réfléchir, avec ta méthode, pour positionner les aiguilles (des fois, ça sert ;D )
Ne pas prendre en compte les boucles de retournement, ça va être un grave problème pour moi. Je m'explique :
Quand, à l'extérieur de ma gare, je vais aller me balader, je vais avoir :
Voie6 reliée à Voie5
Voie4 reliée à Voie1
Voie3 reliée à Voie2
Voie0 reliée à Voie7.
Analyse électrique :
Voie0 à Voie 7 : aucun problème.
Mais tous les autres vont être, globalement, des boucles de retournement.
Exemple :
Je pars de VoieGarage1, je sors Voie5, puis je reviens Voie6 vers VoieGarage14.
Si tu suis les rails, tu as un beau cours jus.
Donc, il est absolument nécessaire sur mon réseau qu'on sache régler le cas des boucles de retournement.
L'idée de Jean-Luc, à savoir marquer les éléments qu'on prend en compte, mais en tenant compte aussi du sens de parcours de cet élément, me parait parfaite.
Je vais aussi réfléchir à écrire un Specifs.h adapté à ta méthode, comme je l'avais fait pour le méthode de Jean-Luc.
Il me parait indispensable qu'un débutant puisse se servir de ce programme, sans "mettre les mains dans le cambouis".
-
Bonjour
Ce qui se passe hors de ta gare n'a pas à intervenir sur les itinéraires de la gare.
Sur l'exemple du Locodrome ce qui se passe sur la boucle n'est pas pris en compte par les itinéraires. La zone Z3 n'a pas de suivantes-paires et la zone Z4 n'a pas de suivantes-impaires. Il n'y a pas d'itinéraire possible passant par le haut de la boucle.
Pierre
-
Bien sûr, il faut limiter les zones d'action des chercheurs d'itinéraires récursifs.
Et donc, il faut définir DES grills.
Je pense que dans ta méthode, il faudra, non seulement des zones occupées et des zones utilisées (qui existent déjà dans ton programme), mais aussi des zones bloquées qui interdisent au chercheur d'itinéraire d'aller plus loin.
Chaque grill aura donc une liste des zones bloquées autour de lui.
Pour chercher un itinéraire, on devra dire dans quel grill on se situe (= avec telles zones bloquées) et lancer la recherche.
Autre remarque :
Je veux pouvoir envoyer le train de telle voie de la gare vers une voie libre de la gare cachée en cliquant simplement origine - extrémité.
Cela suppose qu'on prenne au moins 2 grills (celui de sortie de la gare visible et celui d'entrée de la gare cachée)
Donc des méta-itinéraires. Je rappelle que cette fonction est utilisée dans TrainsController, même si je me doute qu'ils utilisent une méthode "à la petite cuillère" et pas avec recherche automatique. Mais je n'ai pas creusé.
Tout cela pour dire que j'utiliserai cette méthode pour aller d'une voie à l'autre de ma gare.
Le problème, avec le récursif, c'est de lui rogner convenablement les ailes pour qu'il n'aille pas se perdre partout et nulle part.
C'est la phase II.
Finissons d'abord la phase I, sur un seul grill avec des voies bloquées. Cela sera déjà pas mal. :P
-
La discussion est très technique et je suppose qu'elle va osciller entre "le système de Jean-Luc" et "le système de Pierre", et, pourquoi pas "le système de Denis".
J'imagine combien c'est interessant pour les visiteurs qui veulent éviter un logiciel du commerce : il est bien évident maintenant que "nos" gestionnaires 100% Arduino n'auront rien à envier à une quelconque réalisation commerciale, qui, beuhhh, ne tourne pas sur toutes les plateformes.
Je veux pouvoir envoyer le train de telle voie de la gare vers une voie libre de la gare cachée en cliquant simplement origine - extrémité.
Cela suppose qu'on prenne au moins 2 grills (celui de sortie de la gare visible et celui d'entrée de la gare cachée)
C'est exactement ma question du moment : j'aurai 4 trains qui tournent automatiquement entre la gare principale et la gare cachée, en double voie, et vice versa en faisant le tour du réseau. Et en plus, un metro qui fait le va-et-vient entre z40 et z41.
(http://www.locoduino.org/IMG/png/reseaudbtco.png)
Il y aura donc un itinéraire z27-z29-z30-z31-z32-z33-z34-z35 puis z22 ou z23 en choisissant celle qui est libre. Là le train arrêté en z22 (par exemple) attendra et le train préalablement stoppé sur z23 démarrera pour aller s'arrêter en gare principale selon l'itinéraire z23-z24-z25-z26-z27.
Selon z27 est libre ou non ou selon le type de train, l'arrivée pourra être z28.
On a donc à définir et faire fonctionner 2 itinéraires, avec en plus la notion du temps (arrêt des trains en gare).
Dans l'autre sens on pourra avoir le même type d'itinéraires : z13 (ou z14)-z15-z16-z17-z5 ou z4, puis
z5 ou z4-z6-z7-z8-z9-z10-z11-z12-z13 ou z14
Donc encore 2 autres itinéraires.
Il y aura bien évidemment la gestion d'aiguille en entrée et sortie des 2 gares.
J'ai le sentiment qu'il n'est pas vraiment nécessaire de faire une recherche exhaustive de tous les itinéraires possibles dans mon réseau comme l'a calculé Denis dans ce fil (http://forum.locoduino.org/index.php?topic=167.msg2122#msg2122 (http://forum.locoduino.org/index.php?topic=167.msg2122#msg2122)), d'autant que les itinéraires de voie de garage à voie de garage ne seront manoeuvrés que manuellement, sauf ceux qui permettront d'atteindre la ligne de métro en z40 ou z41.
Donc comment faire ?
J'ai le sentiment que toutes les briques nécessaires sont dans le gestionnaire de Pierre avec, en plus, l'appel à la récursivité mentionnée plus haut. Le gestionnaire de Jean-Luc me semble aussi capable de traiter cela. Mais sa "boite à outils" me parait moins complète et c'est une philosophie différente (à priori).
Je me sens comme un cobaye prêt à tester dans un domaine où Denis a déjà écrit des kilomètres de posts (et tes rails, au fait, sont-ils posés ?)
Je vais donc étudier tout cela maintenant. Quelle chance de vous avoir :) :D ;D
Dominique
-
Bonjour
J'ai un réseau très semblable au tien avec les mêmes volontés d'exploitation. J'ai une grand gare à double voie de passage, une coulisse exactement comme la tienne (sans tramway), avec en plus une petite gare terminus de voie unique et un dépôt.
J'utilise ma coulisse comme la tienne, quand un train arrive dans un sens un autre train part après un certain temps dans le même sens et pareil pour l'autre sens.
Pour cela j'ai deux "postes d'aiguillages", un pour la grande gare (présenté dans un post précédent) et un "poste d'aiguillage" pour la coulisse. J'ai aussi deux autres postes pour la petite gare et pour le dépôt. Ce découpage en plusieurs postes est tout à fait conforme à ce que fait la SNCF (j'en ai parlé un peu avec l'article sur les itinéraires).
Chaque poste a ses propres itinéraires, il y a des itinéraires pour la grande gare et des itinéraires pour la coulisse (les deux autres postes ont aussi leurs itinéraires).
Pour pouvoir faire circuler des trains sur les deux ovales sans avoir besoin d'intervenir, j'ai des itinéraires "permanents" (j'en ai parlé un peu avec l'article sur les signaux) sur la grande gare et sur la coulisse.
Le poste de la coulisse a un mode automatique activable séparément sur chacun des sens, qui réalise l'alternance des trains. Je n'ai toujours pas fini la mise au point de cet automatisme et il reste des bugs (c'est pas trivial car il y a beaucoup de cas particuliers).
Ce que vous cherchez à faire (Denis et toi) c'est un peu une commande centralisée comme à la SNCF, mais à la SNCF il n'y a pas de boucles dans ce qui est commandé. Je ne sais pas trop bien comment fonctionnent ces commandes centralisées à la SNCF car je n'ai jamais eut l'occasion d'en visiter contrairement aux postes d'aiguillages classique. J'ai eu la chance de pouvoir visiter longuement des postes électromécaniques et des PRS. Mais on peut discuter sur ce sujet.
Pierre
-
Merci pour ta réponse, Pierre,
Je pense savoir comment je vais faire, en activant un automate dans le gestionnaire périodiquement qui lancera les itinéraires dans les postes d'aiguillage, selon toutes sortes de conditions pour assurer la sécurité.
J'ai déjà résolu le problème du tramway ou métro en développant une centrale DCC dédiée à l'automate de va et vient et en isolant les réseaux avec des relais.
Donc il y aura une grosse "loop" dans mon gestionnaire qui traitera tous les messages CAN des autres modules, + quelques automates comme indiqué ci- dessus. D'où l'intérêt du Due.
Je vais tacher de décrire pas à pas la réalisation du gestionnaire de mon réseau dans le fil dédié à ton gestionnaire.
Ce qui est marrant c'est qu'on arrive à tirer des ponts entre les gestionnaires ;D
-
Bonjour Denis
Je déterre un peu ce fil qui est à l'arrêt depuis janvier en espérant que tu lises ce message.
Mon projet de TCO avance et j'en suis arrivé à la recherche d'itinéraires donc j'ai repris ce fil et mis en œuvre la recherche d'itinéraires sur la base du travail de Jean-Luc (Que je remercie au passage pour sa contribution).
Puis j'ai relu l'intégralité de ce fil pour vérifier que je n'avais pas loupé quelques choses. Et je suis tombé sur ta contribution, que j'avais survolé quand tu avais posté mais je n'avais pas forcément tout compris car je n'en étais pas là. Du coup j'ai adapté mon programme pour tenir compte de tes propositions que j'ai trouvées très pertinentes.
Aujourd'hui ma recherche d'itinéraires fonctionne parfaitement sur ta gare que j'ai pris pour vérifier que tout fonctionnait correctement. Et j'en suis au même point que toi (du moins à fin janvier) à savoir comment trouver "LE" meilleur itinéraire. Tu as commencé à élaborer une théorie sur le calcul d'un "poids" des itinéraires en sachant que le meilleur serait celui dont le poids est le plus faible.
As-tu finalisé cette méthode et si oui pourrais-tu nous en dire quelques mots ?
PS : Je développe mon TCO sous DELPHI (programmation Pascal) pour qu'il tourne sur un PC Windows.
Locoduino est vraiment un site formidable
-
Bonjour,
Génial...
J'ai modifié le fichier Specifs.h pour que les voies de garage 4, 5, 17 et 18 deviennent des voies normales (VOIE_54, VOIE_55, VOIE_67, VOIE_68).
il devient possible de relier la voie de garage11 à la voie de garrage12.
################
De VOIE_GARAGE_11 a VOIE_GARAGE_12
================
AIGUILLE_D_00 AIGUILLE_D_30 AIGUILLE_G_20 AIGUILLE_G_30 AIGUILLE_G_50 TJD_3 TJD_5 TJD_7 TJD_10 TJD_11 TJD_15 CROISEMENT_0 CROISEMENT_1 CROISEMENT_2 VOIE_7 VOIE_14 VOIE_20 VOIE_32 VOIE_55 VOIE_68 VOIE_GARAGE_11 VOIE_GARAGE_12
AIGUILLE_D_00 AIGUILLE_D_30 AIGUILLE_D_40 AIGUILLE_G_20 AIGUILLE_G_30 AIGUILLE_G_50 TJD_4 TJD_5 TJD_7 TJD_10 TJD_11 TJD_15 TJD_16 CROISEMENT_1 CROISEMENT_2 VOIE_7 VOIE_14 VOIE_16 VOIE_20 VOIE_25 VOIE_28 VOIE_32 VOIE_54 VOIE_67 VOIE_GARAGE_11 VOIE_GARAGE_12
================
Duree : 1764527 micro-secondes
Nombre d'itineraires : 2
Nombre d'impossibilites : 0
Fin du test de tous les itineraires
Nombre de voies : 93
Reste a gérer le CAN et les messages...
A bientôt
Yannick
Ajout le 19/05/18
Bonjour,
A quoi servent les table sources et destinations (Specifs.h) ? Il est en effet possible de partir de n'importe quelle voie vers n'importe quelle autre voie (sous réserve de compatibilité...)
Ou alors, cela permet au programmeur de se poser la question sans autre intérêt pour le système.
Merci
-
Bonjour Jean-Luc,
Après avoir à nouveau parcouru les descriptions des modèles de Pierre, Denis et le tien, il me vient une question concernant les trains.
Il faut bien qu'à un moment ou un autre, le système ait une représentation des trains et de leur progression sur le réseau, synchronisée par les détecteurs d'occupation. Ma question est donc: comment les trains sont-ils modélisés ?
En pleine réflexion sur ce sujet pour mon 2ème petit réseau en N, je pense créer une classe Train et l'instancier pour chaque train présent sur le réseau. Charge ensuite aux objets de parcourir les itinéraires.
Peut-être que ma question est superflue si c'est déjà expliqué quelque part et que j'ai manqué ce point.
Merci pour tout ce partage.
Meilleures salutations.
Marc-Henri
-
Bonjour
Normalement la progression des trains est matérialisée sur le TCO par la coloration (en rouge) des zones où est le train (avec décoloration quand le train quitte une zone. C'est la rétrosignalisation qui fournit les occupation et libérations de zones. C'est le système de base, pas besoin d'objet train.
Si on veut faire en plus du suivi des trains (pour savoir quel train est dans quelle zone), il faut bien entendu un objet train (qui reste petit dans ce cas là).
Il est très pratique de pouvoir faire circuler sur le TCO des trains virtuels (comme sur le Locodrome), pour faire de la mise au point (TCO et gestionnaire), pour tester un réseau avant de le construire ou tout simplement pour jouer sans réseau. Dans ce cas l'objet train est assez conséquent.
L'idéal serait de pouvoir visualiser des trains sur le TCO synchronisés avec les trains réels, c'est à dire déplacer les trains virtuels sur le TCO en fonction des déplacements des trains réels. C'est assez délicat mais on y travaille.
Cordialement
Pierre
-
Il faut bien qu'à un moment ou un autre, le système ait une représentation des trains et de leur progression sur le réseau, synchronisée par les détecteurs d'occupation. Ma question est donc: comment les trains sont-ils modélisés ?
Bonjour Marc-Henri
Effectivement il est nécessaire d’avoir une représentation des trains. Dans ce qui est présenté ici on a juste le graphe du réseau et la recherche de chemin mais, pour l’instant, pas de liaison avec la detection d’occupation où les trains. Je suis en train de refaire sous forme de bibliothèque et de l’enrichir mais comme j’ai d’autres projets en cours, ce n’est pas pour tout de suite.
En plus de ce qui est présenté je pense ajouter : l’information occupé mis à jour via la détection d’occupation ; Les Block et les UniBlock, portion de rail où un train peut s’arrêter et munis d’une detection de pleine voie et de zone d’arrêt ; La notion d’ensemble d’occupation : détection partagée par plusieurs éléments de voies, typiquement les zones d’aiguilles. En plus du graphe d’éléments de voies, on a un graphe d’occupation de plus forte granularité.
Les Trains qui se baladent sur le graphe d’occupation. Un Train possède une direction de marche et une liste doublement chaînée de pointeurs vers les nœuds contigus du graphe d’occupation, nœuds qu’il occupe. La tête de liste est la tête du train si le train a la direction de marche normale. Si le train est dans la direction de marche inverse, la tête de liste est la queue de train.
(La suite plus tard, je dois filer :P)
-
Il en trouve 26 et 2 impossibles.
Mais je n'ai pas compris lesquels ... ???
Je m'explique :
1) je te fournis le plan de ton reseau avec ma numerotation (celle du programme TCO et de SGDD).
2) Je te fournis aussi le programme Arduino de Jean-Luc, avec la version ton reseau.
Celui-la, tu peux le telle verser sur un Arduino DUE et voir ce qu'il donne.
L'onglet Specifs.h est la description, "comme Jean-Luc" cette fois, de ton reseau.
Pour t'aider je te joins aussi le fichier tansform.txt qui est la traduction numerotation DD -> numerotation JLB.
(numerotation DD = 1000+numerotation DD du plan pour que tout soit bien aligne)
Ce fichier ne sert à rien d'autre qu’a nous aider, pauvres humains :)
Il est quand meme genere par l'ordi, sans intervention humaine.
En retirant les // pour voir les taches, tu verras comment travaille le programme de Jean-Luc.
Et tu comprendras ma reponse du debut ;D
Merci à Jean-Luc et Denis, ma convalescence va me permettre de comprendre cette notion de connecteurs. Je vais commencer par mettre à jour le circuit suite aux dernières modifications... l’année dernière !
-
C'est parti !
J'ai repris le schéma de mon réseau que je joins ici : les aiguilles ne changent pas de numéro (a0 à a20), par contre les zones z0 à z41 changent de nom VOIE_0 à VOIE_30. Certaines de ces VOIES sont déclarées en VOIE_GARAGE avec le numéro indiqué sur le schéma.
(http://forum.locoduino.org/index.php?action=dlattach;topic=167.0;attach=2233;image)
On voit que j'en ai perdu au passage : toutes les zones contenant une ou plusieurs aiguilles ne sont plus déclarées car remplacées par les aiguilles AIGUILLE_0 à AIGUILLE_20.
Ce qui me donne les identifiants suivants pour tout le réseau :
/*
Indentifiants du reseau
*/
enum {
/* voies */
VOIE_0,
VOIE_1,
VOIE_2,
VOIE_3,
VOIE_4,
VOIE_5,
VOIE_6,
VOIE_7,
VOIE_8,
VOIE_9,
VOIE_GARAGE_10,
VOIE_GARAGE_11,
VOIE_GARAGE_12,
VOIE_GARAGE_13,
VOIE_14,
VOIE_GARAGE_15,
VOIE_16,
VOIE_17,
VOIE_18,
VOIE_19,
VOIE_20,
VOIE_21,
VOIE_22,
VOIE_23,
VOIE_24,
VOIE_25,
VOIE_GARAGE_26,
VOIE_27,
VOIE_28,
VOIE_29,
VOIE_GARAGE_30,
/* aiguille */
AIGUILLE_0,
AIGUILLE_1,
AIGUILLE_2,
AIGUILLE_3,
AIGUILLE_4,
AIGUILLE_5,
AIGUILLE_6,
AIGUILLE_7,
AIGUILLE_8,
AIGUILLE_9,
AIGUILLE_10,
AIGUILLE_11,
AIGUILLE_12,
AIGUILLE_13,
AIGUILLE_14,
AIGUILLE_15,
AIGUILLE_16,
AIGUILLE_17,
AIGUILLE_18,
AIGUILLE_19,
AIGUILLE_20, //52 elements
/* Valeur speciale */
AUCUNE_VOIE
};
Comme les sens de circulation normaux sont indiqués par les flèches, j'ai voulu déclarer les connexions entre les noeuds en suivant le sens de ces flèches.
Comme il y a une circulation interieure dans le sens trigo et une circulation extérieure dans le sens horaire, je tombe sur une petite difficulté pour connecter les aiguilles 0 et 2 à gauche de la gare et 8 et 11 à droite de la gare :
/*
* Connexions des voies
*/
// metro
voieGarage30.connecteAVoie(voie29, ENTRANT);
voie29.connecteSortantAVoie(voie28, ENTRANT);
voie28.connecteSortantAVoie(aiguille15, SORTANT_DROIT);
aiguille15.connecteEntrantAVoie(voie27, ENTRANT);
voie27.connecteSortantAVoie(voieGarage26, SORTANT);
// voie circulaire exterieure
voie4.connecteSortantAVoie(aiguille16, ENTRANT);
aiguille16.connecteSortantDevieAVoie(aiguille15, SORTANT_DEVIE);
aiguille16.connecteSortantDroitAVoie(aiguille13, SORTANT_DEVIE);
voie3.connecteSortantAVoie(aiguille13, SORTANT_DROIT);
aiguille13.connecteEntrantAVoie(voie5, ENTRANT);
voie5.connecteSortantAVoie(voie6, ENTRANT);
voie6.connecteSortantAVoie(voie7, ENTRANT);
voie7.connecteSortantAVoie(voie8, ENTRANT);
voie8.connecteSortantAVoie(voie9, ENTRANT);
voie9.connecteSortantAVoie(aiguille8, SORTANT_DROIT);
aiguille8.connecteEntrantAVoie(aiguille7, ENTRANT);
aiguille7.connecteSortantDroitAVoie(voie0, ENTRANT);
aiguille7.connecteSortantDevieAVoie(aiguille6, SORTANT_DEVIE);
aiguille6.connecteEntrantAVoie(voie1, ENTRANT);
voie0.connecteSortantAVoie(aiguille4, SORTANT_DROIT);
voie1.connecteSortantAVoie(aiguille5, ENTRANT);
aiguille5.connecteSortantDevieAVoie(aiguille4, SORTANT_DEVIE);
aiguille4.connecteEntrantAVoie(aiguille2, ENTRANT);
aiguille2.connecteSortantDroitAVoie(voie2, ENTRANT);
voie2.connecteSortantAVoie(aiguille17, ENTRANT);
aiguille17.connecteSortantDevieAVoie(voie4, ENTRANT);
aiguille17.connecteSortantDroitAVoie(voie3, ENTRANT);
// voie circulaire interieure
voie23.connecteSortantAVoie(aiguille18, SORTANT_DROIT);
voie24.connecteSortantAVoie(aiguille18, SORTANT_DEVIE);
aiguille18.connecteEntrantAVoie(voie25, ENTRANT);
voie25.connecteSortantAVoie(aiguille0, ENTRANT);
aiguille0.connecteSortantDroitAVoie(aiguille1, ENTRANT);
aiguille1.connecteSortantDroitAVoie(voie16, ENTRANT);
aiguille1.connecteSortantDevieAVoie(aiguille3, SORTANT_DEVIE);
voieGarage15.connecteAVoie(aiguille3, SORTANT_DROIT);
aiguille3.connecteEntrantAVoie(voie17, ENTRANT);
voie16.connecteSortantAVoie(aiguille9, SORTANT_DROIT);
voie17.connecteSortantAVoie(aiguille9, SORTANT_DEVIE);
aiguille9.connecteEntrantAVoie(aiguille11, SORTANT_DROIT);
aiguille11.connecteEntrantAVoie(voie18, ENTRANT);
voie18.connecteSortantAVoie(voie19, ENTRANT);
voie19.connecteSortantAVoie(voie20, ENTRANT);
voie20.connecteSortantAVoie(voie21, ENTRANT);
voie21.connecteSortantAVoie(voie22, ENTRANT);
voie22.connecteSortantAVoie(aiguille14, ENTRANT);
aiguille14.connecteSortantDroitAVoie(voie23, ENTRANT);
aiguille14.connecteSortantDevieAVoie(voie24, ENTRANT);
// depot
voieGarage11.connecteAVoie(aiguille12, SORTANT_DROIT);
voieGarage12.connecteAVoie(aiguille12, SORTANT_DEVIE);
voieGarage13.connecteAVoie(aiguille10, SORTANT_DEVIE);
aiguille12.connecteEntrantAVoie(aiguille10, SORTANT_DROIT);
aiguille10.connecteEntrantAVoie(aiguille20, ENTRANT);
aiguille20.connecteSortantDroitAVoie(aiguille6, SORTANT_DROIT);
aiguille20.connecteSortantDevieAVoie(voie14, ENTRANT);
voie14.connecteSortantAVoie(aiguille19, SORTANT_DEVIE);
aiguille5.connecteSortantDroitAVoie(aiguille19, SORTANT_DROIT);
aiguille19.connecteEntrantAVoie(voieGarage10, SORTANT);
// passages voies interieurs <-> exterieures
aiguille0.connecteSortantDevieAVoie(aiguille2, SORTANT_DEVIE);
aiguille8.connecteSortantDevieAVoie(aiguille11, SORTANT_DEVIE);
Au lancement du programme, le moniteur affiche 2 anomalies :
Direction deja fixee : AIGUILLE_2
Direction deja fixee : AIGUILLE_8
Nombre de voies : 52
Peut-être devrais-je déclarer les connexions autrement ???
En tout cas tous les tests d'itinéraires fonctionnent (je déclare sur le moniteur une voie de départ et une voie d'arrivée et le programme affiche le résultat). exemple :
De VOIE_1 a VOIE_GARAGE_26
VOIE_1 VOIE_2 VOIE_4 VOIE_GARAGE_26 VOIE_27 AIGUILLE_2 AIGUILLE_4 AIGUILLE_5 AIGUILLE_15 AIGUILLE_16 AIGUILLE_17
De VOIE_1 a VOIE_3
VOIE_1 VOIE_2 VOIE_3 AIGUILLE_2 AIGUILLE_4 AIGUILLE_5 AIGUILLE_17
-
Au lancement du programme, le moniteur affiche 2 anomalies :
Direction deja fixee : AIGUILLE_2
Direction deja fixee : AIGUILLE_8
Nombre de voies : 52
Les connexions doivent être faites selon une seule direction une fois celle-ci choisie. Tu pars d'un élément et tu tournes dans une seule direction. Il ne faut pas en changer entre le circuit extérieur et intérieur.
Quand tu écris :
aiguille4.connecteEntrantAVoie(aiguille2, ENTRANT);
La direction de aiguille2 est fixée à DIRECTION_AVANT et celle de aiguille4 à DIRECTION_ARRIERE
Ensuite quand tu écris
aiguille0.connecteSortantDevieAVoie(aiguille2, SORTANT_DEVIE);
Tu tentes de fixer la direction d'aiguille2 à DIRECTION_ARRIERE
D'où le message d'erreur
-
Merci Jean-Luc,
Cela a pour conséquence que je ne peux pas décrire les 2 boucles en sens inverse l’une de l’autre, à partir du moment où il y a une liaison entre les deux.
Donc sur une boucle un train circulera en marche avant et sur l’autre boucle un autre train circulera en marche arrière.
-
L'orientation du graphe de ton réseau n'a rien à voir avec le sens de circulation normal des trains.
-
Voilà, j'ai repris la description, toujours dans le sens horaire et l'erreur n'apparait plus.
Je joins le programme complet avec une trace qui montre comment le programme explore le réseau, c'est très intéressant ;D
Pour tester il faut entrer au moniteur d'abord le numéro de la voie de départ (ou voie de garage), puis ENTER, puis le numéro de la voie d'arrivée, puis ENTER.
Exemple : On voit bien les retours à l'aiguille précédente pour tester l'autre coté !
Depart VOIE_GARAGE_11 Arrivee VOIE_GARAGE_15
VOIE_GARAGE_11
AIGUILLE_12
AIGUILLE_10
AIGUILLE_20
AIGUILLE_6
VOIE_1
AIGUILLE_5
AIGUILLE_19
VOIE_GARAGE_10
AIGUILLE_4
AIGUILLE_2
VOIE_2
AIGUILLE_17
VOIE_3
AIGUILLE_13
VOIE_5
VOIE_6
VOIE_7
VOIE_8
VOIE_9
AIGUILLE_8
AIGUILLE_7
VOIE_0
AIGUILLE_4
AIGUILLE_6
VOIE_4
AIGUILLE_16
AIGUILLE_13
AIGUILLE_15
VOIE_27
VOIE_GARAGE_26
AIGUILLE_0
VOIE_25
AIGUILLE_18
VOIE_23
AIGUILLE_14
VOIE_22
VOIE_21
VOIE_20
VOIE_19
VOIE_18
AIGUILLE_11
AIGUILLE_9
VOIE_16
AIGUILLE_1
AIGUILLE_0
VOIE_17
AIGUILLE_3
VOIE_GARAGE_15
Bon, j'ai 2 ans de retard sur Denis mais je me prépare pour la suite ...
Amicalement
Dominique
-
Bravo Dominique !
Je suis content que tu te sois frotté au problème des itinéraires, liés au fait qu'il faut bien décrire le réseau d'une manière ou d'une autre.
La méthode de Jean-Luc est basée sur une remarque "simple" : ce que les modélistes appellent un réseau est pour les mathématiciens un graphe.
Depuis Léonard Euler (1707-1783) et les ponts de Königsberg, on connait la puissance des graphes, avec leurs nœuds et leurs arcs qu'on peut parcourir de différentes façons
De nombreuses recherches (depuis 300 ans !), des bibliothèques pour différents langages : il y a de la matière.
L'autre intérêt de son programme, c'est la gestion très subtile de la place mémoire.
Ce que j'en ai retenu de fondamental, c'est la notion de connecteur, extrêmement puissante.
J'ai (aussi) utilisé cette méthode, avec quelque subtilités supplémentaires :
1°) Je n'ai pas de liste des départs ou des arrivées. On part de n'importe quel signal vers n'importe quel signal.
2°) On peut effacer l'itinéraire en plein milieu (si on s'arrête) et en changer. Et même changer de sens à ce moment.
3°) On peut chaîner les itinéraires automatiquement
Donc, Dominique, tu es sur la bonne voie ;D ;D
PS : j'ai fini ma nouvelle mouture de mon éditeur (1300 lignes en moins) et il reste quelques bugs sur la nouvelle mouture du gestionnaire, avec une loco. Bientôt sur le forum.
PPS : si on m'avait dit un jour que je caserai les ponts de Königsberg sur Locoduino, je ne l'aurais jamais cru. 8)
-
Les itinéraires pas si faciles que cela en a l'air.
Avec une bonne représentation de la topologie d'un réseau il est assez facile de trouver des chemins entre une voie d'origine et une voie de destination. Avec toutefois deux problèmes classiques :
- en général il y a plusieurs chemins possibles (sur des réseaux pas trop simples) et il faut faire un choix
- il faut éviter les bouclages (beaucoup de nos réseaux sont en boucle)
Un chemin n'est pas forcement un itinéraire. A la SNCF un itinéraire part d'une voie avec un signal CARRE, dans le sens du signal, pour aller vers une voie répertoriée comme fin d'un itinéraire (voies à quai, voies de départ ou d'arrivée, voies de garage, tiroirs, …), voie qui n'a pas forcément de signal. Il faut aussi que toutes les voies empruntées par l'itinéraire soient parcourables dans le sens de l'itinéraire.
Un itinéraire tel que défini précédemment ne sert pas à grand chose, il faut pouvoir l'établir et aussi le détruire. L'établissement nécessite deux phases :
- vérification que l'itinéraire est établissable (vérification des enclanchements)
- établissement effectif de l'itinéraire (manoeuvre des aiguilles et des signaux)
Pour qu'un itinéraire soit établissable plusieurs conditions sont nécessaires :
- pas de cisaillement ou de nez à nez avec d'autres itinéraires déja établis
- en transit rigide toutes les zones de l'itinéraire doivent êtres libres
- en transit souple des zones peuvent êtres occupées, mais les signaux doivent pouvoir présenter le sémaphore
- la zone de la voie d'arrivée doit être libre (pas de train), sinon il faut que le signal à l'origine de l'itinéraire puisse présenter un feu manoeuvre (blanc lunaire)
Si l'itinéraire est établissable alors il faut manoeuvrer les aiguilles, puis ouvrir le ou les signaux en présentant les bons feux.
Un itinéraire est détruit automatiquement par le passage d'un train, mais il doit pouvoir être détruit manuellement sous conditions :
- pas d'enclanchement d'approche (train ayant vu l'avertissement du carré ouvert)
- pas de zones occupées (pas de train dessus)
Il peut être pratique de pouvoir enregistrer les itinéraires non établissables (voire de les sur-enregistrer).
Certains appareils de voie (TJD, TJS, aiguille triple ou croisement) peuvent compliquer la définition de la topologie du réseau ainsi que l'établissement des itinéraires.
Cordialement
Pierre