/////////////////////////////////////////////////////////////////////////////////
/// dynamic mapping, node list functions
/////////////////////////////////////////////////////////////////////////////////

//#include <windows.h>
#include <stdio.h>

#include	"world.h"
#include	"nodelist.h"
#include	"skat.h"

//////////////////////////////////////////////////////////////////////////////////
//	defines
//////////////////////////////////////////////////////////////////////////////////

//#define DllExport	extern "C"	__declspec( dllexport )

//DllExport	void	node_node (userEntity_t *self);

//////////////////////////////////////////////////////////////////////////////////
//	defines
//////////////////////////////////////////////////////////////////////////////////

// maximum allowable distance between nodes
#define		MAX_NODE_DIST	256.0

//////////////////////////////////////////////////////////////////////////////////
//	globals
//////////////////////////////////////////////////////////////////////////////////

userEntity_t	*node_viewer;	//	the entity whose node use is being tracked by
								//	changing models to node, cur_node, and lastnode
mapHeader_t		*client_nodes;	

static	int				counter	[512];  
static	unsigned char	flag	[512];  
static	int				show_nodes;

int		nodes_in_map;

//*******************************************************************************
//	debugging functions 
//*******************************************************************************

///////////////////////////////////
//	node_set_viewer
///////////////////////////////////

void	node_set_viewer (userEntity_t *self)
{
	node_viewer = self;
}

///////////////////////////////////
//	node_remove_marker
///////////////////////////////////

void	node_remove_marker (userEntity_t *self)
{
	gstate->RemoveEntity (self);
}

///////////////////////////////////
//	node_marker_think
///////////////////////////////////

void	node_marker_think (userEntity_t *marker)
{
	if (marker->s.render_scale [0] > 2.0)
		marker->delay = 0.95;
	else if (marker->s.render_scale [0] < 0.5)
		marker->delay = 1.05;

	com->MultVector (marker->s.render_scale, marker->delay, marker->s.render_scale);

	marker->think = node_marker_think;
	marker->nextthink = gstate->time + 0.1;
}

///////////////////////////////////
//	node_set_marker
///////////////////////////////////

void	node_set_marker (userEntity_t *viewer, mapNode_t *node, char *model)
{
	if (viewer != node_viewer || !show_nodes)
		return;

	if (node)
		if (node->marker)
		{
			node->marker->s.modelindex = gstate->ModelIndex (model);
		}
}

///////////////////////////////////
//	node_marker
///////////////////////////////////

void	node_marker (mapNode_t *node)
{
	userEntity_t	*temp;

	if (node->marker || !show_nodes)
		return;

	node->marker = temp = gstate->SpawnEntity ();

	temp->s.modelindex = gstate->ModelIndex ("models/debug/node/node.md2");
	gstate->SetSize (temp, 0, 0, 0, 0, 0, 0);
	gstate->SetOrigin2 (temp, node->origin);

	temp->solid = SOLID_NOT;
	temp->movetype = MOVETYPE_FLY;
	temp->className = (char *) com->malloc (256, MEM_MALLOC);
	sprintf (temp->className , "node %i", node->number);
	
	com->SetVector (temp->s.render_scale, 1.0, 1.0, 1.0);
	com->SetVector (temp->avelocity, 90, 90, 90);

	temp->delay = 1.05;

	temp->think = node_marker_think;
	temp->nextthink = gstate->time + rnd () * 0.25;
}

/////////////////////////////
//	node_show_links
//
/////////////////////////////

void	node_show_links	(userEntity_t *self)
{
	userEntity_t	*temp;
	mapNode_t		*cur_node, *head;
	playerHook_t	*hook;// = (playerHook_t *) self->input_entity->userHook;
	int				i, j;
	Vector			vel, forward, org;

	if (!show_nodes)
		return;

	if (self->input_entity)
		hook = (playerHook_t *) self->input_entity->userHook;
	else
		hook = (playerHook_t *) self->userHook;

	cur_node = hook->node_list->cur_node;
/*
	// set all markers to cubes
	head = hook->node_list->header->head;
	while (head)
	{
		node_set_marker (self->input_entity, head, "models/debug/node/node.md2");
		head = head->next_node;
	}
*/
	i = 0;
	while (cur_node->link [i])
		i++;

//	node_set_marker (self, cur_node, "models/debug/curnode/curnode.md2");

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (cur_node->link [i])
		{
			//	Q2FIXME:	change to Q2 network functions
			/*
			gstate->WriteByte (self, MSG_BROADCAST, SVC_TEMPENTITY);
			gstate->WriteByte (self, MSG_BROADCAST, TE_LASER);

			// send the target entity for this temporary entity
			gstate->WriteEntity (self, MSG_BROADCAST, cur_node->marker);

			gstate->WriteCoord (self, MSG_BROADCAST, cur_node->origin [0]);
			gstate->WriteCoord (self, MSG_BROADCAST, cur_node->origin [1]);
			gstate->WriteCoord (self, MSG_BROADCAST, cur_node->origin [2]);
	
			gstate->WriteCoord (self, MSG_BROADCAST, cur_node->link [i]->s.origin [0]);
			gstate->WriteCoord (self, MSG_BROADCAST, cur_node->link [i]->s.origin [1]);
			gstate->WriteCoord (self, MSG_BROADCAST, cur_node->link [i]->s.origin [2]);

			gstate->WriteEntity (self, MSG_BROADCAST, cur_node->link [i]->marker);
			*/

			// determine if the linked-to node has a node back.  If it does, then
			// draw it
			for (j = 0; j < MAX_NODE_LINKS; j++)
			{
				if (cur_node->link [i]->link [j] == cur_node)
				{
					forward = Vector (cur_node->link [i]->marker->s.origin) - Vector (cur_node->marker->s.origin);
					com->VecToAngles (vel, forward);
					vel.AngleVectors (forward, right, up);

					//	Q2FIXME:	change to Q2 network functions
					/*
					gstate->WriteByte (self, MSG_BROADCAST, SVC_TEMPENTITY);
					gstate->WriteByte (self, MSG_BROADCAST, TE_LINKFROM);

					// send the target entity for this temporary entity
					gstate->WriteEntity (self, MSG_BROADCAST, cur_node->link [i]->marker);

					org = Vector (cur_node->link [i]->s.origin) - up * 8.0;
					gstate->WriteCoord (self, MSG_BROADCAST, org.x);
					gstate->WriteCoord (self, MSG_BROADCAST, org.y);
					gstate->WriteCoord (self, MSG_BROADCAST, org.z);

					org = Vector (cur_node->origin) - up * 8.0;
					gstate->WriteCoord (self, MSG_BROADCAST, org.x);
					gstate->WriteCoord (self, MSG_BROADCAST, org.y);
					gstate->WriteCoord (self, MSG_BROADCAST, org.z);

					gstate->WriteEntity (self, MSG_BROADCAST, cur_node->marker);
					*/
				}
			}
		}
	}
}

