navigate.cpp

this keik game source

//-----------------------------------------------------------------------------
//
//  $Logfile:: /Quake 2 Engine/Sin/code/game/navigate.cpp                     $
// $Revision:: 68                                                             $
//   $Author:: Markd                                                          $
//     $Date:: 11/18/98 7:47p                                                 $
//
// Copyright (C) 1998 by Ritual Entertainment, Inc.
// All rights reserved.
//
// This source may not be distributed and/or modified without
// expressly written permission by Ritual Entertainment, Inc.
//
// $Log:: /Quake 2 Engine/Sin/code/game/navigate.cpp                          $
// 
// 68    11/18/98 7:47p Markd
// Allowed NearestNode to not use bounding box
// 
// 67    11/12/98 8:58p Jimdose
// made creating paths message a developer only thing
// 
// 66    11/12/98 2:31a Jimdose
// Added ReadFile.  Archives now read from pak files
// 
// 65    11/08/98 6:33p Jimdose
// added SetNodeFlagsEvent
// 
// 64    10/27/98 3:52a Jimdose
// made AI_FindNode accept node numbers from scripts
// 
// 63    10/26/98 8:23p Jimdose
// CalcPathEvent and DisconnectPathEvent weren't returning after call to
// Event::Error
// 
// 62    10/26/98 6:32p Jimdose
// made CalcPathEvent do fast path calculation
// 
// 61    10/26/98 5:16p Jimdose
// Added CalcPath and DisconnectPath
// 
// 60    10/26/98 4:59p Jimdose
// added recalc paths
// 
// 59    10/26/98 2:16p Markd
// Fixed pathnode target issue
// 
// 58    10/24/98 3:26a Markd
// Put in tolerance for horizontal test
// 
// 57    10/23/98 9:41p Jimdose
// Re-fixed the paths for monster clip brushes.  Path traces no longer get
// blocked by monsters or players.
// 
// 56    10/23/98 5:25p Jimdose
// Made paths work with monster clip brushes
// 
// 55    10/19/98 12:10a Jimdose
// made all code use fast checks for inheritance (no text lookups when
// possible)
// isSubclassOf no longer requires ::_classinfo()
// 
// 54    10/18/98 3:22a Jimdose
// Added code for timing paths
// 
// 53    10/17/98 12:22a Jimdose
// made it so paths could be saved in savegames
// 
// 52    10/14/98 10:57p Jimdose
// mapname is now passed into PathSearch::Init
// 
// 51    10/14/98 5:21p Markd
// Added jumping capabilities to the path nodes
// 
// 50    9/18/98 10:58p Jimdose
// Started on swimming actors
// 
// 49    9/14/98 5:39p Jimdose
// NearestNode now requires that you pass in the entity that is going to use
// the path.
// NearestNode no longer hard codes the size when testing moves
// Added ai_shownodenums
// Revamped tests for valid paths.  Actors get stuck much less often.
// Made DrawAllConnections more usefull.
// ClearPathTo now uses binary search for finding the max height of a path.
// Upped version number
// Added FindEntities to fixup door entity numbers when loading pathfiles
// 
// 48    9/08/98 9:50p Jimdose
// Enabled multi-size bounding box path code
// Got rid of skipstaticnodes
// Fixed bug with AI_ResetNodes where it never freed the nodes
// Added version checking to path file
// changed granularity of size info in paths from 16 to 8
// path loading code now autosaves the pathnodes when the file version is wrong
// 
// 47    9/03/98 9:11p Jimdose
// made path code aware of doors
// don't save out paths if an error occured while reading the paths
// 
// 46    8/29/98 9:44p Jimdose
// Added call info to G_Trace
// 
// 45    8/26/98 11:14p Jimdose
// Fixed off by 1 error in AI_GetNode and AI_RemoveNode
// Made path tests check for startsolid in traces
// 
// 44    8/24/98 6:58p Jimdose
// Added array of heights for each width that a path supports
// 
// 43    8/19/98 7:57p Jimdose
// Began support for ladder and jump nodes
// 
// 42    8/18/98 10:01p Jimdose
// Separated checks for connection from checks for near nodes so that non-door
// nodes will not connect to nodes through doors
// 
// 41    8/16/98 12:58a Jimdose
// Off by one error in AI_FindNode. doh!
// 
// 40    8/15/98 5:33p Jimdose
// I made AI_FindNode use ai_maxnode instead of MAX_PATHNODES
// 
// 39    7/31/98 8:09p Jimdose
// Script commands now include flags to indicate cheats and console commands
// 
// 38    7/26/98 5:36a Jimdose
// ai_maxnodes now incremented
// added occupiedTime
// 
// 37    7/26/98 4:07a Jimdose
// Added animnames, targetnames, angles, etc. to archive
// 
// 36    7/26/98 2:41a Jimdose
// Path files moved to maps directory
// Path files now contain full connection information to improve load times
// 
// 35    7/25/98 2:10a Jimdose
// Removed square root calculation from NearestNode
// Preparing for door nodes
// 
// 34    7/19/98 8:27p Jimdose
// Made DrawAllConnections check if the node is in the pvs before drawing it
// 
// 33    6/17/98 10:12p Jimdose
// Fixed height bug in ClearPathTo
// 
// 32    6/17/98 3:03p Markd
// Changed NumArgs back to previous behavior
// 
// 31    6/13/98 8:23p Jimdose
// Removed ai_trainlevel cvar
// Made search algorithm into it's own class
// Added maxwidth and maxheight to paths
// 
// 30    6/10/98 7:53p Markd
// Made NumArgs behave correctly like argc
// 
// 29    6/09/98 5:32p Jimdose
// added ai_maxnode
// 
// 28    6/04/98 10:48p Jimdose
// Fixed a bunch of things that got broken just in time for E3.  Paths and
// scripting actually work now.
// 
// 27    5/27/98 5:11a Jimdose
// working on ai
// 
// 26    5/25/98 7:51p Jimdose
// Made archive functions use AI_GetNode to get each node in the level
// 
// 25    5/25/98 5:30p Jimdose
// Pathnodes are no longer a subclass of Entity.  This was done to save on
// edicts
// 
// 24    5/24/98 8:46p Jimdose
// Made a lot of functions more str-friendly.
// Got rid of a lot of char * based strings
// Cleaned up get spawn arg functions and sound functions
// 
// 23    5/24/98 1:03a Jimdose
// Removed unused variable
// 
// 22    5/22/98 9:37p Jimdose
// Made paths check through doors
// 
// 21    5/18/98 8:14p Jimdose
// Renamed Navigator back to PathManager
// 
// 20    5/14/98 10:18p Jimdose
// Remove ai_shownodes
// No longer uses eon model
// Added UpdateNode for moving nodes
// 
// 19    5/13/98 4:47p Jimdose
// RemoveFromGrid now disconnects node from other nodes
// enabled ClearNodes
// 
// 18    5/09/98 9:48p Jimdose
// gi.FindFile was failing because it prepended the gamename to the filename.
// Changed it to a fopen
// 
// 17    5/09/98 8:03p Jimdose
// Added automatic path saving and loading
// 
// 16    5/08/98 2:51p Jimdose
// Worked on archiving
// 
// 15    5/07/98 10:43p Jimdose
// added archiving
// 
// 14    5/03/98 4:43p Jimdose
// changed Vector class
// 
// 13    4/29/98 5:18p Jimdose
// Added ai_showroutes
// 
// 12    4/27/98 6:09p Jimdose
// Changed alpha on debug lines
// 
// 11    4/27/98 4:11p Jimdose
// nodes are now stored in a 2d grid allowing for more effiecient nearestnode
// queries.
// 
// 10    4/20/98 5:44p Jimdose
// working on ai
// 
// 9     4/20/98 2:45p Jimdose
// working on ai
// 
// 8     4/18/98 4:06p Jimdose
// Working on ai
// 
// 7     4/18/98 3:01p Jimdose
// Working on ai
// 
// 6     4/16/98 3:15p Jimdose
// ClearOPEN and ClearCLOSED now clear OPEN and CLOSED respectively.  This was
// the cause of the exit crash
// 
// 5     4/16/98 2:07p Jimdose
// Major rewrite
// Cleaned up code a lot
// PathSearch uses premade adjacency map
// 
// 4     4/07/98 11:55p Jimdose
// Changed beams to specify color
// 
// 3     3/23/98 1:31p Jimdose
// Revamped event and command system
// 
// 2     3/02/98 5:44p Jimdose
// Continued development.  Now use Path class to represent finished paths.
// 
// 1     2/25/98 2:27p Jimdose
// 
// 9     2/21/98 1:07p Jimdose
// Updated for Q2 dlls
// 
// 7     12/06/97 6:32p Jimdose
// Further evolution on path code.
// 
// 6     11/17/97 5:26p Jimdose
// Added step up and step down values to call to testSlideMove.
// 
// 5     11/12/97 2:11p Jimdose
// Simplified the interface to PathSearch
// 
// 4     11/07/97 6:39p Jimdose
// More work on integrating with Sin
// 
// 3     11/05/97 4:00p Jimdose
// More work converting to work with Sin.
// 
// 2     9/26/97 6:14p Jimdose
// Added standard Ritual headers
//
// DESCRIPTION:
// C++ implementation of the A* search algorithm.
// 

