Project 4: Mirror Universe

You are searching through a grid-like landscape, trying to find the exit cell. You don't know the map in advance, but you can gather information about your local surroundings as you travel. There are obstacles in your way, and the map as a whole is surrounded by obstacles. You can see beyond the obstacles, even if you cannot travel through them.

So far, this seems like a simple enough search problem. However, you are searching in a mirror universe. What that means is that your movement commands (the eight principal compass directions) are obeyed by two different agents, traversing different maps. These maps may differ in size, and in the density of obstacles. If one agent is asked to move in a direction with an adjacent obstacle, that agent stays put, while the other agent will move if his corresponding neighboring cell is free. As the agents move around, you get more information about each of their maps.

The primary goal of this project is to get the two agents to their respective exits on the same move. An agent stops moving altogether when he reaches an exit. If one of your agents reaches an exit and the other does not, your score goes up by 1 for each extra move needed by the second agent before he reaches his exit. (A smaller score is better.)

In the event of ties, e.g., if two groups both succeed at getting their agents out simultaneously, rank will be based on who used the fewest moves overall. But the total number of moves is a secondary measure: it is definitiely worth investing extra moves in order to get the agents to their exits closer in time.

You get information about a square region aligned with the grid and centered at your current location. The side length of this square is 2r+1 where r is a parameter. You can assume that each map is no larger than 100x100. Each time the game starts, the player will begin at a random location that is not the exit cell. To enable repeatable simulations, there will be a random number seed input to the simulator.

Some maps will be provided, and others will be generated by you. Maps must be connected, i.e., every cell without an obstacle must be reachable from every other cell. We'll have a tournament at the end in which some of the maps will not have previously been seen. In the tournament, you will not be allowed to save information (such as a map of the terrain) from one game to the next.

Some things to thing about:

• How might you use obstacles to align your two agents?
• How do you balance your effort searching the two maps, particularly when the open territory on each map is in a different direction?
• Are some kinds of exits (e.g., those on the corner of a map) harder to deal with than others?