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


/* 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.
*/

#define unix 1
#if defined(macintosh)
#include <types.h>
#else
#include <sys/types.h>
#endif
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "merc.h"

#define TRACK_THROUGH_DOORS
#define TRACK_IS_SKILL

struct track_queue_struct
{
   ROOM_INDEX_DATA *room;
   char   dir;
   struct track_queue_struct *next;
};

static struct track_queue_struct *queue_head = NULL, *queue_tail = NULL;

#define TRACK_NO_PATH          -1
#define TRACK_ALREADY_THERE    -2
#define TRACK_ERROR            -3


/* Utility macros */
#define MARK(room)      (SET_BIT((room)->room_flags, ROOM_MARK))
#define UNMARK(room)    (REMOVE_BIT((room)->room_flags, ROOM_MARK))
#define IS_MARKED(room) (IS_SET((room)->room_flags, ROOM_MARK))
#define TOROOM(x, y)    ((x)->exit[(y)] ? (x)->exit[(y)]->to_room : NULL)
#define IS_CLOSED(x, y) (IS_SET((x)->exit[(y)]->exit_info, EX_CLOSED))
#define IS_SAME_AREA(x,y)  ((x)->area == (y)->area)

#ifdef TRACK_THROUGH_DOORS
#define VALID_EDGE(x, y) ((x)->exit[(y)] && \
			  (TOROOM((x), (y)) != NULL) &&	\
			  (!IS_MARKED(TOROOM((x), (y)))) &&  \
                          (IS_SAME_AREA((x), TOROOM((x),(y)))))
#else
#define VALID_EDGE(x, y) ((x)->exit[(y)] && \
			  (TOROOM((x), (y)) != NULL) &&	\
			  (!IS_CLOSED((x), (y))) &&		\
			  (!IS_MARKED(TOROOM((x), (y)))) && \
                          (IS_SAME_AREA((x), TOROOM((x),(y)))))
#endif

bool can_go( CHAR_DATA *ch, int dir )
{
  ROOM_INDEX_DATA *room;
  EXIT_DATA *exit;

  if ( !(room = ch->in_room) )
    return FALSE;

  if ( !(exit = ch->in_room->exit[dir]) )
    return FALSE;

  if ( !exit->to_room )
    return FALSE;

/*  if ( !IS_SAME_AREA(room, exit->to_room) )
    return FALSE;*/

  if ( IS_SET(exit->exit_info, EX_BASHED) )
    return TRUE;

#ifdef TRACK_THROUGH_DOORS
  if ( IS_CLOSED(room, dir) )
    return FALSE;
#endif

  return TRUE;
}
  

