---
# System prepended metadata

title: IMPLEMENTATION.md
tags: [nuggets]

---

# CS50 Nuggets
## Implementation Spec
### Team XVI, Spring 2024


According to the [Requirements Spec](REQUIREMENTS.md), the Nuggets game requires two standalone programs: a client and a server.
Our design also includes player, map, gridpoint, and visualization modules.
We describe each program and module separately.
We do not describe the `support` library nor the modules that enable features that go beyond the spec.
We avoid repeating information that is provided in the requirements spec.

## Separation into Modules
    
### Programs
- [Client](#Client-Module)
- [Server](#Server-Module)

### Game-Logic Library
- [Player](#Player-Module)
- [Gridpoint](#Gridpoint-Module)
- [Map](#Map-Module)
- [Visibility](#Visibility-Module)


## Plan for division of labor

- Client Program - Zach
- Server Program - Michael
- Visibility - Will
- Map - Dylan

## Client Module

### Data structures

The client also heavily utilizes a module, `message`. More detail on the `message_` module can be found in its associated header file.


The message module initializes communication to a server.

On the client's end:
    
    connect to server
    message_loop
        recieve keystrokes and send messages
            PLAY, SPECTATE, KEY
            
The `message_loop` takes two functions to handle `input` and `messages`. Both functions will take a `void* arg` parameter. We will need to pass several client variables into these functions, so it is cleanest to store them all in a struct `user_t`:

```c
typedef struct user{
  addr_t server;
  char* playername;
  char letter;
  int goldStatus[3];
  char explanation[100];
  const char* quitExplanation;
}user_t;
```

* The `server` of type `addr_t` is a module off of `message`, and holds various _sin_ and _IP_ info. 
* The `playername` should be `NULL` if the user is a _spectator_ otherwise it should be the provided playername. 
* `letter` Is assigned to the user from an `OK L` message, where `L` is the user's spot in an alphabetical array.
* `goldStatus` is a 3-int array which stores `n`, `p`, & `r`: _gold recieved on newest move_, _total gold in purse_, & _remaining gold in game_ respectively
* `explanation` is allocated on the stack, and is the right-most information on the status line
* `quitExplanation` is recieved after inputting `Q` as a client. It prints after closing the game

### Definition of function prototypes

Validate and assign command-line arguments.
```c
static void parseArgs(const int argc, char* argv[], char** serverHost, char** serverPort, user_t* user);
```

Initialize display and begin communication with server.
```c
static void initializeClient(user_t* user);
```

Validate and process user keystrokes.
```c
static bool handleInput(void* arg);
```
Validate and process messages received from server.
```c
static bool handleMessage(void* arg, const addr_t from, const char* message);
```
Print out the visible map recieved from the server. 
```c
static void displayGrid(const char* grid);
```
Print out game updates recieved from the server. 
```c
static void displayStatusLine(user_t* user);
```

Helper functions to break up message handling.
```c
static void recieveGRID(const char* info);
static void recieveOK(const char* info, user_t* user);
static void recieveGOLD(const char* info, user_t* user);
static void recieveQUIT(const char* info, user_t* user); 
static void recieveERROR(const char* info, user_t* user); 
```

### Detailed pseudo code

#### `main`:

The main function should parse user arguments with `parseArgs`, set up client-side messaging with `initializeClient`, call a `message_loop`, and exit depending on the success of the loop:

    parseArgs and validate user parameters
    initializeClient and send initial messages to server
    bool success mapped to message_loop(server, handleInput, handleMessage)
    end ncurses
    print any closing messages
    return success casted as an interger

#### `parseArgs`:

To validate all the user parameters passed into the command line, a function`parseArgs` is helpful to handle all non-zero exit statements.
`parseArgs` should check that there is a correct count of parameters, initialize pointers from `argv[]`, validate those parameters, and exit non-zero at any point of failure:

	if (parameters == 3 || 4)
        initialize message module
            on failure exit non-zero
	    print assigned port number
        if (3 parameters)
            declare client as a spectator
        if (4 parameters)
            declare client as a player
            set user->playername
    else
        exit non-zero

#### `initializeClient`:

The `initializeClient` function should set up `ncurse` within the terminal for individual character parsing and a refreshing display.
On success, the function sends an initial `PLAY` or `SPECTATE` message to the server:

    validate message addr_t
    initialize curses
    if (user->playername == NULL)
        send "SPECTATE" to server
    else
        copy "PLAY " to message
        copy playername to message
        send message to server

#### `handleInput`:

The `handleInput` function is called from `message_loop` to continually get keystrokes and send them to the server:

    create addr_t from arg*
    if (addr == NULL)
        return true and break _loop
    if (addr != valid) 
        return true and break _loop
        
    current char keystroke
    bool valid keystroke
    if getch() != ERR
        char[] of possible lowercase keystrokes 
        iterate through []
            if tolower(keystroke) == char[i] AND playername != NULL
                valid is true
            if keystroke == 'Q'
                valid is true
    else
        return true
        
    if valid
        send "KEY " + keystroke
             
    return false
            

#### `handleMessage`:

The `handleMessage` will recieve messages from the server. 
The client should only be recieving `OK`, `GRID`, `GOLD`, `DISPLAY`, `QUIT`, and `ERROR` messages. For clarity sake, the `recieve` functions have been integrated into the switch. The logic should be separated:

So validate as such and display the grid:

    set user->addr_t to new from addr_t
    
    tokenize first word of message into char* phrase
    tokenize rest of message into char* info
    
    switch phrase
    case "OK"
        update user->letter to info
    case "GRID"
        scan rows and columns into ints
        getmaxyx() for resolution of screen
        while screen resolution < grid resolution
            display warning in status line
    case "GOLD"
        scan n, p, r into goldStatus[3]
        update explanation to display gold recieved
    case "DISPLAY"
        mvprintw infor on line below status (1,0)
    case "QUIT"
        copy quit explanation into user
    case "ERROR"
        update explanation to display error
        
#### `displayStatusLine`:

`displayStatusLine` is called through the message handler, and deals strictly with printing the `statusLine`(s) recieved from the server:

    if user->playername != NULL
        mvprintw player letter and their gold,
            gold remaining,
            and most recent status update
    else
        mvprintw gold remaining,
            and most recent status update
    refresh() ncurses

---

## Server Module

```c
// Global constants:
static int MaxNameLength = 50;   // max number of chars in playerName
static int MaxPlayers = 26;      // maximum number of players
```

### Data structures

### Definition of function prototypes

A function to parse and validate the command-line arguments.
```c
void parseArgs(int argc, char* argv[], char** mapText, int* seed);
```
A function to stop the game and free all memory.
```c
void gameOver(addr_t* playerAddresses, char* playerNames);
```
Called by the message loop each time a message is received; correctly responds to each message
```c
static bool handleMessage(void* arg, const addr_t from, const char* message);
```
send a GOLD message to all the players, specifically telling `player` how much new gold they aquired.
```c 
static void sendGoldUpdates(addr_t* addresses, char player, int amt);
```
send a DISPLAY message to all the players with the current state of the map for their view.
```c 
static void sendDisplayUpdates(addr_t* addresses);
```
get the player character corresponding to a given address
```c
static char getCharFromAddress(addr_t* playerAddresses, addr_t* address);
```

### Detailed pseudo code

#### `main`:

    call parseArgs
    call map_init with the map text filename
    playerAddresses <-- an array of MaxPlayers+1 blank addr_t*'s
    playerNames <-- an empty array of strings
    numPlayers <-- 0
    set up and start messaging loop
        - log to stderr
        - give handleMessage a copy of the playerAddresses and numPlayers
    call gameOver
    
    // clean up
    free all memory associated with playerAddresses and playerNames arrays
    close down map module
    close down message module
    

#### `parseArgs`:

	validate num of args 
	verify map file can be opened for reading
	if seed provided
	    verify it is a valid seed number
	    seed the random-number generator with that seed
	else
	    seed the random-number generator with getpid()



#### `gameOver`:
    intialize game over message
    for char c in A..Z:
        get final info about player c
        add info to game over message
    for address in playerAddresses:
        send game over message to address
    
#### `handleMessage`:
these cases will likely be separated into their own functions.

    unpack arg into playerAdresses array and numPlayers
    char player <-- getCharFromAddress
    
    switch on first word of message:
    case PLAY:
        if numPlayers == maxPlayers:
            send quit message
        else if no name:
            send quit message for no name
        else:
            tell map to add a new character
            if unsuccessful, tell client to quit
            else:
                send the OK message to client
                normalize name
                add player address and name to approriate arrays
                send GRID message
                send individual GOLD message
                sendDisplayUpdates
         return false
                
    case SPECTATE:
        if there is a spectator:
            tell spectator to quit
        set client address to start of playerAddresses
        send GRID message
        send individual GOLD message
        send individual DISPLAY message
        return false
    
    case KEY: // right now this just skips an invalid key
        if player is 0:
            tell client to quit and that it needs to 
            start the game as a player or spectator
        if key is 'q' or 'Q':
            send QUIT message to client
            remove player from map
            remove player from server (free and null-out associated data)
        else if key is a movement key:
            if player is '@':
                tell client ERROR: spectators cannot move
            tell map to move character
            if successful:
                sendDisplayUpdates
            if gold was collected:
                sendGoldUpdates(player, amt)
                if no more gold in the game:
                    return true            
        return false
    default:
        send a message-type error
        return false
            
    
#### `sendGoldUpdates`:

    t <-- get total remaining gold
    for char c in @,A..Z:
        p <-- get c's purse
        if c is the player:
            n <-- amt
        else:
            n <-- 0
        send "GOLD n p t" to c's address
        

#### `sendDisplayUpdates`:

    for char c in @,A..Z:
        mapString <-- get c's map string
        send "DISPLAY\nmapString" to c's address

#### `getCharFromAddress`:

    for char c in @,A..Z:
        if playerAdresses[c] matches given address:
            return c
    return 0

---
## Gridpoint Module


### Data structures
We implement a new data structure `gridpoint` that stores information about a location in the map. The gridpoint will store the default character of the map, the gold amount, a set of other gridpoints visible from each point, and the player at the gridpoint.

The gridpoint should be defined as follows:

```c
typedef struct gridpoint{
    int x;
    int y;
    char mapChar;
    char player; 
    int gold;
    bool visible[MaxPlayers+1];
    hashtable_t* visiblePoints;
} gridpoint_t*;
```
Where:
* *x* and *y* represent the (row,col) coordinates of the gridpoint
* *mapChar* represents the background character \{ + , - , | , # , • , etc. }
* *player* represents the letter occupying a space
* *gold* represents the quantity of gold occupying the space
* *visible* is an array of players to whom the gridpoint is visible. The 0-index represents the spectator, who can see everything; as such, every entry is always true.
    * i.e., a gridpoint visible to players 'A' and the spectator would contain: 
    ```c
    [true, true, false, false ... false];
    ```

The module also makes use of our previously developed `hashtable` data structure to store calculated  visibility from a certain gridpoint. This tactic allows us to perform the expensive player visibility computations only once per gridpoint and only when necessary. 

### Definition of function prototypes
Set the visibility of a player at a certain gridpoint
```c
gridpoint_t* gridpoint_new(char mapChar);
```
Get the default map character at a certain gridpoint
```c
char gridpoint_getChar(gridpoint_t* gp);
```
Get the hashtable of gridpoints that can be seen from a certain gridpoint
```c
hashtable_t* gridpoint_getVisibility(gridpoint_t* gp);
```
Get the gold at a certain gridpoint
```c
int gridpoint_getGold(gridpoint_t* gp);
```
Get the player at a certain gridpoint, if any
```c
char gridpoint_getPlayer(gridpoint_t* gp);
```
Set the hashtable of gridpoints that can be seen from a certain gridpoint
```c
bool gridpoint_setVisibility(gridpoint_t* gp, hashtable_t* visible);
```
Set the gold at a certain gridpoint
```c
bool* gridpoint_setGold(gridpoint_t* gp, int gold);
```
Set the player at a certain gridpoint
```c
bool* gridpoint_setPlayer(gridpoint_t* gp, char player);
```
Print a gridpoint for debugging
```c
bool* gridpoint_print(gridpoint_t* gp);
```

### Detailed pseudo code
The functions within the gridpoint module are trivial (simply getting and setting the variables within a gridpoint), so we omit pseudocode for this module.

---
## Player Module

This module provides a player data structure to represent a single player of the game.

### Data Structures

```c 
typedef struct player {
    bool active; 
    int gold;
    int xPos;
    int yPos;
    hashtable_t* seen;
} player_t*;
```

### Definition of Function Prototypes


Add a new player to the game:
```c 
player_t* player_new();
```
Remove a player from the game:
```c 
void player_delete(player_t* player);
```
Getters and Setters:
```c
void player_setGold(player_t* player, int gold);
int player_getGold(player_t* player);
void player_setPos(player_t* player, int x, int y);
int player_getX(player_t* player);
int player_getY(player_t* player);
```

---
## Map Module

```c
static int GoldTotal = 250;      // amount of gold in the game
static int GoldMinNumPiles = 10; // minimum number of gold piles
static int GoldMaxNumPiles = 30; // maximum number of gold piles
```
### Data structures
We implement a new datastructure called `map`, which holds information about the game status. This includes an array of gridpoints, redefined as a `grid`, the total gold left in the game, the players in the game, and the number of players who have joined the game.

*Note: num_players is non-decreasing, a player leaving the game will not affect this value*


```c
typedef gridpoint_t*** grid_t; 

struct map {
    grid_t grid;
    int totalGold;
    int remainingGold;
    player_t** players;
    int num_players;
    int width;
    int height;
} map_t*
```
This map is initialized as a global variable, and all functions reference this global map.
### Definition of function prototypes

Initialize the map global variable from a provided text file
```c
bool map_init(fileName);
```
Distribute gold across the map in between minPiles and maxPiles piles
```c
static bool map_distributeGold();
```
Gets the remaining gold amount
```c 
int map_getRemainingGold():
```
Get the amount of money in a player's purse
```c 
int map_getPurse(char player);
```
Gets the player with certain char id
```c
static player_t* map_getPlayer(char player);
```
Randomly place character in map, create player struct
```c
char map_addPlayer();
```
Removes a player from the game
```c 
void map_removePlayer(char player);
```
Returns the gridpoint at a certain location
```c
gridpoint_t* map_getLocation(int x int y);
```
Cleans up the map
```c
void map_delete();
```
Moves player in certain direction (key input)
```c
int map_movePlayer(char player, char direction)
```

Moves player exactly once, if possible.
```c 
static int map_movePlayerOnce(char player, int dy, int dx);
```

```c 
int map_getWidth();
int map_getHeight();
```
### Detailed pseudo code
Pseudocode for  `map_init`:
```c
setWidth = false;

file = fopen(fileName);
while((c = getc(file)) != EOF):
    if(c == '\n'):
        setWidth = true;
        map.height++;
    elif(setWidth == false):
        map.width++;

rewind(file);
map.grid = malloc(sizeof(gridpoint_t**)*height);
for(row in map.grid):
    row = malloc(sizeof(gridpoint_t*)*width);

int x = 0;
int y = 0;
gridpoint_t* gp;
while((c = getc(file)) != EOF):
    gp = gridpoint_new(c);
    map.grid[y][x] = gp;
```    
Pseudocode for `map_distributeGold()`
```c
int numPiles = rand()%(maxPiles - minPiles);
numPiles+=minPiles;

    
```
Pseudocode for `map_getPlayer()`
```c
return map.players[player-'A']
```
Pseudocode for `map_addPlayer()`
```c 
if we don't have room for a new character:
    return 0
else:
    char player = numPlayers + '@';
    increment number of players
    
placed = false;
while(!placed):
    x = rand()%width
    y = rand()%height
    if(gridpoint_getChar(map.grid[y][x]) == '.' && gridpoint_getPlayer(map.grid[y][x]) == '\0' && gridpoint_getGold((map.grid[y][x])) == 0):
        new_player = player_new(player);
        if (new_player == NULL) return 0;
        gridpoint_setPlayer(map.grid[y][x], player);
        player_setPos(new_player, x, y);
        add player to list of players;
        placed = true;

return player
        
```
Pseudocode for `map_removePlayer()`
``` 
if player doesn't exist, return
free player struct
set pointer in players array to NULL
remove character from the grid
```
Pseudocode for `map_getLocation()`
```c
return map.grid[y][x]
```
Pseudocode for `map_movePlayer()`
```c
ignore invalid direction
if(isUpper(dir)):
    move player until hitting a wall or swapping with a player
    keep track of total gold collected
else:
    move player once in direction if possible
    record gold collected
    
if movement was unsuccessful, return -1
else return amt of gold collected

```
Pseudocode for `map_delete()` is omitted for the implementation spec, as it's relatively trivial

---

## Visibility Module

### Control Flow

Visibility functions are called only by the map module. visibility_set is called whenever a player moves or is added to the game. visibility_clear is called whenever a player moves, *before they move*.

### Data structures

Visibility relies on the `grid_t` 2D array of gridpoints contained within the global `map` structure. This module also needs access to the player structure.

### Definition of function prototypes


Calculates which gridpoints should be visible to a particular player.
```c
void visibility_set(map_t map, player_t* player);
```
resets the gridpoints that are visible while retaining those that have been seen
```c
void visibility_clear(map_t map, player_t* player);
```

### Detailed pseudocode

visibility_set:
    
    if gridpoint at current location has a non-NULL hashtable
        this location has been calculated before
        for each gridpoint item in the hashtable:
            set visibility for this gridpoint and provided player to true
    
    otherwise, calculate all points that are visible     
        px = player_getX
        py = player_getY
        mark map[px][py] as visible and seen for current player
        add map[px, py] to hashtable of visible gridpoints for this gridpoint
        iterate through each gridpt gx, gy in the map
            get the horizontal distance from player to gridpt
            get the vertical distance from player to gridpt
            dy/dx = vertical / horizontal
            dx/dy = horizontal / vertical
            float current x = px
            float current y = py
            bool checkRow = false
            bool checkCol = false
            Iterate through the rows, starting at py+1:
            while cy is less than gridpoint y
                current x += dx/dy
                current y += 1
                if the current row is a gridpt (cx % 1 = 0)
                    if the gridpt == {+,-,|,#} it blocks visibility.
                        set visibility to false, just in case
                        break out of while loop
                otherwise, round down column
                if both map[x][y] and map[x+1][y] == {+,-,|,#}:
                    set visibility to false, just in case
                    break out of while loop
                if no wall detected, checkRow = true
            if checkRow is false, 
                break and move to next gridpt
            otherwise, reset cx and cy
            Iterate through the rows, starting at py+1:
            while cx < gridpoint x
            current x += 1
            current y += dy/dx
            if the current col is a gridpt (cy % 1 = 0)
                if the gridpt == {+,-,|,#} it blocks visibility.
                        set visibility to false, just in case
                        break out of while loop
                otherwise, round down row
                if both map[x][y] and map[x][y+1] == {+,-,|,#}:
                    set visibility to false, just in case
                    break out of while loop
                if no wall detected,
                    checkCol = true;
            if checkCol is false:
                break and move to next column
            otherwise:
                mark map[cx][cy] as visible to player
                add map[cx][cy] to visiblePoints for key "px,py"

visibility_clear:

    for each row in the map:
        for each col in the map:
            gridpoint = map[x][y]
            if a gridpoint was visible to current player
                seen for current player is true
            visibility for current player is false

### Error Handling and Recovery

Any error producing the visibility array would likely be fatal or result in unexpected behavior when displaying the map to a client. As such, the visibility functions do attempt to catch and respond to errors; this is left to the higher-level modules. Visibility functions assume a valid `map_t` map and an existing `player`, both of which should be validated prior to their inclusion as a parameter in a function call. 

The use of a `hashtable` to document other gridpoints visible from a given gridpoint is a memory-intensive process. While visibility_set does not allocate memory for new sets, it does add items to existing sets. So long as `set_delete()` is eventually called on each gridpoint, no memory issues should occur. 

---

## Testing plan

### unit testing

#### map and visibility

We plan to manually create a few small environment maps in which to test that the visibility functions run as expected. This will be implemented in a visibilityTest module, complementary to the visibility module. 
* First, we will build a 4x4 room encased by walls to ensure that all gridpoints are visible to one or two players. For both scenarios, we will artificially 'move' the player by altering the contents of the player struct. To validate the resulting 
    * As display of characters and gold is handled by a simple conditional within the server's display, testing of this component will simply consist of checking a gridpoint's visibility and the results of calling gridpoint_getGold and gridpoint_getPlayer.

* Second, we will build a more complex corridor similar to the one in the demonstration video to test that hidden gridpoints remain hidden. Again, we will artificially 'move' players to check that the clearVisibility function accurately preserves seen gridpoints.

  
### integration testing

#### server

We plan to test the functional server with the provided dummy client scripts. We'll also make use of the simple stdin-based client to try out bad input.
- trying to joing while already playing
- spectating while already playing
- sending movement strokes as a spectator

#### client

We plan to test the functional client with the provided `miniserver.c`. When both the server and client are functional, we plan to test the two together in a variety of _valid_ cases, including:

* One player
* One spectator
* One player and one spectator
* Several players
* Several players and one spectator

As well, we will test the client for _invalid edge_ and _base_ cases:

* More than 1 spectator(s)
* More than 26 players
* Unopened server port

These tests will probe only the ability of the server and client to process joining and quitting. Full-function testing is described below.

### system testing

We plan to apply a provided bot testing script, complete with 26 players and a spectator. Each client sends random messages to the server. These messages are valid but may not code for valid movement.

We'll also try having too many clients and clients that leave and rejoin a lot

---

## Limitations

> To be updated as modules are implemented.

