---
# System prepended metadata

title: CS50 Nuggets Implementation

---

# CS50 Nuggets Implementation
## Implementation Spec
### Breaking-Bash (Team 7), Winter, 2023

According to the [Requirements Spec](REQUIREMENTS.md), the Nuggets game requires two standalone programs: a client and a server. Following our [Design Spec](DESIGN.md), we included a *grid* module to handle functions that manipulate and update details of the game. Here we describe each program and module separately focusing on the following sections:
* Data structures 
* Definition of function prototypes
* Detailed pseudocode for each function

## Plan for division of labor

### Rachel
Rachel is responsible for implementing following functions:

- Implement the server functions `parseArgs`, `initPlayerLocation`, `initGold`, `server_update_all_clients`, `handleMessage`, `movePlayer`, `handleSPECTATE`, `handleKEY`, `player_move`
- Further debugging of the server

### Jonathan

Jonathan is responsible for implementing the following:

- Implement the handling messages function `handleMessage`, `handleQUIT` and `handleSPECTATE` ,`getPlayerIndex;
`, `handleInput`, `initializeGame`
- Finish testing of `server.c` and help debug server.


### Khanh
Khanh is responsible for implementing the following:

- Implement `grid_updateVisibility`, `grid_isVisible` `serverUpdatePlayers`, `gameOver`
- Write `grid.h` and `grid.c`
- Write and test grid module.
- Write `README.md` for `grid` module
- Create a new map and upload it in `maps/` directory.
- 

## Server

### Data structures
#### Global Constants:
```c
#define MaxNameLength 50  // max number of chars in playerName
#define MaxPlayers 26     // maximum number of players

static const int GoldTotal = 250;      // amount of gold in the game
static const int GoldMinNumPiles = 10; // minimum number of gold piles
static const int GoldMaxNumPiles = 30; // maximum number of gold piles
```


#### `game` struct:
```c 
typedef struct game{
    grid_t* map; //game-global map
    grid_t* originalMap;  //Base map
    
    //Information on gold in the game
    int goldPilesLeft;
    int goldCollected;
    int goldLeft;
    
    //Array of all players in the game
    player_t* allPlayers[MaxPlayers];
    int totalPlayers;
    addr_t spectator;
} game_t;
```

#### `player` struct:
```c
typedef struct player{
    grid_t* mapSeen; //Map visible to a specific player
    addr_t address;
    char playerRep; //A-Z
    char name[MaxNameLength];  //Player's name
    
    // player's gold purse
    int totalGoldCollected;
    int recentGoldCollected;
    
    // player's location
    int row;
    int col;
} playter_t;
```
#### Global variable
```c
static game_t* game;
```

### Definition of function prototypes

> For function, provide a brief description and then a code block with its function prototype.
> For example:

A function to parse the command-line arguments, initialize the game struct, initialize the message module, and (BEYOND SPEC) initialize analytics module.

#### `parseArgs`

Extracts arguments from the command line into function parameters such as the map and seed for random number generator:
```c
static void parseArgs(const int argc, char* argv[],
                         char** gridPathname, int* seed);
```
#### `initPlayerLocation`
Initializes a new player's location on the map randomly.

```c
void initPlayerLocation(player_t* player);
```
#### `initGold`
Drops gold piles in random location on the map.
```c
void initGold();
```
#### `initializeGame`
Initializes a game and launches it by loading the grid and allocating memory for information on the game struct.
```c
void initializeGame(char* gridPathname);
```

#### `initializePlayer`
Initializes a new player's details.
```c
void initializePlayer(player_t* player);
```

#### `getPlayerIndex`
Extracts a player's index in from the array of players in the global game struct.
```c
static int getPlayerIndex(const addr_t address);
```

#### `handleMessage`
Callback function that handles messages coming from a client and calls other functions based on the message content.
```c
static bool handleMessage (void* arg, const addr_t from,
                                   const char* message);
```
#### `handlePlay`
Handles 'PLAY ' message from the client and adds a player to the game.
```c
bool handlePlay(void* arg, const addr_t from,
                                    const char* message);
```

#### `handleKey`
Handles 'KEY ' message from client. Moves the player or quits the client's program if key is valid.
```c
bool handleKey(void* arg, const addr_t from,
                                    const char* keyGiven);
```
#### `handleSpectate`
Handles the 'SPECTATE ' message from client. Replaces an existing or adds a new spectator to the game.
```c
bool handleSpectate(const addr_t from);
```

#### `handleQuit`
Ends game session with the client that sent the message.
```c
bool handleQuit(const addr_t address);
```
#### `movePlayer`
Moves the player to the new location based on the key they pressed.
```c
bool movePlayer(player_t* player, int row, int col);

```
#### `serverUpdatePlayers`
Updates clients on the all changes made on the game grid and like when a player moves or quits.
```c
static void serverUpdatePlayers(void);
```

#### `gameOver`
Ends the game and prints the game leaderboard.
```c
static void gameOver();
```

### Detailed pseudo code