//////////////////////////////////
//	node_toggle_nodes 
//////////////////////////////////

void	node_toggle_nodes	(userEntity_t *self)	
{
	playerHook_t	*hook = (playerHook_t *) self->userHook;
	mapList_t		*node_list = hook->node_list;
	mapNode_t		*cur_node, *head;

	cur_node = hook->node_list->header->head;

	if (show_nodes)
		show_nodes = FALSE;
	else 
		show_nodes = TRUE;

	while (cur_node)
	{
		// remove marker
		if (cur_node->marker)
		{	
			gstate->RemoveEntity (cur_node->marker);
			cur_node->marker = NULL;
		}

		// if showing nodes, make marker visible
		if (show_nodes)
			node_marker (cur_node);

		cur_node = cur_node->next_node;
	}

	node_set_marker (self, node_list->cur_node, "models/debug/curnode/curnode.md2");
	node_set_marker (self, node_list->last_node, "models/debug/lastnode/lastnode.md2");

	node_show_links (self);
}

//*******************************************************************************
//	node list management functions 
//*******************************************************************************

////////////////////////////////
//	node_create_header
//
//	creates a new header to a list of nodes
////////////////////////////////

mapHeader_t	*node_create_header (void)
{
	mapHeader_t	*map_header;

	map_header = (mapHeader_t *) com->malloc (sizeof (mapHeader_t), MEM_MALLOC); 
	
	map_header->head = NULL;
	map_header->node_count = 0;

	return	map_header;
}


////////////////////////////////
//  node_create_nodelist
//
//	creates a new list pointing to header
//
//	one of these is created for each entity
//	who needs to follow the nodes in the list
//	pointed to by a header
////////////////////////////////

mapList_t	*node_create_nodelist (mapHeader_t *header)
{
	mapList_t	*new_list;

	new_list = (mapList_t *) com->malloc (sizeof (mapList_t), MEM_MALLOC);

	new_list->header = header;
	new_list->cur_node = NULL;
	new_list->last_node = NULL;

	return	new_list;
}

///////////////////////////////
//	node_delete_nodelist
//
//	creates a new list pointing to header
///////////////////////////////

void	node_delete_nodelist (mapHeader_t **header)
{
	mapNode_t	*node, *next;
	mapHeader_t	*h;

	h = * header;
	node = h->head;

	while (node)
	{
		next = node->next_node;
		if (node->marker)
			gstate->RemoveEntity (node->marker);
		com->free (node);
		node = next;
	}

	com->free (*header);
	*header = NULL;
}

////////////////////////////////
//	node_create_node
//
//	mallocs up a new node and places it in the list
////////////////////////////////

mapNode_t	*node_create_node (mapHeader_t **header)
{
	mapNode_t	*new_node, *head;

	//	malloc memory for node
	new_node = (mapNode_t *) com->malloc (sizeof (mapNode_t), MEM_MALLOC);
	//	set all times to 0
	memset (new_node, 0x00, sizeof (mapNode_t));

	//	malloc memory for time stamps
	new_node->node_time = (nodeTime_t *) com->malloc (sizeof (nodeTime_t), MEM_MALLOC);
	memset (new_node->node_time, 0x00, sizeof (nodeTime_t));

	if (!new_node)
	{
		gstate->Con_Dprintf ("node_create_node: malloc failed\n");
		return	NULL;
	}

	head = (*header)->head;

	if (head)
	{
		// go to the end of the list
		while (head->next_node)
			head = head->next_node;

		head->next_node = new_node;
	}
	// first node in this list
	else
		(*header)->head = new_node;

	(*header)->node_count++;
	
	new_node->number = (*header)->node_count;

	return	new_node;
}

////////////////////////////////
//	node_add_node
//
//	adds a node to node_list.
////////////////////////////////

