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 N2 since the input is of size N2. 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 Am I allowed to add one? No, we will use our versions of,, and, 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 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

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.