> For each function write pseudocode indented by a tab, which in Markdown will cause it to be rendered in literal form (like a code block).
> Much easier than writing as a bulleted list!
> For example:


#### `parseArgs`:
```
validate commandline
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()
```
#### `initPlayerLocation`
```
 while player position is not valid
    get a random position on grid
    if position is in an empty room spot
        position is valid
        add player to grid
        update player location
```

#### `initGold`
```
generate random num bw GoldMinNumPiles and GoldMaxNumPiles
initialize number of piles, collected gold, and gold left in game
for each gold pile
    determine random num gold nuggets in pile
    determine random location of gold pile
    while location is not valid
        get random row and col
        if it is an empty room spot
            location is valid
            add gold char (*) to grid
            add gold value to gold array
```


#### `initializeGame`
```
open the map txt file for reading
allocate memory for the game
initialize unique address for spectator
initialize game map and the game original map
load both game map and original map from textfile
call initGold to initialize gold on grid
close the map txt file
```

#### `intializePlayer`
```
initialize player's total collected and recent collected to zero
obtain player's index as num of players in game
Create player's alphabet representation
initialize player's location using initPlayerLocation(player)
create the player's mapSeen
```


#### `handleMessage`:
```
create copy of the message
if message is "PLAY "
    return value of handlePlay
if message is "KEY "
    extract the key
    return value of handlePlay
if message is "SPECTATE"
    retun value of handleSpectate
else message is malformed
    Log error message
    return false;
```
#### `handlePlay`:
```
check if player provided a name
if no name
    send back quit message
else if number of players in game if MaxPlayers
    send back quit message
else
    allocate memory for new player
    truncate and clean up player's name
    call initializePlayer
    add new player to the game
    update the game grid-map
    send OK message to player
    send GRID message to player
```

#### `handleKey`
```
get player's index from the array
if index is negative
    log a message with log_v
extract the player's details
if key is Q
    call handleQuit
extract player's location
Move player depending on key
    if 'h': left
    if 'H': farthest left
    if 'l': right
    if 'L': farthest right
    if 'j': down
    if 'J': farthest down
    if 'k': up
    if 'K': farthest up
    if 'y': up,left
    if 'Y': farthest up,left
    if 'u': up,right
    if 'U': farthest up,right 
    if 'b': down,left
    if 'B': farthest down,left
    if 'n': down,right
    if 'N': farthest down,right max
    default case: log a message
        send message to client
if all gold is collected return true
else return false
```

#### `handleSpectate`
```
if there is an old spectator
    send quit message to them
initialize the new spectator
send GRID message the spectator
call serverUpdatePlayers
return false
```

#### `movePlayer`
```
 check if position is moveable
     if position is gold
       add gold to player totalGoldCollected
       set recentGoldCollected to gold
       subtract 1 from goldPilesLeft on game
       add gold to goldCollcted on game
       subtract gold from goldLeft on game
       set gold on gold array to 0
       update player position to empty spot
       move player to spot
    if another player
        steal their gold
        set moving player's recent gold collected
        set other player's purse to 0
    if empty spot
       update player position to empty spot
       move player to spot
```
#### `getPlayerIndex`
```
loop through array of players to get a matching address
Compare the addresses, if they match
    set the index and break from loop
return the index
```

#### `serverUpdatePlayers`
```
for the spectator
    create the GOLD message and send
    send DISPLAY message

loop through all the players
    send GOLD message to them
    reset the number of recent collected gold
    update their mapSeen using visibility
    create and send DISPLAY message
```
#### `gameOver`
```
Create quit game over title
loop through all players
    create memory for the player's results
    get player's total gold collected and name
    create quit game over message
send message to spectator and players
free memory allocated for player's mapSeen and each player
delete the game map and original
free game
```

##  Grid module
### Data structures
```c 
typedef struct grid {
    int nrow;
    int ncol;
    char** array;
    int** goldArr;
} grid_t;
```

### Definition of function prototypes
```c
grid_t* grid_new(int nrows, int ncols);
void grid_load(FILE* fp, grid_t* grid);
void grid_update(grid_t* grid, int row, int col, char c);
void gold_update(grid_t* grid, int row, int col, int gold);
int grid_getGold(grid_t* grid, int row, int col);
char grid_getchar(grid_t* grid, int row, int col);
bool grid_isGold(grid_t* grid, int row, int col);
bool grid_isBoundary(grid_t* grid, int row, int col);
bool grid_isEmptyRoom(grid_t* grid, int row, int col);
bool grid_isPlayer(grid_t* grid, int row, int col);
bool grid_isRock(grid_t* grid, int row, int col);
bool grid_isMoveable(grid_t* grid, int row, int col);
bool grid_isBlocked(grid_t* grid, int row, int col);
void grid_print(grid_t* grid);
bool grid_isVisible(grid_t* basemap, int pr, int pc,int r, int c);
void grid_reset(grid_t* basemap, grid_t* seenmap);
void grid_updateVisibility(int pr, int pc, grid_t* basemap,
                                  grid_t* seenmap, grid_t* rawmap);
int grid_getRow(grid_t* grid);
int grid_getCol(grid_t* grid);
char* grid_toString(grid_t* grid);
void grid_delete(grid_t* grid);

```