#include "g_local.h"
#include "navigate.h"
#include "path.h"
#include "misc.h"
#include "doors.h"

#define PATHFILE_VERSION 4

Event EV_AI_SavePaths( "ai_savepaths", EV_CHEAT );
Event EV_AI_SaveNodes( "ai_save", EV_CHEAT );
Event EV_AI_LoadNodes( "ai_load", EV_CHEAT );
Event EV_AI_ClearNodes( "ai_clearnodes", EV_CHEAT );
Event EV_AI_RecalcPaths( "ai_recalcpaths", EV_CHEAT );
Event EV_AI_CalcPath( "ai_calcpath", EV_CHEAT );
Event EV_AI_DisconnectPath( "ai_disconnectpath", EV_CHEAT );
Event EV_AI_SetNodeFlags( "ai_setflags", EV_CHEAT );

cvar_t	*ai_createnodes = NULL;
cvar_t	*ai_showpath;
cvar_t	*ai_debugpath;
cvar_t	*ai_debuginfo;
cvar_t	*ai_showroutes;
cvar_t   *ai_shownodenums;
cvar_t   *ai_timepaths;

static Entity	*IgnoreObjects[ MAX_EDICTS ];
static int		NumIgnoreObjects;

static PathNode *pathnodes[ MAX_PATHNODES ];
static qboolean pathnodesinitialized = false;
static qboolean loadingarchive = false;
int ai_maxnode;

#define	MASK_PATHSOLID		(CONTENTS_SOLID|CONTENTS_MONSTERCLIP|CONTENTS_WINDOW|CONTENTS_FENCE)

PathSearch PathManager;

int path_checksthisframe;

PathNode *AI_FindNode
	(
	const char *name
	)

	{
	int i;

	if ( !name )
		{
		return NULL;
		}

	if ( name[ 0 ] == '!' )
		{
		name++;
      return AI_GetNode( atof( name ) );
		}

	if ( name[ 0 ] == '$' )
		{
		name++;
		}

	for( i = 0; i <= ai_maxnode; i++ )
		{
		if ( pathnodes[ i ] && ( pathnodes[ i ]->TargetName() == name ) )
			{
			return pathnodes[ i ];
			}
		}

	return NULL;
	}

PathNode *AI_GetNode
	(
	int num
	)

	{
	if ( ( num < 0 ) || ( num > MAX_PATHNODES ) )
		{
		assert( false );
		return NULL;
		}

	return pathnodes[ num ];
	}

void AI_AddNode
	(
	PathNode *node
	)

	{
	int i;

	assert( node );

	for( i = 0; i < MAX_PATHNODES; i++ )
		{
		if ( pathnodes[ i ] == NULL )
			{
			break;
			}
		}

	if ( i < MAX_PATHNODES )
		{
		if ( i > ai_maxnode )
			{
			ai_maxnode = i;
			}
		pathnodes[ i ] = node;
		node->nodenum = i;
		return;
		}

	gi.error( "Exceeded MAX_PATHNODES!\n" );
	}

void AI_RemoveNode
	(
	PathNode *node
	)

	{
	assert( node );
	if ( ( node->nodenum < 0 ) || ( node->nodenum > ai_maxnode ) )
		{
		assert( false );
		gi.error( "Corrupt pathnode!\n" );
		}

	// If the nodenum is 0, the node was probably removed during initialization
	// otherwise, it's a bug.
	assert( ( pathnodes[ node->nodenum ] == node ) || ( node->nodenum == 0 ) );
	if ( pathnodes[ node->nodenum ] == node )
		{
		pathnodes[ node->nodenum ] = NULL;
		}
	}

void AI_ResetNodes
	(
	void
	)
	
	{
	int i;

	if ( !pathnodesinitialized )
		{
		memset( pathnodes, 0, sizeof( pathnodes ) );
		pathnodesinitialized = true;
		}
	else
		{
		for( i = 0; i < MAX_PATHNODES; i++ )
			{
			if ( pathnodes[ i ] )
				{
				delete pathnodes[ i ];
				}
			}
		}

	ai_maxnode = 0;
	}

/*****************************************************************************/
/*SINED info_pathnode (1 0 0) (-24 -24 0) (24 24 32) FLEE DUCK COVER DOOR JUMP LADDER

FLEE marks the node as a safe place to flee to.  Actor will be removed when it reaches a flee node and is not visible to a player.

DUCK marks the node as a good place to duck behind during weapon fire.

COVER marks the node as a good place to hide behind during weapon fire.

DOOR marks the node as a door node.  If an adjacent node has DOOR marked as well, the actor will only use the path if the door in between them is unlocked.

JUMP marks the node as one to jump from when going to the node specified by target.
"target" the pathnode to jump to.

/*****************************************************************************/

CLASS_DECLARATION( Listener, PathNode, "info_pathnode" );

Event EV_Path_FindChildren( "findchildren" );
Event EV_Path_FindEntities( "findentities" );

ResponseDef PathNode::Responses[] =
	{
		{ &EV_Path_FindChildren,      ( Response )PathNode::FindChildren },
      { &EV_Path_FindEntities,      ( Response )PathNode::FindEntities },
		{ NULL, NULL }
	};

static int			numNodes = 0;
static PathNode	*NodeList = NULL;

PathNode::PathNode()
	{
	nodenum = 0;
	if ( !loadingarchive )
		{
		// our archive function will take care of this stuff
		AI_AddNode( this );
		PostEvent( EV_Path_FindChildren, 0 );
		}

	occupiedTime = 0;

	nodeflags = G_GetIntArg( "spawnflags" );

	setOrigin( G_GetSpawnArg( "origin" ) );

	setangles = ( G_GetSpawnArg( "angle" ) || G_GetSpawnArg( "angles" ) );
	if ( setangles )
		{
		float angle;

		angle = G_GetFloatArg( "angle", 0 );
		setAngles( G_GetVectorArg( "angles", Vector( 0, angle, 0 ) ) );
		}

	animname = G_GetStringArg( "anim" );
	targetname = G_GetStringArg( "targetname" );
	target = G_GetStringArg( "target" );

	// crouch hieght
	setSize( "-24 -24 0", "24 24 40" );

	f = 0;
	h = 0;
	g = 0;

	inlist = NOT_IN_LIST;

	// reject is used to indicate that a node is unfit for ending on during a search
	reject = false;

	numChildren = 0;

	Parent	= NULL;
	NextNode = NULL;
	}

PathNode::~PathNode()
	{
	PathManager.RemoveNode( this );

	AI_RemoveNode( this );
	}

str &PathNode::TargetName
	(
	void
	)

	{
	return targetname;
	}

void PathNode::setAngles
	(
	Vector ang
	)

	{
	worldangles = ang;
	}

void PathNode::setOrigin
	(
	Vector org
	)

	{
	worldorigin = org;
   contents = gi.pointcontents( worldorigin.vec3() );
	}

void PathNode::setSize
	(
	Vector min,
	Vector max
	)

	{
	mins = min;
	maxs = max;
	}

EXPORT_FROM_DLL void PathNode::Setup
	(
	Vector pos
	)

	{
	CancelEventsOfType( EV_Path_FindChildren );

	setOrigin( pos );

	ProcessEvent( EV_Path_FindChildren );
	}

EXPORT_FROM_DLL void PathNode::Archive
	(
	Archiver &arc
	)

	{
	int i;

	arc.WriteInteger( nodenum );
	arc.WriteInteger( nodeflags );
	arc.WriteVector( worldorigin );
	arc.WriteVector( worldangles );
	arc.WriteBoolean( setangles );
	arc.WriteString( target );
	arc.WriteString( targetname );
	arc.WriteString( animname );

   arc.WriteFloat( occupiedTime );
   arc.WriteInteger( entnum );

	arc.WriteInteger( numChildren );
	for( i = 0; i < numChildren; i++ )
		{
		arc.WriteShort( Child[ i ].node );
		arc.WriteShort( Child[ i ].moveCost );
		arc.WriteRaw( Child[ i ].maxheight, sizeof( Child[ i ].maxheight ) );
		arc.WriteInteger( Child[ i ].door );
		}
	}

EXPORT_FROM_DLL void PathNode::FindEntities
   (
   Event *ev
   )

   {
   int i;
   Door *door;
   PathNode *node;

	for( i = 0; i < numChildren; i++ )
		{
      if ( Child[ i ].door )
         {
		   node = AI_GetNode( Child[ i ].node );

         assert( node );

         door = CheckDoor( node->worldorigin );
         if ( door )
            {