mapNode_t	*node_add_node (userEntity_t *self, mapList_t *node_list, vec3_t org, mapNode_t *last_node)
{
	mapNode_t	*new_node, *head;

/*
	new_node = (mapNode_t *) com->malloc (sizeof (mapNode_t), MEM_MALLOC);
	memset (new_node, 0x00, sizeof (mapNode_t));

	if (!new_node)
	{
		gstate->Con_Dprintf ("node_add_node: malloc failed\n");
		//gstate->ServerCmd ("pause\n");
		return NULL;
	}

	head = node_list->header->head;

	if (head)
	{
		while (head->next_node)
			head = head->next_node;

		head->next_node = new_node;
	}
	// first node in this list
	else
		node_list->header->head = new_node;

	node_list->header->node_count++;
*/

	if (!(new_node = node_create_node (&node_list->header)))
		return	NULL;

	new_node->origin [0] = org [0];
	new_node->origin [1] = org [1];
	new_node->origin [2] = org [2];
	new_node->next_node = NULL;
	new_node->number = node_list->header->node_count;

	// set up a link from the last node to this node
	if (last_node)
	{
		if (qv_dist (last_node->origin, new_node->origin) > MAX_NODE_DIST)
			//	assume teleported, fell, something odd
			node_link_node (last_node, new_node);
		else 
			node_link_nodes (self, last_node, new_node);
	}

	node_marker (new_node);

	return	new_node;
}

///////////////////////////////////////
//	node_find_node
//
//	returns the closest node within dist units of origin
//	that is of the same node_type as type
//
///////////////////////////////////////

mapNode_t	*node_find_node (mapList_t *node_list, vec3_t org, float dist, int type)
{
	mapNode_t	*head;
	float		head_dist, max_dist;

	max_dist = dist;

	for (head = node_list->header->head; head; head = head->next_node)
	{
		if (head->node_type == type)
		{
			head_dist = qv_dist (head->origin, org);
			
			if (head_dist <= dist)
				return	head;
		}
	}

	return	NULL;
}

//*******************************************************************************
//	node list building functions 
//*******************************************************************************

///////////////////////////////////
//	node_visible
//
//	trace a line from self->s.origin to node->origin to determine
//	if there is anything blocking the view of this node  
///////////////////////////////////

int		node_visible (userEntity_t *ignore, vec3_t start, vec3_t end)
{
	//userTrace_t	trace;

	gstate->TraceLine (start, end, TRUE, ignore, &trace);
	
	if (trace.fraction == 1.0)
		return TRUE;
	else
		return FALSE;
}

///////////////////////////////////
//	node_link_node
//
//	links node1 to node2 in one direction only
///////////////////////////////////

void	node_link_node (mapNode_t *node1, mapNode_t *node2)
{
	int		i;

	if (node1 == node2)
		gstate->Con_Dprintf ("node_link_node: node linked to itself!\n");

	if (!node1)
	{
		gstate->Con_Dprintf ("node_link_node:  node1 is NULL\n");
		return;
	}

	if (!node2)
	{
		gstate->Con_Dprintf ("node_link_node:  node2 is NULL\n");
		return;
	}

	// determine if we have already linked to this node
	// previously
	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (node1->link [i])
		{
			if (node2 == node1->link [i])
			{
				//gstate->Con_Dprintf ("node_link_node: nodes already linked.\n");
				return;
			}
		}
	}

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (node1->link [i] == NULL)
			break;
	}

	// did we find an empty link?
	if (i < MAX_NODE_LINKS)
		node1->link [i] = node2;
//	else
//		gstate->Con_Dprintf ("node_link_node: Out of links!  Path lost!\n");
}

///////////////////////////////////
//	node_link_nodes
//
//	links node1 to node2 in both directions
///////////////////////////////////

void	node_link_nodes (userEntity_t *self, mapNode_t *node1, mapNode_t *node2)
{
	playerHook_t	*hook = (playerHook_t *) self->userHook;
	int				i;

	if (node1 == node2)
		gstate->Con_Dprintf ("node_link_nodes: node linked to itself!\n");

	// don't link nodes after a fall
	if (fabs (node1->origin [2] - node2->origin [2]) > 96.0)
		return;

	// determine if we have already linked to this node
	// previously
	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (node2 == node1->link [i])
		{
			//gstate->Con_Dprintf ("node_link_node: nodes already linked.\n");
			return;
		}
	}

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (node1->link [i] == NULL)
			break;
	}

	// did we find an empty link?
	if (i < MAX_NODE_LINKS)
		node1->link [i] = node2;
	else
		gstate->Con_Dprintf ("node_link_nodes: Out of links!  Path lost!\n");

	// only link back to last node if the player jumped or
	// did not leave the ground
//	if ((hook->off_ground && hook->jumped) || (!hook->off_ground && !hook->jumped))
		node_link_node (node2, node1);

	// reset flags
	hook->off_ground = FALSE;
	hook->jumped = FALSE;
}

///////////////////////////////////
//	node_is_linked
//
//	returns true if this node has any other links from it
///////////////////////////////////

int			node_is_linked (mapNode_t *node)
{
	int			i;

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (node->link [i])
			return TRUE;
	}

	return FALSE;
}

///////////////////////////////////
//	node_log_items
//
//	searches around current node for items and records their location
//	in self's skat list
///////////////////////////////////

void	node_log_items	(userEntity_t *self, mapList_t *node_list)
{
	userEntity_t	*item;
	playerHook_t	*hook = (playerHook_t *) self->userHook;

//	return;

	//	FIXME: make search item_list instead of entire entity list
	item = gstate->FirstEntity ();

	while (item)
	{
		if (item->flags & FL_ITEM)
		{
			if (node_visible (self, node_list->cur_node->origin, item->s.origin))
				hook->skat_list = skat_add_item (hook->skat_list, node_list->cur_node, item, qv_dist (node_list->cur_node->origin, item->s.origin));
		}

		item = gstate->NextEntity (item);
	}
}

///////////////////////////////////
//	node_stamp_time
//
///////////////////////////////////

