navigate.h

this keik game source

//-----------------------------------------------------------------------------
//
//  $Logfile:: /Quake 2 Engine/Sin/code/game/navigate.h                       $
// $Revision:: 42                                                             $
//   $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.h                            $
// 
// 42    11/18/98 7:47p Markd
// Allowed nearestnode to ignore entity bbox
// 
// 41    11/08/98 6:34p Jimdose
// added SetNodeFlagsEvent
// 
// 40    10/26/98 6:32p Jimdose
// added fulltest to CheckPath and ClearPathTo
// 
// 39    10/26/98 5:16p Jimdose
// Added CalcPath and DisconnectPath
// 
// 38    10/26/98 4:42p Jimdose
// added recalcpaths
// 
// 37    10/25/98 11:53p Jimdose
// added EXPORT_TEMPLATE
// 
// 36    10/18/98 3:22a Jimdose
// Added code for timing paths
// 
// 35    10/14/98 10:59p Jimdose
// map name is now passed into Init
// 
// 34    10/14/98 5:22p Markd
// Changed jumptarget to target
// 
// 33    9/22/98 12:49p Markd
// Put in archive and unarchive functions
// 
// 32    9/18/98 10:59p Jimdose
// Started on swimming actors
// 
// 31    9/14/98 5:40p 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
// Fixed definition of MAX_WIDTH (it was still multiplied by 2 from the way it
// used to work).
// 
// 30    9/08/98 9:51p Jimdose
// Changed NUM_PATHSPERNODE and NUM_WIDTH_VALUES
// Made CHECK_PATH use a granularity of 8 instead of 16
// 
// 29    9/03/98 9:12p Jimdose
// made paths aware of doors
// 
// 28    8/29/98 9:53p Jimdose
// moved prototype of SV_TestMovestep to g_phys.h
// 
// 27    8/24/98 6:58p Jimdose
// Added array of heights for each width that a path supports
// 
// 26    8/19/98 7:59p Jimdose
// Began adding support for ladder and jump nodes
// 
// 25    8/18/98 10:03p Jimdose
// Separated checks for connection from checks for near nodes so that non-door
// nodes will not connect to nodes through doors
// 
// 24    8/15/98 5:32p Jimdose
// Increased MAX_PATHNODES
// 
// 23    7/26/98 6:42a Jimdose
// Added entnum to pathnode
// 
// 22    7/26/98 5:37a Jimdose
// added occupiedTime
// 
// 21    7/26/98 2:41a Jimdose
// Path files moved to maps directory
// Path files now contain full connection information to improve load times
// 
// 20    7/25/98 2:10a Jimdose
// Preparing for door nodes
// 
// 19    7/17/98 8:34p Jimdose
// Fixed bug where CreatePath would overwrite the stack if the path was longer
// than MAX_PATH_LENGTH
// 
// 18    6/13/98 8:21p Jimdose
// Moved search algorithm to separate object - PathFinder
// Removed optimize path stuff
// Added maxwidth and maxheight to paths
// 
// 17    6/09/98 5:32p Jimdose
// added ai_maxnode
// 
// 16    5/27/98 5:11a Jimdose
// working on ai
// 
// 15    5/25/98 5:31p Jimdose
// Pathnodes are no longer a subclass of Entity.  This was done to save on
// edicts
// 
// 14    5/22/98 9:40p Jimdose
// Made paths check through Movers
// 
// 13    5/18/98 8:14p Jimdose
// Renamed Navigator back to PathManager
// 
// 12    5/14/98 10:26p Jimdose
// Added UpdateNode
// Made alot of info in PathNode private
// 
// 11    5/13/98 4:50p Jimdose
// Added use of SafePtrs
// 
// 10    5/09/98 8:04p Jimdose
// added path saving and loading
// PathSearch now a Listener instead of a Class object
// 
// 9     5/07/98 10:43p Jimdose
// added archiving
// 
// 8     4/29/98 5:39p Jimdose
// added ai_checkroutes
// 
// 7     4/27/98 5:27p Jimdose
// working on ai
// 
// 6     4/20/98 2:45p Jimdose
// working on ai
// 
// 5     4/18/98 3:02p Jimdose
// Added ai_createnodes and ai_showpath	
// working on ai
// 
// 4     4/16/98 2:10p Jimdose
// Major rewrite
// 
// 3     3/02/98 8:49p Jimdose
// Changed CLASS_PROTOTYPE to only take the classname
// 
// 2     3/02/98 5:44p Jimdose
// Continued development.  Now use Path class to represent finished paths.
// 
// 1     2/25/98 2:27p Jimdose
// 
// 8     2/21/98 1:07p Jimdose
// Updated for Q2 dlls
// 
// 6     12/06/97 6:32p Jimdose
// Further evolution on path code.
// 
// 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:
// Potentially could be an C++ implementation of the A* search algorithm, but
// is currently unfinished.
// 

