What to Record: Build Algorithm
By: Matt Shellhammer (Electronics & Control Engineer)
Approved by: Lucas Gutierrez (Project Manager)
Table of Contents
Introduction
To navigate throughout the maze we must record and update the information about the robots location within the maze. This will be done by using the maze stored in program memory, a two dimensional array to store information about direction and intersections, and a subroutine called “enterRoom”.
Methodology
To update the information about the maze as navigating throughout the maze I have developed a subroutine called “enterRoom”. What this subroutine does is calls three additional subroutines: “turnInMaze”, “stepInMaze”, and “roomInMaze”. I developed all of these subroutines using a structure called robot_inst that includes the following information: direction, turn, row, column, room, and bees. Then when calling these subroutines I simply send an instance of this structure to the subroutine and then store the result of enterRoom within that instance.
The subroutine turnInMaze uses the turn and direction values from the robot_inst structure and return a new direction value within robot_inst.
The subroutine stepInMaze uses the direction, row, and column values from robot_inst to return updated row and column values within robot_inst.
The subroutine roomInMaze uses the current row and column values to update the room and bees values within robot_inst.
Software
Main .ino file
////////////////////////////////////////////////////////////////
// Name : Update room
//
// Author : Matt Shellhammer
//
// Date : 18 October, 2017
//
// Version : 1.0 //
////////////////////////////////////////////////////////////////
#define __PROG_TYPES_COMPAT__ // __PROG_TYPES_COMPAT__
#include <avr/pgmspace.h>
#include "maze.h"
void setup() {
Serial.begin(9600);
delay(5000);
}
void loop() {
// Robot is outside of maze in the bottom left corner
// Initialization within structure prototype
static myRobot_t robot_inst; // create an instance of myRobot_t called robot_inst
static boolean newRoom = 0;
static uint8_t room_idx = 0;
// If we make a turn in the real world then we have to update robot_inst.turn
// to match the turn exicuted in the real world.
if (newRoom == 1){
robot_inst = enterRoom(robot_inst);
currRow = robot_inst.maze.row;
currCol = robot_inst.maze.col;
nextDir[room_idx] = robot_inst.dir;
room_idx++;
newRoom = 0;
}
}
Virtual instructions
myRobot_t enterRoom(myRobot_t current){
current = turnInMaze(current);
current = stepInMaze(current);
current = roomInMaze(current);
}
myRobot_t turnInMaze(myRobot_t current_1){
// index = 4*turn_val + dir_val
uint8_t index = (current_1.turn << 2) + current_1.dir;
current_1.dir = pgm_read_byte_near(turn_table + index);
return current_1;
}
myRobot_t stepInMaze(myRobot_t current_2){
// index = 2*current_2.dir
uint8_t index = (current_2.dir << 1);
current_2.maze.row += pgm_read_byte_near(map_table + index); // Add either -1, 0, or 1 to current
// row value.
current_2.maze.col += pgm_read_byte_near(map_table + index + 1); // Add either -1, 0, or 1 to current
// column value.
return current_2;
}
myRobot_t roomInMaze(myRobot_t current_3){
// index = 21*current_3.maze.row + current_3.maze.col
uint16_t index = (21*current_3.maze.row) + current_3.maze.col;
uint8_t maze_val = pgm_read_byte_near(theMaze + index);
current_3.room = maze_val & 0x0F; // clear upper nibble and store as the room value
uint8_t temp_bees = (maze_val & 0xF0) >> 4; // clear lower nibble and store as the temp bees value
current_3.bees += temp_bees; // add temp_bees to curret bees value
return current_3;
}
Header file
// Autonoumous maze arrays
uint8_t currRow;
uint8_t currCol;
uint8_t nextDir[256] = {0};
struct coord_t{
uint8_t row = 0x13;
uint8_t col = 0x00;
};
struct myRobot_t{
uint8_t dir = 0x03; // Robot is initially facing north
uint8_t turn = 0x00; // First action is no turn
coord_t maze;
uint8_t room = 0x00; // Initial room is empty
uint8_t bees = 0x00; // No bees present
};
//Compass S E W N
//dir 00 01 10 11
const uint8_t turn_table[] PROGMEM =
{0b00, 0b01, 0b10, 0b11, // 00 no turn
0b10, 0b00, 0b11, 0b01, // 01 turn right
0b01, 0b11, 0b00, 0b10, // 10 turn left
0b11, 0b10, 0b01, 0b00 // 11 turn around
};
// row col dir
const int8_t map_table[] PROGMEM =
{1 , 0, // 00
0 , 1, // 01
0 , -1, // 10
-1 , 0 // 11
};
const int maze_length = 399;
const uint8_t theMaze[] PROGMEM =
// 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14
{0x05,0x09,0x09,0x09,0x09,0x09,0x01,0x03,0x05,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x29,0x09,0x09,0x09,0x02, // 00
0x0C,0x09,0x09,0x03,0x05,0x09,0x0A,0x06,0x06,0x05,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x03,0x05,0x03,0x06, // 01
0x05,0x09,0x0B,0x06,0x06,0x05,0x09,0x0A,0x06,0x0C,0x09,0x09,0x09,0x09,0x09,0x01,0x0B,0x0C,0x0A,0x06,0x06, // 02
0x06,0x0D,0x09,0x0A,0x06,0x06,0x05,0x03,0x0C,0x09,0x09,0x03,0x05,0x09,0x09,0x0A,0x05,0x09,0x09,0x08,0x02, // 03
0x06,0x05,0x09,0x09,0x0A,0x06,0x06,0x0C,0x09,0x09,0x09,0x0A,0x0C,0x09,0x09,0x03,0x06,0x05,0x09,0x09,0x0A, // 04
0x06,0x0C,0x03,0x05,0x09,0x02,0x06,0x05,0x09,0x09,0x09,0x09,0x09,0x09,0x03,0x06,0x06,0x0C,0x03,0x05,0x03, // 05
0x06,0x05,0x0A,0x0C,0x03,0x06,0x06,0x06,0x05,0x01,0x03,0x07,0x05,0x03,0x06,0x06,0x06,0x05,0x0A,0x06,0x06, // 06
0x06,0x0C,0x09,0x03,0x0E,0x0C,0x04,0x02,0x06,0x06,0x06,0x06,0x06,0x06,0x0C,0x02,0x06,0x0C,0x06,0x02,0x06, // 07
0x06,0x05,0x0B,0x0C,0x09,0x09,0x09,0x04,0x02,0x06,0x06,0x06,0x06,0x0C,0x09,0x0A,0x04,0x09,0x0B,0x06,0x06, // 08
0x0C,0x08,0x09,0x09,0x09,0x09,0x01,0x01,0x02,0x06,0x0C,0x08,0x08,0x09,0x01,0x09,0x08,0x09,0x03,0x06,0x06, // 09
0x05,0x01,0x09,0x09,0x0B,0x07,0x06,0x04,0x02,0x0C,0x09,0x09,0x09,0x03,0x04,0x09,0x03,0x07,0x06,0x06,0x06, // 0A
0x06,0x0C,0x09,0x09,0x09,0x02,0x06,0x04,0x02,0x0D,0x09,0x09,0x09,0x0A,0x0C,0x03,0x06,0x06,0x06,0x06,0x06, // 0B
0x06,0x05,0x09,0x09,0x09,0x0A,0x06,0x0C,0x0A,0x05,0x09,0x09,0x09,0x09,0x03,0x06,0x06,0x06,0x06,0x06,0x06, // 0C
0x06,0x0C,0x09,0x09,0x09,0x03,0x04,0x09,0x09,0x08,0x0B,0x05,0x03,0x05,0x0A,0x06,0x06,0x06,0x06,0x06,0x06, // 0D
0x04,0x09,0x09,0x09,0x09,0x08,0x02,0x05,0x01,0x09,0x03,0x06,0x06,0x06,0x05,0x0A,0x0E,0x06,0x06,0x06,0x06, // 0E
0x06,0x05,0x09,0x09,0x09,0x09,0x0A,0x0E,0x06,0x07,0x06,0x06,0x06,0x06,0x06,0x05,0x09,0x0A,0x06,0x06,0x06, // 0F
0x06,0x0C,0x09,0x09,0x09,0x09,0x09,0x09,0x0A,0x06,0x06,0x06,0x06,0x0E,0x0E,0x06,0x05,0x09,0x0A,0x06,0x06, // 10
0x04,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x0A,0x0C,0x0A,0x06,0x05,0x09,0x0A,0x06,0x0D,0x09,0x0A,0x06, // 11
0x04,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x08,0x08,0x09,0x09,0x08,0x09,0x09,0x09,0x0A, // 12
};