Project 1: Timing maze

You are navigating an unusual outdoor maze. The maze consists of a 100x100 array of cells. Each cell has four doors, one in each orthogonal direction. A door may be open or closed at any point in time. To move to an adjacent cell, two doors must be open: the door in the present cell facing the neighboring cell, and the door in the neighboring cell facing the current cell. We'll call these ``touching'' doors.

Each door is on its own timing loop, specified by an integer frequency n. If n=0 then the door is always closed. If n=1 then the door is always open. Otherwise, the door is open precisely every nth turn in the game. $n\leq L$ where L is a game parameter set at the start of the game and known to the player.

You have the aid of a drone which flies directly above you and can observe all doors within a radius of r and report to you whether the door is open or closed on the current turn. r is also a game parameter known to the player.

A map contains an assignment of frequencies to doors, with the constraint that doors that are on the perimeter of the maze have n=0. A map also designates a cell as a start cell, and another cell as a target cell. The game starts with the player on the start cell, and the player's goal is to find and move to the target cell in as few turns as possible. The drone will be able to recognize the target cell if it is within the radius r from your current position. A map is valid if every cell is reachable from every other cell, i.e., there is no group of always-closed doors that partitions the maze. The simulator will check that a map is valid before starting the simulation.

The player does not know the global coordinates of the start cell or the target cell. The simulator will report values in a coordinate system centered on the player's current cell. As the game progresses, the player might be able to infer global coordinates as the drone encounters the perimeter of the maze.

Each group will be asked to come up with three ``interesting'' maps at the start of the project, one ``easy,'' one ``medium'' and one ``difficult''. The simulator will also have the functionality to generate random valid maps in which each non-perimeter door frequency has uniform probability from 0..L and start and target cells are chosen at random. The simulator will use a random number seed so that the same map can be generated for multiple runs.

Things to think about:

• What is the worst-case waiting time at a door with frequency n>1 assuming that the touching door has nonzero frequency?
• Is navigating a random maze different from navigating a designed maze?