void track_enqueue(ROOM_INDEX_DATA *room, char dir)
{
  struct track_queue_struct *curr;

  curr = alloc_mem( sizeof( *curr ));
  curr->room = room;
  curr->dir = dir;
  curr->next = NULL;

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


void track_dequeue(void)
{
  struct track_queue_struct *curr;

  curr = queue_head;

  if (!(queue_head = queue_head->next))
    queue_tail = NULL;
  free_mem(curr, sizeof( *curr ));
}


void track_clear_queue(void) 
{
  while (queue_head)
    track_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(ROOM_INDEX_DATA *src, ROOM_INDEX_DATA *target)
{
   int curr_dir;
   int curr_room;

   if (!src || !target)
   {
      bug("Illegal value passed to find_first_step (track.c)", 0 );
      return TRACK_ERROR;
   }

   if (src == target)
      return TRACK_ALREADY_THERE;

   if ( !IS_SAME_AREA( src, target ) )
     return TRACK_NO_PATH;

   /* clear marks first */
   for (curr_room = src->area->lvnum; curr_room <= src->area->uvnum;
	curr_room++)
     if ( get_room_index(curr_room) )
       UNMARK(get_room_index(curr_room));

   MARK(src);

   /* first, enqueue the first steps, saving which direction we're going. */
   for (curr_dir = 0; curr_dir < 6; curr_dir++)
      if (VALID_EDGE(src, curr_dir))
      {
         MARK(TOROOM(src, curr_dir));
         track_enqueue(TOROOM(src, curr_dir), curr_dir);
      }

   /* now, do the track. */
   while (queue_head)
   {
      if (queue_head->room == target)
      {
	 curr_dir = queue_head->dir;
	 track_clear_queue();
	 return curr_dir;
      }
      else
      {
	for (curr_dir = 0; curr_dir < 6; curr_dir++)
	  if (VALID_EDGE(queue_head->room, curr_dir))
	  {
	    MARK(TOROOM(queue_head->room, curr_dir));
	    track_enqueue(TOROOM(queue_head->room, curr_dir),queue_head->dir);
	  }
	track_dequeue();
      }
   }

   return TRACK_NO_PATH;
}


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

void do_track( CHAR_DATA *ch, char *argument )
{
   CHAR_DATA *vict;
   int dir;
   char arg[MAX_INPUT_LENGTH];
   char buf[MAX_STRING_LENGTH];

   one_argument(argument, arg);

    if ( !IS_NPC( ch )
        && !can_use_skpell( ch, gsn_track ) )
    {
        send_to_char(C_DEFAULT, "Huh?\n\r", ch );
        return;
    }

   if (!*arg)
   {
     if ( ch->hunting )
     {
       send_to_char(AT_RED, "No longer tracking.\n\r", ch );
       ch->hunting = NULL;
     }
     else
     {
       send_to_char(AT_BLUE, "Whom are you trying to track?\n\r", ch);
     }
     return;
   }

   if (!(vict = get_char_world(ch, arg)) || !IS_SAME_AREA(ch->in_room,
							  vict->in_room))
   {
      send_to_char(AT_BLUE, "You can't find them.\n\r", ch);
      return;
   }

   dir = find_first_step(ch->in_room, vict->in_room);

   switch(dir)
   {
      case TRACK_ERROR:
         send_to_char(AT_BLUE, "Hmm.. something seems to be wrong.\n\r", ch);
	 ch->hunting = NULL;
         break;
      case TRACK_ALREADY_THERE:
         send_to_char(AT_BLUE, "You're already in the same room!!\n\r", ch);
	 ch->hunting = NULL;
         break;
      case TRACK_NO_PATH:
         sprintf(buf, "You can't sense a trail to %s from here.\n\r",
		 vict->sex == SEX_FEMALE ? "her" :
		 vict->sex == SEX_MALE ? "him" : "it" );
         send_to_char(AT_BLUE, buf, ch);
	 ch->hunting = NULL;
         break;
      default:
         /* if you want to make this into a skill instead of a command,
            the next few lines make it give you a random direction if you
            fail the random skill roll.
         */

#ifdef TRACK_IS_SKILL
	 {
/*	   int counter;*/

	   if(!IS_NPC(ch) && ch->pcdata->learned[gsn_track] < number_percent())
	   {
	     int numv = 0;
	     CHAR_DATA *vch = NULL;

	     for ( vch = char_list; vch; vch = vch->next )
	     {
	       if ( vch->deleted || !IS_NPC(vch) || !can_see(ch, vch) ||
		    !IS_SAME_AREA(ch->in_room, vch->in_room) ||
		    (dir = find_first_step(ch->in_room, vch->in_room)) < 0 )
		 continue;
	       if ( number_range(0,numv) == 0 )
		 vict = vch;
	       numv++;
	     }
	     if ( !vict )
	     {
	       send_to_char(AT_BLUE, "You can't sense a trail from here.\n\r",ch);
	       return;
	     }
/*	     for( counter = 0; counter < 50; counter++ )
	     {
	       dir = number_door();
	       if ( can_go( ch, dir ) &&
		    IS_SAME_AREA(ch->in_room, ch->in_room->exit[dir]->to_room))
		 break;
	       dir = -1;
	     }
	     for ( vch = char_list; vch; vch = vch->next )
	     {
	       if ( vch->deleted || !IS_NPC(vch) )
		 continue;
	       if ( number_range(0,numv) == 0 )
		 vict = vch;
	       numv++;
	     }*/
	   }
	   else
	     update_skpell( ch, gsn_track );
	   if ( dir < 0 )
	   {
	     sprintf(buf, "You can't sense a trail to %s from here.\n\r",
		     vict->sex == SEX_FEMALE ? "her" :
		     vict->sex == SEX_MALE ? "him" : "it" );
	     send_to_char(AT_BLUE, buf, ch );
	     return;
	   }
	 }
#endif

	 if ( !IS_NPC(vict) )
	 {
	   sprintf(buf, "You sense a trail %s from here!\n\r", dir_name[dir]);
	   send_to_char(AT_RED, buf, ch);
	 }
	 else
	   ch->hunting = vict;
         break;
   }
}


void hunt_victim(CHAR_DATA *ch)
{
   int dir;
/*   int found;
   CHAR_DATA *tmp;*/
   char buf[MAX_STRING_LENGTH];

   if (!ch || ch->fighting || !ch->hunting)
      return;

   /* make sure the char still exists */
/*   for (found = FALSE, tmp = char_list; tmp && !found; tmp = tmp->next)
   {
     if ( tmp->deleted )
       continue;
     if (ch->hunting == tmp)
       found = 1;
   }*/


   if (/*!found ||*/ !can_see(ch, ch->hunting))
   {
     if ( IS_NPC(ch) )
       do_say(ch, "Damn!  My prey is gone!!");
     else if ( ch->desc )
       write_to_buffer(ch->desc, "&rTrack1: &RYou have lost the trail.\n\r",0);
     ch->hunting = NULL;
     return;
   }

   dir = find_first_step(ch->in_room, ch->hunting->in_room);
   if (dir < 0)
   {
     if ( IS_NPC( ch ) )
     {
       sprintf(buf, "Damn!  Lost %s!", ch->hunting->sex == SEX_FEMALE
	       ? "her" : ch->hunting->sex == SEX_MALE ? "him" : "it" );
       do_say(ch, buf);
     }
     else if ( ch->desc )
     {
       if ( dir == TRACK_ALREADY_THERE )
	 write_to_buffer(ch->desc,
			 "\n\r&rTrack: &RAhh.. You have found your prey.",0);
       else
	 write_to_buffer(ch->desc, "\n\r&rTrack2: &RYou have lost the trail.",
			 0);
     }
     ch->hunting = NULL;
     return;
   }
   else
   {
     if ( IS_NPC( ch ) )
     {
       move_char(ch, dir, FALSE);
       sprintf( log_buf, "%s hunting %s at %d.", ch->short_descr,
	      ( IS_NPC( ch->hunting ) ) ? ch->hunting->short_descr : 
	        ch->hunting->name, ch->hunting->in_room->vnum );
       log_string( log_buf, 1 , -1 );
     }
     else
     {
       sprintf(log_buf,"\n\r&rTrack: &RYou sense a trail %s of here!",
	       dir_name[dir]);
       write_to_buffer(ch->desc, log_buf, 0);
     }
      if (ch->in_room == ch->hunting->in_room)
      {
	if ( IS_NPC( ch ) )
	{
	  do_say(ch, "Now i've got you!");
	  multi_hit(ch, ch->hunting, TYPE_UNDEFINED);
	}
	else if ( ch->desc )
	  write_to_buffer(ch->desc,
			  "\n\r&rTrack: &RAhh.. you have found your prey.",0);
	ch->hunting = NULL;
      }	 
      return;
   }
}