NPC ~ Independent Feature: NPC Movement Design Document - uchicago-cs/chiventure GitHub Wiki
Overview
This document will cover a rough design of any features that the rpg-npc team will be working on independently. These features have been established following inter-team discussions upon which we have been able to delineate which features/tasks should be worked upon by each team and where there are dependencies. The features described in this document will later be integrated into another team's feature, for example the npc movement feature is ultimately part of the rpg open-world module.
- NPCs in the Open World
- Spawning NPCs in Rooms
- NPC Movement Through the World
- npc-move Module
- rooms-npc Module
Features
NPCs in the open world
Following a meeting with the rpg open-world team it is clear that the ultimate goal is to create an auto-generating room function that loads with items and npc that fit the specification of that room. It appears that the npc openworld team is using a hash table to store the paths accessible to that room, as well as tag that classifies what kind of room it is. Based on this we can create a tentative design as to how we wish to generate npcs in the correct rooms, as well as implement some sort of movement of npcs between adjacent rooms (given that the npc has the status/class to move between the two adjacent rooms).
For the moment, the npc team has provided an npc struct as such:
/* A non-playable character in game */
typedef struct npc {
/* hh is used for hashtable, as provided in uthash.h */
UT_hash_handle hh;
char *npc_id;
int health;
convo_t *dialogue; // placeholder for incoming dialogue module
item_hash_t *inventory;
} npc_t;
typedef struct npc npc_hash_t;
A comprehensive description of the npc struct can be found in the following wiki: https://github.com/uchicago-cs/chiventure/wiki/NPC-Design-and-Planning
Additionally, the open-world team have roughly defined the following struct for a room:
typedef enum room_tag { LIBRARY, DUNGEON, OPEN_FIELD } room_tag_t;
typedef struct room {
/* hh is used for hashtable, as provided in uthash.h */
UT_hash_handle hh;
room_tag_t room_tag;
char *room_id;
char *short_desc;
char *long_desc;
item_list_t *items;
path_hash_t *paths;
} room_t;
The entirety of these struct definitions can be found here: https://github.com/uchicago-cs/chiventure/blob/openworld/sample-generation/include/openworld/sample_rooms.h
Spawning NPCs in rooms
The following struct would hold the different npcs in a hash table, this would allow for easy access to each npc in the room. In addition to the following struct, we have also included the following two basic functions.
/*
* Struct for adding and handling npcs in rooms
*
* Components:
* room_id: The name of the room
* npc_list: Hash table storing the npcs in the room
* num_of_npcs: Number of npcs in the room
*/
typedef struct npcs_in_room {
UT_hash_handle hh;
char* room_id;
npc_hash_t *npc_list;
int num_of_npcs;
} npcs_in_room_t;
/* To make the struct hashable */
typedef struct npcs_in_room npcs_in_room_hash_t;
/* Adds an npc to the given npcs_in_room
*
* Parameters:
* npcs_in_room_t: pointer to the npcs_in_room struct
* npc_t: pointer to an npc
*
* Returns:
* SUCCESS if successful, FAILURE if an error occured.
*/
int add_npc_to_room(npcs_in_room_t *npcs_in_room, npc_t *npc);
/*
* Returns the number of npcs in a room
*
* Parameters:
* npcs_in_room: the struct holding the npcs in the room
*
* Returns:
* int, the number of npcs in the room
*/
int get_num_of_npcs(npcs_in_room_t *npcs_in_room);
The function above adds an npc into the struct created above that essentially contains all the npcs that exist in a room. This needs to be then further integrated into the room struct where the room struct will hold this specific npcs_in_room struct for each room. This would therefore contain a list of npcs that exist in the room.
NPC movement through the world
A potential other feature we can implement would be to integrate an npc movement element in which it can move through adjacent rooms similar to how the player can. The primary issue with this is that often times adjacent rooms may not have the same room_tag, thus the npc will be restricted to a single room. But in the case that adjacent rooms may be of a room_tag that that particular npc_class has been associated to both room_tag, then this can facilitate movement between rooms.
NPC movement has been split into two modules: 'npc-move' and 'rooms_npc'
npc_move module
The first module, npc_move, 'npc_move' contains the struct 'npc_mov_t' and various functions that encapsulate basic NPC movement possibilities. This struct can be seen in the npc module included as part of the npc_t struct:
/*pointer to an exisitng npc_move struct */
npc_mov_t *movement;
For each npc we are therefore including the 'npc_mov_t' struct that addresses the movement of the npcs between rooms. This struct holds a union determining what kind of movement the npc is participating in, and this can fall under two categories:
- A definite path (labelled mov_def_t): this is the first case when an npc is required to move from point A to point B for a specific reason (that being for a quest, etc.). In this case the npc is merely moving from point A to point B and the movement ends at point B.
- If an npc is static and will only stay in one room, it will still fall into the definite path category. In this case, the field room_list_t will only have one element.
- An indefinite path (labelled mov_indef_t): this is the second case when an npc is simply moving through the map but without a definite end point. This is simulate the open-world so that npcs will be continuously moving through the world. In this case the npc will also hold a linked list of rooms to move through, but in addition it must have contain a hash table that holds the time that it should spend in each room in seconds.
- Note that the functionality for moving NPCs with indefinite paths has not yet been implemented, however, the framework to do so exists. This will be touched on again below.
Using these two types of movement we have created the following basic structs in the npc_move module:
/*
* Struct to encapsulate the time an NPC should stay in that particular room
* and the room details
*
* Components:
* room_id: The name of the room
* time: Time in miliseconds the NPC will stay in this particular room
*/
typedef struct npc_room_time {
UT_hash_handle hh;
char* room_id;
int time;
} npc_room_time_t;
/* To make the struct hashable */
typedef struct npc_room_time npc_room_time_hash_t;
/*
* Struct for the definite path movement for npcs
* Definite path: when the NPC has a certain start and end with a
* role to play in the destination room
*
* Component:
* npc_path: The list of rooms that the NPC will go through
*/
typedef struct npc_mov_definite {
room_list_t *npc_path;
} npc_mov_definite_t;
/*
* Struct for the indefinite path movement for NPCs
* Indefinite path: this is the second case when an NPC is simply moving
* through the map but without a definite end point.
*
* Components:
* npc_path: The list of rooms that the NPC will go through
* room_time: Time in miliseconds for the NPC corresponding to each room
*/
typedef struct npc_mov_indefinite {
room_list_t *npc_path;
npc_room_time_hash_t *room_time;
} npc_mov_indefinite_t;
/* Union that holds the definite and indefinite movement structs */
typedef union npc_mov_type {
npc_mov_definite_t *npc_mov_definite;
npc_mov_indefinite_t *npc_mov_indefinite;
} npc_mov_type_t;
/*
* Enum to define NPC movement type - to simplify implementation
* Definite movement is 0, Indefinite movement is 1
*/
enum mov_type { NPC_MOV_DEFINITE, NPC_MOV_INDEFINITE };
typedef enum mov_type npc_mov_enum_t;
/*
* Struct that deals with NPC movement for both types of npc movements
*
* Components:
* npc_id: The NPC being considered
* npc_mov_type: Union with the structs for both mov types
* mov_type: Enum type of movement
* track: tracker variable that returns current room id
*/
typedef struct npc_mov {
npc_mov_type_t npc_mov_type;
npc_mov_enum_t mov_type;
char *track;
} npc_mov_t;
With these structs there are the init, new, and free functions:
/*
* Initializes the struct that handles the movement of an npc
*
* Parameters:
* npc_mov: The id of the npc that is being addressed; must point to already
* allocated memory
* npc_id: The npc that is being referred to; must ppint to allocated
* memory
* mov_type: The tpye of movement that the npc will have
* room: The room that the npc will start in
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int npc_mov_init(npc_mov_t *npc_mov, npc_mov_enum_t mov_type, room_t *room);
/*
* Allocates a new npc_mov struct in the heap
*
* Parameters:
* npc_id: The ID of the NPC that is being referred to; must ppint to
* allocated memory
* mov_type: The tpye of movement that the npc will have
* room: The room that the npc will begin in
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
npc_mov_t *npc_mov_new(npc_mov_enum_t mov_type, room_t *room);
/*
* Frees resources associated with an npc_mov struct
*
* Parameters:
* npc_mov: The npc_mov struct to be freed
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int npc_mov_free(npc_mov_t *npc_mov);
As well as additional functionalities to complete the npc_move module:
/*
* Registers a time spent in a specific room in the hash table, if the room is
* not yet in the hash table it will create a new entry
*
* Parameters:
* npc_mov: The npc_mov struct
* room: The room to be registered
* time: The time to be spent in the room by that NPC in miliseconds
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int register_npc_room_time(npc_mov_t *npc_mov, room_t *room, int time);
/*
* Adds a room to the path of definite NPC movement - changes destination of the NPC
*
* Parameters:
* npc_mov: The NPC movement struct
* room_to_add: The room that has to be added to the path
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int extend_path_definite(npc_mov_t *npc_mov, room_t *room_to_add);
/*
* Adds a room to the path of indefinite NPC movement (not the corresponding
* time); changes destination of the NPC
*
* Parameters:
* npc_mov: The NPC movement struct
* room_to_add: The room that has to be added to the path
* time: The time the NPC has to stay in that room in miliseconds
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int extend_path_indefinite(npc_mov_t *npc_mov, room_t *room_to_add, int time);
/*
* Returns the room that the npc is currently in
*
* Parameters:
* npc_mov: The NPC movement struct
*
* Returns:
* The room the NPC is in as a char*, NULL if error.
*/
char* track_room(npc_mov_t *npc_mov);
/*
* Reverses the path, so that the npc goes back to where it started
* (this is only for definite movement paths, because indef will naturally
* move back and forth)
*
* Parameters:
* npc_mov: The NPC movement struct
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int reverse_path(npc_mov_t *npc_mov);
/*
* Moves the npc to the next room for npcs with definite movement
*
* Paramters:
* npc_mov: The NPC movement struct
*
* Returns:
* 0 if move in unsuccessful
* 1 npc has reached the end of the path, reverse_path is called, but
* the move is not implemented
* 2 successful move to the next room
*/
int move_npc_definite(npc_mov_t *npc_mov);
Spring 2020 team: We are not able to finish implementing the functions below by the end of the quarter, but the following functions are for future implementation. Spring 2021 team: These functions with tests will be completed by the end of our Sprint 3 on the npc/mov-funcs branch and are expected to be merged in early Sprint 4.
/*
* Moves the npc to the next room for npcs with indefinite movement
*
* Paramters:
* npc_mov: The NPC movement struct
*
* Returns:
* SUCCESS, OR FAILURE
*/
int move_npc_indefinite(npc_mov_t *npc_mov);
/*
* Generates a random movement struct for an NPC based on the current rooms in
* the map and a given npc_mov_t struct.
*
* Parameters:
* - npc_mov: npc_mov_t struct with a known npc_mov_type
* - game: current game, this is necessary for determining the current rooms in the map
*
* Returns:
* - returns SUCCESS on success, returns FAILURE on failure
* - Updates npc_mov to have a new, randomly generated movement path.
* Maintains the same type of movement (indefinite / definite)
*
*/
int auto_gen_movement(npc_mov_t *npc_mov, game_t *game);
Spring 2021: These two functions have been implemented in the npc_move module. auto_gen_movement() uses a helper function called get_num_rooms() which determines the number of rooms in a current game. Additionally, a function has been implemented to get the number of rooms in an NPC's path. If these implementations do not exist on the dev branch, they have not been merged yet and exist in the npc/mov-funcs branch.
/*
* helper function for auto_gen_movement to find number of rooms in game
*
* Parameters:
* - game: current game
*
* Returns
* - # of rooms in game
*
*/
int get_num_rooms(game_t *game);
/*
* Gets the number of rooms in an NPC's path
*
* Parameters:
* - npc_mov: The NPC movement struct
*
* Returns:
* - number of rooms in an NPC's path, represented as an int
*/
int get_npc_num_rooms(npc_mov_t *npc_mov);
Tests for these functions have also been implemented in the npc/mov-funcs branch.
/* Tests get_npc_num_rooms function for definite move */
Test(npc_mov, get_npc_num_rooms_def)
/* Tests get_npc_num_rooms function for indefinite move */
Test(npc_mov, get_npc_num_rooms_indef)
/* Tests move_npc_indef function */
Test(npc_mov, move_npc_indefinite)
/* Tests auto_gen_movement for definite movement function */
Test(npc_mov, auto_gen_movement_definite)
/* Tests auto_gen_movement for indefinite movement function */
Test(npc_mov, auto_gen_movement_indefinite)
rooms-npc module
The second module facilitating NPC movement is the rooms-npc module, which contains the struct 'npcs_in_room_t.' This module keeps track of which NPCs are in one specific room using a hash table and is otherwise a very straightforward module.
Currently, the only struct that exists in the rooms-npc module is the npcs_in_room_t struct:
/*
* Struct for adding and handling npcs in rooms
*
* Components:
* room_id: The name of the room
* npc_list: Hash table storing the npcs in the room
* num_of_npcs: Number of npcs in the room
*/
typedef struct npcs_in_room {
UT_hash_handle hh;
char* room_id;
npc_hash_t *npc_list;
int num_of_npcs;
} npcs_in_room_t;
/* To make the struct hashable */
typedef struct npcs_in_room npcs_in_room_hash_t;
With this struct there are init, new, and free functions:
/*
* Initializes the struct that holds the npcs inside a certain room
*
* Parameters:
* npcs_in_room: the npcs in a certain room; must point to already
* allocated memory
* room: the room that the npc will start in
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int npcs_in_room_init(npcs_in_room_t *npcs_in_room, char *room_id);
/*
* Allocates a new npcs_in_room struct in the heap
*
* Parameters:
* room_id: The unique id of the room
*
* Returns:
* Pointer to allocated npcs_in_room struct
*/
npcs_in_room_t *npcs_in_room_new(char* room_id);
/*
* Frees resources associated with an npcs_in_room struct
*
* Parameters:
* npcs_in_room: The npcs_in_room struct to be freed
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs.
*/
int npcs_in_room_free(npcs_in_room_t *npcs_in_room);
As well as additional functions to complete the rooms-npc module:
/*
* Returns the number of npcs in a room
*
* Parameters:
* npcs_in_room: The struct holding the npcs in the room
*
* Returns:
* The number of NPCs in the room as an int
*/
int npcs_in_room_get_number(npcs_in_room_t *npcs_in_room);
/* Adds an npc to the given npcs_in_room
*
* Parameters:
* npcs_in_room_t: Pointer to the npcs_in_room struct
* npc_t: Pointer to an NPC
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs or if NPC is already in the
* respective room.
*/
int add_npc_to_room(npcs_in_room_t *npcs_in_room, npc_t *npc);
/* Removes an npc in a given npcs_in_room
*
* Parameters:
* npcs_in_room_t: Pointer to the npcs_in_room struct
* npc_t: Pointer to an NPC
*
* Returns:
* SUCCESS on success, FAILURE if an error occurs or if NPC is not
* in the room
*/
int delete_npc_from_room(npcs_in_room_t *npcs_in_room, npc_t *npc);
Currently, our team does not see any future changes to the rooms-npc module unless changes in other modules deem this necessary.