/* ************************************************************************
   *   File: graph.c                                       Part of CircleMUD *
   *  Usage: various graph algorithms                                        *
   *                                                                         *
   *  All rights reserved.  See license.doc for complete information.        *
   *                                                                         *
   *  Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University *
   *  CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991.               *
   ************************************************************************ */


#define TRACK_THROUGH_DOORS

/* You can define or not define TRACK_THOUGH_DOORS, above, depending on
   whether or not you want track to find paths which lead through closed
   or hidden doors.
 */

#include "conf.h"
#include "sysdep.h"

#include "structs.h"
#include "utils.h"
#include "comm.h"
#include "interpreter.h"
#include "handler.h"
#include "db.h"
#include "spells.h"


/* Externals */
extern int top_of_world;
extern const char *dirs[];
extern struct room_data *world;

struct bfs_queue_struct
  {
    long room;
    char dir;
    struct bfs_queue_struct *next;
  };

static struct bfs_queue_struct *queue_head = 0, *queue_tail = 0;

/* Utility macros */
#define MARK(room) (SET_BIT(ROOM_FLAGS(room), ROOM_BFS_MARK))
#define UNMARK(room) (REMOVE_BIT(ROOM_FLAGS(room), ROOM_BFS_MARK))
#define IS_MARKED(room) (IS_SET(ROOM_FLAGS(room), ROOM_BFS_MARK))
#define TOROOM(x, y) (world[(x)].dir_option[(y)]->to_room)
#define IS_CLOSED(x, y) (IS_SET(world[(x)].dir_option[(y)]->exit_info, EX_CLOSED))

#ifdef TRACK_THROUGH_DOORS
#define VALID_EDGE(x, y) (world[(x)].dir_option[(y)] && \
			  (TOROOM(x, y) != NOWHERE) &&	\
			  (!ROOM_FLAGGED(TOROOM(x, y), ROOM_NOTRACK)) && \
			  (!IS_MARKED(TOROOM(x, y))))
#else
#define VALID_EDGE(x, y) (world[(x)].dir_option[(y)] && \
			  (TOROOM(x, y) != NOWHERE) &&	\
			  (!IS_CLOSED(x, y)) &&		\
			  (!ROOM_FLAGGED(TOROOM(x, y), ROOM_NOTRACK)) && \
			  (!IS_MARKED(TOROOM(x, y))))
#endif

void 
bfs_enqueue (long room, int dir)
{
  struct bfs_queue_struct *curr;

  CREATE (curr, struct bfs_queue_struct, 1);
  curr->room = room;
  curr->dir = dir;
  curr->next = 0;

  if (queue_tail)
    {
      queue_tail->next = curr;
      queue_tail = curr;
    }
  else
    queue_head = queue_tail = curr;
}


void 
bfs_dequeue (void)
{
  struct bfs_queue_struct *curr;

  curr = queue_head;

  if (!(queue_head = queue_head->next))
    queue_tail = 0;
  free (curr);
}


void 
bfs_clear_queue (void)
{
  while (queue_head)
    bfs_dequeue ();
}


/* find_first_step: given a source room and a target room, find the first
   step on the shortest path from the source to the target.

   Intended usage: in mobile_activity, give a mob a dir to go if they're
   tracking another mob or a PC.  Or, a 'track' skill for PCs.
 */

int 
find_first_step (long src, long target)
{
  int curr_dir;
  long curr_room;

  if (src < 0 || src > top_of_world || target < 0 || target > top_of_world)
    {
      log ("Illegal value passed to find_first_step (graph.c)");
      return BFS_ERROR;
    }
  if (src == target)
    return BFS_ALREADY_THERE;

  /* clear marks first */
  for (curr_room = 0; curr_room <= top_of_world; curr_room++)
    UNMARK (curr_room);

  MARK (src);

  /* first, enqueue the first steps, saving which direction we're going. */
  for (curr_dir = 0; curr_dir < NUM_OF_DIRS; curr_dir++)
    if (VALID_EDGE (src, curr_dir))
      {
	MARK (TOROOM (src, curr_dir));
	bfs_enqueue (TOROOM (src, curr_dir), curr_dir);
      }
  /* now, do the classic BFS. */
  while (queue_head)
    {
      if (queue_head->room == target)
	{
	  curr_dir = queue_head->dir;
	  bfs_clear_queue ();
	  return curr_dir;
	}
      else
	{
	  for (curr_dir = 0; curr_dir < NUM_OF_DIRS; curr_dir++)
	    if (VALID_EDGE (queue_head->room, curr_dir))
	      {
		MARK (TOROOM (queue_head->room, curr_dir));
		bfs_enqueue (TOROOM (queue_head->room, curr_dir), queue_head->dir);
	      }
	  bfs_dequeue ();
	}
    }

  return BFS_NO_PATH;
}


/************************************************************************
*  Functions and Commands which use the above fns		        *
************************************************************************/

ACMD (do_track)
{
  struct char_data *vict;
  int dir, num;

  if (!GET_SKILL (ch, SKILL_TRACK))
    {
      send_to_char ("You have no idea how.\r\n", ch);
      return;
    }
  one_argument (argument, arg);
  if (!*arg)
    {
      send_to_char ("Whom are you trying to track?\r\n", ch);
      return;
    }
  if (!(vict = get_char_vis (ch, arg)))
    {
      send_to_char ("No-one around by that name.\r\n", ch);
      return;
    }
  if (IS_AFFECTED (vict, AFF_NOTRACK))
    {
      send_to_char ("You sense no trail.\r\n", ch);
      return;
    }
  dir = find_first_step (ch->in_room, vict->in_room);

  switch (dir)
    {
    case BFS_ERROR:
      send_to_char ("Hmm.. something seems to be wrong.\r\n", ch);
      break;
    case BFS_ALREADY_THERE:
      send_to_char ("You're already in the same room!!\r\n", ch);
      break;
    case BFS_NO_PATH:
      sprintf (buf, "You can't sense a trail to %s from here.\r\n",
	       HMHR (vict));
      send_to_char (buf, ch);
      break;
    default:
      num = number (0, 101);	/* 101% is a complete failure */
      if (GET_SKILL (ch, SKILL_TRACK) < num)
	do
	  {
	    dir = number (0, NUM_OF_DIRS - 1);
	  }
	while (!CAN_GO (ch, dir));
      sprintf (buf, "You sense a trail %s from here!\r\n", dirs[dir]);
      send_to_char (buf, ch);
      break;
    }
}


void 
hunt_victim (struct char_data *ch)
{
  ACMD (do_say);
  extern struct char_data *character_list;

  int dir;
  byte found;
  struct char_data *tmp;

  if (!ch || !HUNTING (ch))
    return;

  /* make sure the char still exists */
  for (found = 0, tmp = character_list; tmp && !found; tmp = tmp->next)
    if (HUNTING (ch) == tmp)
      found = 1;

  if (!found)
    {
      do_say (ch, "Damn!  My prey is gone!!", 0, 0);
      HUNTING (ch) = 0;
      return;
    }
  dir = find_first_step (ch->in_room, HUNTING (ch)->in_room);
  if (dir < 0)
    {
      sprintf (buf, "Damn!  Lost %s!", HMHR (HUNTING (ch)));
      do_say (ch, buf, 0, 0);
      HUNTING (ch) = 0;
      return;
    }
  else
    {
      perform_move (ch, dir, 1);
      if (ch->in_room == HUNTING (ch)->in_room)
	hit (ch, HUNTING (ch), TYPE_UNDEFINED);
      return;
    }
}