I'm trying to make some robots which can solve mazes with loops and want to do it using Pledge Algorithm:
The Pledge algorithm is more sophisticated than wall-following and solves a larger class of mazes because it can jump between islands. The basic idea of the Pledge algorithm is that you pick an absolute direction (such as North, South, East, or West) and always try to go in that direction. I'll call this direction your favored direction. When you run into a wall, you turn right and do left-hand wall-following until you're facing your favored direction and the sum total of your turns is zero (where clockwise turns are considered negative and counter-clockwise turns are considered positive). At that point, you continue going straight in your favorite direction again, and so on. The requirement that your turns sum to zero is necessary to keep you from getting caught in certain loops, such as one shaped like a capital G (try it out on paper to see what I mean).
-from http://www.ibm.com/developerworks/java/library/j-robots/
or http://www.astrolog.org/labyrnth/algrithm.htm
My Problem is, that i can't get it to work.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
//I have the fallowing functions:
int movef() //Moves forward in the right direction, returns 1 if it was able to move, 0 if it wasn't
void turnl() //turns left
void turnr(; //turns right
int rfree() //returns 1 if it is possible to move right
int lfree() //returns 1 if it is possible to move left
//And the fallowing variables:
int entry[2]
int exit [2]
int turns // the counting variable which decides if i can move in my chosen direction again
int x,y //my current position
This is what my mazesolving function currently looks like:
When you run into a wall, you turn right and do left-hand wall-following until you're facing your favored direction and the sum total of your turns is zero
So the idea is that I cannot do 4 turn right.
However here you are allowing that to happen. this->turn=this->turn % 4;
You may want to encapsulate the turn++; inside of turnr() so you don't forget to update it.
Please indent your code, is difficult to follow when the different cases apply.
1 2 3
if (this->dir == 's' //assuming that it is your preferred direction
and (this->turn % 4 == 0) //¿zero turn?
and (rfree())) //¿why right free?
Alright, i encapsulated the counting and removed that contraproductive rfree()-check.
What exaclty do you mean with "indent your code. . . different cases" ? Did you mean the tabs? I kinda reworked those now ;)
I think i fixed the if statement, but the this->turn=this->turn % 4; itself is correct, right? Might not be needed, but as i display it for debugging reasons it's more than helpful to have low numbers instead of -153 and the sort.
void rob::dolab(){
this->turn=0;
this->steps=0;
this->dir='s'; //starting direction = prefered direction
cout <<this->x<<" und "<<this->y<<endl<<laby->exit[0]<<" und "<<laby->exit[1]<<endl; //print entry and exit (Debugging)
//Print the unused labyrinth
laby->labarray[this->x][this->y]='E';
for(int x = 0; x<laby->labarray.size(); x++){
cout<<laby->labarray[x]<<endl;}
while (movef()); //for other prefered directions, shouldn't do any harm
while (1){//actually doing the lab
this->turn=this->turn % 4; //keeping the count low, for human eyes
if (this->dir == 's' && (this->turn % 4 == 0)){ //if the direction is right and it untwisted itself: Move until it hits the next wall
while(movef());
if (rfree()){ //priority 1: Go right
turnr();
movef();
}elseif (lfree()){//priority 2: Go left
turnl();
movef();
}else{ //Dead end, turn around
turnr();
turnr();
movef();
}
}elseif (lfree()){ //while fallowing a wall: If passage left: Go left
turnl();
movef();
}elseif (movef()){ //while fallowing a wall: no passage left + passage ahead: Go straight
}else{ //while fallowing a wall: no passage left or ahead: Definitly go right (maybe to turn around)
turnr();
movef();
}
if(this->x == laby->exit[0]){ //check if finished
if(this->y == laby->exit[1]){
break;
}
}
}
}
also, lots of comments
€:
The Code works fine for simple mazes without loops aswell as unicursal ones. But it gets stuck in some loops
turn == 8 means that he should have untwisted himself. Or am I wrong here? So that turn must be exactly 0?
When wall following, count the number of turns you make, e.g. a left turn is -1 and a right turn is 1. Only stop wall following and take your chosen direction when the total number of turns you've made is 0, i.e. if you've turned around 360 degrees or more, keep wall following until you untwist yourself
€:HOLY FRAKADOODLE!
That was it! I changed it to turn == 0 and it worked!
Thank's a lot man!
In this maze he hasn't yet finished the labyrinth, even though he already reached the finish.
He arrives from the right, enters the finish, continues to his left, comes back at some point and then he actually reaches it.
Do i have a mistake in my finish-reached-break?
strangely it is only in this labyrinth, so far all others work fine.