C Code for Line-Maze Algorithm

A student recently asked me for help on writing the C code to fill and edit the “turns” array for a line maze robot. Here is my reply which may help some…

So, your code will look something like…

int main(void)
{
  char turns[50]; // Use a number here that is bigger than the number of turns you expect in the maze
  char turn = 'U' /* This would be for a U-Turn. I use these characters for the turns:
		'L' = Left
		'R' = Right
		'S' = Straight
		'U' = U-Turn 
		The array starts out with nothing */

  int pointer = 0; //Points to the next available position in the array.

  //Now, each time you take a turn, add it to the list, like...
  // (Say you took a left turn, so turn = 'L')
  turns[pointer] = turn;	//This puts an L in the first position of the array
  pointer++		//Add one to the pointer so the next letter goes in the next position in the array.

  // and later you take a left, then a U-Turn, then come back to the intersection and take a left. The array now looks like:
  // turns = 'LLUL'
  // showing that the first four turns were left, left, u-turn, then a left.

//EVERY time you take a turn, go to a function called 'check' to see if the next-to-last character in the array is a 'U'.
//If the next-to-last character is a 'U', then the last turn was unnecessary.
//check() will look something like:

void check(turns, int pointer)
{
  if (len(turns) < 3)	//Need at least three characters for this algorithm to work
    return;

  if (turns[pointer] - 1 != 'U') // Exit if the next-to-last turn is NOT a U-Turn
    return;

  //Then pick out the possibilities and replace the last three characters with the turn the robot SHOULD HAVE TAKEN INSTEAD.
  //I'll do 2, you do the others...

  if (right.turns[3] == 'LUL')	//Look at the right three characters in the array
    pointer = pointer - 3;	//shorten the array by 3 characters. We'll "chop off" the LUL and replace with S
    turns[pointer] = 'S';	//The turn we should have taken (and will take next time.
    pointer++;		// set up the pointer to point to the next character in the array.

  if (right.turns[3] == 'RUR')	//Look at the right three characters in the array
    pointer = pointer - 3;	//shorten the array by 3 characters. We'll "chop off" the RUR and replace with S
    turns[pointer] = 'S';	//The turn we should have taken (and will take next time.
    pointer++;		// set up the pointer to point to the next character in the array.

//...and so on for the combinations you have in your maze.

Thanks for sharing! For anyone looking for more info on line-maze solving, we have more information in the 3pi user’s guide.

I noticed that a lot of the code you wrote in the check() function will not work in C. Did you intend to leave the process of fixing it as an exercise for the student? :wink:

–David

Correct! It is intentionally non-working code.

As a programming teacher for the last 25 years, I am a strong believer in “Don’t give them the fish- - - teach them how to fish” school of programming.

Almost always (and I believe this time) I try to give the concept. If you understand the concept of this post - - stacking/filling an array, then checking and adjusting the contents - - Then you have the algorithm. I rarely just give the student the code.