# 2015 Project 1A

## Overview

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.

## Getting Started and Example Navigator

Download the code here: media: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);
}
}
```

You are to write a memoryless function, navigate() in the file navigate.c. In terms of C code that means your navigate.c code can have no global or static variables. Your challenge is to write it so that it is able to solve as many potential navigation problems as possible. It should be able to solve all of the test_worlds/convexX problems that contain only convex obstacles. Note that there are some convex problems that may not be solvable due to the limited sensing your robot has. You will receive bonus points if your navigator can solve concave problems we throw at it.

Exception: It is allowable to use a static variable if necessary to support random number generation. That's the only use of memory allowed.

## Resources and Ideas

The Bug 0 algorithm is a good place to start for a memoryless algorithm. Here's a link [1]. Once you have Bug 0 going, consider how it can be defeated and see if you can improve it. Hint: Any deterministic memoryless navigator can be defeated.

## What to Turn In

Via t-square turn in attachments only:

• Your code in 1 file, navigate.c