void	node_stamp_time (userEntity_t *self, mapNode_t *node)
{
	playerHook_t	*hook = (playerHook_t *) self->userHook;
	nodeTime_t		*node_time;
	float			id, oldest_time;
	int				i, oldest;

	if (!(self->flags & (FL_CLIENT + FL_BOT)))
		return;

	node_time = node->node_time;

	//	determine if we've already got a stamp here for this entity
	for (i = 0; i < node_time->num_stamps; i++)
	{
		if (hook->ID == node_time->ID_stamp [i])
			break;
	}

	if (i < node_time->num_stamps)
	{
		//	found this ID, so replace time
		node_time->time_stamp [i] = gstate->time;
	}
	else if (i >= MAX_TIME_STAMPS)
	{
		//	filled up all our time stamps here, so
		//	find oldest time and replace it

		oldest_time = gstate->time;
		oldest = MAX_TIME_STAMPS;

		for (i = 0; i < MAX_TIME_STAMPS; i++)
		{
			if (node_time->time_stamp [i] < oldest_time)
			{
				oldest = i;
				oldest_time = node_time->time_stamp [i];
			}
		}
	}
	else
	{
		//	add a new stamp here
		node_time->num_stamps++;
		node_time->time_stamp [i] = gstate->time;
		node_time->ID_stamp [i] = hook->ID;
	}
}

///////////////////////////////////
//	node_place_spawn_node
//
//	places a node at a spawn position if there is no other node
//	visible from self's current location.  Otherwise, the visible
//	node is considered the current node.
///////////////////////////////////

void	node_place_spawn_node (userEntity_t *self, mapList_t *node_list)
{
	mapNode_t	*head, *the_one_and_only_matching_node_fool;
	float		dist, last_dist;
	vec3_t		temp;
	int			count;

	last_dist = 1000;
	// search for a node visible from self->s.origin
	head = node_list->header->head;	
	node_list->cur_node = node_list->last_node = NULL;
	the_one_and_only_matching_node_fool = NULL;
	count = 0;

	// search the entire list and find the very very very mostest close node to the spawn point
	while (head && node_list->header->node_count > 0)
	{
		dist = qv_dist (self->s.origin, head->origin);

		if (dist < last_dist)
		{
			if (node_visible (self, head->origin, self->s.origin))
			{
				the_one_and_only_matching_node_fool = head;
				last_dist = dist;
			}
		}

		head = head->next_node;
		count++;
	}

	if (the_one_and_only_matching_node_fool)
	{
//		node_list->last_node = node_list->cur_node;
		node_list->last_node = NULL;
		node_list->cur_node = the_one_and_only_matching_node_fool;
	}
	else
	{
		head = node_add_node (self, node_list, self->s.origin, NULL);
		node_list->last_node = NULL;
		node_list->cur_node = head;
	}

	node_log_items (self, node_list);

	//	put this entities time_stamp here
	node_stamp_time (self, node_list->cur_node);
}

/////////////////////////////
//	node_find_cur_node
//
/////////////////////////////

int	node_find_cur_node (userEntity_t *self, mapList_t *node_list)
{
	playerHook_t	*hook = (playerHook_t *) self->userHook;
	mapNode_t		*head, *cur_node;
	float			dist, min_dist, max_dist;
	Vector			temp;
	vec3_t			origin;

	if (self->movetype == MOVETYPE_FLY)
	{
		//	flying things don't leave their own nodes, so check for closest
		//	node from a point 24 units above the ground

		hook->ground_org.set (origin);
	}
	else
		com->CopyVector (origin, self->s.origin);

	head = node_list->header->head;

	max_dist = min_dist = MAX_NODE_DIST;

	cur_node = NULL;

	while (head)
	{
		//	never choose a NODE_TELEPORTER as the current node!
		if (head->node_type != NODE_TELEPORTER)
		{
			dist = qv_dist (origin, head->origin);
			
			if (dist < min_dist)
			{
				// is this node is nearly the same height as our current node?
				if (fabs (origin [2] - head->origin [2]) < 48.0)
				{
					// can this node see the entity who is checking it?
					gstate->TraceLine (origin, head->origin, TRUE, self, &trace);

					if (trace.fraction == 1.0)
					{
		/*
						// can the new node see our current node?
						gstate->TraceLine (node_list->cur_node->origin, head->s.origin, TRUE, self, &trace);

						if (trace.fraction == 1.0)
						{
		*/
							cur_node = head;
							min_dist = dist;
		//					}
					}
				}
			}
			else if (dist == min_dist)
				cur_node = head;
		}

		head = head->next_node;
	}

	// was a visible node found that is < MAX_NODE_DIST away or closer than our current node?  
	// if so, make it the cur_node
	if (cur_node != NULL)
	{
		if (cur_node != node_list->cur_node)
		{
			//	put this entities time_stamp on the node they're leaving
			node_stamp_time (self, node_list->cur_node);

			//	put this entities time_stamp on the new node
			node_stamp_time (self, cur_node);

			node_set_marker (self, node_list->last_node, "models/debug/node/node.md2");
	
			node_list->last_node = node_list->cur_node;
			node_list->cur_node = cur_node;

			node_link_nodes (self, node_list->last_node, node_list->cur_node);
		
			node_set_marker (self, node_list->cur_node, "models/debug/curnode/curnode.md2");
			node_set_marker (self, node_list->last_node, "models/debug/lastnode/lastnode.md2");
		}

		return	TRUE;
	}
	else
		return	FALSE;
}

