Design and implement an effective strategy to seek out and intercept a moving adversary. Design and implement an effective counter-strategy to avoid being intercepted by such an adversary.
Historical perspective. In the late 1970s, Ken Arnold designed a C library (later to be named curses) that enabled the user to put a character at a specific location on the screen, enabling a crude form of interactive graphics. While experimenting with this new library, Michael Toy and Glen Wichman, designed a graphical adventure game coined Rogue. The purpose of Rogue is "to descend into the Dungeons of Doom, defeat monsters, find treasure, and return to the surface with the amulet of Yendor using its levitation capabilities." This revolutionary game became the undisputed most popular game on college campuses after it was included in BSD Unix 4.2 in 1980. It would later spawn the role-playing game (RPG) genre, including its direct descendant NetHack.
In 1984, a group of grad students at CMU developed a computer program named Rog-o-matic to automatically play the game of Rogue. At one time, the Rog-o-matic player was the highest rated Rogue player at CMU. A crucial component of the Rog-o-matic algorithm was to avoid contact with the monster for as long as possible, so that the your health could regenerate before confronting the monster in a battle to the death. This involves an interesting graph search problem, and is the inspiration for this programming assignment.
Rules of the game. The game of Rogue is played on an N-by-N grid that represents the dungeon. The rogue (typically a human player) is represented with the character @. The monster is represented by an uppercase letter. (In the real game of Rogue, there are 26 different monsters named A through Z, each with different capabilities.) The monster and rogue take turns making moves, with the monster going first. If the monster intercepts the rogue (occupies the same site), then the monster burns/freezes/bludgeons the rogue to death, and the game ends. In each turn, a player either remains stationary or moves to an adjacent site. There are three types of sites: room, corridor, and wall, and they are represented by '.', '+', and ' ', respectively. If the player is in a room site, then they can move to an adjacent room site in one of the 8 compass directions (N, E, S, W, NW, NE, SW, SE) or a corridor site in one of the 4 directions (N, E, S, W). If the player is in a corridor site, then they can move to an adjacent room or corridor site in one of the 4 directions (N, E, S, W). The walls are impenetrable.
+ + + + + . . . . . . . . A .
+ + . . . . . . . . . .
. . . . . . . . + . . . . . . . . . .
. . . . . @ . . + . . . . . . . . . .
. . I . . . . . + . . . . @ . . . . .
. . . . . . . . + . . . . . . . . . .
. . . . . . . . + . . . . . . . . . .
+ + . . . . . . . . . .
+ + . . . . . . . . . .
+ + + + + . . . . . . . . . .
Monster's strategy. The monster is tenacious and its sole mission is to chase and intercept the rogue. A natural strategy for the monster is to always take one step toward the rogue. In terms of the underlying graph, this means that the monster should compute a shortest path between itself and the rogue, and take one step along such a path. This strategy is not necessarily optimal, since there may be ties, and taking a step along one shortest path may be better than taking a step along another shortest path. For example, in the first dungeon below the Bat Monster's only optimal strategy is to take a step in the NE direction. Moving N or E would enable the rogue to make a mad dash for the opposite corridor entrance. In the second dungeon, the Centaur Monster can guarantee to intercept the rogue by moving E.
+ + + + + + + + + + + + +
+ + + +
. . . . . . . + . . . . . . . . +
. . . . . . . + . . . . . . . . +
. . . . @ . . + . . C . . @ . . +
. . B . . . . + . . . . . . . . +
. . . . . . . + . . . . . . . . +
. . . . . . . + + + + +
. . . . . . . + +
. . . . . . . + + + + +
Your first task is to implement an effective strategy for the monster.
Rogue's strategy. The rogue's goal is to avoid the monster for as long as possible. A naive strategy is to move to an adjacent site that is as far as possible from the monster's current location. It is easy to see that this strategy may lead to a quick and unnecessary death, as in the second dungeon below where the rogue can avoid the Jabberwock Monster by moving SE. Another potentially deadly strategy would be to go to the nearest corridor. To avoid the Flytrap Monster, the rogue must move towards a northern hallway.
10 + + + . . . . . . . + + . . . . . . . + + + . . . . . @ . . . . . . . . . . . . + + + . . . . . . . . . . . + . . . . . . . . . . . + + + . . . . + + + + + . . . . . . J @ . . . + + . . . . . . . . . . . + + + + + . . . . . . . . . . F . . . . . . .
A more effective strategy is to identify a sequence of adjacent corridor and room sites which the rogue can run around in circles forever, thereby avoiding the monster indefinitely. This involves identifying and following certain cycles in the underlying graph. Of course, such cycles may not always exist, in which case your goal is to survive for as long as possible.
Input format. The input dungeon consists of an integer N, followed by N rows of 2N characters each.
10
+ + + + + + + +
+ +
. . . . . . . +
. . . . . . . +
. . . . @ . . +
. . B . . . . +
. . . . . . . +
. . . . . . . + + +
. . . . . . .
. . . . . . .
The rogue game engine. So that you can concentrate on the strategy part of the program, we provide some of the infrastructure. Your task is to write a program Monster.java that has the following interface.
and an analogous program Rogue.java.public Monster(Game g) // create a new monster who is playing a game g public Site move() // return the adjacent site to which you are moving
public Rogue(Game g) // create a new rogue who is playing a game g public Site move() // return the adjacent site to which you are moving
Program Game.java reads in the dungeon from standard input and does the game playing and refereeing. It has three primary interface functions that will be needed by Rogue.java and Monster.java.
Program Dungeon.java represents an N-by-N dungeon.public Site getMonsterSite() // return the site occupied by the monster public Site getRogueSite() // return the site occupied by the rogue public Dungeon getDungeon() // return the dungeon
Program Site.java is a tiny data type that represents a location site in the N-by-N dungeon.public boolean isLegalMove(Site v, Site w) // is moving from site v to w legal? public boolean isCorridor(Site v) // is site v a corridor site? public boolean isRoom(Site v) // is site v a room site? public int size() // return N = dimension of dungeon
public Site(int i, int j) // instantiate a new Site for location (i, j) public int i() // get i coordinate public int j() // get j coordinate public int manhattan(Site w) // return Manhattan distance from invoking site to w public boolean equals(Site w) // is invoking site equal to w?
Deliverables. Submit your version of Monster.java and Rogue.java, along with any accompanying code and readme.txt. Justify your strategies, explaining their strengths and weaknesses.
Extra credit. Submit some interesting dungeons that are useful for debugging, testing, and developing strategies. Describe each dungeon and why it is useful or interesting. Creativity will also be a factor.
Challenges for the bored. There are limitless additional possibilities for creativity here. We don't really expect that you can do these now, but try them sometime for a challenge. Allow two monsters that can coordinate their attack. Make it work on arbitrary graphs. In the real game, you don't even know the whole graph until you start walking through it, so account for this. In the real game, the rogue collects treasure, potions, and powerful weapons while traveling through the dungeon. Modify your strategy to maximize the amount of material collected, while still avoiding the monster.
This assignment was developed by Andrew Appel and Kevin Wayne.