1  /* ************************************************************************
  2  *   File: graph.c                                       Part of CircleMUD *
  3  *  Usage: various graph algorithms                                        *
  4  *                                                                         *
  5  *  All rights reserved.  See license.doc for complete information.        *
  6  *                                                                         *
  7  *  Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University *
  8  *  CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991.               *
  9  ************************************************************************ */
 10  
 11  #include "conf.h"
 12  #include "sysdep.h"
 13  
 14  
 15  #include "structs.h"
 16  #include "utils.h"
 17  #include "comm.h"
 18  #include "interpreter.h"
 19  #include "handler.h"
 20  #include "db.h"
 21  #include "spells.h"
 22  
 23  
 24  /* external functions */
 25  ACMD(do_say);
 26  
 27  /* external variables */
 28  extern const char *dirs[];
 29  extern int track_through_doors;
 30  
 31  /* local functions */
 32  int VALID_EDGE(room_rnum x, int y);
 33  void bfs_enqueue(room_rnum room, int dir);
 34  void bfs_dequeue(void);
 35  void bfs_clear_queue(void);
 36  int find_first_step(room_rnum src, room_rnum target);
 37  ACMD(do_track);
 38  void hunt_victim(struct char_data *ch);
 39  
 40  struct bfs_queue_struct {
 41    room_rnum room;
 42    char dir;
 43    struct bfs_queue_struct *next;
 44  };
 45  
 46  static struct bfs_queue_struct *queue_head = 0, *queue_tail = 0;
 47  
 48  /* Utility macros */
 49  #define MARK(room)	(SET_BIT(ROOM_FLAGS(room), ROOM_BFS_MARK))
 50  #define UNMARK(room)	(REMOVE_BIT(ROOM_FLAGS(room), ROOM_BFS_MARK))
 51  #define IS_MARKED(room)	(ROOM_FLAGGED(room, ROOM_BFS_MARK))
 52  #define TOROOM(x, y)	(world[(x)].dir_option[(y)]->to_room)
 53  #define IS_CLOSED(x, y)	(EXIT_FLAGGED(world[(x)].dir_option[(y)], EX_CLOSED))
 54  
 55  int VALID_EDGE(room_rnum x, int y)
 56  {
 57    if (world[x].dir_option[y] == NULL || TOROOM(x, y) == NOWHERE)
 58      return 0;
 59    if (track_through_doors == FALSE && IS_CLOSED(x, y))
 60      return 0;
 61    if (ROOM_FLAGGED(TOROOM(x, y), ROOM_NOTRACK) || IS_MARKED(TOROOM(x, y)))
 62      return 0;
 63  
 64    return 1;
 65  }
 66  
 67  void bfs_enqueue(room_rnum room, int dir)
 68  {
 69    struct bfs_queue_struct *curr;
 70  
 71    CREATE(curr, struct bfs_queue_struct, 1);
 72    curr->room = room;
 73    curr->dir = dir;
 74    curr->next = 0;
 75  
 76    if (queue_tail) {
 77      queue_tail->next = curr;
 78      queue_tail = curr;
 79    } else
 80      queue_head = queue_tail = curr;
 81  }
 82  
 83  
 84  void bfs_dequeue(void)
 85  {
 86    struct bfs_queue_struct *curr;
 87  
 88    curr = queue_head;
 89  
 90    if (!(queue_head = queue_head->next))
 91      queue_tail = 0;
 92    free(curr);
 93  }
 94  
 95  
 96  void bfs_clear_queue(void)
 97  {
 98    while (queue_head)
 99      bfs_dequeue();
100  }
101  
102  
103  /* 
104   * find_first_step: given a source room and a target room, find the first
105   * step on the shortest path from the source to the target.
106   *
107   * Intended usage: in mobile_activity, give a mob a dir to go if they're
108   * tracking another mob or a PC.  Or, a 'track' skill for PCs.
109   */
110  int find_first_step(room_rnum src, room_rnum target)
111  {
112    int curr_dir;
113    room_rnum curr_room;
114  
115    if (src == NOWHERE || target == NOWHERE || src > top_of_world || target > top_of_world) {
116      log("SYSERR: Illegal value %d or %d passed to find_first_step. (%s)", src, target, __FILE__);
117      return (BFS_ERROR);
118    }
119    if (src == target)
120      return (BFS_ALREADY_THERE);
121  
122    /* clear marks first, some OLC systems will save the mark. */
123    for (curr_room = 0; curr_room <= top_of_world; curr_room++)
124      UNMARK(curr_room);
125  
126    MARK(src);
127  
128    /* first, enqueue the first steps, saving which direction we're going. */
129    for (curr_dir = 0; curr_dir < NUM_OF_DIRS; curr_dir++)
130      if (VALID_EDGE(src, curr_dir)) {
131        MARK(TOROOM(src, curr_dir));
132        bfs_enqueue(TOROOM(src, curr_dir), curr_dir);
133      }
134  
135    /* now, do the classic BFS. */
136    while (queue_head) {
137      if (queue_head->room == target) {
138        curr_dir = queue_head->dir;
139        bfs_clear_queue();
140        return (curr_dir);
141      } else {
142        for (curr_dir = 0; curr_dir < NUM_OF_DIRS; curr_dir++)
143  	if (VALID_EDGE(queue_head->room, curr_dir)) {
144  	  MARK(TOROOM(queue_head->room, curr_dir));
145  	  bfs_enqueue(TOROOM(queue_head->room, curr_dir), queue_head->dir);
146  	}
147        bfs_dequeue();
148      }
149    }
150  
151    return (BFS_NO_PATH);
152  }
153  
154  
155  /********************************************************
156  * Functions and Commands which use the above functions. *
157  ********************************************************/
158  
159  ACMD(do_track)
160  {
161    char arg[MAX_INPUT_LENGTH];
162    struct char_data *vict;
163    int dir;
164  
165    /* The character must have the track skill. */
166    if (IS_NPC(ch) || !GET_SKILL(ch, SKILL_TRACK)) {
167      send_to_char(ch, "You have no idea how.\r\n");
168      return;
169    }
170    one_argument(argument, arg);
171    if (!*arg) {
172      send_to_char(ch, "Whom are you trying to track?\r\n");
173      return;
174    }
175    /* The person can't see the victim. */
176    if (!(vict = get_char_vis(ch, arg, NULL, FIND_CHAR_WORLD))) {
177      send_to_char(ch, "No one is around by that name.\r\n");
178      return;
179    }
180    /* We can't track the victim. */
181    if (AFF_FLAGGED(vict, AFF_NOTRACK)) {
182      send_to_char(ch, "You sense no trail.\r\n");
183      return;
184    }
185  
186    /* 101 is a complete failure, no matter what the proficiency. */
187    if (rand_number(0, 101) >= GET_SKILL(ch, SKILL_TRACK)) {
188      int tries = 10;
189      /* Find a random direction. :) */
190      do {
191        dir = rand_number(0, NUM_OF_DIRS - 1);
192      } while (!CAN_GO(ch, dir) && --tries);
193      send_to_char(ch, "You sense a trail %s from here!\r\n", dirs[dir]);
194      return;
195    }
196  
197    /* They passed the skill check. */
198    dir = find_first_step(IN_ROOM(ch), IN_ROOM(vict));
199  
200    switch (dir) {
201    case BFS_ERROR:
202      send_to_char(ch, "Hmm.. something seems to be wrong.\r\n");
203      break;
204    case BFS_ALREADY_THERE:
205      send_to_char(ch, "You're already in the same room!!\r\n");
206      break;
207    case BFS_NO_PATH:
208      send_to_char(ch, "You can't sense a trail to %s from here.\r\n", HMHR(vict));
209      break;
210    default:	/* Success! */
211      send_to_char(ch, "You sense a trail %s from here!\r\n", dirs[dir]);
212      break;
213    }
214  }
215  
216  
217  void hunt_victim(struct char_data *ch)
218  {
219    int dir;
220    byte found;
221    struct char_data *tmp;
222  
223    if (!ch || !HUNTING(ch) || FIGHTING(ch))
224      return;
225  
226    /* make sure the char still exists */
227    for (found = FALSE, tmp = character_list; tmp && !found; tmp = tmp->next)
228      if (HUNTING(ch) == tmp)
229        found = TRUE;
230  
231    if (!found) {
232      char actbuf[MAX_INPUT_LENGTH] = "Damn!  My prey is gone!!";
233  
234      do_say(ch, actbuf, 0, 0);
235      HUNTING(ch) = NULL;
236      return;
237    }
238    if ((dir = find_first_step(IN_ROOM(ch), IN_ROOM(HUNTING(ch)))) < 0) {
239      char buf[MAX_INPUT_LENGTH];
240  
241      snprintf(buf, sizeof(buf), "Damn!  I lost %s!", HMHR(HUNTING(ch)));
242      do_say(ch, buf, 0, 0);
243      HUNTING(ch) = NULL;
244    } else {
245      perform_move(ch, dir, 1);
246      if (IN_ROOM(ch) == IN_ROOM(HUNTING(ch)))
247        hit(ch, HUNTING(ch), TYPE_UNDEFINED);
248    }
249  }