//////////////////////////////////////////////////////////////////////
//	node_place_node
//
//	This is the major function called from player/bot routines.
//	It places a node at self's last location if:
//	
//	1) the last node is not visible from self's origin 
//	2) there is no other node which is visible from this spot
//	which also can see the last node
//
//	if a node is placed or linked, then that node is returned.
//	otherwise NULL is returned
//
//	the code that calls node_place_node must update the cur_node and
//	last_node variable accordingly.  This is because bots and players
//	will be using different hook types, so we won't necessarily know
//	which type of hook self is using here, so we don't want to update
//	it.
//////////////////////////////////////////////////////////////////////

void	node_place_node (userEntity_t *self, mapList_t *node_list, vec3_t last_loc)
{
	mapNode_t		*head;
	Vector			temp;
	int				pc, found_node, i;
	float			dist;
	playerHook_t	*hook = (playerHook_t *) self->userHook;

	if (self->flags & FL_DEBUG)
		node_show_links (self);

	if (self->movetype == MOVETYPE_NOCLIP)
		return;

	// did bot move a significant distance?
	temp = hook->last_origin - Vector (self->s.origin);
	if (temp.vlen () < 4.0)
		return;

	if (self->movetype == MOVETYPE_FLY)
	{
		node_find_cur_node (self, node_list);
		return;
	}

	pc = gstate->PointContents (self->s.origin);
	// if entity is falling do not place a node
	if (!((int)self->flags & FL_ONGROUND) && (self->velocity [2] != 0.0) && (pc != CONTENTS_WATER))
		return;

	if (self->groundEntity)
		if (qv_len (self->groundEntity->velocity) != 0.0)
			return;

	//	FIXME: adjust for teleporting
	//	we need a new node!!  Make cur_node the closest visible map node
	if (node_find_cur_node (self, node_list))
	{
		// an existing, visible node was found that is < MAX_NODE_DIST away, so return
		return;
	}

	// no existing node was found that fits the criteria, so make one
	head = node_add_node (self, node_list, last_loc, node_list->cur_node);

	node_set_marker (self, node_list->last_node, "models/debug/node/node.md2");

	node_list->last_node = node_list->cur_node;
	node_list->cur_node = head;

	node_set_marker (self, node_list->cur_node, "models/debug/curnode/curnode.md2");
	node_set_marker (self, node_list->last_node, "models/debug/lastnode/lastnode.md2");

	//	make a list of the items that are available at this node
	node_log_items (self, node_list);

	//	put this entities time_stamp here
	node_stamp_time (self, node_list->cur_node);
}

/////////////////////////////////////////////
//	node_force_node
//
//	forces a node to be placed at self->s.origin
//
//	used to place rocket jump and teleport nodes
//
//	data must be a MEM_MALLOC block
//	if a node already exists here, then data is freed
/////////////////////////////////////////////

void	node_force_node (userEntity_t *self, mapList_t *node_list, vec3_t origin, int type, void *data)
{
	mapNode_t		*head;
	Vector			temp;
	int				pc, found_node;
	float			dist;
	playerHook_t	*hook = (playerHook_t *) self->userHook;

	//	make sure there is not already a node here
	head = node_find_node (node_list, origin, 0, type);

	if (head)
	{
		//	already a node here, so free data
		if (data)
			com->free (data);
	}
	else
		// no existing node was found that fits the criteria, so make one
		head = node_add_node (self, node_list, origin, node_list->cur_node);

	node_set_marker (self, node_list->last_node, "models/debug/node/node.md2");

	node_list->last_node = node_list->cur_node;
	node_list->cur_node = head;

	node_set_marker (self, node_list->cur_node, "models/debug/curnode/curnode.md2");
	node_set_marker (self, node_list->last_node, "models/debug/lastnode/lastnode.md2");

	//	make a list of the items that are available at this node
	node_log_items (self, node_list);

	node_list->cur_node->node_data = data;
	node_list->cur_node->node_type = type;
}

/////////////////////////////////////////////
//	node_move_node
//
//	moves cur_node to self->s.origin
/////////////////////////////////////////////

void	node_move_node (userEntity_t *self, mapNode_t *cur_node)
{
	com->CopyVector (cur_node->origin, self->s.origin);
}

//*******************************************************************************
//	path finding functions
//*******************************************************************************

//////////////////////////////////
//	path_last_node
//
//	returns the last node in a path
//////////////////////////////////

pathNode_t	*path_last_node (pathNode_t *path)
{
	pathNode_t	*head;

	head = path;

	while (head && head->next_node)
		head = head->next_node;

	return head;
}

//////////////////////////////////
//	path_add_node
//
//	adds a node to the beginning of a path
//
//	a path is a list of nodes that each point to a map_node
//////////////////////////////////

pathNode_t	*path_add_node (pathNode_t *path, mapNode_t *map_node)
{
	pathNode_t	*last_node, *new_node;

	if (path == NULL)
	{
		// set up first path node
		// we are using malloc because these nodes have to
		// be deallocated each time a new path is formed
//		gstate->Con_Dprintf ("creating path: malloced %i bytes\n", sizeof (pathNode_t));
		path = (pathNode_t *) com->malloc (sizeof (pathNode_t), MEM_MALLOC);
		path->map_node = map_node;
		path->next_node = NULL;

		return	path;
	}

	// append a path node
//	gstate->Con_Dprintf ("appending path: malloced %i bytes\n", sizeof (pathNode_t));
	new_node = (pathNode_t *) com->malloc (sizeof (pathNode_t), MEM_MALLOC);
	new_node->map_node = map_node;
	new_node->next_node = path;

	path = new_node;

	return	path;
}

