Modélisation logicielle d'un réseau - le système de Jean-Luc

[DDEFF]

Jean-Luc étant bien occupé, j'ai continué de mon côté. 

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 :



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

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 :

Code: [Sélectionner]

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 …

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 ! 

[DDEFF]

Une étape a été franchie ! 

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. 

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. 



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. 

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 ! 

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 :

Code: [Sélectionner]

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

[DDEFF]

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.

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 :

Code: [Sélectionner]

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 :

Code: [Sélectionner]

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") :

Code: [Sélectionner]

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

[DDEFF]

Trouver le meilleur itinéraire…
Vaste question !

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 :



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 …

[Pierre59]

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 :

Le programme en Processing :

Code: [Sélectionner]


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; }
}Le programme en C++ :

Code: [Sélectionner]

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 :


Pierre

[DDEFF]

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

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. 

[Pierre59]

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


 

[DDEFF]

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  )

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

[Pierre59]

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

[DDEFF]

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.

[Dominique]

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.



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), 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 

Dominique

[Pierre59]

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

[Dominique]

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 

[Jack56]

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

[Souris verte]

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.

Code: [Sélectionner]

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