2015 Project 1A
Overview
Ahhh, life in the Navy. It’s not just a job, it’s a robotics problem! You wake up to the sunrise after your last night of liberty in Singapore. You probably drank too much, but it was worth it. Anyhow, you find yourself amidst hundreds of cargo containers bound for Malaysia. Your watch reads seven forty-five. Uh oh, you’ve only got half an hour to reach your ship before it leaves port. Good thing that from here you can see the mast of your ship. Unfortunately, you still must negotiate the maze of cargo between here and there. Which brings us to the problem. The challenge is for you to write an efficient C routine, navigate(), for navigation across a two dimensional field with obstacles. You will splice your function into the sailor’s brain, sailor.c, and see if he makes it home. As input, your function will get a list of nearby obstacles, and an approximate heading to the ship. It should return a value indicating which way to go. Your function doesn’t necessarily have to keep track of where the sailor is, the main program will do this. main() will repeatedly call your function and move the sailor in whatever direction you say until he reaches his ship.
If your function guides our sailor home, we can measure its efficiency in three ways:
- Path length: how far did the sailor have to walk?
- Brain cells: how large is your compiled function?
- Time: how long did it take? Remember, it hurts to think with a hangover.
More Detail
Here are more details on the rules of the game: For simplicity, this game takes place on a rectangular grid, so there are only a finite number of points the sailor can occupy. In fact, the grid is 23 by 80 cells, a convenient size for ASCII character animation. At each step, the sailor may move in any of eight compass directions: north, northeast, east, etc. (from here on out we’ll abbreviate these with capital letters). Moves E, W, N or S 2 units. Each time your function, navigate(), is called it receives a list of nearby obstacles and the direction to the ship. The obstacle list is an array of nine integers set to EMPTY, OCCUPIED, or GOAL depending on whether or not a cargo container is blocking the way or the goal is adjacent to the sailor’s position. Here is how the obstacle array is indexed:
NW N NE W SAILOR E SW S SE
These symbols have been defined for you in sailor.h, so the result of an expression like if (obstacles[NW] == OCCUPIED) would tell you if there is an obstacle to the NW of the sailor. The SAILOR element is always EMPTY. Note that if you ever command the sailor to move over an obstacle your command will be ignored. The direction to the ship is also given as one of the eight compass directions. If you’d like to keep track of the sailor’s location, you’ll need to declare some static variables on your own.
Download the code here: sailor.zip, then unzip it. On a Unix machine you can run a demonstration as follows:
unzip sailor.zip cd sailor ./demo
Your navigation algorithm should be written in the file navigate.c. We provide a simple reactive example for you. Here it is:
#include "sailor.h"
int navigate(int obstacles[9], int ship_direction)
{
int i;
if (obstacles[ship_direction] == EMPTY)
return(ship_direction);
if (obstacles[ship_direction] == GOAL)
return(ship_direction);
else
{
for(i = 0; i <= 9; i++)
if ((obstacles[i] == EMPTY) && (i != SAILOR)) break;
return(i);
}
}
It uses a rather simple approach: first, it attempts to go towards the ship, but if that direction is blocked, it finds the next open direction.
You can compile and test
