COS 226 Programming Assignment Checklist: Rogue

Frequently Asked Questions

What's the Manhattan distance? If you have two sites located a coordinates (i1, j1) and (i2, j2), then the Manhattan distance between i and j is |i1 - i2| + |j1 - j2|. Is is the length you have to travel, assuming you can only move horizontally and vertically, as in Manhattan city blocks.

How large will the dungeons be? They will likely be very small, like the sample input files. Of course, this does not give you license to use grossly inefficient algorithms, Ideally, a linear amount of work per move, but quadratic is not too bad. Here, linear means proportional to N² since the input is of size N². Do not worry much about the constants of proportionality, especially if if it makes your program easier to understand.

I want another interface method for Game.java. Am I allowed to add one? No, we will use our versions of Game.java, Dungeon.java, and Site.java, so you must stick to our specs. If you lobby convincingly to the instructor, we might add one and make it available to the whole class.

Which should I implement first, the monster or the hero? We recommend the monster strategy since it is probably easier to devise and implement. It is also a good starting point for the hero strategy.

Must my resulting strategies be optimal? That's not a requirement. We believe our implementations are optimal on the dungeons supplied, but there are dungeons on which they are sub-optimal. We will award extra credit if you supply such a dungeon.

Can I run my ideas by the staff members? Of course. We will do our best to poke holes in your strategies if we can.

Do I need to use an explicit Graph? No, but if you do, you can reuse the graph code from lecture or the Sedgewick book. Otherwise, you will have to re-create BFS and DFS (which is good programming experience).

Can I cheat? The game engine Game.java is not industrial strength, and there may be some opportunities to cheat the system. Your monster and hero implementations must play by the rules. However, to encourage security awareness, we will award some extra credit if you indicate any weaknesses you can exploit and what changes you would need to make to prevent such hacking.

Input, Output, and Testing

Test dungeons. We have crafted a number of sample dungeons, named dungeon[A-Z].txt, each with a different starting configuration. Each file contains a brief description of what the dungeon is testing. You will certainly want to use some of these as test cases, and we will draw some of our grading test cases from these inputs.

Submission and readme

Readme. Here is a template readme.txt file. Please answer all of the questions.

Grading. Your monster and hero strategies will face off against our super-secret implementations in a fight to the death.

Possible Progress Steps

• Download the directory rogue. This directory is mirrored on arizona at /u/cos226/pub/rogue. It contains a number of sample dungeons and the game engine (Game.java, Site.java, Dungeon.java, and In.java).

• Try out your strategies with the interactive versions of the game rogue1.jar and rogue2.jar. In rogue1.jar, you are the monster and your goal is to intercept the computer rogue; in rogue2.jar, you are the rogue and your goal is to evade the monster. To run the executable jar files, use the following commands.

  % java -jar rogue1.jar < dungeon.txt
  % java -jar rogue2.jar < dungeon.txt
  

• Programs Monster.java and Rogue.java provide a template for the players. At each step the player chooses a random move among all legal moves. Run the game using the default monster and rogue implementations.

  java Game < dungeon.txt | more
  

• To implement the monster's strategy, you will almost certainly want to use BFS. Start with the provided file Monster.java, but rewrite the method move to implement your strategy. You may wish to modify the constructor so that it builds a graph of the underlying dungeon. If you do so, be sure to thoroughly test that it's building the graph correctly.

• To implement the rogue's strategy, you may want to use both BFS and DFS. You can learn about using DFS to find the bridges in a graph in Sedgewick, Chapter 18.6.

Enrichment Links

Is there a Java version of the game? Certainly, here is Rogue.

Where can I learn more about Rogue? Here is a description of the 26 monsters and information on weopons, potions, and treasure.