CSE 151 Final Project

How the Code Works

return Home

Introduction:

Our MINDSTORMS robot uses a program written in NQC.  The code is relatively straightforward, and for the most part the comments make everything clear.  The purpose of this document is to explain the data structures and basic algorithms used.

Maze requirements and basic robot motion:

This program assumes the use of a special maze environment.  The maze must be divided up into a grid of equally sized squares.  Walls may only be placed on gridlines, and any given section of wall must be placed on a side of a grid-square.  The gridlines must be black.  This grid allows the robot to determine at all times where it is within the maze, as well as where it has already been.  Currently, the maze can be no larger than 4x4 grid squares, but this could be modified (see below).  There is a gray grid that's offset from the black grid.  The robot uses the gray grid for alignment.

The first and biggest problem we encountered was the difficulty of getting our robot to make a near-perfect 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 grid-square.  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.

Data storage:

Maze representation:

The robot uses an internally maintained bit string to keep track of where it has already been in the maze.  Each bit represents a grid square.  A 0 indicates that the square has not yet been visited, and a 1 indicates that it has.  The ordering of the bits is relatively simple.  The last four bits represent the top row of the maze.  Left-to-right ordering within a row is the same as the actual maze.  The penultimate four bits represent the second row of the maze, and so on.  Here is a more graphical explanation:
 
sample maze grid
1
2
3
4
5
6
7
8
9
0
A
B
C
D
E
F

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:
 
X
X
 
X
 
X
 
X
 
X
X
X
 
X
   

This would be stored as follows:  0100 0111 0101 1101

Our coordinate system places (0,0) at the top-left corner.  The vertical coordinate, i, increases downwards.  The horizontal coordinate, j, increases rightwards.  Thus, our bitmap updating equation is:  bitmap += 1 << (4*i + (3-j)).  The 1 <<(4*i + (3-j)) 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 + (3-j)) can be ANDed with the bitmap.  If the result is 0, then the location has not been visited.

Directions:

The robot keeps track at all times of what direction it is facing.  This is necessary for general navigation.  The process is fairly simple.  The possible directions are coded as follows:
 
 
NORTH=0
 
WEST=3
 
EAST=1
 
SOUTH=2
 

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.

Recent move stack:

This directional coding system is also used to keep track of recent moves.  Each move is stored as the direction the robot traveled.  For example, if the most recent move was SOUTH, the robot knows it needs to go NORTH to back up one square.

The actual stack implementation is very crude.  This is partially due to the limitations of NQC, but mostly because a (quickly-coded) crude stack was perfectly sufficient for a smaller maze like ours.  Basically, four variables are updated regularly:  lastmove, lastmove2, lastmove3, and lastmove4lastmove2 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.

Maze-solving algorithm:

The basic algorithm is to go forward until a wall is reached. While traveling, a separate task will note when a new square is entered, and update the bitmap. When a wall is hit, we enter a decision loop. This loop looks for a new path, and once it is found, returns us to the beginning, where we are moving forward again.

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.

Parting note:

Finally, it is important to note that our robot is accompanied by a LEGO figure of Darth Maul.  Although unproven, we believe that The Force Is With Us, and we do not give any assurances about performance without the addition of a Jedi Knight.  We recommend the use of a Sith Lord only when absolutely necesssary, as they are prone to deception and/or mutiny.


return Home