The first and biggest problem we encountered was the difficulty of getting our robot to make a nearperfect 90° turn. It had to be very close, because small errors would eventually add up and we would be traveling in an entirely wrong direction. We chose to deal with this problem by adding the special "turning grid" inside each gridsquare. Each square of the maze must therefore be divided in four equal parts by an inner grid, whose lines are gray. Rather than attempting to turn for a given amount of time, which proved inconsistent, our robot will turn until it detects this gray "calibrating line".
Another problem with movement in the maze was getting our robot to travel in a straight line. The gray inner grids solve this problem as well, by forming a consistent gray line along the center of any two squares. We were therefore able to program our robot to follow this gray line whenever traveling forward.
















The squares above would match the bits in the string as follows: CDEF 90AB 5678 1234
Here is an example. A square with an X has been visited already:












This would be stored as follows: 0100 0111 0101 1101
Our coordinate system places (0,0) at the topleft corner. The vertical coordinate, i, increases downwards. The horizontal coordinate, j, increases rightwards. Thus, our bitmap updating equation is: bitmap += 1 << (4*i + (3j)). The 1 <<(4*i + (3j)) yields the bitmask for the current location's bit. It's then added to the overall bitmap to mark that location visited. To check if a given spot has been visited already, the mask 1 << (4*i + (3j)) can be ANDed with the bitmap. If the result is 0, then the location has not been visited.






When the robot makes a turn, it updates the direction using addition and modulus operations. When turning right, Direction = (Direction+1)%4 and when turning left, Direction = (Direction+3)%4.
The actual stack implementation is very crude. This is partially due to the limitations of NQC, but mostly because a (quicklycoded) crude stack was perfectly sufficient for a smaller maze like ours. Basically, four variables are updated regularly: lastmove, lastmove2, lastmove3, and lastmove4. lastmove2 is the second most recent move made, and so on. Every time a new square is entered, that move is pushed onto the stack. When the robot has to back out of a dead end, the stack is popped.
The loop checks each direction for a new path. More specifically, it looks at each adjacent square. If the square is not blocked by a wall, and has not already been visited, then it is a new path. If there is no new path available from the current square, then we back up to the square we just came from and repeat the loop.
return Home