# Design Specs for Maze Challenge Project
## Team: Group 9 - Invalid Pointer
Members: Samiha Datta, Mer Anderson, Sabrina Jain
GitHub usernames: samihadatta, meranderson, sabrinajain747
Date: February 28th, 2020; Update Date: March 9th, 2020

## User Interface

The maze challenge's only interface with the user is through the command line, which has seven arguments.

`./AMstartup -n n_avatars -d difficulty -h host_name`

For example:

`./AMstartup -n 2 -d 4 -h flume.cs.dartmouth.edu`

Users will also see the progress of avatars through an ASCII graphical user interface, which will look like the following:

samihadatta, 45751, Mon Mar  9 13:27:38 2020
******************************
Inserted avatar 0 at (1,3)
    0   1   2   3   4   5  
  +---+---+---+---+---+---+
0 |                       |
  +   +   +   +   +   +   +
1 |                       |
  +   +   +   +   +   +   +
2 |                       |
  +   +   +   +   +   +   +
3 |     0                 |
  +   +   +   +   +   +   +
4 |                       |
  +   +   +   +   +   +   +
5 |                       |
  +   +   +   +   +   +   +
6 |                       |
  +   +   +   +   +   +   +
7 |                       |
  +   +   +   +   +   +   +
8 |                       |
  +---+---+---+---+---+---+
******************************

## Pseudo Code for Logic/Algorithmic Flow

