# A2: Adventure
**Deadline:** Wednesday, 09/21/16, 11:59 pm
*This assignment is to be done as individuals, not with partners nor with teams.*
In this assignment, you will develop a *text adventure game*
(TAG), also known as *interactive fiction*. The
characteristic elements of TAGs include gameplay driven by
exploration and puzzle-solving, and a text-based interface
in which users type natural-language commands and the game
responds with text. The classic example of this genre is the
[Colossal Cave Adventure][cave].
**Exercise:** Spend a few minutes playing an [online version of
Colossal Cave Adventure][playcave] before you read the rest of
this assignment. (But note that game is far bigger than what
you will build in this assignment.)
[cave]: http://rickadams.org/adventure/
[playcave]: http://www.amc.com/shows/halt-and-catch-fire/exclusives/colossal-cave-adventure
## Overview
For this assignment, you are to implement a *game engine* that
could be used to play many *adventures*. Here, the game
engine is an OCaml program that implements the gameplay and
user interface. An adventure is a [JSON][json] data file that is
input by the game engine and describes a particular gaming
experience: exploring a cave, hitchhiking on a spaceship,
finding the missing pages of a powerful magical book, etc.
This factoring of responsibility between the engine and
input file is known as *data driven design* in games.
[json]: http://json.org/
The gameplay of TAGs is based on an *adventurer* moving between *rooms*.
Rooms might represent actual rooms, or they might be more
abstract—for example, a room might be an interesting location in a
forest. Each room also has a text description associated with it. Some
rooms have *items* in them. These items can be taken by the adventurer
and carried to another location, where they can then be dropped. The
adventurer begins the game in a predetermined *starting* room, possibly
with some predetermined items.
The *player* does not so much win a TAG as *complete* the TAG by
accomplishing various tasks: exploring the entire *map* of rooms and
corridors, finding items, moving items to specified locations, etc. To
indicate the player's progress toward completion, a TAG gives a player a
numeric *score*. The TAG also tracks the number of *turns* taken by the
player. Savvy players attempt to achieve the highest score with the
lowest number of turns.
The interface to a TAG is based on the player issuing text *commands* to
a *prompt*; the game replies with more text and a new prompt, and so on.
Thus, the interface is a kind of read-eval-print-loop (REPL), much like
`utop`. For this assignment, commands will generally be two-word phrases
of the form "VERB OBJECT":
* **Movement** is performed by using the verb "go" followed by the
direction. The room itself determines what the allowed directions are;
common possibilities include "north", "south", "east", "west", "up", and
"down", but those are by no means the only possibilities.
If such movement is possible, the adventurer transitions to a
new room, and the description of the new room is displayed. If the
movement is impossible, an error message is displayed. As a
*shorthand*, the player may simply type the direction itself without the
verb "go". For example, "go north" and "north" are equivalent.
* **Items** can be manipulated by the verbs "take" and "drop" followed
by the name of the item: "take" transfers an item from the current room
to the adventurer's *inventory*, and "drop" transfers an item from the
inventory to the current room. If an item is present in a room, it must
be mentioned when the room is described.
* **Other commands** include "quit", which ends the game, "look", which
re-displays the description of the current room, "inventory" (shorthand:
"inv"), which gives a list of what the adventurer is currently carrying,
"score", which displays the current score, and "turns" which displays
the current number of turns.
For this assignment, scoring will be as follows:
* The player starts with zero points, but might automatically receive
more as described below.
* Every room is worth a certain number of points, which are earned simply
for having entered the room at least once. The player automatically
gets whatever points are associated with the starting room at the
beginning of play.
* Every item is worth a certain number of points. The points for an
item are earned if the item is currently located in that item's *treasure room*.
Different items may have different treasure rooms. Dropping an item
in the item's treasure room earns points, and taking the item away
from that room loses points. The player automatically gets whatever points
are associated with items already located in their treasure room at
the beginning of play. Taking or dropping an item in a room
other than its treasure room is permitted but has no effect on the score.
Items in the adventurer's inventory are not located in any room;
they must be dropped to be considered as located in a room.
The *maximum score* for a game is sum of all the item points plus the
sum of all the room points, regardless of whether it's actually possible
to earn those points. If the player does earn the maximum score
possible for the adventure, the game engine informs the player that they
have completed the adventure, but the player is still allowed to interact
with the game after that point—it doesn't automatically quit. So
the player's score might go down again.
For this assignment, a *turn* is any successfully completed issue of the commands
"go" (or any of its shorthand forms), "take", or "drop". For example,
"go north" counts as a turn only if the current room permits exit to the
north. At the beginning of play, the current number of turns is zero.
Your task is to develop a game engine and to write a small adventure of your own.
## Objectives
* Design and use data types, especially records and variants.
* Write code that uses pattern matching and higher-order functions on lists and
on trees.
* Interact with the environment outside the program by reading and writing
information from files and the user.
* Use JSON, a standard data format.
* Practice writing programs in the functional style using immutable data.
## Recommended reading
* [Lectures and recitations 4–7][web]
* [RWO chapter 15][rwojson]
* The front page of the [JSON website][json]
[web]: http://www.cs.cornell.edu/Courses/cs3110/2016fa/
[rwojson]: https://realworldocaml.org/v1/en/html/handling-json-data.html
## Requirements
The primary requirements are the following:
1. Your game engine must implement all the functionality and commands described
in the Overview above.
2. Your game engine must be compatible with the adventure file format
described in the appendix titled "Adventure file format",
so that we can test your engine on our own adventures.
3. You must implement the required functions provided as templates in the release code
and described in the appendix titled "Testing interface".
4. You must submit an OUnit test suite, as described below.
5. Your game engine must be robust: we should not see any unhandled exceptions,
infinite loops, or other faulty behavior during our testing of it.
6. The text interface must be case-insensitive. For example, "go north" and "GO NORTH" and
"Go NoRtH" should all be recognized and treated as the same.
7. Your own small adventure must have at least 5 rooms and 3 items.
8. Your code must be written with good style and be well documented.
All functions, except for nested helper functions, should have specification comments
written in the style of those we provided for you in A1.
9. You must submit an overview document, as described below.
As for gameplay, we leave most of it up to your own creativity. In grading,
we will not be strictly comparing your interface's text output against
expected output, so you have freedom in designing the interface.
## What we provide
In the release code on the course website you will find these files:
* A template file `game.ml` and `game_test.ml` for your implementation
of the game engine and an OUnit test suite, and a file `main.ml` that
runs the game engine.
* A couple small adventure files, `oneroom.json` and `tworoom.json`, that you could
use as a basis for writing new adventures.
* A JSON schema `schema.json` for adventure files that defines
the format of such files. Most people will want to ignore this file,
but we provide it for those who want an exact description of the JSON format
for adventures.
* A file `.ocamlinit` that will help automatically load some code into `utop`
each time you launch it. This should help with testing. Feel free to modify
this file.
* Some additional scripts for compiling your code.
## What to turn in
Submit files with these names on [CMS][cms]:
* `main.ml`, containing your game driver
* `game.ml`, containing your game engine.
* `game_test.ml`, containing your OUnit test suite.
* `adv.json`, containing your new adventure.
* `overview.txt` or `overview.pdf`, containing your overview document.
[cms]: https://cms.csuglab.cornell.edu/
## Grading issues
* **Late submissions:** Carefully review the course policies on
[submission and late assignments][late]. Verify before the deadline on CMS
that you have submitted the correct version.
* **Environment, names, and types:** Your solution must compile and run
under OCaml 4.03.0. You are required to adhere to the names and
types of the functions specified below. Your solution must pass the
`make check` described below in Part 0. Otherwise, your solution will receive minimal
credit.
* **Code style:** Refer to the [CS 3110 style guide][style].
Ugly code that is functionally correct will nonetheless be penalized.
Take extra time to think and find elegant solutions.
[late]: http://www.cs.cornell.edu/Courses/cs3110/2016fa/syllabus.php#late
[style]: http://www.cs.cornell.edu/Courses/cs3110/2016fa/handouts/style.html
## Prohibited OCaml features
You may not use imperative data structures, including refs, arrays,
mutable fields, and the `Bytes` and `Hashtbl` modules. Strings are
allowed, but the deprecated (mutable) functions on them in the `String`
module are not. Your solutions may not require linking any additional
libraries/packages beyond OUnit, Yojson, Str, and ANSITerminal.
You may and in fact must use I/O functions provided by the
`Pervasives` module, even though they cause side effects,
to implement your user interface.
## Overview document
For this assignment, you are to turn in an *overview document* as
described by this [handout on overview documents][overviewdocs]. Think
of this is an expanded version of the feedback document you wrote for
A1. We aren't providing a template, but that handout does describe all
the required material you should discuss; you should read the handout
carefully. The handout also provides an example overview document for an
old assignment.
[overviewdocs]: ../handouts/overview.html
## Part 0: Sanity check
First, install an additional OPAM package:
```
opam install ansiterminal
```
Everyone needs to *install* the package. No one actually needs to *use*
this package to solve the assignment, but some people might want it for
sake of the karma problems or for building a richer user interface. As
an example, the provided `main.ml` file uses it to make one line of output be red.
Second, download the release code. Run `make check` from the folder containing
the release code. You should get output that includes the following
(other lines might be interspersed):
```
===========================================================
Your OCaml environment looks good to me. Congratulations!
===========================================================
Your function names and types look good to me.
Congratulations!
===========================================================
```
If instead you get warnings about your OCaml environment, seek help
immediately from a consultant: something is wrong with the version of
OCaml you have installed.
Assuming your environment is good, you should not get warnings about
about your function names and types at this point. As you complete the
assignment, you should periodically re-run `make check` to ensure that
you haven't changed the names or types of any of the required functions.
Although that script does its best to determine whether your names and types
are correct, in the end it's your responsibility to make sure that you've
adhered to the required names and types as described in the Appendix.
Running `make test` or simply `make` will build your OUnit test suite in
`game_test.ml` and run it. Running `make play` will build your game engine
in `main.ml` and launch it. Running `make clean` will delete
generated files produced by the make and build systems.
## Part 1: Design
A1 was structured in several parts, which progressively
built on one another; most of the design had been done for you.
But on A2, you're assuming most of that responsibility.
Begin by reading this entire writeup and making sure you have a good
understanding of it. The next thing you should do is spend a good bit of
time, maybe a whole day, sketching out on paper how you're going to
solve this assignment. Your focus should be on identifying what features
you need to implement, what data structures and functions you'll need
for those features, and how you'll go about testing those data
structures and functions during the process of implementing them.
Waiting until the very end to test is a recipe for disaster!
We provide the following design tips to help you get started.
**Model:** One of the first things you should design is the data type(s)
you will use to capture the state of the game: what the map is,
where the adventurer is located, what items are in the inventory, etc.
Those data type(s) are called the *model* of the game, and the most important
of them will be the `state` data type that is used in the release code. It will be
difficult to implement your game engine if you repeatedly make changes
to the model during the implementation. So get the design of it done early
and try not to make last-minute changes.
**Representing the map:** Identify what data structure would be
appropriate for representing the map. Investigate the JSON
representation in the adventure file (and described below) to get some
inspiration about what might or might not be appropriate.
- If you're thinking about hash tables, remember they (the `Hashtbl` module in particular)
are imperative data structures hence are prohibited. But hash tables
are just one way to implement a *dictionary*, and we have seen
dictionaries implemented with association lists in this class already.
- If you're thinking about graphs, and are struggling with how to implement them
functionally, consider an adjacency list representation (as you learned in 2110).
Rather than attempting to use pointers (which are imperative), it might help to
use identifiers (e.g., strings) for nodes.
- It might be helpful to know that the adventure files with which we
test your code will never have huge maps in them; as a rough estimate
there might be on the order of 100 rooms and 100 items.
**REPL:** Think carefully about how to structure the main read-eval-print "loop"
of your game: keep the amount of code in it small by defining and
calling additional functions. Sketch out how you will implement the
eval phase with an eye toward whether your model is appropriate.
**Testing:** Consider how you will use the testing interface (described below)
to write OUnit tests for your own implementation. You might want to
create some JSON test adventures of your own for this purpose.
## Part II: Implementation and Testing
After you have spent time thinking about the design of your game engine,
start implementing. Be smart about how you approach this part: don't
try to build everything all at once. Instead, build out small pieces of
functionality and test them individually, as you did in A1. If the
assignment begins to feel a bit overwhelming and open-ended at this
point, it could be useful to speak with a consultant to get advice about
where you are and how to proceed.
Here are some implementation tips on specific pieces of functionality that
you need to build:
[str]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Str.html
[yojsonbasic]: http://mjambon.com/yojson-doc/Yojson.Basic.html
**Text interface:**
All the console I/O functions you need are in the `Pervasives` module. Some
people might want to investigate the `Printf` module for output, but
it's not necessary. The `Scanf` module is overkill for input in this
assignment; in fact the `read_line` function in `Pervasives` is probably
all you need.
**Parsing player commands:** Although you are unlikely to need
any functionality outside of the standard `String` module,
you are welcome to use the OCaml [Str library][str].
**Parsing adventure files:**
We recommend using the [Yojson library's Basic module][yojsonbasic] for parsing JSON
adventure files. Although you are welcome to use any functionality
provided by the library, we suggest concentrating your attention
as follows:
* Use `Yojson.Basic.from_file` to read the contents
of a JSON file and construct a `Yojson.Basic.json` tree.
* Use the `Yojson.Basic.Util` module to extract information
from that tree. That module might seem intimidating at first,
but there are really a very small number of functions that you
need. In fact, you can implement your entire parser with just
these: `member`, `to_list`, `to_string`, and `to_int`.
[RWO chapter 15][rwojson] has a tutorial on Yojson. But the ATDgen library
and tool at the end of the tutorial is not permitted for use on this assignment;
using it would preclude some of the list and tree processing that we want
you to learn from this assignment.
In keeping with the requirement that your game engine be robust, if an
adventure file is ill-formed according to the specification given in the
Appendix, your engine should cleanly shut down rather than raise an
exception.
**Testing:** There are two aspects to testing this assignment.
The first is to create an OUnit test suite in `game_test.ml`.
The second is to playtest your REPL.
* *Unit testing*: Write unit tests to determine whether the initial
state computed by your JSON parser is correct. Also write unit tests to
determine whether the state is updated correctly based on commands. Your
unit tests should use the testing interface described in the Appendix.
You are not required to submit unit tests for any functions beyond those
in the interface (e.g., helper functions you design yourself), though of
course you are permitted to do so.
* *Playtesting:*
When your implementation is reaching maturity, get your non-3110 friends to play
an adventure using your game engine. A good game that no one can learn to play is a bad
game! Here is some advice on playtesting:
- Pay attention to what your playtesters say about the game.
- Observe where and how they run into trouble.
- Bear in mind not to coach them while they play.
- Don't take any criticism personally.
- Remind them to think out loud as the play—you want to know
everything going on in their head.
Gameplay will be only a small part of the grading. But bear in mind
that really poor gameplay could make it difficult or impossible for the
grader to assess your submission.
## Part 3: Your own adventure
Write and submit your own adventure that a grader will play using your own engine.
(If your engine is somehow non-operable, the grader will attempt to play it using
the staff's own engine.) We ask you to do this for two reasons. First, it
will help you understand the adventure file format and implement your game engine.
(So you need not do this part last!) Second, it provides you with an opportunity
for some creativity, which we encourage but will not assess as part of your grade.
If there are some really great adventures submitted, we will consider making them
available for other students to play.
## Karma
You are highly encouraged to go beyond the minimal
requirements for this assignment as described above.
But, no matter what you implement, be sure to maintain
compatibility with the basic adventure file format and
required commands. Note that it should be possible to add
additional information (e.g., properties and objects) to the JSON
file and still remain compatible with the required schema.
All your karma implementation must be located within the required
files you are submitting to CMS; it cannot rely on additional files.
**Experienced Adventurer:**
* getting lost
* item sizes and weights, and inventory limits on those
* game save and restore
* consumable items (e.g., money, which could be earned and spent)
* time passing as adventurer explores, with effects occurring as a result
(e.g., the sun rises and sets, and what is possible changes as a result)
* other in-game characters (which could be stationary or could themselves
wander around) with which the adventurer can have conversations
**Seasoned Adventurer:**
* text-based graphics to display images of rooms, a map of the area
explored so far, etc.
* a level editor that makes it easy for designers to create adventure files
without having to write JSON themselves
**Master Adventurer:**
* a larger vocabulary of commands that enables designers to create puzzles
and players to solve them (e.g., manipulating items and rooms—locks and
keys are a good place to start)
* flexible command parsing so that users can type in interesting natural
language instead of two-word commands
* an automated bot that completes adventures without human assistance
## Appendix 1: Testing interface
Your submission is required to define the types, exceptions, and functions that
are specified below. Submissions that do not provide these will receive minimal credit.
```
(* [state] represents the state of an adventure. You may choose whatever
* definition you wish for it. *)
type state
(* [Illegal] is raised by [do'] to indicate that a command is illegal;
* see the documentation of [do'] below. *)
exception Illegal
(* [init_state j] is the initial state of the game as
* determined by JSON object [j] *)
val init_state : Yojson.Basic.json -> state
(* [max_score s] is the maximum score for the adventure whose current
* state is represented by [s]. *)
val max_score : state -> int
(* [score s] is the player's current score. *)
val score : state -> int
(* [turns s] is the number of turns the player has taken so far. *)
val turns : state -> int
(* [current_room_id s] is the id of the room in which the adventurer
* currently is. *)
val current_room_id : state -> string
(* [inv s] is the list of item id's in the adventurer's current inventory.
* No item may appear more than once in the list. Order is irrelevant. *)
val inv : state -> string list
(* [visited s] is the list of id's of rooms the adventurer has visited.
* No room may appear more than once in the list. Order is irrelevant. *)
val visited : state -> string list
(* [locations s] is an association list mapping item id's to the
* id of the room in which they are currently located. Items
* in the adventurer's inventory are not located in any room.
* No item may appear more than once in the list. The relative order
* of list elements is irrelevant, but the order of pair components
* is essential: it must be [(item id, room id)]. *)
val locations : state -> (string*string) list
(* [do' c st] is [st'] if it is possible to do command [c] in
* state [st] and the resulting new state would be [st']. The
* function name [do'] is used because [do] is a reserved keyword.
* - The "go" (and its shortcuts), "take" and "drop" commands
* either result in a new state, or are not possible because
* their object is not valid in state [st] hence they raise [Illegal].
* + the object of "go" is valid if it is a direction by which
* the current room may be exited
* + the object of "take" is valid if it is an item in the
* current room
* + the object of "drop" is valid if it is an item in the
* current inventory
* + if no object is provided (i.e., the command is simply
* the bare word "go", "take", or "drop") the behavior
* is unspecified
* - The "quit", "look", "inventory", "inv", "score", and "turns"
* commands are always possible and leave the state unchanged.
* - The behavior of [do'] is unspecified if the command is
* not one of the commands given in the assignment writeup.
* The underspecification above is in order to enable karma
* implementations that provide new commands. *)
val do' : string -> state -> state
```
## Appendix 2: Adventure file format
Adventure files are formatted in JSON. We provide in the release code a
couple example adventure files, which for most people will probably be
adequate for describing the file format. Note that the JSON property
names in that file may not be changed. Also note that many of the
property values are strings, which can contain arbitrary characters
(including whitespace). An adventure file contains five main entries:
* The rooms. Each room contains five entries:
- an id,
- a description,
- the number of points exploring the room is worth,
- the exits from the room (an exit itself contains two entries: the
direction of the exit, and the room to which it leads), and
- the treasures that should be dropped in the room.
* The items. Each item contains three entries:
- an id (which is the item's name by which it can be taken and dropped),
- a description, and
- the number of points the item is worth when it is dropped in its designated room.
* The starting room (where the adventurer begins).
* The starting items (which are initially in the inventory).
* The starting locations of all items not in the inventory. Each location contains
two entries:
- the id of the item
- the room id where the item starts
For those who desire precision, we provide a JSON schema for
adventure files in `schema.json`. Your game engine is required to be
compatible with this schema, which defines the required elements of the
file and their names. It is possible for you to extend this schema
to add more functionality to your engine, but you must make sure that
you don't remove any properties or objects and that you maintain support
for adventures that don't have your additional features. Otherwise,
the course staff will be unable to grade your submission using our test suite
of adventures. Using a JSON [schema validator][validator], you can check the
well-formedness of an adventure file again the schema.
[schema]: schema.json
[validator]: http://www.jsonschemavalidator.net/
## Appendix 3: Plan of attack
Purely as a suggestion, here's one way you might approach the implementation
part of this assignment.
1. Implement the loading of an adventure file into a `json`-typed value, including
any exception handling that would help make your engine robust.
2. Implement converting that JSON into OCaml types, including designing
the types. Do some interactive testing in `utop` to check whether it looks
like the conversion is being done right.
3. Implement the game state, including producing the initial state,
and all the required functions except `do'`. Write an OUnit test suite
using those required functions to make sure the initial state is correct for
some small adventure files.
4. Implement parsing of a string into a verb and object (if any),
including designing a type to represent commands. Do interactive
testing in `utop` to make sure all the commands that need to be supported
are being correctly parsed.
5. Implement `do'` and write a OUnit test suite for some test adventure files.
6. Implement the REPL, test it interactively, and get a non-3110 friend to
playtest it for you.
If you took six days to do the implementation, spending one day per each of the
above tasks, you would stay on track to meet the submission deadline.
Tasks 2 and 5 are probably the hardest, but YMMV.
* * *
**Acknowledgement:** Adapted from Prof. John Estell (Ohio Northern University).