The `grid_new` function is responsible for creating a new 2D array and for each row and each column, or each spot [row][col] for a character.

The `grid_load` function is responsible for loading the map.txt file into the grid. 

The `grid_update` function is responsible for updating changes to the map (e.g. dropping golds and players on the map)

The `gold_update` function updates the gold character on the raw map

The `grid_getGold` function returns the num of gold at location the provided 

The `grid_getchar` function returns the character at a specific location on the map.

The `grid_isGold` function checks for gold character on the map (`*`).

The `grid_isBoundary` function checks for boundary character on the map (`|`, `-`, `+`).

The `grid_isEmptyRoom` function checks for empty spot on the map (`.`).

The `grid_isPlayer` function checks for player character on the map (`A-Z`, '@').

The `grid_isRock` function checks for rock on the map (` `).

The `grid_isMovable` function checks whether a spot allows a player to move to.

The `grid_isBlocked` function checks if a player's view is blocked.

The `grid_print` function prints the grid map for testing.

The `grid_isVisible` function calculates player's view in the game

The `grid_reset` function changes game's map based on visibility when the player moves

The `grid_updateVisibility` function resets map and updates area seen by player

The `grid_getRow` function returns number of rows in grid

The `grid_getCol` function returns number of columns in grid

The `grid_toString` function returns a string that represents the grid for display

The `grid_delete` function frees memory allocated to grid when deleting grid


### Detailed pseudo code
#### `grid_new`:
```
if valid number of rows and columns:
    allocate memory for the grid
    if grid is not null:
        allocate memory for the rows
        if rows is not null:
            allocate memory for the columns for each rows, which means allocating memory for each character in the map
```

#### `grid_load`:
```
find the number of rows and columns from the map
for each line in map
    read the line
    get the character and store it in the grid
```

#### `grid_getchar`:
```
get character at the specified location on the grid
```
#### `grid_isGold`:
```
compare character at the specified location to `*`
``` 
#### `grid_isBoundary`:
```
compare character at the specified location to `|`, `+`, and `-`
```
#### `grid_isEmptyRoom`:
```
compare character at the specified location to `.`
```
#### `grid_isPlayer`:
```
compare character at the specified location 'A-Z' character

```
#### `grid_isRock`:
```
compare character at the specified location to ` `

```

#### `grid_isMovable`:
```
compare character at the specified location to all the movable spot.

```
#### `grid_isBlocked`:
```
check if character at the specified location is the boundary or passage spot (which restrict the visibility of players)
```

#### `grid_isVisbile`:
```
check whether at current location (pr, pc), player can see the specified location on the map (r,c)
    if on the same row or column:
        check visibility for all the spots in between pr r or pc c 
    if not:
        calculate the slope and check whether the slope passes through the gridpoint
        if yes, check if that point is visible
        if no,
            for each row that the slope pass through, check for the visibility of two adjacent column
            for each column that the slope pass through, check for the visibility of the two adjacent row
        
```

#### `grid_isVisbile`:
```
check whether at current location (pr, pc), player can see the specified location on the map (r,c)
    if on the same row or column:
        check visibility for all the spots in between pr r or pc c 
    if not:
        calculate the slope and check whether the slope passes through the gridpoint
        if yes, check if that point is visible
        if no,
            for each row that the slope pass through, check for the visibility of two adjacent column
            for each column that the slope pass through, check for the visibility of the two adjacent row
        
```

#### `grid_updateVisibility`:
```
for each grid point on the map
    check for the visibility 
    if visible
        update the map
        
```

#### `grid_toString`:
```
for each character in the grid
    store it in the result grid string
        
```

#### `grid_reset`:
```
if the gold character or a player is no longer within a player's view
    update the seenMap to the original map character

```

#### `grid_delete`:
```
free the memory allocated for the grid array
free the memory allocated for the gold array
free the grid

```

#### `grid_getCol`:
```
return num of cols in map

```

#### `grid_getRow`:
```
return num of rows in map

```


---


## Testing plan

### Unit testing
Our impementation has two main components, the *grid* module and the *server* which has the main program.
As described in our DESIGN.md, each function in the module will be thoroughly tested to ensure that the grid's functions work seamlessly. Since the *grid* is innately connected to the all parts of the server, we will create a `testgrid` program that will load test maps and call all the *grid* functions on it. The tests will focus on ensuring that the grid is properly updated whenever a change is made in the game including visibility.

### Integration testing
For the `server`, we will test the areas such as dropping gold in random spots on the grid, assigning players random locations, displaying the game, as well as testing that all changes done on the grid are reflected in the game. This will be achieved firsrt by using the `miniclient` program already provided in the program in addition to the `bot` program, as mentioned, again, in DESIGN.md then using the full client program provided. We'll write a bash script to handle all the test cases and run the programs using a Makefile. Finally, we will run VALGRIND on the `server` while using the `testgrid` to check memory leaks and other errors to ensure that all allocated memory is freed.

---
