diff options
| -rw-r--r-- | Makefile | 11 | ||||
| -rw-r--r-- | ht.c | 185 | ||||
| -rw-r--r-- | ht.h | 20 | ||||
| -rw-r--r-- | main.c | 84 |
4 files changed, 262 insertions, 38 deletions
@@ -1,10 +1,15 @@ all: main -main: main.c cavegen.o - $(CC) main.c cavegen.o -lcurses -o main -D_XOPEN_SOURCE_EXTENDED +CFLAGS=-g + +main: main.c cavegen.o ht.o + $(CC) main.c cavegen.o ht.o -lcurses -o main -D_XOPEN_SOURCE_EXTENDED $(CFLAGS) cavegen.o: cavegen.c - $(CC) cavegen.c -c -o cavegen.o + $(CC) cavegen.c -c -o cavegen.o $(CFLAGS) + +ht.o: ht.c + $(CC) ht.c -c -o ht.o $(CFLAGS) clean: rm -rf main cavegen.o @@ -0,0 +1,185 @@ +#include "ht.h" + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define SIZE 1024 + +struct node { + char *key; + void *val; + struct node *next; +}; + +struct hash_table { + struct node **vals; + int max_size; + int size; + + int curr_index; + struct node *curr_node; + bool iterating; +}; + +static unsigned long djb2_hash(char *str) +{ + unsigned long hash = 5381; + int c; + + // hash * 33 + c + while ((c = *str++)) hash = ((hash << 5) + hash) + c; + + return hash; +} + +ht_t *ht_create(void) +{ + ht_t *h = malloc(sizeof(ht_t)); + h->max_size = SIZE; + h->size = 0; + h->vals = malloc(sizeof(struct node) * h->max_size); + h->curr_index = 0; + h->curr_node = NULL; + h->iterating = false; + + return h; +} + +void ht_destroy(ht_t *h) +{ + // only destroy if h isn't NULL + if (h) { + // only destroy vals if it isn't NULL + if (h->vals) { + // iterate through the hash values + for (int i = 0; i < h->max_size; ++i) { + // iterate through the linked list and remove the value + struct node *curr = h->vals[i]; + struct node *prev; + while (curr) { + prev = curr; + curr = curr->next; + free(prev->key); + free(prev); + } + } + free(h->vals); + } + free(h); + } +} + +void *ht_find(ht_t *h, char *key) +{ + unsigned int hash = djb2_hash(key) % h->max_size; + + // exit early if hash isn't in table + if (!h->vals[hash]) + return NULL; + + // iterate through values stored at `hash`; exit early if found + struct node *curr = h->vals[hash]; + while (curr) { + if (strcmp(key, curr->key) == 0) + return curr->val; + curr = curr->next; + } + + return NULL; +} + +void ht_insert(ht_t *h, char *key, void *val) +{ + unsigned int hash = djb2_hash(key) % h->max_size; + + // create a node + int len = strlen(key); + struct node *new = malloc(sizeof(struct node)); + new->key = malloc(sizeof(char) * (len + 1)); + for (int i = 0; i < len; ++i) { + new->key[i] = key[i]; + } + new->key[len] = 0; + new->val = val; + + // insert node at beginning of list + if (h->vals[hash]) { + new->next = h->vals[hash]; + } + h->vals[hash] = new; + + ++(h->size); +} + +void ht_delete(ht_t *h, char *key) +{ + unsigned int hash = djb2_hash(key) % h->max_size; + + if (!h->vals[hash]) + return; // exit if the hash is not found + + // remove the key from the front of the list if it's there + if (strcmp(key, h->vals[hash]->key) == 0) { + struct node *temp = h->vals[hash]; + h->vals[hash] = h->vals[hash]->next; + free(temp->key); + free(temp); + } else { + // iterate through list and remove once a match is found + struct node *prev = h->vals[hash]; + struct node *curr = h->vals[hash]->next; + while (curr) { + if (strcmp(key, curr->key) == 0) { + prev->next = curr->next; + free(curr->key); + free(curr); + return; + } + + prev = curr; + curr = curr->next; + } + } +} + +int ht_size(ht_t *h) +{ + return h->size; +} + +void ht_iter_init(ht_t *h) +{ + h->curr_index = 0; + h->curr_node = h->vals[0]; +} + +void *ht_iter_next(ht_t *h) +{ + // return NULL if we've reached the end + if (!h->curr_node && h->curr_index >= h->max_size) + return NULL; + + if (!h->curr_node) { + // look for next index with node if current node is NULL + while (!h->curr_node) { + h->curr_node = h->vals[h->curr_index++]; + if (h->curr_index >= h->max_size) + return NULL; + } + return h->curr_node->val; + } else { + // move to the next node + h->curr_node = h->curr_node->next; + if (h->curr_node) + return h->curr_node->val; + + // look for next index with node if necessary + while (!h->curr_node) { + h->curr_node = h->vals[h->curr_index++]; + if (h->curr_index >= h->max_size) + return NULL; + } + return h->curr_node->val; + } +} @@ -0,0 +1,20 @@ +#ifndef HT_H_ +#define HT_H_ + +#include <stdbool.h> + +typedef struct hash_table ht_t; + +ht_t *ht_create(void); +void ht_destroy(ht_t *h); + +void *ht_find(ht_t *h, char *key); +void ht_insert(ht_t *h, char *key, void *val); +void ht_delete(ht_t *h, char *key); + +int ht_size(ht_t *h); + +void ht_iter_init(ht_t *h); +void *ht_iter_next(ht_t *h); + +#endif // HT_H_ @@ -4,6 +4,7 @@ #include <time.h> #include "cavegen.h" +#include "ht.h" #define MAIN_PANEL_WIDTH 100 #define MAIN_PANEL_HEIGHT 41 @@ -17,7 +18,6 @@ #define MAX_ENTITIES 100 struct entity { - char *name; struct point p; char *disp_ch; bool solid; @@ -75,15 +75,15 @@ void initialize(void) refresh(); } -void display_map( - WINDOW *win, struct map *map, struct entity *entities, int num_entities -) +void display_map(WINDOW *win, struct map *map, ht_t *entities) { // print map + struct entity *camera = ht_find(entities, "camera"); + for (int i = 1; i < MAIN_PANEL_HEIGHT - 1; ++i) { for (int j = 1; j < MAIN_PANEL_WIDTH - 1; ++j) { - int map_i = i - 1 + entities[0].p.y; - int map_j = j - 1 + entities[0].p.x; + int map_i = i - 1 + camera->p.y; + int map_j = j - 1 + camera->p.x; if (map_i > map->height || map_j > map->width || map_i < 0 || map_j < 0) { @@ -118,14 +118,17 @@ void display_map( } // print entities - for (int i = 1; i < num_entities; ++i) { - if (entities[i].visible) { + ht_iter_init(entities); + struct entity *e; + while ((e = ht_iter_next(entities))) { + if (e->visible) { mvwprintw( - win, entities[i].p.y - entities[0].p.y + 1, - entities[i].p.x - entities[0].p.x + 1, entities[i].disp_ch + win, e->p.y - camera->p.y + 1, e->p.x - camera->p.x + 1, + e->disp_ch ); } } + wrefresh(win); } @@ -221,32 +224,42 @@ int main(void) struct map map; create_cave(&map); - // create the camera and player at the up stairs - struct entity *entities = malloc(sizeof(struct entity) * MAX_ENTITIES); - entities[0].disp_ch = ""; - entities[0].name = "camera"; - entities[0].p.x = map.entry_point.x - MAIN_PANEL_WIDTH / 2 + 1; - entities[0].p.y = map.entry_point.y - MAIN_PANEL_HEIGHT / 2 + 1; - entities[0].solid = false; - entities[0].visible = false; - entities[1].disp_ch = "@"; - entities[1].name = "player"; - entities[1].p = map.entry_point; - entities[1].solid = true; - entities[1].visible = true; - int num_entities = 2; + // create the entity map + ht_t *entities = ht_create(); + + // create the camera + struct entity camera; + camera.disp_ch = ""; + camera.solid = false; + camera.visible = false; + ht_insert(entities, "camera", &camera); + + // create the player + struct entity player; + player.disp_ch = "@"; + player.solid = true; + player.visible = true; + ht_insert(entities, "player", &player); + + // set starting point + struct point cam_p = { + .x = map.entry_point.x - MAIN_PANEL_WIDTH / 2 + 1, + .y = map.entry_point.y - MAIN_PANEL_HEIGHT / 2 + 1, + }; + entity_set_pos(&player, map.entry_point, &map); + entity_set_pos(&camera, cam_p, &map); // start displaying things - display_map(windows.main, &map, entities, num_entities); + display_map(windows.main, &map, entities); display_instructions(windows.inst); - display_status(windows.stat, &entities[1]); + display_status(windows.stat, &player); display_message(windows.msgs, ""); int ch; bool done = false; while (!done && (ch = getch()) != KEY_F(1)) { - struct point newp = entities[1].p; - struct point newp_cam = entities[0].p; + struct point newp = player.p; + struct point newp_cam = camera.p; switch (ch) { case 'k' : --newp.y; @@ -265,8 +278,7 @@ int main(void) ++newp_cam.x; break; case '>' : - if (map.map[entities[1].p.y * map.width + entities[1].p.x] == - DOWN_STAIR) { + if (map.map[player.p.y * map.width + player.p.x] == DOWN_STAIR) { free(map.map); create_cave(&map); @@ -278,17 +290,19 @@ int main(void) } break; case '<' : - if (map.map[entities[1].p.y * WIDTH + entities[1].p.x] == - UP_STAIR) { + if (map.map[player.p.y * WIDTH + player.p.x] == UP_STAIR) { done = true; } break; } - if (entity_set_pos(&entities[1], newp, &map)) - entity_set_pos(&entities[0], newp_cam, &map); + if (entity_set_pos(&player, newp, &map)) + entity_set_pos(&camera, newp_cam, &map); - display_map(windows.main, &map, entities, num_entities); + display_map(windows.main, &map, entities); + char msg[100]; + sprintf(msg, "x: %d, y: %d", player.p.x, player.p.y); + display_message(windows.msgs, msg); } free(map.map); |