For Milestone 3, we decided to implement DFS using recursion. In order to this, we wrote a function called traverseHelper. This function had parameters: coordX and coordY which corresponded to our global x and y variables. Our method of implementation gave priority to directions in the following order: front, left, right. So, if the front node has been been visited, we check the left node and if the right has been visited, we check the right node.
We initially just implemented this by checking each sensor in the above mentioned order and then turning and/or moving forward accordingly. We soon realised that in order to accurately call traverseHelper(coordX, coordY) on the node we moved to, we would have to take Arnold's direction into account. So we added a direction dependent switch statement to our code, updated our coordinates accordingly with the help of local variables nextX and nextY and then called traverseHelper(coordX, coordY) on the newly updated coordinates.
With this alone, our code correctly traversed an empty maze (no walls) using DFS but failed to return to it's starting point after that. This led us to realise that we hadn't implemented any form of backtracking for Arnold. While the recursive functions returned to their caller functions, Arnold had no idea how to move to his parent nodes. To fix this, we implemented another helper function called moveSrcToDest(dx, dy) which we called after calling traverseHelper(coordX, coordY) on the updated coordinates. This way, when the recursive functions returned to their caller, Arnold actually had a way to return to where he was when the function was called.
The function moveSrcToDest(dx, dy) takes in parameters dx and dy which are the change in x and change in y respectively. For this, we also used a direction dependent switch statement. We used this function to decide how Arnold needed to move based on the difference between his source and destination coordinates. Source coordinates in this case is where he currently is and destination coordinates refers to where he went (the coordX and coordY when the child traverseHelper() was initially called).
void moveSrcToDest(int dx, int dy) { // Dest - Src switch (dir) { case NORTH: { if (dx == -1) { turnAround(); goToIntersection(); } else if (dx == 1) { // Go forward goToIntersection(); } else if (dy == -1) { turnRight(); goToIntersection(); } else if (dy == 1) { turnLeft(); goToIntersection(); } else { // Do nothing } // goToIntersection(); break; } case EAST: { if (dx == -1) { turnRight(); goToIntersection(); } else if (dx == 1) { turnLeft(); goToIntersection(); } else if (dy == -1) { // Do nothing goToIntersection(); } else if (dy == 1) { turnAround(); goToIntersection(); } else { // Do nothing } //goToIntersection(); break; } case SOUTH: { if (dx == -1) { // Do nothing goToIntersection(); } else if (dx == 1) { turnAround(); goToIntersection(); } else if (dy == -1) { turnLeft(); goToIntersection(); } else if (dy == 1) { turnRight(); goToIntersection(); } else { // Do nothing } //goToIntersection(); break; } case WEST: { if (dx == -1) { turnLeft(); goToIntersection(); } else if (dx == 1) { turnRight(); goToIntersection(); } else if (dy == -1) { turnAround(); goToIntersection(); } else if (dy == 1) { // Do nothing goToIntersection(); } else { // Do nothing } //goToIntersection(); break; } } }
After implementing this function, Arnold was still having trouble traversing different maze configurations using DFS. We eventually realised that this was because when he returned to a particular node, he was facing a different direction than when he originally visited the node. Because of how we wrote our if-statements, this meant that Arnold didn't end up checking all paths from every node. He would sometimes end up checking one path two times. For example, when Arnold wants to go from node A to node B, he checks the front-wall sensor. Since there is no front-wall (hypothetically), he goes forward i.e. to node B. When he comes back (as part of backtracking) to node A, then he tries to check left-wall as part of the sequence (Remember our order of checking walls? Front-Left-Right). But Arnold’s left is not left anymore because it came back from node B and his direction is flipped. So we should have incorporated his previous direction and current direction while choosing walls, which we didn’t so that was the problem! We decided to fix this problem by forcing Arnold to remember his original direction and checking sensors based on that direction instead of his current direction. We kept track of the direction everytime traverseHelper was called in a variable called referenceDir. We also wrote functions for each wall Arnold could possibly see, to decide which sensor to check. The choice of sensor was dependent on the difference between referenceDir and dir (our global direction variable). The functions were frontWallDetection(referenceDir), leftWallDetection(referenceDir) and rightWallDetection(referenceDir).
Below is our fronWallDetection function, to give an idea of how all three of the wallDetection functions were written:
bool frontWallDetection(int referenceDir) { int change = referenceDir - dir; switch (change) { case -3: { return leftWall(); } case -2 : { return false; } case -1: { return rightWall(); } case 0: { return frontWall(); } case 1: { return leftWall(); } case 2: { return false; } case 3: { return rightWall(); } } }
After implementing these functions, Arnold was still struggling. He could now successfully traverse the maze but he wasn't backtracking correctly. He kept running into walls that he knew were there (as seen from the GUI). After stepping through the code and pretending to be Arnold, we realised that we were deciding where walls were based on the initial direction but we were still turning based on Arnold's current direction. This caused him to keep running into walls, because even though we fixed the checking-wall function, we still had to fix the turning function. Confused? Consider the same above example. Arnold is smart enough now to check the right wall (for instance) even though he wants to detect left wall; because he know his heading is flipped in process of backtracking. But what he still doesn’t know is the fact that his capability of turning is also flipped. What that means is, he has to dynamically decide where to turn. For example, a left turn for Arnold when he is facing North is equal to right turn when facing South. In order to dynamically decide turns, we added decideLeft() and decideRight().
Below is the code for decideLeft(), which closely mirrors decideRight() in structure:
void decideLeft(int referenceDir) { int change = dir - referenceDir; switch (change) { case -3: { //nothing break; } case -2: { turnRight(); goToIntersection(); break; } case -1: { goToIntersection(); break; } case 0: { turnLeft(); goToIntersection(); break; } case 1: { //nothing break; } case 2: { turnRight(); goToIntersection(); break; } case 3: { goToIntersection(); break; } } }
After adding those functions, Arnold was able to successfully traverse multiple maze configurations using DFS successfully. Here are a few videos of Arnold doing his thing.
Here's Arnold traversing a (nearly) empty 4x5 maze:
Here are some more complicated 4x5 mazes to fully show off our DFS and backtracking:
Here are a few instances of Arnold starting on a tone and traversing a maze: