// HPB bot - botman's High Ping Bastard bot
//
// (http://planethalflife.com/botman/)
//
// waypoint.cpp
//

#include "gen_bot_header.h"

#ifndef __linux__
#include <io.h>
#endif
#include <fcntl.h>
#ifndef __linux__
#include <sys\stat.h>
#else
#include <sys/stat.h>
#endif

CWaypointClass WaypointClass;
CWaypointFlooder WaypointFlooder;

// ==================================================================
// Code of CWaypointClass - Begin
// ==================================================================

CWaypointClass::CWaypointClass(void) : m_bDrawWaypoints(false), m_bDrawWPPaths(false),
									   m_vLastCreatedWP(g_vecZero), m_bAutoWaypoint(false),
									   m_bAutoPlacePaths(true), m_iRouteWaypointCount(0),
									   m_iWaypointCount(0)
{
	int i;
	
	for (i=0; i < 4; i++)
    {
	    m_pShortestPath[i] = NULL;
		m_pFromTo[i] = NULL;
    }

    for (i=0; i < MAX_WAYPOINTS; i++)
    {
		m_Waypoints[i].pWaypointPaths = NULL;
    }
};

// returns true if waypoints succesfull loaded
bool CWaypointClass::LoadWaypoints()
{
    FILE *bfp;
    char mapname[64];
    char filename[256];
    char new_filename[256];
#ifdef __linux__
    char cmd[512];
#endif
    waypoint_header_s header;
    int index, i;
    short int num;
    short int path_index;
    bool need_rename;

    strcpy(mapname, STRING(gpGlobals->mapname));
    strcat(mapname, ".ESF_wpt");

    BuildBotFileName(filename, "waypoints", mapname);

    bfp = fopen(filename, "rb");

    need_rename = FALSE;

    // if .HBP_wpt files doesn't exist, check .wpt file...
    if (bfp == NULL)
    {
		need_rename = TRUE;

		strcpy(mapname, STRING(gpGlobals->mapname));
		strcat(mapname, ".wpt");

		BuildBotFileName(filename, "waypoints", mapname);

		bfp = fopen(filename, "rb");
    }

    // if file exists, read the waypoint structure from it
    if (bfp != NULL)
    {
		fread(&header, sizeof(header), 1, bfp);

		header.szFileType[7] = 0;
		if ((strcmp(header.szFileType, "HPB_bot") == 0) ||
			(strcmp(header.szFileType, "esf_bot") == 0))
		{
			if (header.iWPFileVersion != WAYPOINT_VERSION)
			{
				cout << "Incompatible ESF bot waypoint file version!\nWaypoints not loaded!\n";

				fclose(bfp);
				return false;
			}

			header.szMapname[31] = 0;

			if (strcmp(header.szMapname, STRING(gpGlobals->mapname)) == 0)
			{
				Init();  // remove any existing waypoints

				for (i=0; i < header.iWPCount; i++)
				{
					fread(&m_Waypoints[i].Waypoint, sizeof(m_Waypoints[0].Waypoint), 1, bfp);
					m_iWaypointCount++;
				}

				// read and add waypoint paths...
				for (index=0; index < m_iWaypointCount; index++)
				{
					// read the number of paths from this node...
					fread(&num, sizeof(num), 1, bfp);

					for (i=0; i < num; i++)
					{
						fread(&path_index, sizeof(path_index), 1, bfp);

						AddPath(index, path_index);
					}
				}		
			}
			else
			{
				cout << filename << " ESF bot waypoints are not for this map!\n";

	            fclose(bfp);
		        return false;
			}
		}
		else
		{
			cout << filename << " is not a ESF bot waypoint file!\n";

			fclose(bfp);
			return false;
		}

		fclose(bfp);

		if (need_rename)
		{
			strcpy(mapname, STRING(gpGlobals->mapname));
			strcat(mapname, ".ESF_wpt");

			BuildBotFileName(new_filename, "waypoints", mapname);

#ifndef __linux__
			rename(filename, new_filename);
#else
			sprintf(cmd, "/bin/mv -f %s %s", filename, new_filename);
			system(cmd);
#endif
		}

		RouteInit();
	}
    else
    {
		cout << "Waypoint file " << filename << " does not exist!\n";

		return false;
   }

   return true;
}


void CWaypointClass::SaveWaypoints()
{
    char filename[256];
    char mapname[64];
    waypoint_header_s header;
    int index, i;
    short int num;
    waypoint_path_s *pPath;

    strcpy(header.szFileType, "esf_bot");

    header.iWPFileVersion = WAYPOINT_VERSION;

    header.iWPFileFlags = 0;  // not currently used

    header.iWPCount = m_iWaypointCount;

    memset(header.szMapname, 0, sizeof(header.szMapname));
    strncpy(header.szMapname, STRING(gpGlobals->mapname), 31);
    header.szMapname[31] = 0;

    strcpy(mapname, STRING(gpGlobals->mapname));
    strcat(mapname, ".ESF_wpt");

    BuildBotFileName(filename, "waypoints", mapname);

    FILE *bfp = fopen(filename, "wb");

    // write the waypoint header to the file...
    fwrite(&header, sizeof(header), 1, bfp);

    // write the waypoint data to the file...
    for (index=0; index < m_iWaypointCount; index++)
    {
		fwrite(&m_Waypoints[index].Waypoint, sizeof(m_Waypoints[0].Waypoint), 1, bfp);
    }

    // save the waypoint paths...
    for (index=0; index < m_iWaypointCount; index++)
    {
		// count the number of paths from this node...

		pPath = m_Waypoints[index].pWaypointPaths;
		num = 0;

		while (pPath != NULL)
		{
			i = 0;

			while (i < MAX_PATH_INDEX)
			{
				if (pPath->sIndex[i] != -1)
					num++;  // count path node if it's used
	            i++;
			}

			pPath = pPath->next;  // go to next node in linked list
		}

		fwrite(&num, sizeof(num), 1, bfp);  // write the count

		// now write out each path index...

		pPath = m_Waypoints[index].pWaypointPaths;

		while (pPath != NULL)
		{
			i = 0;

			while (i < MAX_PATH_INDEX)
			{
				if (pPath->sIndex[i] != -1)  // save path node if it's used
					fwrite(&pPath->sIndex[i], sizeof(pPath->sIndex[0]), 1, bfp);

				i++;
			}

			pPath = pPath->next;  // go to next node in linked list
		}
    }

    fclose(bfp);
}


void CWaypointClass::Think()
{
	WaypointFlooder.FloodThink();

	CBasePlayer *pHost = BotManager.GetHost();
	if (UTIL_IsValidPlayer(pHost, false, false) == false)
		return;

	float flDistance, flMinDist;
    Vector start, end;
    int i, index = 0;  //EEKHOORN : gave index a value

    if (m_bAutoWaypoint) // is auto waypoint on?
    {
		// find the distance from the last used waypoint
		flDistance = UTIL_Distance(m_vLastCreatedWP, pHost->pev->origin);

		if ((flDistance > 200) || (m_vLastCreatedWP == g_vecZero))
		{
			flMinDist = 9999.0;

			// check that no other reachable waypoints are nearby...
			for (i=0; i < m_iWaypointCount; i++)
			{
				if (m_Waypoints[i].Waypoint.iFlags & W_FL_DELETED)
					continue;

				if (m_Waypoints[i].Waypoint.iFlags & W_FL_AIMING)
					continue;

				if (WPIsReachable(pHost, i))
				{
					flDistance = UTIL_Distance(pHost->pev->origin,
											   m_Waypoints[i].Waypoint.v_origin);

					if (flDistance < flMinDist)
						flMinDist = flDistance;
				}
			}

			// make sure nearest waypoint is far enough away...
			if (flMinDist >= 200)
			{
				AddWaypoint(pHost);  // place a waypoint here
			}
		}
	}

    flMinDist = 9999.0;

    if (m_bDrawWaypoints)  // display the waypoints if turned on...
    {
		for (i=0; i < m_iWaypointCount; i++)
		{
			if ((m_Waypoints[i].Waypoint.iFlags & W_FL_DELETED) == W_FL_DELETED)
				continue;

			flDistance = UTIL_Distance(pHost->pev->origin, m_Waypoints[i].Waypoint.v_origin);

			if (flDistance < 500)
			{
				if (flDistance < flMinDist)
				{
					index = i; // store index of nearest waypoint
					flMinDist = flDistance;
				}

				if ((m_Waypoints[i].flLastDrawTime + 1.0) < gpGlobals->time)
				{
					if (m_Waypoints[i].Waypoint.iFlags & W_FL_CROUCH)
					{
						start = m_Waypoints[i].Waypoint.v_origin - Vector(0, 0, 17);
						end = start + Vector(0, 0, 34);
					}
					else if (m_Waypoints[i].Waypoint.iFlags & W_FL_AIMING)
					{
						start = m_Waypoints[i].Waypoint.v_origin + Vector(0, 0, 10);
						end = start + Vector(0, 0, 14);
					}
					else
					{
						start = m_Waypoints[i].Waypoint.v_origin - Vector(0, 0, 34);
						end = start + Vector(0, 0, 68);
					}

					// draw a blue waypoint
					UTIL_DrawBeam(pHost, start, end, 30, 0, 0, 0, 255, 250, 5, 12);

					m_Waypoints[i].flLastDrawTime = gpGlobals->time;
				}
			}
		}

		// check if path waypointing is on...
		if (m_bDrawWPPaths)
		{
			// check if player is close enough to a waypoint and time to draw path...
			if ((flMinDist <= 50) && (m_fPathDrawTime <= gpGlobals->time))
			{
				waypoint_path_s *pPath = m_Waypoints[index].pWaypointPaths;

				m_fPathDrawTime = gpGlobals->time + 1.0;

				while (pPath != NULL)
				{
					i = 0;

					while (i < MAX_PATH_INDEX)
					{
						if (pPath->sIndex[i] != -1)
						{
							Vector v_src = m_Waypoints[index].Waypoint.v_origin;
							Vector v_dest = m_Waypoints[pPath->sIndex[i]].Waypoint.v_origin;

							// draw a white line to this index's waypoint
							UTIL_DrawBeam(pHost, v_src, v_dest, 10, 2, 250, 250, 250, 200, 10);
						}

						i++;
					}

					pPath = pPath->next;  // go to next node in linked list
				}
			}
		}
    }

	WaypointFlooder.DrawNearFloodWPs();
}

// initialize the waypoint structures...
void CWaypointClass::Init()
{
	int i;

	Clear();  // Free previously allocated path memory

    for (i=0; i < 4; i++)
    {
		if (m_pShortestPath[i] != NULL)
		{
			delete [] m_pShortestPath[i];
			m_pShortestPath[i] = NULL;
		}

		if (m_pFromTo[i] != NULL)
		{
			delete [] m_pFromTo[i];
			m_pFromTo[i] = NULL;
		}
    }

    for (i=0; i < MAX_WAYPOINTS; i++)
    {
		m_Waypoints[i].flLastDrawTime = 0.0f;
		m_Waypoints[i].Waypoint.iFlags = 0;
		m_Waypoints[i].Waypoint.v_origin = g_vecZero;
		m_Waypoints[i].pWaypointPaths = NULL;
    }

	m_fPathDrawTime = 0.0;  // reset waypoint path display time
    m_iWaypointCount = 0;
	m_vLastCreatedWP = g_vecZero;
}

// free the linked list of waypoint path nodes...
void CWaypointClass::Clear()
{
	int i;
	
	for (i=0; i < 4; i++)
    {
		if (m_pShortestPath[i] != NULL)
		{
			delete [] m_pShortestPath[i];
		    m_pShortestPath[i] = NULL;
		}

        if (m_pFromTo[i] != NULL)
		{
			delete [] m_pFromTo[i];
			m_pFromTo[i] = NULL;
		}
    }

    for (i=0; i < MAX_WAYPOINTS; i++)
    {
		if (m_Waypoints[i].pWaypointPaths)
		{
			waypoint_path_s *pPath = m_Waypoints[i].pWaypointPaths;
			waypoint_path_s *pNext;

			while (pPath)  // free the linked list
			{
				pNext = pPath->next;  // save the link to next
				delete pPath;
				pPath = pNext;
			}

			m_Waypoints[i].pWaypointPaths = NULL;
		}
    }
}

void CWaypointClass::AddWaypoint(CBasePlayer *pPlayer)
{
	int index = 0;

    if (m_iWaypointCount >= MAX_WAYPOINTS)
	{
		cout << "Cannont create waypoints, max reached\n";
		return;
	}

	// find the next available slot for the new waypoint...
	while (index < m_iWaypointCount)
    {
		if (m_Waypoints[index].Waypoint.iFlags & W_FL_DELETED)
			break;

		index++;
    }

	m_Waypoints[index].Waypoint.iFlags = 0;

	// store the origin (location) of this waypoint (use entity origin)
	m_Waypoints[index].Waypoint.v_origin = pPlayer->pev->origin;

	// store the last used waypoint for the auto waypoint code...
	m_vLastCreatedWP = pPlayer->pev->origin;

    // set the time that this waypoint was originally displayed...
    m_Waypoints[index].flLastDrawTime = gpGlobals->time;

    Vector start, end;

    start = pPlayer->pev->origin - Vector(0, 0, 34);
    end = start + Vector(0, 0, 68);

	// draw a blue waypoint
    UTIL_DrawBeam(pPlayer, start, end, 30, 0, 0, 0, 255, 250, 5);

    if (m_bDrawWaypoints)
		EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "weapons/xbow_hit1.wav", 1.0, ATTN_NORM, 0, 100);

    // increment total number of waypoints if adding at end of array...
    if (index == m_iWaypointCount)
		m_iWaypointCount++;

	// calculate all the paths to this new waypoint
    for (int i=0; i < m_iWaypointCount; i++)
    {
		if (i == index)
			continue;  // skip the waypoint that was just added

		if (m_Waypoints[i].Waypoint.iFlags & W_FL_AIMING)
			continue;  // skip any aiming waypoints

		// check if the waypoint is reachable from the new one (one-way)
		if (m_bAutoPlacePaths && WPIsReachable(pPlayer, i))
		{
			AddPath(index, i); // Add a path from a to b
			AddPath(i, index); // Add a path from b to a
		}
    }
}

void CWaypointClass::DeleteWaypoint(CBasePlayer *pPlayer)
{
	int index;

    if (m_iWaypointCount < 1)
		return;

	index = GetNearestWaypoint(pPlayer, 50.0, -1);

    if (index == -1)
		return;

	if ((m_Waypoints[index].Waypoint.iFlags & W_FL_SNIPER) ||
		(m_Waypoints[index].Waypoint.iFlags & W_FL_SENTRYGUN) ||
        (m_Waypoints[index].Waypoint.iFlags & W_FL_DISPENSER) ||
		(m_Waypoints[index].Waypoint.iFlags & W_FL_JUMP))
    {
		int i;
		int min_index = -1;
		int min_distance = 9999.0;
		float distance;

		// search for nearby aiming waypoint and delete it also...
		for (i=0; i < m_iWaypointCount; i++)
		{
			if (m_Waypoints[i].Waypoint.iFlags & W_FL_DELETED)
				continue;  // skip any deleted waypoints

			if ((m_Waypoints[i].Waypoint.iFlags & W_FL_AIMING) == 0)
				continue;  // skip any NON aiming waypoints

			distance = UTIL_Distance(m_Waypoints[i].Waypoint.v_origin, m_Waypoints[index].Waypoint.v_origin);

			if ((distance < min_distance) && (distance < 40))
			{
				min_index = i;
				min_distance = distance;
			}
		}

		if (min_index != -1)
		{
			m_Waypoints[min_index].Waypoint.iFlags = W_FL_DELETED;  // not being used
			m_Waypoints[min_index].Waypoint.v_origin = Vector(0,0,0);
			m_Waypoints[min_index].flLastDrawTime = 0.0;
		}
    }

	// delete any paths that lead to this index...
	DeletePath(index);

	// free the path for this index...

	if (m_Waypoints[index].pWaypointPaths != NULL)
    {
		waypoint_path_s *pPath = m_Waypoints[index].pWaypointPaths;
		waypoint_path_s *pNext;

		while (pPath)  // free the linked list
		{
			pNext = pPath->next;  // save the link to next
			delete pPath;
			pPath = pNext;

		}

		m_Waypoints[index].pWaypointPaths = NULL;
    }

	m_Waypoints[index].Waypoint.iFlags = W_FL_DELETED;  // not being used
	m_Waypoints[index].Waypoint.v_origin = Vector(0,0,0);
	m_Waypoints[index].flLastDrawTime = 0.0;

	EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "weapons/mine_activate.wav", 1.0, ATTN_NORM, 0, 100);
}

void CWaypointClass::AddPath(short sWPIndex, short sWPindex2)
{
	waypoint_path_s *pPath, *pPrev;
    int i;

    pPath = m_Waypoints[sWPIndex].pWaypointPaths;
    pPrev = NULL;

    // find an empty slot for new path_index...
    while (pPath != NULL)
    {
		i = 0;

		while (i < MAX_PATH_INDEX)
		{
			if (pPath->sIndex[i] == -1)
			{
				pPath->sIndex[i] = sWPindex2;

				return;
			}

			i++;
		}

		pPrev = pPath;     // save the previous node in linked list
		pPath = pPath->next;  // go to next node in linked list
    }

    pPath = new waypoint_path_s;

    if (pPath == NULL)
    {
		ALERT(at_error, "ESF_bot - Error allocating memory for path!");
		return;
    }

    pPath->sIndex[0] = sWPindex2;
    pPath->sIndex[1] = -1;
    pPath->sIndex[2] = -1;
    pPath->sIndex[3] = -1;
    pPath->next = NULL;

    if (pPrev != NULL)
		pPrev->next = pPath;  // link new node into existing list

	if (m_Waypoints[sWPIndex].pWaypointPaths == NULL)
		m_Waypoints[sWPIndex].pWaypointPaths = pPath;  // save head point if necessary
}

// Deletes all paths connected to the given waypoint
void CWaypointClass::DeletePath(short Index)
{
	waypoint_path_s *pPath;
    int index, i;

    // search all paths for this index...
    for (index=0; index < m_iWaypointCount; index++)
    {
		pPath = m_Waypoints[Index].pWaypointPaths;

		// search linked list for Index...
		while (pPath != NULL)
		{
			i = 0;

			while (i < MAX_PATH_INDEX)
			{
				if (pPath->sIndex[i] == Index)
				{
					pPath->sIndex[i] = -1;  // unassign this path
				}

				i++;
			}

			pPath = pPath->next;  // go to next node in linked list
		}
    }
}

// Deletes path between 2 waypoints(1 way)
void CWaypointClass::DeletePath(short WPIndex1, short WPIndex2)
{
	waypoint_path_s *pPath;
	int i;

    pPath = m_Waypoints[WPIndex1].pWaypointPaths;

    // search linked list for del_index...
    while (pPath != NULL)
    {
		i = 0;

		while (i < MAX_PATH_INDEX)
		{
			if (pPath->sIndex[i] == WPIndex2)
			{
				pPath->sIndex[i] = -1;  // unassign this path
			}

			i++;
		}

		pPath = pPath->next;  // go to next node in linked list
    }
}

void CWaypointClass::ManuallyCreatePath(CBasePlayer *pPlayer, int iCmd, bool TwoWay)
{
	static int waypoint1 = -1;  // initialized to unassigned
    static int waypoint2 = -1;  // initialized to unassigned

	if (iCmd == 1)  // assign source of path
    {
		waypoint1 = GetNearestWaypoint(pPlayer, 50.0, -1);

		if (waypoint1 == -1)
		{
			// play "cancelled" sound...
			EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_moveselect.wav", 1.0,
							ATTN_NORM, 0, 100);

			return;
		}

		// play "start" sound...
		EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_hudoff.wav", 1.0,
						ATTN_NORM, 0, 100);

		return;
    }

	if (iCmd == 2)  // assign dest of path and make path
    {
		waypoint2 = GetNearestWaypoint(pPlayer, 50.0, -1);

		if ((waypoint1 == -1) || (waypoint2 == -1))
		{
			// play "error" sound...
			EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_denyselect.wav", 1.0,
				            ATTN_NORM, 0, 100);

			return;
		}

		AddPath(waypoint1, waypoint2);

		if (TwoWay)
			AddPath(waypoint2, waypoint1);

		// play "done" sound...
		EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_hudon.wav", 1.0,
			            ATTN_NORM, 0, 100);
    }
}

void CWaypointClass::ManuallyDeletePath(CBasePlayer *pPlayer, int iCmd, bool TwoWay)
{
	static int waypoint1 = -1;  // initialized to unassigned
    static int waypoint2 = -1;  // initialized to unassigned

    if (iCmd == 1)  // assign source of path
    {
		waypoint1 = GetNearestWaypoint(pPlayer, 50.0, -1);

		if (waypoint1 == -1)
		{
			// play "cancelled" sound...
			EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_moveselect.wav", 1.0,
				            ATTN_NORM, 0, 100);

			return;
		}

		// play "start" sound...
		EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_hudoff.wav", 1.0, ATTN_NORM, 0, 100);

		return;
    }

	if (iCmd == 2)  // assign dest of path and delete path
    {
		waypoint2 = GetNearestWaypoint(pPlayer, 50.0, -1);

		if ((waypoint1 == -1) || (waypoint2 == -1))
		{
			// play "error" sound...
			EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_denyselect.wav", 1.0,
							ATTN_NORM, 0, 100);

			return;
		}

		DeletePath(waypoint1, waypoint2);

		if (TwoWay)
			DeletePath(waypoint2, waypoint1);

		// play "done" sound...
		EMIT_SOUND_DYN2(pPlayer->edict(), CHAN_WEAPON, "common/wpn_hudon.wav", 1.0, ATTN_NORM, 0, 100);
    }
}

bool CWaypointClass::WPIsReachable(CBasePlayer *pPlayer, short sWaypointIndex)
{
	TraceResult tr;
	Vector v_src = pPlayer->pev->origin;
	Vector v_dest = m_Waypoints[sWaypointIndex].Waypoint.v_origin;

    float distance = (v_dest - v_src).Length();

	// is the destination close enough?
	if (distance < REACHABLE_RANGE)
    {
		// check if this waypoint is "visible"...
		UTIL_TraceLine( v_src, v_dest, ignore_monsters, pPlayer->pev->pContainingEntity, &tr );

		// if waypoint is visible from current position (even behind head)...
		return (tr.flFraction >= 1.0);
    }

	return false;
}

int CWaypointClass::GetNearestWaypoint(CBasePlayer *pPlayer, float flRange, short sTeam)
{
	int i, min_index;
    float distance;
    float min_distance;
    TraceResult tr;

    if (m_iWaypointCount < 1)
		return -1;

	// find the nearest waypoint...

    min_index = -1;
    min_distance = 9999.0;

    for (i=0; i < m_iWaypointCount; i++)
    {
		if (m_Waypoints[i].Waypoint.iFlags & W_FL_DELETED)
			continue;  // skip any deleted waypoints

		if (m_Waypoints[i].Waypoint.iFlags & W_FL_AIMING)
			continue;  // skip any aiming waypoints

		// skip this waypoint if it's team specific and teams don't match...
		if ((sTeam != -1) && (m_Waypoints[i].Waypoint.iFlags & W_FL_TEAM_SPECIFIC) &&
			((m_Waypoints[i].Waypoint.iFlags & W_FL_TEAM) != sTeam))
			continue;

		distance = (m_Waypoints[i].Waypoint.v_origin - pPlayer->pev->origin).Length();

		if ((distance < min_distance) && (distance < flRange))
		{
			// if waypoint is visible from current position (even behind head)...
			UTIL_TraceLine(pPlayer->EyePosition(), m_Waypoints[i].Waypoint.v_origin,
                           ignore_monsters, pPlayer->pev->pContainingEntity, &tr );

			if (tr.flFraction >= 1.0)
			{
				min_index = i;
				min_distance = distance;
			}
		}
    }

    return min_index;
}

// find the nearest waypoint to the source postition and return the index
int CWaypointClass::GetNearestWaypoint(Vector v_src, CBaseEntity *pEntity, float range, int team)
{
    int index, min_index;
    float distance;
    float min_distance;
    TraceResult tr;

    if (m_iWaypointCount < 1)
		return -1;

    // find the nearest waypoint...

    min_index = -1;
    min_distance = 9999.0;

    for (index=0; index < m_iWaypointCount; index++)
    {
		if (m_Waypoints[index].Waypoint.iFlags & W_FL_DELETED)
			continue;  // skip any deleted waypoints

		if (m_Waypoints[index].Waypoint.iFlags & W_FL_AIMING)
			continue;  // skip any aiming waypoints

		// skip this waypoint if it's team specific and teams don't match...
		if ((team != -1) && (m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM_SPECIFIC) &&
			((m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM) != team))
			continue;

		distance = (m_Waypoints[index].Waypoint.v_origin - v_src).Length();

		if ((distance < min_distance) && (distance < range))
		{
			// if waypoint is visible from source position...
			UTIL_TraceLine( v_src, m_Waypoints[index].Waypoint.v_origin, ignore_monsters,
							pEntity->pev->pContainingEntity, &tr );

			if (tr.flFraction >= 1.0)
			{
				min_index = index;
				min_distance = distance;
			}
		}
    }

    return min_index;
}

void CWaypointClass::RouteInit()
{
	unsigned int index;
    bool build_matrix[4];
    int matrix;
    unsigned int array_size;
    unsigned int row;
    int i, offset;
    unsigned int a, b;
    float distance;
    unsigned short *pShortestPath, *pFromTo;
    char msg[80];
    unsigned int num_items;
    FILE *bfp;
    char filename[256];
    char filename2[256];
    char mapname[64];

    if (m_iWaypointCount <= 0)
		return;

	// save number of current waypoints in case waypoints get added later
	m_iRouteWaypointCount = m_iWaypointCount;

	strcpy(mapname, STRING(gpGlobals->mapname));
	strcat(mapname, ".ESF_wpt");

	BuildBotFileName(filename, "waypoints", mapname);

	build_matrix[0] = TRUE;  // always build matrix 0 (non-team and team 1)
    build_matrix[1] = FALSE;
    build_matrix[2] = FALSE;
    build_matrix[3] = FALSE;

    // find out how many route matrixes to create...
    for (index=0; index < m_iRouteWaypointCount; index++)
    {
		if (m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM_SPECIFIC)
		{
			if ((m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM) == 0x01)  // team 2?
				build_matrix[1] = TRUE;

			if ((m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM) == 0x02)  // team 3?
				build_matrix[2] = TRUE;

			if ((m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM) == 0x03)  // team 4?
				build_matrix[3] = TRUE;
		}
    }

    array_size = m_iRouteWaypointCount * m_iRouteWaypointCount;

    for (matrix=0; matrix < 4; matrix++)
    {
		if (build_matrix[matrix])
		{
			char ext_str[16];  // ".ESF_wpX\0"

			sprintf(ext_str, ".ESF_wp%d", matrix+1);

			strcpy(mapname, STRING(gpGlobals->mapname));
			strcat(mapname, ext_str);

			BuildBotFileName(filename2, "waypoints", mapname);

			if (IsValidFile(filename2))  // does the .HPB_wpX file exist?
			{
				if (FileIsOlder(filename, filename2))  // is .HPB_wpt older than .HPB_wpX file?
				{
					cout << "loading ESF bot waypoint paths for team " << matrix+1 << "\n";

					m_pShortestPath[matrix] = new unsigned short[array_size];

					if (m_pShortestPath[matrix] == NULL)
						ALERT(at_error, "ESF_bot - Error allocating memory for shortest path!");

					m_pFromTo[matrix] = new unsigned short [array_size];

					if (m_pFromTo[matrix] == NULL)
						ALERT(at_error, "ESF_bot - Error allocating memory for from to matrix!");

					bfp = fopen(filename2, "rb");

					if (bfp != NULL)
					{
						num_items = fread(m_pShortestPath[matrix], sizeof(unsigned short), array_size, bfp);

						if (num_items != array_size)
						{
							// if couldn't read enough data, free memory to recalculate it

							ALERT(at_console, "error reading enough path items, recalculating...\n");

							delete [] m_pShortestPath[matrix];
							m_pShortestPath[matrix] = NULL;

							delete [] m_pFromTo[matrix];
							m_pFromTo[matrix] = NULL;
						}
						else
						{
							num_items = fread(m_pFromTo[matrix], sizeof(unsigned short), array_size, bfp);

							if (num_items != array_size)
							{
								// if couldn't read enough data, free memory to recalculate it

								ALERT(at_console, "error reading enough path items, recalculating...\n");

								delete [] m_pShortestPath[matrix];
								m_pShortestPath[matrix] = NULL;

								delete [] m_pFromTo[matrix];
								m_pFromTo[matrix] = NULL;
							} 
						}
					}
					else
					{
						ALERT(at_console, "ESF_bot - Error reading waypoint paths!\n");

						delete [] m_pShortestPath[matrix];
						m_pShortestPath[matrix] = NULL;

						delete [] m_pFromTo[matrix];
						m_pFromTo[matrix] = NULL;
					}

					fclose(bfp);
				}
			}
		 

			if (m_pShortestPath[matrix] == NULL)
			{
				cout << "calculating ESF bot waypoint paths for team " << matrix+1 << "...\n";

				m_pShortestPath[matrix] = new unsigned short [array_size];

				if (m_pShortestPath[matrix] == NULL)
					ALERT(at_error, "ESF_bot - Error allocating memory for shortest path!");

				m_pFromTo[matrix] = new unsigned short [array_size];

				if (m_pFromTo[matrix] == NULL)
					ALERT(at_error, "ESF_bot - Error allocating memory for from to matrix!");

				pShortestPath = m_pShortestPath[matrix];
				pFromTo = m_pFromTo[matrix];

				for (index=0; index < array_size; index++)
					pShortestPath[index] = WAYPOINT_UNREACHABLE;

				for (index=0; index < m_iRouteWaypointCount; index++)
					pShortestPath[index * m_iRouteWaypointCount + index] = 0;  // zero diagonal

				for (row=0; row < m_iRouteWaypointCount; row++)
				{
					if (m_Waypoints[row].pWaypointPaths != NULL)
					{
						waypoint_path_s *pPath = m_Waypoints[row].pWaypointPaths;

						while (pPath)
						{
							i = 0;

							while (i < MAX_PATH_INDEX)
							{
								if (pPath->sIndex[i] != -1)
								{
									index = pPath->sIndex[i];

									// check if this is NOT team specific OR matches this team
									if (!(m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM_SPECIFIC) ||
										((m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM) == matrix))
									{ 
										distance = (m_Waypoints[row].Waypoint.v_origin - m_Waypoints[index].Waypoint.v_origin).Length();

										if (distance > (float)WAYPOINT_MAX_DISTANCE)
											distance = (float)WAYPOINT_MAX_DISTANCE;

										if (distance > REACHABLE_RANGE)
										{
											sprintf(msg, "Waypoint path distance > %4.1f at from %d to %d\n",
                                              REACHABLE_RANGE, row, index);
											ALERT(at_console, msg);
										}
										
										offset = row * m_iRouteWaypointCount + index;

										pShortestPath[offset] = (unsigned short)distance;
									}
								}
								i++;
							}

							pPath = pPath->next;  // go to next node in linked list
						}
					}
				}

				// run Floyd's Algorithm to generate the from_to matrix...
				CalculatePaths(pShortestPath, pFromTo);

				for (a=0; a < m_iRouteWaypointCount; a++)
				{
					for (b=0; b < m_iRouteWaypointCount; b++)
						if (pShortestPath[a * m_iRouteWaypointCount + b] == WAYPOINT_UNREACHABLE)
							pFromTo[a * m_iRouteWaypointCount + b] = WAYPOINT_UNREACHABLE;
				}

				bfp = fopen(filename2, "wb");

				if (bfp != NULL)
				{
					num_items = fwrite(m_pShortestPath[matrix], sizeof(unsigned short), array_size, bfp);

					if (num_items != array_size)
					{
						// if couldn't write enough data, close file and delete it

						fclose(bfp);
						remove(filename2);
					}
					else
					{
						num_items = fwrite(m_pFromTo[matrix], sizeof(unsigned short), array_size, bfp);

						fclose(bfp);

						if (num_items != array_size)
						{
							// if couldn't write enough data, delete file
							remove(filename2);
						}
					}
				}
				else
				{
					ALERT(at_console, "ESF_bot - Error writing waypoint paths!\n");
				}

				cout << "ESF bot waypoint path calculations for team " << matrix+1 << " complete!\n";
			}
		}
	}
}

void CWaypointClass::CalculatePaths(unsigned short *pShortestPath, unsigned short *pFromTo)
{
    unsigned int x, y, z;
    int changed = 1;
    int distance;

    for (y=0; y < m_iRouteWaypointCount; y++)
    {
		for (z=0; z < m_iRouteWaypointCount; z++)
		{
			pShortestPath[y * m_iRouteWaypointCount + z] = z;
		}
    }

    while (changed)
    {
		changed = 0;

		for (x=0; x < m_iRouteWaypointCount; x++)
		{
			for (y=0; y < m_iRouteWaypointCount; y++)
			{
				for (z=0; z < m_iRouteWaypointCount; z++)
				{
					if ((pShortestPath[y * m_iRouteWaypointCount + x] == WAYPOINT_UNREACHABLE) ||
						(pShortestPath[x * m_iRouteWaypointCount + z] == WAYPOINT_UNREACHABLE))
						continue;

					distance = pShortestPath[y * m_iRouteWaypointCount + x] +
							   pShortestPath[x * m_iRouteWaypointCount + z];

					if (distance > WAYPOINT_MAX_DISTANCE)
						distance = WAYPOINT_MAX_DISTANCE;

					if ((distance < pShortestPath[y * m_iRouteWaypointCount + z]) ||
						(pShortestPath[y * m_iRouteWaypointCount + z] == WAYPOINT_UNREACHABLE))
					{
						pShortestPath[y * m_iRouteWaypointCount + z] = distance;
						pFromTo[y * m_iRouteWaypointCount + z] = pFromTo[y * m_iRouteWaypointCount + x];
						changed = 1;
					}
				}
			}
		}
    }
}

unsigned short CWaypointClass::RouteFromTo(int src, int dest, int Team)
{
	unsigned short *pFromTo;

    if ((Team < -1) || (Team > 3))
		return WAYPOINT_UNREACHABLE;

	if (Team == -1)  // -1 means non-team play
		Team = 0;

	if (m_pFromTo[Team] == NULL)  // if no team specific waypoints use team 0
		Team = 0;

	if (m_pFromTo[Team] == NULL)  // if no route information just return
		return WAYPOINT_UNREACHABLE;

	pFromTo = m_pFromTo[Team];

	return pFromTo[src * m_iRouteWaypointCount + dest];
}

// find a path from the current waypoint. (pPath MUST be NULL on the
// initial call. subsequent calls will return other paths if they exist.)
int CWaypointClass::FindPath(waypoint_path_s **pPath, int *path_index, int waypoint_index, int team)
{
	int index;

    if (*pPath == NULL)
    {
		*pPath = m_Waypoints[waypoint_index].pWaypointPaths;
		*path_index = 0;
    }

	if (*path_index == MAX_PATH_INDEX)
    {
		*path_index = 0;

		*pPath = (*pPath)->next;  // go to next node in linked list
    }

	while (*pPath != NULL)
    {
		while (*path_index < MAX_PATH_INDEX)
		{
			if ((*pPath)->sIndex[*path_index] != -1)  // found a path?
			{
				// save the return value
				index = (*pPath)->sIndex[*path_index];

				// skip this path if next waypoint is team specific and NOT this team
				if ((team != -1) && (m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM_SPECIFIC) &&
					((m_Waypoints[index].Waypoint.iFlags & W_FL_TEAM) != team))
				{
					(*path_index)++;
					continue;
				}

				// set up stuff for subsequent calls...
				(*path_index)++;

				return index;
			}

			(*path_index)++;
		}

		*path_index = 0;

		*pPath = (*pPath)->next;  // go to next node in linked list
    }

    return -1;
}

// ==================================================================
// Code of CWaypointClass - End
// ==================================================================

// ==================================================================
// Code of CWaypointFlooder - Begin
// ==================================================================


void CWaypointFlooder::StartFlood()
{
	m_FloodWPsToCheck.DeleteAllNodes();

	CBaseEntity *pEnt = NULL, *pStart = NULL;
	flood_wp_s *pFloodWP;
	Vector v_origin;

	while ((pEnt = UTIL_FindEntityByClassname(pEnt, "trigger_teleport")) != NULL)
	{
		v_origin = VecBModelOrigin(pEnt->pev);
		Vector v_new;
		bool FoundNewOne = false;

		if (!CanPlaceNodeAt(v_origin))
		{
			for(int x=-1;x<=1;x++)
			{
				for(int y=-1;y<=1;y++)
				{
					for(int z=-1;z<=1;z++)
					{
						v_new = v_origin + Vector(25*x, 25*y, 25*z);
						if (CanPlaceNodeAt(v_new))
						{
							v_origin = v_new;
							FoundNewOne = true;
							break;
						}
					}
				}
			}

			if (!FoundNewOne)
				continue;
		}

		if (!IsNull(pEnt) && !GetNearestFloodWP(pEnt->pev->origin, 150.0f))
		{
			cout << "Adding tele node...\n";
			pFloodWP = PlaceFloodWP(v_origin, NULL, FDIR_NONE);
			if (pFloodWP)
			{
				pFloodWP->Flags |= FL_TELEPORT;
				pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
				m_FloodWPsToCheck.AddNode(pFloodWP);
			}
		}
	}

	pEnt = NULL;
	while ((pEnt = UTIL_FindEntityByClassname(pEnt, "info_teleport_destination")) != NULL)
	{
		if (!IsNull(pEnt) && CanPlaceNodeAt(pEnt->pev->origin) &&
			!GetNearestTeleDestFloodWP(pEnt->pev->origin, 150.0f))
		{
			cout << "Adding tele dest node...\n";
			pFloodWP = PlaceFloodWP(pEnt->pev->origin, NULL, FDIR_NONE);
			if (pFloodWP)
			{
				pFloodWP->Flags |= FL_TELEPORTDEST;
				pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
				m_FloodWPsToCheck.AddNode(pFloodWP);
			}
		}
	}

	pEnt = NULL;
	while ((pEnt = UTIL_FindEntityByClassname(pEnt, "item_sensubeanbag")) != NULL)
	{
		if (!IsNull(pEnt) && CanPlaceNodeAt(pEnt->pev->origin) &&
			!GetNearestFloodWP(pEnt->pev->origin, 150.0f))
		{
			pFloodWP = PlaceFloodWP(pEnt->pev->origin, NULL, FDIR_NONE);
			if (pFloodWP)
			{
				pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
				m_FloodWPsToCheck.AddNode(pFloodWP);
			}
		}
	}

	pEnt = NULL;
	while ((pEnt = UTIL_FindEntityByClassname(pEnt, "item_dragonball")) != NULL)
	{
		if (!IsNull(pEnt) && CanPlaceNodeAt(pEnt->pev->origin) && 
			!GetNearestFloodWP(pEnt->pev->origin, 150.0f))
		{
			pFloodWP = PlaceFloodWP(pEnt->pev->origin, NULL, FDIR_NONE);
			if (pFloodWP)
			{
				pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
				m_FloodWPsToCheck.AddNode(pFloodWP);
			}
		}
	}

	pStart = NULL;
	pEnt = UTIL_FindEntityByClassname(NULL, "info_good_start");
	while(!pStart || (pEnt != pStart))
	{
		if (IsNull(pEnt))
			break;

		if ((!GetNearestFloodWP(pEnt->pev->origin, 200.0f)) &&
			(CanPlaceNodeAt(pEnt->pev->origin)))
		{
			pFloodWP = PlaceFloodWP(pEnt->pev->origin, NULL, FDIR_NONE);
			pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
			m_FloodWPsToCheck.AddNode(pFloodWP);
		}

		pStart = pEnt;
		pEnt = UTIL_FindEntityByClassname(pEnt, "info_good_start");
	}

	pStart = NULL;
	pEnt = UTIL_FindEntityByClassname(NULL, "info_evil_start");
	while(!pStart || (pEnt != pStart))
	{
		if (IsNull(pEnt))
			break;

		if ((!GetNearestFloodWP(pEnt->pev->origin, 200.0f)) &&
			(CanPlaceNodeAt(pEnt->pev->origin)))
		{
			pFloodWP = PlaceFloodWP(pEnt->pev->origin, NULL, FDIR_NONE);
			pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
			m_FloodWPsToCheck.AddNode(pFloodWP);
		}

		pStart = pEnt;
		pEnt = UTIL_FindEntityByClassname(pEnt, "info_evil_start");
	}

	pStart = NULL;
	pEnt = UTIL_FindEntityByClassname(NULL, "info_player_deathmatch");
	while(!pStart || (pEnt != pStart))
	{
		if (IsNull(pEnt))
			break;

		if ((!GetNearestFloodWP(pEnt->pev->origin, 200.0f)) &&
			(CanPlaceNodeAt(pEnt->pev->origin)))
		{
			pFloodWP = PlaceFloodWP(pEnt->pev->origin, NULL, FDIR_NONE);
			pFloodWP->flNextNodeDist = START_NEXTNODEDIST;
			m_FloodWPsToCheck.AddNode(pFloodWP);
		}

		pStart = pEnt;
		pEnt = UTIL_FindEntityByClassname(pEnt, "info_player_deathmatch");
	}

	if (m_FloodWPsToCheck.Empty())
	{
		cout << "Couldn't start flooding!\n";
		return;
	}

	m_vLookAngles = Vector(0, 0, 0);//pHost->pev->v_angle;
	//m_vLookAngles.x = 0;

	cout << "Start flood!\n";
	m_bFlooding = true;
}

flood_wp_s *CWaypointFlooder::GetNearest(Vector v_origin, float flRange, flood_wp_s *pIgnore)
{
	/*modified by harSens
	TLinkedList<flood_wp_s *>::node_s *pNode;
	*/
	node_s<flood_wp_s *> *pNode;
	flood_wp_s *pNearest = NULL;
	short i, j, k, MinI, MaxI, MinJ, MaxJ, MinK, MaxK, Offset = ceil(flRange / SECTOR_SIZE);
	float flNearestDist = 9999.99, flDist;

	GetFloodWPIndexes(v_origin, &i, &j, &k);
	MinI = i - Offset;
	MaxI = i + Offset;
	MinJ = j - Offset;
	MaxJ = j + Offset;
	MinK = k - Offset;
	MaxK = k + Offset;

	if (MinI < 0)
		MinI = 0;
	if (MaxI > MAX_MAP_GRIDS - 1)
		MaxI = MAX_MAP_GRIDS - 1;
	if (MinJ < 0)
		MinJ = 0;
	if (MaxJ > MAX_MAP_GRIDS - 1)
		MaxJ = MAX_MAP_GRIDS - 1;
	if (MinK < 0)
		MinK = 0;
	if (MaxK > MAX_MAP_GRIDS - 1)
		MaxK = MAX_MAP_GRIDS - 1;

	for (int x=MinI;x<=MaxI;x++)
	{
		for(int y=MinJ;y<=MaxJ;y++)
		{
			for(int z=MinK;z<=MaxK;z++)
			{
				pNode = m_FloodWPs[x][y][z].GetFirst();

				while(pNode)
				{
					if (pNode->Entry == pIgnore)
					{
						pNode = pNode->next;
						continue;
					}

					flDist = UTIL_Distance(v_origin, pNode->Entry->v_origin);
					if ((flDist < flNearestDist) && (flDist <= flRange))
					{
						if (IsVisible(v_origin, pNode->Entry->v_origin, NULL))
						{
							pNearest = pNode->Entry;
							flNearestDist = flDist;
						}
					}

					pNode = pNode->next;
				}
			}
		}
	}
	return pNearest;
}

flood_wp_s *CWaypointFlooder::GetNearestToConnectWith(flood_wp_s *pCurrent, Vector v_dest,
													  float flRange)
{
	/*modified by harSens
	TLinkedList<flood_wp_s *>::node_s *pNode;
	*/
	node_s<flood_wp_s *> *pNode;
	flood_wp_s *pNearest = NULL;
	short i, j, k, MinI, MaxI, MinJ, MaxJ, MinK, MaxK, Offset = ceil(flRange / SECTOR_SIZE);
	float flNearestDist = 9999.99, flDist;

	GetFloodWPIndexes(v_dest, &i, &j, &k);
	MinI = i - Offset;
	MaxI = i + Offset;
	MinJ = j - Offset;
	MaxJ = j + Offset;
	MinK = k - Offset;
	MaxK = k + Offset;

	if (MinI < 0)
		MinI = 0;
	if (MaxI > MAX_MAP_GRIDS - 1)
		MaxI = MAX_MAP_GRIDS - 1;
	if (MinJ < 0)
		MinJ = 0;
	if (MaxJ > MAX_MAP_GRIDS - 1)
		MaxJ = MAX_MAP_GRIDS - 1;
	if (MinK < 0)
		MinK = 0;
	if (MaxK > MAX_MAP_GRIDS - 1)
		MaxK = MAX_MAP_GRIDS - 1;

	for (int x=MinI;x<=MaxI;x++)
	{
		for(int y=MinJ;y<=MaxJ;y++)
		{
			for(int z=MinK;z<=MaxK;z++)
			{
				pNode = m_FloodWPs[x][y][z].GetFirst();

				while(pNode)
				{
					if (pNode->Entry == pCurrent)
					{
						pNode = pNode->next;
						continue;
					}

					flDist = UTIL_Distance(v_dest, pNode->Entry->v_origin);
					if ((flDist < flNearestDist) && (flDist <= flRange))
					{
						if (IsVisible(v_dest, pNode->Entry->v_origin, NULL) &&
							IsVisible(pCurrent->v_origin, pNode->Entry->v_origin, NULL))
						{
							pNearest = pNode->Entry;
							flNearestDist = flDist;
						}
					}

					pNode = pNode->next;
				}
			}
		}
	}
	return pNearest;
}

flood_wp_s *CWaypointFlooder::GetNearestTeleDestFloodWP(Vector v_origin, float flRange)
{
	/* modified by harSens
	TLinkedList<flood_wp_s *>::node_s *pNode;
	*/
	node_s<flood_wp_s *> *pNode;
	flood_wp_s *pNearest = NULL;
	short i, j, k, MinI, MaxI, MinJ, MaxJ, MinK, MaxK, Offset = ceil(flRange / SECTOR_SIZE);
	float flNearestDist = 9999.99, flDist;

	GetFloodWPIndexes(v_origin, &i, &j, &k);
	MinI = i - Offset;
	MaxI = i + Offset;
	MinJ = j - Offset;
	MaxJ = j + Offset;
	MinK = k - Offset;
	MaxK = k + Offset;

	if (MinI < 0)
		MinI = 0;
	if (MaxI > MAX_MAP_GRIDS - 1)
		MaxI = MAX_MAP_GRIDS - 1;
	if (MinJ < 0)
		MinJ = 0;
	if (MaxJ > MAX_MAP_GRIDS - 1)
		MaxJ = MAX_MAP_GRIDS - 1;
	if (MinK < 0)
		MinK = 0;
	if (MaxK > MAX_MAP_GRIDS - 1)
		MaxK = MAX_MAP_GRIDS - 1;

	for (int x=MinI;x<=MaxI;x++)
	{
		for(int y=MinJ;y<=MaxJ;y++)
		{
			for(int z=MinK;z<=MaxK;z++)
			{
				pNode = m_FloodWPs[x][y][z].GetFirst();

				while(pNode)
				{
					if (!(pNode->Entry->Flags & FL_TELEPORTDEST))
					{
						pNode = pNode->next;
						continue;
					}

					flDist = UTIL_Distance(v_origin, pNode->Entry->v_origin);
					if ((flDist < flNearestDist) && (flDist <= flRange))
					{
						if (IsVisible(v_origin, pNode->Entry->v_origin, NULL))
						{
							pNearest = pNode->Entry;
							flNearestDist = flDist;
						}
					}

					pNode = pNode->next;
				}
			}
		}
	}
	return pNearest;
}

flood_wp_s *CWaypointFlooder::GetNearestFromDir(Vector v_origin, float flRange, EFloodDir Dir,
												flood_wp_s *pIgnore)
{
	/*modified by harSens
	TLinkedList<flood_wp_s *>::node_s *pNode;
	*/
	node_s<flood_wp_s *> *pNode;
	flood_wp_s *pNearest = NULL;
	short i, j, k, MinI, MaxI, MinJ, MaxJ, MinK, MaxK, Offset = ceil(flRange / SECTOR_SIZE);
	float flNearestDist = 9999.99, flDist, flDot;
	Vector v_angle;
	Vector2D vec2LOS;

	GetFloodWPIndexes(v_origin, &i, &j, &k);
	MinI = i - Offset;
	MaxI = i + Offset;
	MinJ = j - Offset;
	MaxJ = j + Offset;
	MinK = k - Offset;
	MaxK = k + Offset;

	if (MinI < 0)
		MinI = 0;
	if (MaxI > MAX_MAP_GRIDS - 1)
		MaxI = MAX_MAP_GRIDS - 1;
	if (MinJ < 0)
		MinJ = 0;
	if (MaxJ > MAX_MAP_GRIDS - 1)
		MaxJ = MAX_MAP_GRIDS - 1;
	if (MinK < 0)
		MinK = 0;
	if (MaxK > MAX_MAP_GRIDS - 1)
		MaxK = MAX_MAP_GRIDS - 1;

	UTIL_MakeVectors(m_vLookAngles);

	switch(Dir)
	{
	case FDIR_LEFT:
		v_angle = WrapAngles(UTIL_VecToAngles((v_origin - gpGlobals->v_right * 10.0f) - v_origin));
		break;
	case FDIR_RIGHT:
		v_angle = WrapAngles(UTIL_VecToAngles((v_origin + gpGlobals->v_right * 10.0f) - v_origin));
		break;
	case FDIR_FORWARD:
		v_angle = WrapAngles(UTIL_VecToAngles((v_origin + gpGlobals->v_forward * 10.0f) - v_origin));
		break;
	case FDIR_BACK:
		v_angle = WrapAngles(UTIL_VecToAngles((v_origin - gpGlobals->v_forward * 10.0f) - v_origin));
		break;
	case FDIR_UP:
		v_angle = WrapAngles(UTIL_VecToAngles((v_origin + gpGlobals->v_up * 10.0f) - v_origin));
		break;
	case FDIR_DOWN:
		v_angle = WrapAngles(UTIL_VecToAngles((v_origin - gpGlobals->v_up * 10.0f) - v_origin));
		break;
	}

	UTIL_MakeVectors(v_angle);

	for (int x=MinI;x<=MaxI;x++)
	{
		for(int y=MinJ;y<=MaxJ;y++)
		{
			for(int z=MinK;z<=MaxK;z++)
			{
				pNode = m_FloodWPs[x][y][z].GetFirst();

				while(pNode)
				{
					if (pNode->Entry == pIgnore)
					{
						pNode = pNode->next;
						continue;
					}

					flDist = UTIL_Distance(v_origin, pNode->Entry->v_origin);

					if ((flDist >= flNearestDist) || (flDist > flRange))
					{
						pNode = pNode->next;
						continue;
					}

					vec2LOS = ( pNode->Entry->v_origin - v_origin).Make2D();
					vec2LOS = vec2LOS.Normalize();
					
					flDot = DotProduct (vec2LOS , gpGlobals->v_forward.Make2D() );

					if ( flDot < 0.70 )
					{
						pNode = pNode->next;
						continue;
					}

					if (IsVisible(v_origin, pNode->Entry->v_origin, NULL))
					{
						pNearest = pNode->Entry;
						flNearestDist = flDist;
					}

					pNode = pNode->next;
				}
			}
		}
	}
	return pNearest;
}

flood_wp_s *CWaypointFlooder::PlaceFloodWP(Vector v_origin, flood_wp_s *pParent, EFloodDir dir)
{
	flood_wp_s *pWP = new flood_wp_s;
	pWP->v_origin = v_origin;
//	pWP->Index = m_iFloodWPCount;
	pWP->pConnectedWPs[0] = pWP->pConnectedWPs[1] = pWP->pConnectedWPs[2] = pWP->pConnectedWPs[3] = pWP->pConnectedWPs[4] = pWP->pConnectedWPs[5] = NULL;

	if (pParent)
	{
		switch (dir)
		{
		case FDIR_LEFT:
			pWP->pConnectedWPs[1] = pParent;
			pParent->pConnectedWPs[0] = pWP;
			break;
		case FDIR_RIGHT:
			pWP->pConnectedWPs[0] = pParent;
			pParent->pConnectedWPs[1] = pWP;
			break;
		case FDIR_FORWARD:
			pWP->pConnectedWPs[3] = pParent;
			pParent->pConnectedWPs[2] = pWP;
			break;
		case FDIR_BACK:
			pWP->pConnectedWPs[2] = pParent;
			pParent->pConnectedWPs[3] = pWP;
			break;
		case FDIR_UP:
			pWP->pConnectedWPs[5] = pParent;
			pParent->pConnectedWPs[4] = pWP;
			break;
		case FDIR_DOWN:
			pWP->pConnectedWPs[4] = pParent;
			pParent->pConnectedWPs[5] = pWP;
			break;
		}
	}

	m_iFloodWPCount++;
	short i, j, k;
	GetFloodWPIndexes(v_origin, &i, &j, &k);
	m_FloodWPs[i][j][k].PushNode(pWP);

	return pWP;
}

CBaseEntity *CWaypointFlooder::GetTeleporterFromWP(flood_wp_s *pFloodWP)
{
	CBaseEntity *pEnt = NULL;

	while ((pEnt = UTIL_FindEntityByClassname(pEnt, "trigger_teleport")) != NULL)
	{
		if (IsNull(pEnt))
			continue;

		if (UTIL_IsInBModel(pFloodWP->v_origin, pEnt))
			return pEnt;
	}

	return NULL;
}

short CWaypointFlooder::GetFreeSlot(flood_wp_s *pFloodWP)
{
	short sFreeSlot = -1;

	for (short s=0;s<6;s++)
	{
		if (pFloodWP->pConnectedWPs[s] == NULL)
		{
			sFreeSlot = s;
			break;
		}
	}

	return sFreeSlot;
}

bool CWaypointFlooder::FloodLevel()
{
	static EFloodDir CurFloodDir;
	static Vector v_dest, v_direction, v_end;
	static TraceResult tr, tr2;
	static flood_wp_s *pNode, *pNewNode;
	static bool FoundEmptySlot;
	static short NodesAdded, i;
	static float flTraceDist, flTraceOffset, flNewTraceDist, flMaxConnectDist;

	FoundEmptySlot = false;
	NodesAdded = 0;

	while(m_FloodWPsToCheck.Empty() == false)
	{
		// Added 400 nodes?
		if (NodesAdded >= 400)
		{
			cout << "."; // display a dot
			return false; // Break, so hl can display it
		}

		pNode = m_FloodWPsToCheck.Pop();
		for (i=0;i<6;i++)
		{
			if (pNode->pConnectedWPs[i])
				continue;

			UTIL_MakeVectors(m_vLookAngles);

			switch(i)
			{
			case 0:
				CurFloodDir = FDIR_LEFT;
				v_direction = -gpGlobals->v_right;
				break;
			case 1:
				CurFloodDir = FDIR_RIGHT;
				v_direction = gpGlobals->v_right;
				break;
			case 2:
				CurFloodDir = FDIR_FORWARD;
				v_direction = gpGlobals->v_forward;
				break;
			case 3:
				CurFloodDir = FDIR_BACK;
				v_direction = -gpGlobals->v_forward;
				break;
			case 4:
				CurFloodDir = FDIR_UP;
				v_direction = gpGlobals->v_up;
				break;
			case 5:
				CurFloodDir = FDIR_DOWN;
				v_direction = -gpGlobals->v_up;
				break;
			}
	/*
			//flTraceOffset = (pNode->flNextNodeDist / 100.0f) * 20.0f;
			flTraceOffset = MAX_FLOODWPDIST;
			//flMaxConnectDist = (pNode->flNextNodeDist / 100.0f) * 50.0f;
			flTraceDist = pNode->flNextNodeDist + flTraceOffset;
			flMaxConnectDist = flTraceDist + (pNode->flNextNodeDist / 100.0f) * 50.0f;
			v_end = pNode->v_origin + v_direction * flTraceDist;

			/*if (pNode->flNextNodeDist < MAX_FLOODWPDIST)
			{
				flNewTraceDist = pNode->flNextNodeDist + ((pNode->flNextNodeDist / 100.0f) * 40.0f);
				if (flNewTraceDist > MAX_FLOODWPDIST)
					flNewTraceDist = MAX_FLOODWPDIST;
			}
			else
				flNewTraceDist = MAX_FLOODWPDIST;*/

			flTraceOffset = (MAX_FLOODWPDIST / 100.0f) * 20.0f;
			flTraceDist = MAX_FLOODWPDIST + flTraceOffset;
			flMaxConnectDist = MAX_FLOODWPDIST + 75.0f;
			v_end = pNode->v_origin + v_direction * flTraceDist;

			UTIL_TraceHull(pNode->v_origin, v_end, ignore_monsters, human_hull, NULL, &tr);
			UTIL_TraceLine(pNode->v_origin, v_end, ignore_monsters, NULL, &tr2);
			if ((tr.flFraction >= 0.5f) && (tr2.flFraction >= 0.5f))
			{
				if (tr.flFraction <= tr2.flFraction)
					v_dest = pNode->v_origin + v_direction * ((tr.flFraction * flTraceDist) - flTraceOffset);
				else
					v_dest = pNode->v_origin + v_direction * ((tr2.flFraction * flTraceDist) - flTraceOffset);

				if (!CanPlaceNodeAt(v_dest))
					continue;

				flood_wp_s *pNearest = GetNearestFromDir(pNode->v_origin, flMaxConnectDist,
														 CurFloodDir, pNode);
				flood_wp_s *pNearestFromDest = GetNearestToConnectWith(pNode, v_dest, 200.0f);

				if ((!pNearest) && (!pNearestFromDest))
				{
					// Add node here
					FoundEmptySlot = true;
					pNewNode = PlaceFloodWP(v_dest, pNode, CurFloodDir);
					pNewNode->flNextNodeDist = flNewTraceDist;
					m_FloodWPsToCheck.AddNode(pNewNode);
					NodesAdded++;
				}
				else if (pNearest)
				{
					// Connect with pNearest
					int iOtherIndex;
					switch (CurFloodDir)
					{
					case FDIR_LEFT:
						iOtherIndex = 1;
						break;
					case FDIR_RIGHT:
						iOtherIndex = 0;
						break;
					case FDIR_FORWARD:
						iOtherIndex = 3;
						break;
					case FDIR_BACK:
						iOtherIndex = 2;
						break;
					case FDIR_UP:
						iOtherIndex = 5;
						break;
					case FDIR_DOWN:
						iOtherIndex = 4;
						break;
					}

					if (pNearest->pConnectedWPs[iOtherIndex] == NULL)
					{
						pNode->pConnectedWPs[i] = pNearest;
						pNearest->pConnectedWPs[iOtherIndex] = pNode;
						FoundEmptySlot = true;
						NodesAdded++;
					}
				}
				else if (pNearestFromDest &&
						 (UTIL_Distance(v_dest, pNearestFromDest->v_origin) < MAX_FLOODWPCONNECTDIST))
				{
					// Connect with pNearestFromDest
					int iOtherIndex;
					switch (CurFloodDir)
					{
					case FDIR_LEFT:
						iOtherIndex = 1;
						break;
					case FDIR_RIGHT:
						iOtherIndex = 0;
						break;
					case FDIR_FORWARD:
						iOtherIndex = 3;
						break;
					case FDIR_BACK:
						iOtherIndex = 2;
						break;
					case FDIR_UP:
						iOtherIndex = 5;
						break;
					case FDIR_DOWN:
						iOtherIndex = 4;
						break;
					}

					if (pNearestFromDest->pConnectedWPs[iOtherIndex] == NULL)
					{
						pNode->pConnectedWPs[i] = pNearestFromDest;
						pNearestFromDest->pConnectedWPs[iOtherIndex] = pNode;
						FoundEmptySlot = true;
						NodesAdded++;
					}
				}
				else
				{
					// Mark as unconnected
					FoundEmptySlot = true;
					pNode->pConnectedWPs[i] = NULL;
					NodesAdded++;
				}
			}
			else
			{
				// Mark as unconnected
				FoundEmptySlot = true;
				pNode->pConnectedWPs[i] = NULL;
				NodesAdded++;
			}
		}

		if (pNode->Flags & FL_TELEPORT)
		{
			bool NeedATeleportDestNode = true;
			for(i=0;i<6;i++)
			{
				if (pNode->pConnectedWPs[i] &&
					(pNode->pConnectedWPs[i]->Flags & FL_TELEPORTDEST))
				{
					NeedATeleportDestNode = false;
					break;
				}
			}

			if (NeedATeleportDestNode)
			{
				short FreeSlot = GetFreeSlot(pNode);
				if (FreeSlot == -1)
					FreeSlot = RANDOM_LONG(0, 5);

				CBaseEntity *pTeleporter = GetTeleporterFromWP(pNode);
				if (pTeleporter)
				{
					cout << "Found teleporter....\n";
					edict_t *pTarget = FIND_ENTITY_BY_TARGETNAME(NULL, STRING(pTeleporter->pev->target));

					if (pTarget)
					{
						cout << " also a target...";
						flood_wp_s *pTeleDestWP = GetNearestTeleDestFloodWP(pTarget->v.origin, 200.0f);
						if (pTeleDestWP)
						{
							cout << " and dest WP!\n";
							pNode->pConnectedWPs[FreeSlot] = pTeleDestWP;
							FoundEmptySlot = true;
						}
						else
							cout << " but no dest WP!\n";
					}
					else
						cout << " but no target !\n";
				}
				else
					cout << "Didn't found a teleporter...\n";
			}
		}
	}
/*
	if (!FoundEmptySlot)
	{
		if (PrevFloodWPIndex == 0)
			return true;
		else
			m_sCurrentFloodWPIndex = 0;
	}
	
	if (m_iFloodWPCount >= MAX_FLOOD_WPS)
	{
		m_sCurrentFloodWPIndex = 0;
		return true;
	}

//	if (j >= (m_iFloodWPCount-1))
//		m_sCurrentFloodWPIndex = 0;
*/
	return true;
}

void CWaypointFlooder::FloodThink()
{
	if (m_bFlooding)
	{
		if (FloodLevel())
		{
			char szSize[25];
			float flSize = (((float(sizeof(flood_wp_s)) * float(m_iFloodWPCount)) + sizeof(m_FloodWPs)) / 1024.0f / 1024.0f);

			if (m_iFloodWPCount)
				sprintf(szSize, "%.2f", flSize);
			else
				strcpy(szSize, "0.0");

			cout << " Done, Total " << m_iFloodWPCount << " nodes created. Size: " << szSize;
			cout << " MB\n";
			m_bFlooding = false;
		}
	}
}

void CWaypointFlooder::DrawNearFloodWPs()
{
	if (m_fWPDrawDelay > gpGlobals->time)
		return;

	m_fWPDrawDelay = gpGlobals->time + 1.5f;

	if (m_iFloodWPCount < 1)
		return; // No Flood WP's to draw

	CBasePlayer *pHost = BotManager.GetHost();
	if (!UTIL_IsValidPlayer(pHost, false, false))
		return;
	/*modified by harSens
	TLinkedList<flood_wp_s *>::node_s *pNode;
	*/
	node_s<flood_wp_s *> *pNode;
	
	flood_wp_s *pNearest = NULL;
	short i, j, k, MinI, MaxI, MinJ, MaxJ, MinK, MaxK, Offset = ceil(500.0f / SECTOR_SIZE);
	float flNearestDist = 9999.99, flDist;
	short DrawWPCount = 0;

	GetFloodWPIndexes(pHost->pev->origin, &i, &j, &k);
	MinI = i - Offset;
	MaxI = i + Offset;
	MinJ = j - Offset;
	MaxJ = j + Offset;
	MinK = k - Offset;
	MaxK = k + Offset;

	if (MinI < 0)
		MinI = 0;
	if (MaxI > MAX_MAP_GRIDS - 1)
		MaxI = MAX_MAP_GRIDS - 1;
	if (MinJ < 0)
		MinJ = 0;
	if (MaxJ > MAX_MAP_GRIDS - 1)
		MaxJ = MAX_MAP_GRIDS - 1;
	if (MinK < 0)
		MinK = 0;
	if (MaxK > MAX_MAP_GRIDS - 1)
		MaxK = MAX_MAP_GRIDS - 1;

	for (int x=MinI;x<=MaxI;x++)
	{
		for(int y=MinJ;y<=MaxJ;y++)
		{
			for (int z=MinK;z<=MaxK;z++)
			{
				pNode = m_FloodWPs[x][y][z].GetFirst();

				while(pNode)
				{
					flDist = UTIL_Distance(pHost->pev->origin, pNode->Entry->v_origin);
					if (flDist <= 500.0f)
					{
						DrawWPCount++;
						UTIL_DrawBeam(pHost, pNode->Entry->v_origin,
									  pNode->Entry->v_origin + Vector(0, 0, 64), 10, 2, 255, 0, 0,
									  250, 10, 20);

						if (flNearestDist > flDist)
						{
							if (pHost->FInViewCone(&pNode->Entry->v_origin))
							{
								flNearestDist = flDist;
								pNearest = pNode->Entry;
							}
						}
					}

					pNode = pNode->next;
				}
			}
		}
	}

	if (pNearest)
	{
		for(i=0;i<6;i++)
		{
			if (pNearest->pConnectedWPs[i])
			{
				UTIL_DrawBeam(pHost, pNearest->v_origin + Vector(0, 0, 32),
							  pNearest->pConnectedWPs[i]->v_origin + Vector(0, 0, 32), 10, 2, 0,
							  0, 255, 250, 10, 20);
			}
		}
	}
}

void CWaypointFlooder::DestroyFloodWps()
{
	m_iFloodWPCount = 0;
	m_fWPDrawDelay = 0.0f;
	m_FloodWPsToCheck.DeleteAllNodes();

	for(int i=0;i<MAX_MAP_GRIDS;i++)
	{
		for(int j=0;j<MAX_MAP_GRIDS;j++)
		{
			for (int k=0;k<MAX_MAP_GRIDS;k++)
			{
				while(!m_FloodWPs[i][j][k].Empty())
					delete m_FloodWPs[i][j][k].Pop();
			}
		}
	}

}

flood_wp_s *CWaypointFlooder::GetNearestFloodWP(Vector v_origin, float flRange)
{
	return GetNearest(v_origin, flRange, NULL);
}

void CWaypointFlooder::GetFloodWPIndexes(Vector v_origin, short *i, short *j, short *k)
{
	// Function code by cheesy and PMB
	*i = abs((int)((int)(v_origin.x + 4096.0) / SECTOR_SIZE));
	*j = abs((int)((int)(v_origin.y + 4096.0) / SECTOR_SIZE));
	*k = abs((int)((int)(v_origin.z + 4096.0) / SECTOR_SIZE));

    if (*i > MAX_MAP_GRIDS - 1)
		*i = MAX_MAP_GRIDS - 1;
    if (*j > MAX_MAP_GRIDS - 1)
		*j = MAX_MAP_GRIDS - 1;
    if (*k > MAX_MAP_GRIDS - 1)
		*k = MAX_MAP_GRIDS - 1;
}

bool CWaypointFlooder::CanPlaceNodeAt(Vector v_origin)
{
	if (v_origin.x >= 4096) return false;
	if (v_origin.y >= 4096) return false;
	if (v_origin.z >= 4096) return false;
	if (v_origin.x <= -4096) return false;
	if (v_origin.y <= -4096) return false;
	if (v_origin.z <= -4096) return false;

	TraceResult tr;

	UTIL_TraceLine(v_origin, v_origin + Vector(0, 0, -9999), ignore_monsters, NULL, &tr);
	return (tr.flFraction < 1.0f);
}

int CWaypointFlooder::GetNodeCountWithnConnections(short n)
{
	/*modified by harSens
	TLinkedList<flood_wp_s *>::node_s *pNode;
	*/
	node_s<flood_wp_s *> *pNode;
	short NodeCount;
	int NodesWithnConnection = 0;

	for(int x=0;x<MAX_MAP_GRIDS;x++)
	{
		for(int y=0;y<MAX_MAP_GRIDS;y++)
		{
			for(int z=0;z<MAX_MAP_GRIDS;z++)
			{
				pNode = m_FloodWPs[x][y][z].GetFirst();
				while(pNode)
				{
					NodeCount = 0;
					for(byte b=0;b<6;b++)
					{
						if (pNode->Entry->pConnectedWPs[b])
							NodeCount++;
					}

					if (NodeCount == n)
						NodesWithnConnection++;

					pNode = pNode->next;
				}
			}
		}
	}

	return NodesWithnConnection;
}

bool CWaypointFlooder::ConnectionsAreValid()
{
	for(int x=0;x<MAX_MAP_GRIDS;x++)
	{
		for(int y=0;y<MAX_MAP_GRIDS;y++)
		{
			for(int z=0;z<MAX_MAP_GRIDS;z++)
			{
				/*modified by harSens
				TLinkedList<flood_wp_s *>::node_s *pNode = m_FloodWPs[x][y][z].GetFirst();
				*/
				node_s<flood_wp_s *> *pNode = m_FloodWPs[x][y][z].GetFirst();
				while(pNode)
				{
					for(int i=0;i<6;i++)
					{
						if (pNode->Entry->pConnectedWPs[i] == NULL)
							continue;

						if (!IsVisible(pNode->Entry->v_origin, pNode->Entry->pConnectedWPs[i]->v_origin, NULL))
							return false;
					}

					pNode = pNode->next;
				}
			}
		}
	}

	return true;
}

// ==================================================================
// Code of CWaypointFlooder - End
// ==================================================================
