Étape 7: Simplification (optimisation) le chemin d’accès
Revenons à notre exemple. À la recherche du premier groupe d’intersections, nous avons réalisé le le premier volet de gauche est en fait un « Dead End » et donc, si le Robot au lieu d’une "gauche-arrière-gauche" seulement passé directement à la première intersection, beaucoup de temps et d’énergie serait sauvé ! En d’autres termes, une séquence « LBL » en effet serait le même que le « S ». C’est exactement comment le chemin d’accès complet peut être optimisé. Si vous analise toutes les possibilités où une « U turn » est utilisé, l’ensemble des 3 intersections où ce "revirement" ("B") s’affiche ("Xavier") peuvent être réduite à une seule.
Ce qui précède n'est qu’un exemple, ci-dessous vous pouvez trouver la liste complète des possibilités (essayer) :
- LBR = B
- LB = R
- RBL = B
- SBL = R
- SBS = B
- LBL = S
Prenez le chemin d’accès complet ou notre exemple, nous pouvons réduire il :
chemin d’accès = [LLBSBLLBSLLLBL] == > LBL = S
chemin d’accès = [SLLBSBLLBSLL] == > LBS = R
chemin d’accès = [SLRBLLBSLL] == > RBL = B
chemin d’accès = [SLBLBSLL] == > LBL = S
chemin d’accès = [SSBSLL] == > SBS = B
chemin d’accès = [SBLL] == > SBL = R
chemin d’accès = [RL]
Incroyable ! En regardant l’exemple c’est très clair que si le robot prend droit au premier carrefour et après cela, un à gauche, elle atteindra la fin du labyrinthe dans le plus court chemin !
Le premier chemin de labyrinthe solveur code total est consolidé dans la fonction mazeSolve(). Cette fonction est en fait la fonction loop() utilisé avant, mais intégrant toutes les étapes d’optimisation de stockage et de chemin d’accès.
À la fin de la première voie, l’array chemin aura le chemin optimisé. Une nouvelle variable est introduite
unsigned int status = 0 ; résolution = 0 ; atteindre la fin du labyrinthe = 1
Ci-dessous la fonction de premier chemin d’accès :
Sub mazeSolve(void)
{
tandis que (! statut)
{
readLFSsensors() ;
interrupteur (mode)
{
affaire NO_LINE :
motorStop() ;
goAndTurn (gauche, 180) ;
recIntersection('B') ;
rupture ;
affaire CONT_LINE :
runExtraInch() ;
readLFSsensors() ;
Si (mode! = CONT_LINE) {goAndTurn (gauche, 90) ; recIntersection('L');}
d’autre mazeEnd() ;
rupture ;
affaire RIGHT_TURN :
runExtraInch() ;
readLFSsensors() ;
Si (mode == NO_LINE) {goAndTurn (droit, 90) ; recIntersection('R');}
d’autre recIntersection('S');
rupture ;
affaire LEFT_TURN :
goAndTurn (gauche, 90) ;
recIntersection('L');
rupture ;
affaire FOLLOWING_LINE :
followingLine() ;
rupture ;
}
}
}
Ici une nouvelle fonction a été introduite : recIntersection (direction)
Cette fonction servira pour magasin l’intersection et également d’appeler une autre fonction simplifyPath(), qui permettra de réduire le groupe des 3 intersections impliquant un "demi-tour" comme nous l’avons vu avant.
Sub recIntersection(char direction)
{
chemin d’accès [pathLength] = direction ; Stocker l’intersection dans la variable path.
pathLength ++ ;
simplifyPath() ; Simplifier le chemin savant.
}
Le crédit pour la simplifyPath () la fonction est de Patrick McCabe pour le chemin d’accès de Code de résolution de problèmes (pour plus de détails, visitez https://patrickmccabemakes.com! La stratégie de simplification de chemin d’accès est que chaque fois que nous rencontrons une séquence xBx, nous pouvons le simplifier en découpant la voie sans issue. Par exemple, LBL == > S comme nous l’avons vu dans l’exemple.
Sub simplifyPath()
{
Si (pathLength < 3 || chemin [pathLength-2]! = « B ») return ; seulement simplifier le chemin d’accès si le tournant de la seconde à la dernière a été un « B »
int totalAngle = 0 ;
int i ;
pour (i = 1; i < = 3; i ++)
{
Switch(path[pathLength-i])
{
case « R » :
totalAngle += 90 ;
rupture ;
case « L » :
totalAngle += 270 ;
rupture ;
case « B » :
totalAngle += 180 ;
rupture ;
}
}
totalAngle = % totalAngle 360 ; Obtenir l’angle comme un nombre compris entre 0 et 360 degrés.
Switch(totalAngle) / / remplacer la totalité de ces tours avec un seul.
{
case 0 :
chemin d’accès [pathLength - 3] = s ' ;
rupture ;
décision 90 :
chemin d’accès [pathLength - 3] = « R » ;
rupture ;
boitier 180 :
chemin d’accès [pathLength - 3] = « B » ;
rupture ;
cas 270 :
chemin d’accès [pathLength - 3] = « L » ;
rupture ;
}
pathLength-= 2 ; Le chemin est maintenant deux étapes plus courtes.
}