//////////////////////////////////
//	path_delete_first
//
//	deletes and deallocates the first node in a path list
//////////////////////////////////

pathNode_t	*path_delete_first (pathNode_t *path)
{
	pathNode_t	*temp;

	if (path)
	{
		temp = path->next_node;
		com->free (path);
		return	temp;
	}

	return	NULL;
}

//////////////////////////////////
//	path_kill
//
//	deletes and deallocates an entire path
//////////////////////////////////

pathNode_t	*path_kill (pathNode_t *path)
{
	pathNode_t	*temp;

	while (path)
	{
		temp = path->next_node;
		com->free (path);		
		path = temp;
	}

	return	path;
}

//////////////////////////////////
//	path_update_to_node
//
//	determines if node is contained in path and if it is
//	it removes all path nodes prior to it in the list
//////////////////////////////////

pathNode_t	*path_update_to_node (pathNode_t *path, mapNode_t *node)
{
	pathNode_t	*head;
	int			in_path;

	in_path = FALSE;
	head = path;
	
	while (head)
	{
		if (head->map_node == node)
		{
			in_path = TRUE;
			break;
		}

		head = head->next_node;
	}

	// we found node in the path list, so delete every node up to it
	if (in_path)
	{
		while (path->map_node != node)
			path = path_delete_first (path);
	}

	return path;
}

//////////////////////////////////
//	path_shortest
//
//	finds the shortest path from start_node to end_node and returns
//	a pointer to a path list
//////////////////////////////////

pathNode_t	*path_shortest (userEntity_t *self, mapList_t *node_list, mapNode_t *start_node, mapNode_t *end_node, int	&path_length)
{
	int				count, i, high_count, is_linked;
	mapNode_t		*head, *high_link, *temp;
	pathNode_t		*path;
	playerHook_t	*hook = (playerHook_t *) self->userHook;

//	return	NULL;
	
	if (hook->path_time > gstate->time)
		return	NULL;

//	gstate->Con_Dprintf ("%s in path_shortest.\n", self->className);

	hook->path_time = gstate->time + 2.5 * rnd () * 3.0;

	// reset all markers to heads
	head = node_list->header->head;
	while (head)
	{
		node_set_marker (self, head, "models/debug/node/node.md2");

		head = head->next_node;
	}

	// zero the counters for each node
	memset (&counter, 0x00, sizeof (counter));

	counter [start_node->number] = 1;
	count = 0;

	while (counter [end_node->number] == 0 && count <= node_list->header->node_count)
	{
		head = node_list->header->head;
	
		memset (&flag, 0x00, sizeof (flag));		

		while (head)
		{
			if (counter [head->number] > 0 && flag [head->number] == 0)
			{
				counter [head->number]++;
				flag [head->number] = 255;

				for (i = 0; i < MAX_NODE_LINKS; i++)
				{
					if (head->link [i])
					{
						if (flag [head->link [i]->number] == 0 && counter [head->link [i]->number] < 1)
						{
							counter [head->link [i]->number]++;
							flag [head->link [i]->number] = 255;
						}
					}
				}
			}
			head = head->next_node;
		}

		count++;
	}

	// now build the path for the bot to follow
	path = NULL;

	if (counter [end_node->number] > 0)
	{
		path_length = 0;
		head = end_node;

		while (head && head != start_node)
		{
			path = path_add_node (path, head);
			path_length++;
			
			temp = node_list->header->head;
			high_link = NULL;
			high_count = 0;

			while (temp)
			{
				// is temp linked to current head?
				is_linked = FALSE;
				for (i = 0; i < MAX_NODE_LINKS; i++)
				{
					if (temp->link [i] == head)
					{
						is_linked = TRUE;
						break;
					}
					else if (!temp->link [i])
						break;
				}
	
				if (is_linked)
				{
					if (counter [temp->number] > high_count)
					{
						high_link = temp;
						high_count = counter [temp->number];
					}
				}

				temp = temp->next_node;
			}


			head = high_link;
			node_set_marker (self, head, "models/debug/pathnode/pathnode.md2");

			// add start node
			//path = path_add_node (path, start_node);
		}
	}
	else if (count > node_list->header->node_count)
		gstate->Con_Dprintf ("no path found, node_count exceeded\n");
	else if (counter [end_node->number] == 0)
		gstate->Con_Dprintf ("reality failed, universe halted\n");

	return path;
}

//*******************************************************************************
//	node navigation
//*******************************************************************************

//////////////////////////////////
//	node_time_for_ID
//
//////////////////////////////////

float	node_time_for_ID (mapNode_t *node, int ID)
{
	int		i;

	for (i = 0; i < MAX_TIME_STAMPS; i++)
	{
		if (node->node_time->ID_stamp [i] == ID)
			return	node->node_time->time_stamp [i];
	}

	return -1;
}

//////////////////////////////////
//	node_best_time_for_ID
//
//////////////////////////////////

mapNode_t	*node_best_time_for_ID (mapNode_t *cur_node, int ID)
{
	mapNode_t	*node;
	float		time;
	float		best_time = 0;
	mapNode_t	*best_node = NULL;
	int			i;

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (cur_node->link [i])
			time = node_time_for_ID (cur_node->link [i], ID);

		if (time > best_time)
		{
			best_time = time;
			best_node = cur_node->link [i];
		}
	}

	return	best_node;
}

////////////////////////////////////
//	node_random_link
//
//	returns a node pointed to by a one of the passed node's links,
//	chosen randomly
////////////////////////////////////

