Project 4: Explorandum

A new island continent Terra Incognito has been discovered, and explorers from each of $p$ colonial powers have set out to claim territory for their countries. Each explorer arrives at a randomly chosen designated arrival point on the coast of Terra Incognito, and begins searching from there. Your job is to write a computer program to guide one of these explorers in her quest to claim as much territory as possible. ($p$ will probably correspond to the number of project groups.)

Territory is divided into square cells according to standard latitudinal and longitudinal lines. (Assume the continent is small enough that we don't have to worry about the Earth's curvature.)

The coast of Terra Incognito may not be convex. Water is impassable, but does not constitute an obstruction to visibility. Thus you might see a promontory across the water without having to make the long trip around the water to visit it. Lakes in the interior of the continent are possible.

There may also be impassable mountains within the continent. Mountains are an obstruction to both movement and vision.

In order to claim a cell of territory, an explorer must see it. Using her binoculars, an explorer can see all cells whose center is within a Euclidian distance of $d$ from the center of the cell occupied by the explorer. However, if there are mountains anywhere along the line between the centers of the two cells, then the candidate cell is not observable, even if it is within $d$ units.

An explorer may move between cells as long as the destination cell is not impassable (i.e., water or mountain). An orthogonal move takes 2 hours of travel time, while a diagonal move takes 3 hours. You may assume that the continent is contiguous, and that impassable cells do not partition the continent, so that every passable cell is reachable from every other passable cell along some path.

Explorers do not start with any knowledge of Terra Incognito beyond what they can see. You may find it useful to build up a map of the continent as your exploration progresses. If another explorer is on an observable cell, you will see her. A cell may contain multiple explorers.

Exploration lasts for $n$ hours (our explorers do not sleep!) where $n$ will be chosen in advance. We will try a variety of differently shaped continents, and various values of $n$. Explorers will know $n$, but not the exact size of the continent. (We might try unusually large or small values of $n$, to test strategies at the extremes. You can't assume that $n$ is necessarily a proxy for the area of Terra Incognito.)

The claiming of territory is governed by the international treaty of new continent exploration:

A cell of territory can only be claimed if it is observed; a cell remains unclaimed if it has never been observed. Cells containing mountains and water are claimed in the same way that passable cells are claimed. At the end of $n$ hours of exploration, competing claims are resolved as follows:

Each cell is awarded to the colonial power that has observed it most closely, i.e., from the smallest distance. In the event of a tie, the cell goes to the power that observed the cell first from that smallest distance. In the event of a second tie, the cell is awarded randomly to one of the tied powers.

A corollary of this convention is that the first explorer to set foot (alone) on a cell (observing it at distance 0) will claim that cell.

The score of each player will be the fraction of the available cells that they claim for their country.

One or two sample maps will be initially provided, but I'll also ask each group to come up with a map that is interesting to them. There are various ways a map may be interesting, and so hopefully we'll get a variety of map types.

For the tournament at the end of the project, we'll discuss in class which maps to use. The instructor/TA will also design one or two maps that you won't have seen in advance. We'll try different values of $d$ and $n$ to see how that affects strategy.

Some things to think about:

• You won't know where other players have been, and you won't know the score until the end. What can you do to at least estimate how well you're doing?
• What (if anything) should you do if you spot another explorer during your travels?
• How would you respond to different types of terrain (e.g., open spaces versus many obstructions)?
• An explorer will know $p$, $d$, and $n$ at the start of the exploration, and will have access to the time taken so far. How would these values be used to choose a strategy?
• Is it ever worth revisiting an area?