Next: Project 2: Embuzzled Up: W4444 Programming and Problem Previous: Group Membership for Projects
This project was given to the students of the 2008 class. At the end of that project, the students felt that it still had room for further development of the ideas. So we're going to re-use the same project, with one important modification that I'll mention later. The 2009 class will get to see the 2008 reports and submitted code on courseworks, and be able to build on the previous work. Of course, you're welcome to start from scratch if you think you have a new way of approaching the problem. (An advantage of starting with a previous problem is that it is easier to learn the mechanics of working with the provided programming interface.)
Directly building on the code from last year is acceptable, but keep the following points in mind:
Here's the 2008 description:
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:
For 2009, we're going to extend the 2008 description with one potentially significant item that was suggested during class discussions last year. Unlike in 2008, an explorer will observe footprints on the current cell if that cell has been visited before, by anybody. With this small piece of extra information, an explorer might choose to modify the search, given the knowledge that somebody has been to the area previously.