mapNode_t	*node_random_link (mapNode_t *map_node, mapNode_t *last_node)
{
	int			num_links, r;
	mapNode_t	*node;

	r = floor (rnd () * MAX_NODE_LINKS);

	if (map_node->link [r])
		node = map_node->link [r];

	if (node != last_node)
		return	node;

	if (map_node->link [0] && map_node->link [0] != last_node)
		return map_node->link [0];
	else if (map_node->link [1] && map_node->link [1] != last_node)
		return map_node->link [1];
	else if (map_node->link [2] && map_node->link [2] != last_node)
		return map_node->link [2];
	else if (map_node->link [3] && map_node->link [3] != last_node)
		return map_node->link [3];
	else
		return NULL;
}

//////////////////////////////////
//	node_next_travel
//
//	chooses a random node linked to current node that
//	is not the last node visited
//////////////////////////////////

mapNode_t	*node_next_travel (userEntity_t *self, mapList_t *node_list)
{
	int			i, j, last, num_links;
	float		r, r1;
	mapNode_t	*cur_node, *last_node;

	cur_node = node_list->cur_node;
	last_node = node_list->last_node;

	// find the number of beast... I mean link that links to last_node
	// and the number of nodes that this node is linked to
	for (i = 0; i < MAX_NODE_LINKS && cur_node->link [i]; i++)
	{
		if (cur_node->link [i] == last_node)
			last = i;
	}

	num_links = i;

	if (num_links > 1)
	{
		// choose a random node that isn't last node
		do
		{
			j = (int) (rnd () * (float) num_links);
		} while (j == last);

		if (cur_node->link [j] == last_node)
			gstate->Con_Dprintf ("screwed! going to last node!!\n");
		else if (cur_node->link [j] == cur_node)
			gstate->Con_Dprintf ("double screwed! node linked to itself!!\n");

		if (cur_node->link [j] == NULL)
		{
			gstate->Con_Dprintf ("num links = %i\n", num_links);
			gstate->Con_Dprintf ("chose link #%i\n", j);
			for (i = 0; i < MAX_NODE_LINKS; i++)
			{
				if (cur_node->link [i])
					gstate->Con_Dprintf ("link %i = VALID\n", i);
				else
					gstate->Con_Dprintf ("link %i = NULL\n", i);
			}
		}

		return	cur_node->link [j];
	}
	else if (num_links == 1)
	{
		// only node is the node we came from
		return	cur_node->link [0];
	}
	else
	{
		// at a node with no links to anywhere.
		// most likely a spawn node that hasn't been linked yet, 
		// but could be a node that a fall is required to reach
		// and which was never linked to
		// FIXME: should we flag and release such nodes if they 
		// don't get new links?

		for (i = 0; i < MAX_NODE_LINKS; i++)
		{
			if (cur_node->link [i])
				gstate->Con_Dprintf ("link %i = VALID\n", i);
			else
				gstate->Con_Dprintf ("link %i = NULL\n", i);
		}

		return	NULL;
	}
}

///////////////////////////////////
//	node_can_path
//
//	recursive search to determine if one node
//	is reachable from another node
///////////////////////////////////

int	node_can_path (mapNode_t *start_node, mapNode_t *end_node, int depth)
{
	int		i;

	if (start_node == end_node)
		return	TRUE;
	else if (depth == 0)
		return	FALSE;

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (start_node->link [i])
		{
			if (node_can_path (start_node->link [i], end_node, depth - 1))
				return TRUE;
		}
	}

	return	FALSE;
}

////////////////////////////////////
//	node_closest
//
//	returns the node that is closest
//	to and within dist units of origin
////////////////////////////////////

mapNode_t	*node_closest (mapList_t *list, vec3_t origin, float dist)
{
	float		d;
	mapNode_t	*cur_node, *closest;

	closest = NULL;

	for (cur_node = list->header->head; cur_node; cur_node = cur_node->next_node)
	{
		d = qv_dist (cur_node->origin, origin);

		if (d < dist)
		{
			dist = d;
			closest = cur_node;
		}
	}

	return	closest;
}

////////////////////////////////////
//	node_linked_with_target
//
//	returns the node that is closest
//	to and within dist units of origin
////////////////////////////////////

mapNode_t	*node_linked_with_target (mapNode_t *node, char *targetname)
{
	int		i;

	for (i = 0; i < MAX_NODE_LINKS; i++)
	{
		if (node->link [i])
		{
			if (node->link [i]->target)
			{
				if (!stricmp (node->link [i]->target, targetname))
					return	node->link [i];
			}
		}
	}

	return	NULL;
}

//*******************************************************************************
//	saving and restoring nodes
//*******************************************************************************

////////////////////////////////////
//	node_writelist
//
//	saves the node list to disk
////////////////////////////////////

