/************************************************************************
	Realms of Aurealis 		James Rhone aka Vall of RoA

graph.c				Basic algorithms used for tracking thru
				various rooms around the mud.  Primarily
				used for hunting mobs, tracking players,
				shopkeep homes/shops and transports moving
				from one destination to the next.

		******** Heavily modified and expanded ********
		*** BE AWARE OF ALL RIGHTS AND RESERVATIONS ***
		******** Heavily modified and expanded ********
		        All rights reserved henceforth. 

    Please note that no guarantees are associated with any code from
Realms of Aurealis.  All code which has been released to the general
public has been done so with an 'as is' pretense.  RoA is based on both
Diku and CircleMUD and ALL licenses from both *MUST* be adhered to as well
as the RoA license.   *** Read, Learn, Understand, Improve ***
*************************************************************************/
#include "conf.h"
#include "sysdep.h"

#include "structures.h"
#include "utils.h"
#include "comm.h"
#include "interpreter.h"
#include "acmd.h"
#include "handler.h"
#include "db.h"
#include "fight.h"
#include "magic.h"
#include "lists.h"

// external variables
extern const char 	*dirs[];
extern const char 	*rev_dir_str[];
extern rmdata		*world; 

extern struct room_affect_type *spell_affects_room(int room, int spell);

// internal structures and variables
struct bfs_queue_struct {
   int 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(world[room].room_flags, BFS_MARK))
#define UNMARK(room) 	(REMOVE_BIT(world[room].room_flags, BFS_MARK))
#define IS_MARKED(room) (ROOM_FLAGGED((room), BFS_MARK))
#define TOROOM(x, y) 	(DIR(x, y)->to_room)
#define IS_CLOSED(x, y) (EXIT_FLAGGED(DIR(x, y), EX_CLOSED))

// note, this will not track through closed doors
#define VALID_EDGE(x, y) (DIR(x, y) && !INVALID_ROOM(TOROOM(x, y)) && \
			  !IS_CLOSED(x, y) && !IS_MARKED(TOROOM(x, y)) && \
			  !ROOM_FLAGGED2(TOROOM(x, y), NO_TRACK) && \
			  !spell_affects_room(TOROOM(x, y), SKILL_NOTRACK))

/* check terrain to see if we can go/track in this dir */
#define VALID_TERRAIN_EDGE(x, y)  (DIR(x, y) && (TOROOM(x, y) != NOWHERE) && \
				  (!IS_CLOSED(x, y)) && (!IS_MARKED(TOROOM(x, y))) && \
				   similar_terrain(x, TOROOM(x, y)))

// stick a piece on the track queue
void bfs_enqueue(int room, char 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;
}

// take a piece off the end of the track queue
void bfs_dequeue(void)
{
  struct bfs_queue_struct *curr;

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

// wipe out the track queue
void bfs_clear_queue(void) 
{
  while (queue_head)
    bfs_dequeue();
}

// use a bfs to find the first direction to travel in mob hunts or 
// player tracks... does not track thru closed doors i dont think
int find_first_step(int src, int target)
{
  int curr_dir, 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;
}

// player interface to the tracking code
ACMD(do_track)
{
  chdata *vict;
  int dir;

  one_argument(argument, arg);
  if (!*arg) {
    send_to_char("Whom are you trying to track?\n\r", ch);
    return;
  }

  if (!(vict = get_char_vis(ch, arg))) {
    send_to_char("No-one around by that name.\n\r", ch);
    return;
  }

  if (IS_PC(ch))
   if (world[ch->in_room].zone != world[vict->in_room].zone)  /* must be in same zone */
   {
     send_to_char("You are too far away to find a good trail.\n\r",ch);
     return;
   }

  if (IS_AFFECTED(vict, AFF_SNEAK))
  {
    act("$N is currently untrackable from here.", FALSE, ch, 0, vict, TO_CHAR);
    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.\n\r", ch);
       break;
    case BFS_ALREADY_THERE:
       send_to_char("You're already in the same room!!\n\r", ch);
       break;
    case BFS_NO_PATH:
       sprintf(buf, "You can't sense a trail to %s from here.\n\r",
	       HMHR(vict));
       S2C();
       break;
    default:
#ifdef TRACK_IS_SKILL
	 {
            int	num;

	    num = number(0, 101);
	    if (SKILL(ch, SKILL_TRACK) < num)
               do { dir = number(0, NUM_OF_DIRS-1); } while (!CAN_GO(ch, dir));
	 }
#endif

       sprintf(buf, "You sense a trail %s from here!\n\r", dirs[dir]);
       S2C();
       break;
  }
}

// mob uses this track stuff to hun who they are hunting
void hunt_victim(chdata *ch)
{
  int dir;
  byte found;
  chdata *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 = TRUE;

  if (!found) 
  {
    act("$n peers around, looking for lost prey.", TRUE, ch, 0, 0,TO_ROOM);
    HUNTING(ch) = NULL;
    return;
  }

  dir = find_first_step(ch->in_room, HUNTING(ch)->in_room);
  if (dir < 0) 
  {
    act("$n seems to be hunting somebody.", TRUE, ch, 0, 0,TO_ROOM);
    HUNTING(ch) = NULL;
    return;
  } 
  else 
  {
    do_move(ch, "", dir+1, 0);
    if (ch && HUNTING(ch) && SAME_ROOM(ch, HUNTING(ch)))  // make sure alive after move  4/19/98 -jtrhone
    {
      act("$n has %6HUNTED%0 you down!!!",TRUE,ch,0,HUNTING(ch),TO_VICT);
      VWAIT(ch) = 1;
      hit(ch, HUNTING(ch), -1, TRUE);
    }
  }
}

// for tracking which uses similar room terrain
// for transports mainly
BOOL similar_terrain(int rm1, int rm2)
{
  BOOL land = FALSE;
  BOOL air = FALSE;
  BOOL sea_surface = FALSE;
  BOOL undersea = FALSE;

  return TRUE; /* for now... */

  if (world[rm1].terrain_type == world[rm2].terrain_type)
   return TRUE;

  switch (world[rm1].terrain_type)
  {
    case TERRAIN_WATER_SWIM:
    case TERRAIN_WATER_NOSWIM:
	sea_surface = TRUE; break;
    case TERRAIN_UWATER:
	undersea = TRUE; break;
    case TERRAIN_AIR:
	air = TRUE; break;
    default:
      land = TRUE;
  }

  switch (world[rm2].terrain_type)
  {
    case TERRAIN_WATER_SWIM:
    case TERRAIN_WATER_NOSWIM:
	return sea_surface;
    case TERRAIN_UWATER:
	return undersea;
    case TERRAIN_AIR:
	return air;
    default:
        return land; 
  }
}

// identical as find first step, but uses terrain considerations
int find_first_step_terrain(int src, int target)
{
  int curr_dir;
  int 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_TERRAIN_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_TERRAIN_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;
}