1. Execute from command line as shown in user interface (above).
2. Parse and validate arguments.
3. Client connects to the server.
4. Send `AM_INIT` to maze server to define the number. of avatars in the maze (`n_avatars`) and the maze difficulty level (`difficulty`).
5. Receive `AM_INIT_OK` message from maze server, which contains the `maze port`, `maze width`, and `maze height` (or error, in which case exit the program).
6. Start log file for game, called `log_file_name`.
* Write username, date and time to log file.
7. Parse `maze port`, `maze width`, and `maze height` from `AM_INIT_OK` message (if an error, inform the user and exit).
8. Start `n_avatars` threads (one for each `Avatar`).
* Each thread is assigned an `avatar_id`.
* Each thread has access to `n_avatars`, `difficulty`, `host_name`, `maze_port`, and`log_file_name`.
9. Each thread, once started, will send an `AM_AVATAR_READY` message to the maze server with its avatar id.
10. The avatar thread will read in `AM_AVATAR_TURN` messages from the server until there is an error (socket connection is broken, the max number of moves is exceeded, the `AM_WAIT_TIME` timer expires) or the maze is solved (all avatars at same `(x,y)` position).
1. During each turn, each avatar will update its own list of discovered points for the avatar that moved last (unless that turn is the first turn, each avatar will add all points in `AM_AVATAR_TURN` to the list of discovered points for each point's respective avatar).
2. Each avatar will check if it was the avatar that moved last and, if so, will see if its move was successful. If not, the avatar will tell the GUI to build a wall depending on which direction it moved in.
3. Each avatar will check if it is the next avatar to move.
4. If so, calculate which move to make according to the algorithm:
* Implement a left-wall traversal of the maze until all avatars converge.
* When one avatar gets to a spot that another has traversed, follow the other avatar's previously-taken footsteps.
* Eventually, the avatars will meet up and move together until all avatars have met.
* Every move, check if the avatar's previous move was successful; if so, attempt to discover an undiscovered point.
* In the case of an unsuccessful previous move, determine the direction that was last tried and instead, try a direction that hasn't failed in a systematic order.
5. The avatar who wants to move will transmit the server an `AM_AVATAR_MOVE` message detailing the direction of its movement.
6. The server will decide if the sent move is possible and update avatar's positions accordingly before sending avatars another `AM_AVATAR_TURN` message (or `AM_MAZED_SOLVED` message if the maze is now solved).
11. Once the server sends an `AM_MAZE_SOLVED` message (or an error message), each avatar thread will exit.
12. A "maze solved!" message will be written to the log file.
13. All files will be closed, data structures deleted, and pointers freed.
14. Close the connection the server and exit.

## Dataflow Through Modules
* `AMstartup` : parses the parameters, sends an `AM_INIT` message to the maze server, parses an `AM_INIT_OK` message from the server and starts avatar threads (see `avatar`).
* `avatar` : thread that represents one avatar. Receives and sends messages respectively from and to the server to run the algortithm and solve the maze.
* `avatar_info`: contains information that all avatars need to access and an avatar's unique `id`
* `message` : reads in messages from the server in the format of `AM_message` structs; also receives `AM_message` structs from clients and writes them to the server.
* `discovered`: initializes a doubly-linked list to keep track of all coordinates that have already been discovered by each avatar.
* `graphics`: displays the discovered maze in an ASCII graphical user interface. Holds information in a `matrix`.

## Major Data Structures

* An `XYPos` structure to represent different points in the maze, which can hold `x` and `y` coordinates

* An `Avatar` structure to represent each avatar, containing
* an integer `id` to identify the avatar
* an `XYPos` with the `Avatar`'s current location

* An `avatar_info` structure that contains all information that will be passed to each avatar thread:
* `n_avatars`: number of avatars in game
* `difficulty`: difficulty of game
* `maze_port`: port of maze game
* `hostname`: hostname of server
* `id`: id of avatar being started
* `comm_sock`: socket number for server communication
* `log_file`: filename of log file
* `exit_status`: exit status of program (used for exit)
* `maze_width`: width of maze
* `maze_height`: height of maze

* A `hashtable` to serve as a map from one position to the next, where
* The key is a string representing an `XYPos` that represents a location
* The item is for the `id` for the `Avatar` that discovered the point

* Another `hashtable` that stores avatars' ids as keys and a doubly-linked list (`discovered_t`, see below) as objects.
* The key is a string representing an avatar's id
* The item is a pointer to the head of a doubly-linked list of discovered points in order (`discovered_t`) for the avatar

* A `discovered_t` structure set up as a doubly-linked list, where
* Each avatar has its own doubly-linked list that keeps track of all the points it has discovered
* Each list links together nodes `coordinate_t` that contain `Avatar` and track the turn number
* Each doubly-linked list is represented by the head of the list and corresponds to the moves of the avatar with the `id` corresponding to the linked list's index in the larger list

* A `coordinate_t` structure that represents list nodes in the doubly-linked list and holds
* The position of the coordinate
* The id of the avatar that discovered the coordinate
* The turn number on which this point was arrived at
* The previous and next coordinates in the linked list
* Booleans (`found_follow` and `found_match`) to indicate if the current avatar is on another's path and to indicate if the current avatar is moving in tandem with another

* A `grid` structure that manages the graphics for the program, containing
* A matrix of what the current maze looks like, containing
* A number corresponding to the `Avatar` `id` in the position of each `Avatar`
* Dashes (`-` or `|`) for walls (horizontal or vertical, respectively)
* Pluses (`+`) to separate different squares in the grid
* The height and width of the maze
* The height and width of the grid (which is different, because this accounts for walls and spaces between points)

## Testing Plan

### Unit Testing
* `AMstartup`, `avatar_info`, `message` and `avatar`: We will test functions as they are written by running `AMstartup`. During the testing process, we may temporarily include functions in the main of `AMstartup` to check if they are working correctly.
* For any modules that can be run separately: We will test each function individually in separate test files and check error cases there before committing them to Github and using them elsewhere

### System Testing
We will test our full implementation of the maze challenge. We will focus on edge cases and consider all of the following:

#### Failure Cases:

1. Passing an invalid number of arguments to `AMstartup` (1, 2, 3, 4, 5, 6 arguments)
2. Passing a `difficulty` outside of the range of 1-9
3. Passing an invalid host name (should not connect)
4. Passing in invalid options (should not connect)

#### Success Cases:

5. Test the program on a maze of difficulty 1 with 2 and 3 avatars
6. Test the program on a maze of difficulty 2 with 2 and 3 avatars
7. Test the program on a maze of difficulty 3 with 2 and 3 avatars
8. Test the program on a maze of difficulty 1 with 4 and 5 avatars
9. Test the program on a maze of difficulty 2 with 4 and 5 avatars
10. Test the program on a maze of difficulty 3 with 4 and 5 avatars
11. Test the program on a maze of difficulty 4 with 2, 3 and 5 avatars
12. Test the program on a maze of difficulty 5 with 2, 3 and 5 avatars
13. Test the program on a maze of difficulty 6 with 2, 3 and 5 avatars