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