#ifndef __NAVIGATE_H__
#define __NAVIGATE_H__

#include "g_local.h"
#include "class.h"
#include "entity.h"
#include "stack.h"
#include "container.h"
#include "doors.h"

extern Event EV_AI_SavePaths;
extern Event EV_AI_SaveNodes;
extern Event EV_AI_LoadNodes;
extern Event EV_AI_ClearNodes;
extern Event EV_AI_RecalcPaths;
extern Event EV_AI_CalcPath;
extern Event EV_AI_DisconnectPath;

extern cvar_t	*ai_createnodes;
extern cvar_t	*ai_showpath;
extern cvar_t	*ai_shownodes;
extern cvar_t	*ai_debugpath;
extern cvar_t	*ai_debuginfo;
extern cvar_t	*ai_showroutes;
extern cvar_t  *ai_timepaths;

extern int		ai_maxnode;

#define MAX_PATHCHECKSPERFRAME 4

extern int path_checksthisframe;

#define MAX_PATH_LENGTH		128		// should be more than plenty
#define NUM_PATHSPERNODE	16

class Path;
class PathNode;

#define NUM_WIDTH_VALUES	16
#define WIDTH_STEP			8
#define MAX_WIDTH				( WIDTH_STEP * NUM_WIDTH_VALUES )
#define MAX_HEIGHT			128

#define CHECK_PATH( path, width, height ) \
	( ( ( ( width ) >= MAX_WIDTH ) || ( ( width ) < 0 ) ) ? false : \
	( ( int )( path )->maxheight[ ( ( width ) / WIDTH_STEP ) - 1 ] < ( int )( height ) ) )

typedef struct
	{
	short			node;
	short			moveCost;
	byte			maxheight[ NUM_WIDTH_VALUES ];
	int			door;
	} pathway_t;

typedef enum { NOT_IN_LIST, IN_OPEN, IN_CLOSED } pathlist_t;

#define AI_FLEE		1
#define AI_DUCK		2
#define AI_COVER		4
#define AI_DOOR		8
#define AI_JUMP		16
#define AI_LADDER		32
#define AI_ACTION    64

void EXPORT_FROM_DLL DrawAllConnections( void );

class EXPORT_FROM_DLL PathNode : public Listener
	{
	public:
		PathNode			*chain;
		pathway_t		Child[ NUM_PATHSPERNODE ];	// these are the real connections between nodex
		int				numChildren;

		// These variables are all used during the search
		int				f;
		int				h;
		int				g;

		int				gridX;
		int				gridY;

		float				drawtime;
		float				occupiedTime;
		int				entnum;

		pathlist_t		inlist;
	
		// reject is used to indicate that a node is unfit for ending on during a search
		qboolean			reject;

		PathNode			*Parent;

		// For the open and closed lists
		PathNode			*NextNode;

		int				nodeflags;

		friend class   PathSearch;
		friend void		DrawAllConnections( void );

	private :
      qboolean       TestMove( Entity *ent, Vector start, Vector end, Vector &min, Vector &max, qboolean allowdoors = false, qboolean fulltest = false );

		qboolean			ConnectedTo( PathNode *node );
		void				ConnectTo( PathNode *node, byte maxheight[ NUM_WIDTH_VALUES ], float cost, Door *door = NULL );
		void				ConnectTo( PathNode *node, byte maxheight[ NUM_WIDTH_VALUES ] );
		void				Disconnect( PathNode *node );

		void				FindChildren( Event *ev );
      void           FindEntities( Event *ev );

	public:
      CLASS_PROTOTYPE( PathNode );

      int            contents;
		Vector			worldorigin;
		Vector			worldangles;
		Vector			mins;
		Vector			maxs;
		str				targetname;
		str				target;

		int				nodenum;

		qboolean			setangles;
		str				animname;

							PathNode();
							~PathNode();
		
		void				Setup( Vector pos );
		void				setAngles( Vector ang );
		void				setOrigin( Vector org );
		void				setSize( Vector min, Vector max );
		str				&TargetName( void );
		virtual void	Archive( Archiver &arc );
		virtual void	Unarchive( Archiver &arc );
		
		qboolean			CheckPath( PathNode *node, Vector min, Vector max, qboolean fulltest = true );
		Door				*CheckDoor( Vector pos );

      qboolean       CheckMove( Entity *ent, Vector pos, Vector &min, Vector &max, qboolean allowdoors = false, qboolean fulltest = false );
		qboolean			CheckMove( Vector pos, Vector min, Vector max );
		qboolean			ClearPathTo( PathNode *node, byte maxheight[ NUM_WIDTH_VALUES ], qboolean fulltest = true );
		qboolean			LadderTo( PathNode *node, byte maxheight[ NUM_WIDTH_VALUES ] );
		void				DrawConnections( void );
	};

