# Optimizing a Maze-Path

Hi guys

I’m having trouble optimizing a path through a maze (Maze is black lines)
The robot saving ALL turns into an array, and when the bot hits the finishing line, the values from the Array have to be optimized for the direct path.

The values in the array are very simple:

S = Straight
L = Left turn
R = Right turn
B = Back

So the End-Array will look something like FLBLFRFRBLLBLFRFRBSBLBLFRFLBL which represents the complete path.

The rules optimizing this path are very simple, too:

LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S

Since these rules put B’s (backward) in the optimized Path, optimization has to run several times over, because B means backwards, and that isn’t an optimal path.

This Code just runs it once, finds matches and puts them in Optimizedpath.

``````/*
LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S

*/

//Yes the path is static, and not dynamic. This is a test, sketch I made...
char path = {'F','L','B','L','F','R','F','R','B','L','L','B','L','F','R','F','R','B','S','B','L','B','L','F','R','F','L','B','L'};
int slidingwindow = 0;
char optimizedpath;
int optimizedpathcount = 0;

void setup(){

Serial.begin(9600);

}

void loop (){

if (slidingwindow <= 30){

//Printing the Raw Path
Serial.print("Path: ");
for (int i = 0; i <= 30; i++){
Serial.print(path[i]);
}

//New Line
Serial.println("");

Serial.print("Slidingwindow: ");
Serial.print(slidingwindow);
Serial.println("    ");
Serial.print("Optimizedpathcount: ");
Serial.print(optimizedpathcount);

//New Line
Serial.println("");

//Printing the Optimized Path
Serial.print("Optimized Path: ");
for (int i = 0; i <= 10; i++){
Serial.print(optimizedpath[i]);
}

//New Line
Serial.println("");
//New Line
Serial.println("");

delay (1000);

// ####Optimize Path ####

if(path[slidingwindow] == 'S' && path[slidingwindow + 1] == 'B' && path[slidingwindow + 2] == 'S'){
optimizedpath[optimizedpathcount] = 'B';
optimizedpathcount++;
}

else if(path[slidingwindow] == 'S' && path[slidingwindow + 1] == 'B' && path[slidingwindow + 2] == 'L'){
optimizedpath[optimizedpathcount] = 'R';
optimizedpathcount++;
}

else if(path[slidingwindow] == 'R' && path[slidingwindow + 1] == 'B' && path[slidingwindow + 2] == 'L'){
optimizedpath[optimizedpathcount] = 'B';
optimizedpathcount++;
}

else if(path[slidingwindow] == 'L' && path[slidingwindow + 1] == 'B' && path[slidingwindow + 2] == 'S'){
optimizedpath[optimizedpathcount] = 'R';
optimizedpathcount++;
}

else if(path[slidingwindow] == 'L' && path[slidingwindow + 1] == 'B' && path[slidingwindow + 2] == 'R'){
optimizedpath[optimizedpathcount] = 'B';
optimizedpathcount++;
}

else if(path[slidingwindow] == 'L' && path[slidingwindow + 1] == 'B' && path[slidingwindow + 2] == 'L'){
optimizedpath[optimizedpathcount] = 'S';
optimizedpathcount++;
}

slidingwindow++;

}

}

/*  #### Template ####

if(path[slidingwindow] == '' && path[slidingwindow + 1] == '' && path[slidingwindow + 2] == ''){
optimizedpath[optimizedpathcount] = '';
optimizedpathcount++;
}

*/
``````

This code spits out:

Which is semi-correct.

The thing is, that if i DO NOT get a match, the original value (from Path variable) needs to be stored in the Optimizedpath Variable.

Been trying around, and couldn’t get it to work.

Summary: If the Path is RLBL then Optimizedpath should be RS (Because LBL gets optimized to S) and not just S like in the moment.
If there is no match, I need the original path values in the Optimizedpath, because (if there’s nothing to optimize) the values ARE good already.

Do you just need a final ELSE that does whatever is needed if there is no match?
Something like

``````else {
optimizedpath[optimizedpathcount] = path[slidingwindow];
}
``````

I imagine the tests could be greatly shortened by using some of the string (small s) functions. But the result would be the same.

...R

``````char path
....
for (int i = 0; i <= 30; i++){
Serial.print(path[i]);
``````

Errrm.

You could use a while loop, to call the function over and over. Loop until the function makes no changes, then quit. Of course that assumes that you have a function, and that the function reports whether or not it made any changes - two things you don't (currently) have.

In addition to PaulS’s idea it would also be worth using a function to do each comparison and update.

Edit

In fact i’m sure there is a string (mull terminated array of char) function that will check the string “a” starts with string “b”.

Part of the strcmp(), strcpy() group.

Mark

I'm having trouble optimizing a path through a maze (Maze is black lines)
The robot saving ALL turns into an array, and when the bot hits the finishing line, the values from the Array have to be optimized for the direct path.

That's a bit vague - is this on a grid? is it even rectilinear? Do you have complete
information on the maze or only on part that has been explored?

I only have the explored path. Path is eplored Left-hand-on-Wall.

Now listen guys, this is very simple.

We have "Building" that can be shortened into "House".
We have a String consisting of "X" and "Building".
Every time I hit an "X", I want to copy that X in my shortened Path.
Every time I hit a "Building", I want to copy "House" in my shortened Path.
Raw String: XBuildingXXXXBuildingXXBuildingXXXXXBuildingXXXXXXXXXXBuildingXXBuildingXXXXX
Expected Result: XHouseXXXXHouseXXHouseXXXXXHouseXXXXXXXXXXHouseXXHouseXXXXX
Can anyone post a snippet how to solve this? I mean it can't be that hard, can it??

I mean it can't be that hard, can it??

Not if you had a string. Since you (claim to) have a String, you are on your own.

This is quite a bit more complicated than you appear to realize. Take a look at these two pairs of situations.
Each pair has same original left-hand-on-the-wall algorithm, but they resolve to different optimized paths.
L left, R right, B back (turn around), S go straight

johnnygueggu:
Can anyone post a snippet how to solve this? I mean it can't be that hard, can it??

I thought I did in Reply #1

If my idea does not work I need your feedback to help me figure out an alternative.

...R