#include <stdio.h> #include <stdlib.h> #include <time.h> #include "merc.h" void bcopy (register char *s1, register char *s2, int len); void bzero (register char *sp, int len); struct hash_link { int key; struct hash_link *next; void *data; }; struct hash_header { int rec_size; int table_size; int *keylist, klistsize, klistlen; /* this is really lame, AMAZINGLY lame */ struct hash_link **buckets; }; #define WORLD_SIZE 30000 #define HASH_KEY(ht,key)((((unsigned int)(key))*17)%(ht)->table_size) struct hunting_data { char *name; struct char_data **victim; }; struct room_q { int room_nr; struct room_q *next_q; }; struct nodes { int visited; int ancestor; }; #define IS_DIR (get_room_index(q_head->room_nr)->exit[i]) #define GO_OK (!IS_SET( IS_DIR->exit_info, EX_CLOSED )) #define GO_OK_SMARTER 1 #if defined( NO_BCOPY ) void bcopy (register char *s1, register char *s2, int len) { while (len--) *(s2++) = *(s1++); } #endif #if defined( NO_BZERO ) void bzero (register char *sp, int len) { while (len--) *(sp++) = '\0'; } #endif void init_hash_table (struct hash_header *ht, int rec_size, int table_size) { ht->rec_size = rec_size; ht->table_size = table_size; ht->buckets = (void *) calloc (sizeof (struct hash_link **), table_size); ht->keylist = (void *) malloc (sizeof (ht->keylist) * (ht->klistsize = 128)); ht->klistlen = 0; } void init_world (ROOM_INDEX_DATA * room_db[]) { /* zero out the world */ bzero ((char *) room_db, sizeof (ROOM_INDEX_DATA *) * WORLD_SIZE); } void destroy_hash_table (struct hash_header *ht, void (*gman) ()) { int i; struct hash_link *scan, *temp; for (i = 0; i < ht->table_size; i++) for (scan = ht->buckets[i]; scan;) { temp = scan->next; (*gman) (scan->data); free (scan); scan = temp; } free (ht->buckets); free (ht->keylist); } void _hash_enter (struct hash_header *ht, int key, void *data) { /* precondition: there is no entry for <key> yet */ struct hash_link *temp; int i; temp = (struct hash_link *) malloc (sizeof (struct hash_link)); temp->key = key; temp->next = ht->buckets[HASH_KEY (ht, key)]; temp->data = data; ht->buckets[HASH_KEY (ht, key)] = temp; if (ht->klistlen >= ht->klistsize) { ht->keylist = (void *) realloc (ht->keylist, sizeof (*ht->keylist) * (ht->klistsize *= 2)); } for (i = ht->klistlen; i >= 0; i--) { if (ht->keylist[i - 1] < key) { ht->keylist[i] = key; break; } ht->keylist[i] = ht->keylist[i - 1]; } ht->klistlen++; } ROOM_INDEX_DATA * room_find (ROOM_INDEX_DATA * room_db[], int key) { return ((key < WORLD_SIZE && key > -1) ? room_db[key] : 0); } void * hash_find (struct hash_header *ht, int key) { struct hash_link *scan; scan = ht->buckets[HASH_KEY (ht, key)]; while (scan && scan->key != key) scan = scan->next; return scan ? scan->data : NULL; } int room_enter (ROOM_INDEX_DATA * rb[], int key, ROOM_INDEX_DATA * rm) { ROOM_INDEX_DATA *temp; temp = room_find (rb, key); if (temp) return (0); rb[key] = rm; return (1); } int hash_enter (struct hash_header *ht, int key, void *data) { void *temp; temp = hash_find (ht, key); if (temp) return 0; _hash_enter (ht, key, data); return 1; } ROOM_INDEX_DATA * room_find_or_create (ROOM_INDEX_DATA * rb[], int key) { ROOM_INDEX_DATA *rv; rv = room_find (rb, key); if (rv) return rv; rv = (ROOM_INDEX_DATA *) malloc (sizeof (ROOM_INDEX_DATA)); rb[key] = rv; return rv; } void * hash_find_or_create (struct hash_header *ht, int key) { void *rval; rval = hash_find (ht, key); if (rval) return rval; rval = (void *) malloc (ht->rec_size); _hash_enter (ht, key, rval); return rval; } int room_remove (ROOM_INDEX_DATA * rb[], int key) { ROOM_INDEX_DATA *tmp; tmp = room_find (rb, key); if (tmp) { rb[key] = 0; free (tmp); } return (0); } void * hash_remove (struct hash_header *ht, int key) { struct hash_link **scan; scan = ht->buckets + HASH_KEY (ht, key); while (*scan && (*scan)->key != key) scan = &(*scan)->next; if (*scan) { int i; struct hash_link *temp, *aux; temp = (*scan)->data; aux = *scan; *scan = aux->next; free (aux); for (i = 0; i < ht->klistlen; i++) if (ht->keylist[i] == key) break; if (i < ht->klistlen) { bcopy ((char *) ht->keylist + i + 1, (char *) ht->keylist + i, (ht->klistlen - i) * sizeof (*ht->keylist)); ht->klistlen--; } return temp; } return NULL; } void room_iterate (ROOM_INDEX_DATA * rb[], void (*func) (), void *cdata) { register int i; for (i = 0; i < WORLD_SIZE; i++) { ROOM_INDEX_DATA *temp; temp = room_find (rb, i); if (temp) (*func) (i, temp, cdata); } } void hash_iterate (struct hash_header *ht, void (*func) (), void *cdata) { int i; for (i = 0; i < ht->klistlen; i++) { void *temp; register int key; key = ht->keylist[i]; temp = hash_find (ht, key); (*func) (key, temp, cdata); if (ht->keylist[i] != key) /* They must have deleted this room */ i--; /* Hit this slot again. */ } } int exit_ok (EXIT_DATA * pexit) { ROOM_INDEX_DATA *to_room; if ((pexit == NULL) || (to_room = pexit->u1.to_room) == NULL) return 0; return 1; } void donothing () { return; } int find_path (int in_room_vnum, int out_room_vnum, CHAR_DATA * ch, int depth, int in_zone) { struct room_q *tmp_q, *q_head, *q_tail; struct hash_header x_room; int i, tmp_room, count = 0, thru_doors; ROOM_INDEX_DATA *herep; ROOM_INDEX_DATA *startp; EXIT_DATA *exitp; if (depth < 0) { thru_doors = TRUE; depth = -depth; } else { thru_doors = FALSE; } startp = get_room_index (in_room_vnum); init_hash_table (&x_room, sizeof (int), 2048); hash_enter (&x_room, in_room_vnum, (void *) -1); /* initialize queue */ q_head = (struct room_q *) malloc (sizeof (struct room_q)); q_tail = q_head; q_tail->room_nr = in_room_vnum; q_tail->next_q = 0; while (q_head) { herep = get_room_index (q_head->room_nr); /* for each room test all directions */ if (herep->area == startp->area || !in_zone) { /* only look in this zone... saves cpu time and makes world safer for players */ for (i = 0; i <= 5; i++) { exitp = herep->exit[i]; if (exit_ok (exitp) && (thru_doors ? GO_OK_SMARTER : GO_OK)) { /* next room */ tmp_room = herep->exit[i]->u1.to_room->vnum; if (tmp_room != out_room_vnum) { /* shall we add room to queue ? count determines total breadth and depth */ if (!hash_find (&x_room, tmp_room) && (count < depth)) /* && !IS_SET( RM_FLAGS(tmp_room), DEATH ) ) */ { count++; /* mark room as visted and put on queue */ tmp_q = (struct room_q *) malloc (sizeof (struct room_q)); tmp_q->room_nr = tmp_room; tmp_q->next_q = 0; q_tail->next_q = tmp_q; q_tail = tmp_q; /* ancestor for first layer is the direction */ hash_enter (&x_room, tmp_room, ((int) hash_find (&x_room, q_head->room_nr) == -1) ? (void *) (i + 1) : hash_find (&x_room, q_head->room_nr)); } } else { /* have reached our goal so free queue */ tmp_room = q_head->room_nr; for (; q_head; q_head = tmp_q) { tmp_q = q_head->next_q; free (q_head); } /* return direction if first layer */ if ((int) hash_find (&x_room, tmp_room) == -1) { if (x_room.buckets) { /* junk left over from a previous track */ destroy_hash_table (&x_room, donothing); } return (i); } else { /* else return the ancestor */ int i; i = (int) hash_find (&x_room, tmp_room); if (x_room.buckets) { /* junk left over from a previous track */ destroy_hash_table (&x_room, donothing); } return (-1 + i); } } } } } /* free queue head and point to next entry */ tmp_q = q_head->next_q; free (q_head); q_head = tmp_q; } /* couldn't find path */ if (x_room.buckets) { /* junk left over from a previous track */ destroy_hash_table (&x_room, donothing); } return -1; } /* void do_track( CHAR_DATA *ch, char *argument ) */ void do_hunt (CHAR_DATA * ch, char *argument) { char buf[MAX_STRING_LENGTH]; char arg[MAX_STRING_LENGTH]; CHAR_DATA *victim; int direction; bool fArea; one_argument (argument, arg); if (IS_NPC (ch) || ch->level < skill_table[gsn_hunt].skill_level[ch->class]) { send_to_char ("Huh?\n\r", ch); return; } if (arg[0] == '\0') { send_to_char ("Whom are you trying to hunt?\n\r", ch); return; } /* only imps can hunt to different areas */ fArea = (get_trust (ch) < MAX_LEVEL); if (!IS_IMMORTAL (ch)) victim = get_char_area (ch, arg); if (IS_NPC (ch)) victim = get_char_world (ch, arg); else victim = get_char_world (ch, arg); if (victim == NULL) { send_to_char ("No-one around by that name.\n\r", ch); return; } if (ch->in_room == victim->in_room) { act ("$N is here!", ch, NULL, victim, TO_CHAR); return; } /* * Deduct some movement. */ if (ch->move > 2) ch->move -= 3; else { send_to_char ("You're too exhausted to hunt anyone!\n\r", ch); return; } act ("$n carefully sniffs the air.", ch, NULL, NULL, TO_ROOM); WAIT_STATE (ch, skill_table[gsn_hunt].beats); direction = find_path (ch->in_room->vnum, victim->in_room->vnum, ch, -40000, fArea); if (direction == -1) { act ("You couldn't find a path to $N from here.", ch, NULL, victim, TO_CHAR); return; } if (direction < 0 || direction > 5) { send_to_char ("Hmm... Something seems to be wrong.\n\r", ch); return; } /* * Give a random direction if the player misses the die roll. */ if ((IS_NPC (ch) && number_percent () > 75) /* NPC @ 25% */ || (!IS_NPC (ch) && number_percent () > /* PC @ norm */ ch->pcdata->learned[gsn_hunt])) { do { direction = number_door (); } while ((ch->in_room->exit[direction] == NULL) || (ch->in_room->exit[direction]->u1.to_room == NULL)); } /* * Display the results of the search. */ sprintf (buf, "$N is %s from here.", dir_name[direction]); act (buf, ch, NULL, victim, TO_CHAR); check_improve (ch, gsn_hunt, TRUE, 1); return; }