//
// Exported templated classes must be explicitly instantiated
//
#ifdef EXPORT_TEMPLATE
template class EXPORT_FROM_DLL Stack<PathNode *>;
template class EXPORT_FROM_DLL SafePtr<PathNode>;
#endif
typedef SafePtr<PathNode> PathNodePtr;

#define PATHMAP_GRIDSIZE	32
#define PATHMAP_CELLSIZE	( 8192 / PATHMAP_GRIDSIZE )

#define PATHMAP_NODES		126			// 128 - sizeof( int ) / sizeof( short )

class EXPORT_FROM_DLL MapCell
	{
	private :
		int	numnodes;
		short	nodes[ PATHMAP_NODES ];

	public :
								MapCell();
								~MapCell();
		void					Init( void );
		qboolean				AddNode( PathNode *node );
		qboolean				RemoveNode( PathNode *node );
		PathNode				*GetNode( int index );
		int					NumNodes( void );
	};

class EXPORT_FROM_DLL PathSearch : public Listener
	{
	private:
		MapCell				PathMap[ PATHMAP_GRIDSIZE ][ PATHMAP_GRIDSIZE ];

		void					AddToGrid( PathNode *node, int x, int y );
		qboolean				RemoveFromGrid( PathNode *node, int x, int y );
		int					NodeCoordinate( float coord );
		int					GridCoordinate( float coord );
		void					ClearNodes( Event *ev );
		void					LoadNodes( Event *ev );
		void					SaveNodes( Event *ev );
		void					SavePathsEvent( Event *ev );
      void              SetNodeFlagsEvent( Event *ev );
		void					RecalcPathsEvent( Event *ev );
      void              CalcPathEvent( Event *ev );
      void              DisconnectPathEvent( Event *ev );

	public:
      CLASS_PROTOTYPE( PathSearch );

		void					Archive( Archiver &arc );
		void					Unarchive( Archiver &arc );
		void					AddNode( PathNode *node );
		void					RemoveNode( PathNode *node );
		void					UpdateNode( PathNode *node );
		MapCell				*GetNodesInCell( int x, int y );
		MapCell				*GetNodesInCell( Vector pos );
		PathNode				*NearestNode( Vector pos, Entity *ent = NULL, qboolean usebbox = true );
		void					Teleport( Entity *teleportee, Vector from, Vector to );
		void					ShowNodes( void );
		int					NumNodes( void );
		void					SavePaths( void );
		void					Init( const char *mapname );
	};

extern PathSearch PathManager;

#define MAX_PATHNODES 2048

PathNode *AI_FindNode( const char *name );
PathNode *AI_GetNode( int num );
void AI_AddNode( PathNode *node );
void AI_RemoveNode( PathNode *node );
void AI_ResetNodes( void );

#include "path.h"

template<class Heuristic>
class EXPORT_FROM_DLL PathFinder
	{
	private:
	   Stack<PathNode *>	stack;
	   PathNode				*OPEN;
	   PathNode				*CLOSED;
		PathNode				*endnode;

		void					ClearPath( void );
		void					ClearOPEN( void );
		void					ClearCLOSED( void );
		PathNode				*ReturnBestNode( void );
		void					GenerateSuccessors( PathNode *BestNode );
		void					Insert( PathNode *Successor );
		void					PropagateDown( PathNode *Old );
		Path					*CreatePath( PathNode *startnode );

	public:
		Heuristic			heuristic;

								PathFinder();
								~PathFinder<Heuristic>();
		Path					*FindPath( PathNode *from, PathNode *to );
		Path					*FindPath( Vector start, Vector end );
	};

template <class Heuristic>
PathFinder<Heuristic>::PathFinder()
	{
	OPEN   = NULL;
	CLOSED = NULL;
	}

template <class Heuristic>
PathFinder<Heuristic>::~PathFinder()
	{
	ClearPath();
	}

template <class Heuristic>
EXPORT_FROM_DLL void PathFinder<Heuristic>::ClearOPEN
	(
	void
	)

	{
	PathNode *node;

	while( OPEN )
		{
		node = OPEN;
		OPEN = node->NextNode;

		node->inlist = NOT_IN_LIST;
		node->NextNode = NULL;
		node->Parent = NULL;

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

template <class Heuristic>