void	node_writelist (mapHeader_t *node_header)
{
	FILE			*f;
	userEntity_t	*world;
	char			map_name [128];
	char			base_name [128];
	char			temp [128];
	int				i, j, count;
	mapNode_t		*node;

	///////////////////////////////////////////
	//	get the name of the current map's wad
	///////////////////////////////////////////

	strcpy (base_name, gstate->basedir);
	strcat (base_name, "/maps/nodes/");
	strcat (base_name, gstate->mapName);
	strcat (base_name, ".nod");

	gstate->Con_Printf ("mapname = %s\n", gstate->mapName);

	if (!(f = fopen (base_name, "wb")))
	{
		gstate->Con_Printf ("Unable to create node file %s.\n", base_name);
		return;
	}

	//	walk the node list and write each node

	node = node_header->head;
	for (count = 0; node; count++)
	{
		//	save this node's number
		fwrite (&node->number, sizeof (int), 1, f);

		//	save node's origin
		fwrite (node->origin, sizeof (vec3_t), 1, f);
		
		//	save node type
		fwrite (&node->node_type, sizeof (int), 1, f);

		gstate->Con_Printf ("node %i links = ", node->number);

		// write out the node numbers of the six links
		for (i = 0; i < MAX_NODE_LINKS; i++)
		{
			if (node->link [i])
			{
				fwrite (&node->link [i]->number, sizeof (int), 1, f);
				gstate->Con_Printf ("%i ", node->link [i]->number);
			}
			else
			{
				j = 0;
				fwrite (&j, sizeof (int), 1, f);
				gstate->Con_Printf ("0 ");
			}
		}

		gstate->Con_Printf ("\n");

		node = node->next_node;
	}

	fclose (f);

	gstate->Con_Printf ("Wrote %i nodes to %s.\n", count, base_name);
}

////////////////////////////////
//	node_find_num
//
//	returns the node numbered n
////////////////////////////////

mapNode_t	*node_find_num (mapHeader_t	*header, int n)
{
	mapNode_t	*head;

	head = header->head;

	while (head)
	{
		if (head->number == n)
			return	head;

		head = head->next_node;
	}

	return	NULL;
}

////////////////////////////////
//	node_readlist
//
///////////////////////////////

void	node_readlist (mapHeader_t **node_header)
{
	FILE			*f;
	userEntity_t	*world;
	char			map_name [128];
	char			base_name [128];
	char			temp [128];
	int				i, j, count, number;
	mapNode_t		*node;
	mapHeader_t		*h;

	///////////////////////////////////////////
	//	get the name of the current map's wad
	///////////////////////////////////////////

	strcpy (base_name, gstate->basedir);
	strcat (base_name, "/maps/nodes/");
	strcat (base_name, gstate->mapName);
	strcat (base_name, ".nod");

	if (!(f = fopen (base_name, "rb")))
	{
		gstate->Con_Printf ("Could not find %s.\n", base_name);
		return;
	}

	// create the new list
	*node_header = node_create_header ();

	count = 0;

	// read in the entire list of nodes
	while (!feof (f))
	{
		if (!fread (&number, sizeof (int), 1, f))
			break;

		node = node_create_node (&(*node_header));
		//	force number
		node->number = number;

		fread (node->origin, sizeof (vec3_t), 1, f);

		//	read node type
		fread (&node->node_type, sizeof (int), 1, f);

		//	read links
		fread (node->link, sizeof (int), MAX_NODE_LINKS, f);
/*
		gstate->Con_Printf ("node %i links = ", number);
		for (i = 0; i < MAX_NODE_LINKS; i++)
			gstate->Con_Printf ("%i ", (int) node->link [i]);
		gstate->Con_Printf ("\n");
*/
		// show this node
		node_marker (node);
		count++;
	}

	fclose (f);

	// now go through and set up the links from each node to other nodes
	node = (*node_header)->head;
	while (node)
	{
		for (i = 0; i < MAX_NODE_LINKS; i++)
		{
			if (node->link [i])
			{
				node->link [i] = node_find_num (*node_header, (int) node->link [i]);
				if (!node->link [i])
					com->Error ("Error rebuilding node list.  Bad link.");
			}
		}

		node = node->next_node;
	}

	gstate->Con_Printf ("Read %i nodes from %s.\n", count, base_name);
}

/////////////////////////////////////////
//	node_node
//
//	spawn function for node entities
//
//	called on level spawns, adds this node
//	to the client_nodes list and removes the entity
//
//	links are only set to the number of the node
//	they point to and must be re-linked correctly
//	after all nodes have been spawned
/////////////////////////////////////////

void	node_node (userEntity_t *self)
{
	int			i, link;
	mapNode_t	*node;
	char		key [128];

	nodes_in_map++;

	node = node_create_node (&client_nodes);

	//	copy over the origin from the entity to the node
	com->CopyVector (node->origin, self->s.origin);

	for (i = link = 0; self->epair [i].key; i++)
	{
		// get node mumber
		if (!stricmp (self->epair [i].key, "number"))
			node->number = atoi (self->epair [i].value);
		else if (!stricmp (self->epair [i].key, "target"))
			node->target = strdup (self->epair [i].value);
		else if (!stricmp (self->epair [i].key, "targetname"))
			node->targetname = strdup (self->epair [i].value);
		else
		{
			//	setup the link numbers from epairs
			for (link = 0; link < MAX_NODE_LINKS; link++)
			{
				sprintf (key, "link%i", link);
				if (!stricmp (self->epair [i].key, key))
					node->link [link] = (mapNode_t *) atoi (self->epair [i].value);
			}
		}
	}

	node->node_type = self->spawnflags;

	gstate->RemoveEntity (self);
}

/////////////////////////////////////////
//	node_restore_links
//
//	relinks nodes in client_nodes after
//	all nodes have been spawned
/////////////////////////////////////////

void	node_restore_links (userEntity_t *self)
{
	mapNode_t	*node;
	int			i;

	/////////////////////////////////////////////////////////////////////////
	// now go through and set up the links from each node to other nodes
	/////////////////////////////////////////////////////////////////////////

	node = client_nodes->head;
	while (node)
	{
		for (i = 0; i < MAX_NODE_LINKS; i++)
		{
			if (node->link [i])
			{
				node->link [i] = node_find_num (client_nodes, (int) node->link [i]);
				if (!node->link [i])
					com->Error ("Error rebuilding node list.  Bad link.");
			}
		}

		node = node->next_node;
	}
}