typedef struct bfs_queue_struct BFS_DATA;
struct bfs_queue_struct
{
	ROOM_INDEX_DATA *room;
	char dir;
	int num;
	BFS_DATA *next;
};
static BFS_DATA *queue_head = NULL, *queue_tail = NULL, *room_queue = NULL;

/* Utility macros */
#define MARK(room)		( SET_BIT( (room)->room_flags_3, BFS_MARK ) )
#define UNMARK(room)	( REMOVE_BIT( (room)->room_flags_3, BFS_MARK ) )
#define IS_MARKED(room)	( IS_SET( (room)->room_flags_3, BFS_MARK ) )

#define BFS_ERROR			-1
#define BFS_ALREADY_THERE	-2
#define BFS_NO_PATH			-3

bool valid_edge( EXIT_DATA *pexit )
{
	if( pexit->to_room && !IS_MARKED( pexit->to_room ) )
		return TRUE;
	else
		return FALSE;
}

void bfs_enqueue( ROOM_INDEX_DATA * room, char dir )
{
	BFS_DATA *curr;

	curr = ( BFS_DATA * ) malloc( sizeof( BFS_DATA ) );
	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 bfs_dequeue( void )
{
	BFS_DATA *curr;

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


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

void room_enqueue( ROOM_INDEX_DATA *room )
{
	BFS_DATA *curr;

	curr = ( BFS_DATA * ) malloc( sizeof( BFS_DATA ) );
	curr->room = room;
	curr->next = room_queue;

	room_queue = curr;
}

void clean_room_queue( void )
{
	BFS_DATA *curr, *curr_next;

	for( curr = room_queue; curr; curr = curr_next )
	{
		UNMARK( curr->room );
		curr_next = curr->next;
		free( curr );
	}
	room_queue = NULL;
}

const char *const	short_dir_name[] =
{
    "n", "e", "s", "w", "u", "d"
};

int find_first_step( ROOM_INDEX_DATA *src, ROOM_INDEX_DATA *target, int maxdist, bool bBetweenAreas )
{
	int curr_dir, count, dir;
	EXIT_DATA *pexit;

	if( !src || !target )
	{
		BUG( "Src o target NULL" );
		return BFS_ERROR;
	}

	if( src == target )
		return BFS_ALREADY_THERE;

	if( !bBetweenAreas && src->area != target->area )
		return BFS_NO_PATH;

	room_enqueue( src );
	MARK( src );

	// first, enqueue the first steps, saving which direction we're going. 
	for( dir = 0; dir < MAX_DIR; dir++ )
	{
		pexit = src->exit[dir];
		if( exit_ok( pexit ) )
			if( valid_edge( pexit ) )
			{
				curr_dir = dir;
				MARK( pexit->to_room );
				room_enqueue( pexit->to_room );
				bfs_enqueue( pexit->to_room, curr_dir );
			}
	}
	count = 0;
	while( queue_head )
	{
		if( ++count > maxdist )
		{
			bfs_clear_queue(  );
			clean_room_queue(  );
			return BFS_NO_PATH;
		}
		if( queue_head->room == target )
		{
			curr_dir = queue_head->dir;
			bfs_clear_queue(  );
			clean_room_queue(  );
			return curr_dir;
		}
		else
		{
			for( dir = 0; dir < MAX_DIR; dir++ )
			{
				pexit = queue_head->room->exit[dir];
				if( exit_ok( pexit ) )
					if( valid_edge( pexit ) )
					{
						curr_dir = dir;
						MARK( pexit->to_room );
						room_enqueue( pexit->to_room );
						bfs_enqueue( pexit->to_room, queue_head->dir );
					}
			}
			bfs_dequeue(  );
		}
	}
	clean_room_queue(  );

	return BFS_NO_PATH;
}


char *get_path_string( ROOM_INDEX_DATA *start, ROOM_INDEX_DATA *dest, bool path, bool count )
{
	static char buf[MSL * 2];
	char temp[MSL];
	int last_dir = -1;
	int dircount = 0; // used to count how many times we move in the same direction
	ROOM_INDEX_DATA *curr_room = NULL; // room we're currently checking from
	EXIT_DATA *pExit = NULL; // used to get curr_room
	int dir = -1; // What direction we're moving next
	int totalcount = 0;
	bool done = FALSE;

	buf[0] = '\0';
	//Couple of checks
	if( !start )
	{
		BUG( "Room de inicio NULL" );
		return NULL;
	}
	if( !dest )
	{
		BUG( "Room de destino NULL" );
		return NULL;
	}

	curr_room = start;
	// Start our big loop here
	while( !done )
	{
		
		// If there's ever a problem with finding a path to a place
		// that can be walked to on the mud, can increase the distance
		// here I suppose
		dir = find_first_step( curr_room, dest, 1000000, TRUE );
		switch( dir )
		{

			case BFS_ERROR:
				BUG( "Error buscando path" );
				return NULL;
			case BFS_ALREADY_THERE:
				done = TRUE;
				break;
			case BFS_NO_PATH:
				return NULL;
			default:
				break;
		}
		
		if( !done )
		{
			pExit = curr_room->exit[dir];
			curr_room = pExit->to_room;

			//Keep track of how many times we go the same direction so we can do output
			//like 3E, 2S, N, W, 5E etc.
			if( last_dir == -1 )
			{
				dircount = 1;
				last_dir = dir;
			}
			else 
			{
				if( dir != last_dir )
				{
					totalcount += dircount;
					if( dircount > 1 )
						SCOPY( temp, "%d%s, ", dircount, short_dir_name[last_dir] );
					else
						SCOPY( temp, "%s, ", short_dir_name[last_dir] );

					strcat( buf, temp );
					last_dir = dir;
					dircount = 1;
				}
				else
					++dircount;
			}

			if( curr_room->vnum == dest->vnum )
			{
				totalcount += dircount;
				if( dircount > 1 )
					SCOPY( temp, "%d%s.", dircount, short_dir_name[dir] );
				else
					SCOPY( temp, "%s.", short_dir_name[dir] );
				strcat( buf, temp );
			}
		}
	}
	if( !path && !count )
		SCOPY( buf, "Hay %d rooms entre esas dos.", totalcount );
	if( count )
		SCOPY( buf, "%d", totalcount );
	return buf;
}