/* Global Structures */struct gtAStarNode{	/* This is used by the Open/Closed lists. */	int luiHofX; /* Manhatten. */	int luiGofX; /* Distance Travelled. */	unsigned char lucDirection;	/* Wheter or not the node is used or not. */	unsigned char lucUsed;	/* If this node is closed, than don't apply pathfinding	   on it since its already been done! */	unsigned char lucClosed;	/* This is used by the open list. */	unsigned short lusGridRelativeX;	unsigned short lusGridRelativeY;		unsigned short lusGridRealX;	unsigned short lusGridRealY;};

/* Helper: This helper procedure builds a node in both the open and closed lists. */void sAddNode(unsigned short lusGridRealX, unsigned short lusGridRealY,unsigned char lucDirection, int liDestinationCreature, unsigned char lucOverwrite){	int liX;	unsigned short lusRelativeGridX, lusRelativeGridY;	/* The first step is to make sure the path is valid.*/	if(lusGridRealX > 40000)	{		printf("ack");	}	if((fTileConditions(lusGridRealX,lusGridRealY) == flag_Walkable &&	   gaoMap[lusGridRealX + lusGridRealY*1500].loCreature == NULL) ||	   lucOverwrite == 1)	{		/* Calculate the relativity so that the nodes can be placed in respect to the		   21x17 grid. */		lusRelativeGridX = lusGridRealX -  gaoObjects[liDestinationCreature].lusGridX + 10;		lusRelativeGridY = lusGridRealY -  gaoObjects[liDestinationCreature].lusGridY + 8;				if(lusRelativeGridX > 300 || lusRelativeGridY > 300)		{			printf("Ahh NUTS");		}		/* First step is to build the node on the closed list. */		gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lucDirection = lucDirection;		switch(lucDirection)		{			case flag_AStarNoGo:				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].luiGofX = 0;			break;			case flag_AStarWest:				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].luiGofX = 1 +					gaoClosedList[lusRelativeGridX+1 + lusRelativeGridY*17].luiGofX;			break;			case flag_AStarEast:				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].luiGofX = 1 +					gaoClosedList[lusRelativeGridX-1 + lusRelativeGridY*17].luiGofX;			break;			case flag_AStarNorth:				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].luiGofX = 1 +					gaoClosedList[lusRelativeGridX + (lusRelativeGridY+1)*17].luiGofX;			break;			case flag_AStarSouth:				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].luiGofX = 1 +					gaoClosedList[lusRelativeGridX + (lusRelativeGridY-1)*17].luiGofX;			break;		}		gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].luiHofX = 			abs(lusRelativeGridX - 10) + 			abs(lusRelativeGridY - 6);				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lusGridRelativeX = lusRelativeGridX;		gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lusGridRelativeY = lusRelativeGridY;		gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lusGridRealX = lusGridRealX;		gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lusGridRealY = lusGridRealY;		gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lucUsed = 1;		/* Ok, now copy this over to the open list. */		for(liX=0;liX<21*17;liX++)			if(gaoOpenList[liX].lucUsed == 0)			{				gaoOpenList[liX] = gaoClosedList[lusRelativeGridX + lusRelativeGridY*17];				gaoClosedList[lusRelativeGridX + lusRelativeGridY*17].lucClosed = 1;				break;			}		/* All done. =) */	}}

/* Helper [Recursive]: This helper function counts the number of elements in a path. */void sHelperReverseMovePath(unsigned short lusGridX, unsigned short lusGridY, int liRecursionCount, int liLength, int liSourceObject){	if(liLength-liRecursionCount-1 >= 0)	{		if(liLength-liRecursionCount-1 < 0) printf("DAMAGE");		gaoObjects[liSourceObject].lacPathFinding[liLength-liRecursionCount-1] =			gaoClosedList[lusGridX + lusGridY * 17].lucDirection;	}	liRecursionCount++;	switch(gaoClosedList[lusGridX + lusGridY * 17].lucDirection)	{		case flag_AStarNoGo:			return;		break;		case flag_AStarWest:			sHelperReverseMovePath((unsigned short)(lusGridX+1), lusGridY,liRecursionCount,liLength,liSourceObject);		break; 		case flag_AStarEast:			sHelperReverseMovePath((unsigned short)(lusGridX-1), lusGridY, liRecursionCount,liLength,liSourceObject);		break;		case flag_AStarNorth:			sHelperReverseMovePath(lusGridX, (unsigned short)(lusGridY+1), liRecursionCount,liLength,liSourceObject);		break;		case flag_AStarSouth:			sHelperReverseMovePath(lusGridX, (unsigned short)(lusGridY-1), liRecursionCount,liLength,liSourceObject);		break;	}}/* Helper [Recursive]: This helper function counts the number of elements in a path. */int fHelperFindElements(unsigned short lusGridX, unsigned short lusGridY){	switch(gaoClosedList[lusGridX + lusGridY * 17].lucDirection)	{		case flag_AStarNoGo:			return 0;		break;		/* Note that the directions are reversed since we are working		   backgrounds (See the A* descriptions if forgotten). */		case flag_AStarWest:			return 1 + fHelperFindElements((unsigned short)(lusGridX+1), lusGridY);		break;		case flag_AStarEast:			return 1 + fHelperFindElements((unsigned short)(lusGridX-1), lusGridY);		break;		case flag_AStarNorth:			return 1 + fHelperFindElements(lusGridX, (unsigned short)(lusGridY+1));		break;		case flag_AStarSouth:			return 1 + fHelperFindElements(lusGridX, (unsigned short)(lusGridY-1));		break;	}	/* If this occurs, than there is a problem with the A* implementation. */	printf("The A* algorithm encountered an error.");	return 0;}

/* This procedure generates the path for a monster trying to reach a grid X,Y. If it cannot   generate the path, it returns zero, else it returns 1. */int fGeneratePath(int liSourceCreature, int liDestinationCreature){	int liX, liFValue,liFLocation, liRecursionCount=0, liAttempt = 0;	unsigned short lusGridRealX, lusGridRealY;	unsigned short lusGridRelativeX, lusGridRelativeY;	/* First step is to clear the pathfinding buffers. */	memset(gaoOpenList, 0, 21*17*sizeof(struct gtAStarNode));	memset(gaoClosedList, 0, 21*17*sizeof(struct gtAStarNode));	/* Step 1: Find the spawning point relative to the destination creature:	           the destination is always the middle of the rectangle. */	sAddNode(gaoObjects[liSourceCreature].lusGridX,			 gaoObjects[liSourceCreature].lusGridY,			 flag_AStarNoGo, liDestinationCreature,1);	/* Until we either run out of spaces, or we finally find the player, continue calculating. ;D */	while(liAttempt != 500)	{		liAttempt++;				/* Find the lowest F value. */		liFValue = 99999;		for(liX=0;liX<21*17;liX++)			if(gaoOpenList[liX].lucUsed == 1 && gaoOpenList[liX].lucClosed == 0)			{				if(gaoOpenList[liX].luiGofX + gaoOpenList[liX].luiHofX <= liFValue)				{					liFValue = gaoOpenList[liX].luiGofX + gaoOpenList[liX].luiHofX;					liFLocation = liX;				}			}			else if(gaoOpenList[liX].lucUsed == 0)			{				break;			}		/* Now, lets extract the components of the location, and from it, compute the costs to		   go in each direction. */		lusGridRealX = gaoOpenList[liFLocation].lusGridRealX;		lusGridRealY = gaoOpenList[liFLocation].lusGridRealY;		lusGridRelativeX = gaoOpenList[liFLocation].lusGridRelativeX;		lusGridRelativeY = gaoOpenList[liFLocation].lusGridRelativeY;		gaoOpenList[liFLocation].lucClosed = 1;		if(lusGridRealX >40000 || lusGridRealY > 40000)		{			printf("Ahh hell");		}		/* Build four more adjacent paths (If there is room) */		if(lusGridRelativeX-1 >= 0 && gaoClosedList[lusGridRelativeX-1 + lusGridRelativeY*17].lucClosed == 0)		{			if(lusGridRelativeX-1 == 10 && lusGridRelativeY == 8)				{sAddNode((short)(lusGridRealX-1),lusGridRealY,flag_AStarWest,liDestinationCreature,1);}			else				{sAddNode((short)(lusGridRealX-1),lusGridRealY,flag_AStarWest,liDestinationCreature,0);}		}		if(lusGridRelativeX+1 < 21 && gaoClosedList[lusGridRelativeX+1 + lusGridRelativeY*17].lucClosed == 0)		{			if(lusGridRelativeX+1 == 10 && lusGridRelativeY == 8)				{sAddNode((short)(lusGridRealX+1),lusGridRealY,flag_AStarEast,liDestinationCreature,1);}			else				{sAddNode((short)(lusGridRealX+1),lusGridRealY,flag_AStarEast,liDestinationCreature,0);}		}		if(lusGridRelativeY-1 >= 0 && gaoClosedList[lusGridRelativeX + (lusGridRelativeY-1)*17].lucClosed == 0)		{			if(lusGridRelativeX == 10 && lusGridRelativeY-1 == 8)				{sAddNode(lusGridRealX,(short)(lusGridRealY-1),flag_AStarNorth,liDestinationCreature,1);}			else				{sAddNode(lusGridRealX,(short)(lusGridRealY-1),flag_AStarNorth,liDestinationCreature,0);}		}		if(lusGridRelativeY+1 < 17 && gaoClosedList[lusGridRelativeX + (lusGridRelativeY+1)*17].lucClosed == 0)		{			if(lusGridRelativeX == 10 && lusGridRelativeY+1 == 8)				{sAddNode(lusGridRealX,(short)(lusGridRealY+1),flag_AStarSouth,liDestinationCreature,1);}			else				{sAddNode(lusGridRealX,(short)(lusGridRealY+1),flag_AStarSouth,liDestinationCreature,0);}		}		/* If the destination node has been written to, than we KNOW the pathfinding is completed. */		if(gaoClosedList[10+8*17].lucClosed == 1)		{			/* Ok, because the list is backwards (Hehehe), we gotta know a few things. First of all,			   if we know the number of elements that composes the list, we can place the path into			   the creature's path list without the need of a buffer (This is a good idea), so lets			   do that. */			sHelperReverseMovePath(10,8,0,fHelperFindElements(10,8),liSourceCreature);			return 1;		}		/* Instead of letting this thing search continously, lets check if we're all out of spots. */		else if(gaoOpenList[17*21-1].lucClosed == 1)		{			/* Well, this is a sad day for this monster. It cannot find his player. =( */			printf("Unable to find a path. \n");			return 0;		}	}	/* Step 4, work backwords and get the path to the user. */	return 0;}

#ifndef PATHFINDING_H_INCLUDED#define PATHFINDING_H_INCLUDEDnamespace AI{	public ref struct Waypoint	{		inline Waypoint () :		x(0),		y(0)		{}		inline Waypoint ( Waypoint^ point ) :		x(point->x),		y(point->y)		{}		inline Waypoint ( unsigned int x, unsigned int y ) :		x(x),		y(y)		{		}		Waypoint^ operator = ( Waypoint^ point )		{			x = point->x;			y = point->y;			return this;		}		unsigned int	x;		unsigned int	y;	};	ref struct PathNode	{		inline PathNode () :		walkable	(1),		list		(0)		{		}		char			walkable;		unsigned int	movementcost;		unsigned int	estimatecost;		unsigned int	totalcost;		unsigned int	parent;		unsigned int	list;	};	ref class PathMap;	public ref class PathFinder	{	public:		inline PathFinder () :		pathmap(nullptr)		{			waypoints = nullptr;		}		inline PathFinder ( PathMap^ map ) :		pathmap(map)		{			waypoints = nullptr;		}		void LoadWaypoints( array<Waypoint^>^ points )		{			waypoints = points;		}		void SelectMap ( PathMap^ map )		{			pathmap = map;		}		bool FindPath ( Waypoint^ a, Waypoint^ b );		void SetWaypoint ( unsigned int i, Waypoint point )		{			if ( !waypoints ) return;			waypoints->x = point.x;			waypoints->y = point.y;		}		Waypoint^ GetWaypoint ( unsigned int i )		{			if ( waypoints == nullptr ) // this line causes the app to stall sometimes?!?!? stupid MSVS 2005 .net crap				return nullptr;			if ( i > waypoints->Length )				return nullptr;					return waypoints;		}		unsigned int NumWaypoints ()		{			return waypoints->Length;		}			private:		PathMap^			pathmap;		array<Waypoint^>^	waypoints;	};	public ref class PathMap	{	public:		inline PathMap ( unsigned int width, unsigned int height ) :		width	(width),		height	(height),		open	(0),		closed	(width*height)		{			unsigned int size = width * height;			map		= gcnew array<PathNode^>(size);			list	= gcnew array<int>(size+1);			for ( unsigned int i=0; i<size; ++i )				map = gcnew PathNode();		}		void GetDimensions ( unsigned int^ w, unsigned int^ h )		{			if ( w ) *w = width;			if ( h ) *h = height;		}		void SetNodeBlock ( unsigned int x, unsigned int y, bool large )		{			if ( x >= width || y >= height ) return;			map[x + y * width]->walkable	= large ? 0: 2;		}		void SetNodeWalkable ( unsigned int x, unsigned int y )		{			map[x + y * width]->walkable	= 1;		}		bool FindPath ( PathFinder^ pathfinder, Waypoint^ a, Waypoint^ b )		{			if ( !pathfinder ) return false;			//unsigned int node = 0;			unsigned int x;			unsigned int y;			unsigned int cost;			finder	= pathfinder;			start	= a->x + a->y * width;			target	= b->x + b->y * width;			if ( start < 0  || start  >= width*height ) return false;			if ( target < 0 || target >= width*height ) return false;			if ( map[target]->walkable == 0 ) return false;			AddToOpenList(start);			do			{				current = list[1];				// are we adjacent to our target				cost = GetMovementCost(current, target);				if ( cost != 100 )				{					x = current % width;					y = (current-x) / width;					unsigned int tx = target % width;					unsigned int ty = (target-tx) / width;					x = x > tx ? x-tx: tx-x;					y = y > ty ? y-ty: ty-y;					if ( x*x + y*y <= 2 )					{						if ( cost == 10 ) 							return SetFinderPath();						// may not be able to move diagonally						else 						{							int delta = target - current;							if ( delta > 0 )							{								if ( map[target-width]->walkable >= 1 )								{									if ( delta > width )									{										if ( map[target-1]->walkable >= 1 )											return SetFinderPath();									}									else									{										if ( map[target+1]->walkable >= 1 )											return SetFinderPath();									}								}							}							else							{								if ( map[target+width]->walkable >= 1 )								{									if ( delta > -width )									{										if ( map[target-1]->walkable >= 1 )											return SetFinderPath();									}									else									{										if ( map[target+1]->walkable >= 1 )											return SetFinderPath();									}								}							}						}					}				}				x = current % width;				y = (current-x) / width;				if ( x == 0 )				{					AddToOpenList(current + 1);					if ( y > 0 )					{						AddToOpenList(current - width);						if ( map[current - width]->walkable >= 1 )							if ( map[current + 1]->walkable >= 1 )								AddToOpenList(current - width + 1);					}					if ( y < height-1 )					{						AddToOpenList(current + width);						if ( map[current + width]->walkable >= 1 )							if ( map[current + 1]->walkable >= 1 )								AddToOpenList(current + width + 1);					}				}				else if ( x == width-1 )				{					AddToOpenList(current - 1);					if ( y > 0 )					{						AddToOpenList(current - width);						if ( map[current - width]->walkable >= 1 )							if ( map[current - 1]->walkable >= 1 )								AddToOpenList(current - width - 1);					}					if ( y < height-1 )					{						AddToOpenList(current + width);						if ( map[current + width]->walkable >= 1 )							if ( map[current - 1]->walkable >= 1 )								AddToOpenList(current + width - 1);					}				}				else				{					AddToOpenList(current + 1);					AddToOpenList(current - 1);					if ( y > 0 )					{						AddToOpenList(current - width);						if ( map[current - width]->walkable >= 1 )						{							if ( map[current - 1]->walkable >= 1 )								AddToOpenList(current - width - 1);														if ( map[current + 1]->walkable >= 1 )								AddToOpenList(current - width + 1);						}					}					if ( y < height-1 )					{						AddToOpenList(current + width);												if ( map[current + width]->walkable >= 1 )						{							if ( map[current - 1]->walkable >= 1 )								AddToOpenList(current + width - 1);							if ( map[current + 1]->walkable >= 1 )																AddToOpenList(current + width + 1);						}					}				}				RemoveFromOpenList(current);				AddToClosedList(current);			} while ( open > 0 );			CleanUpClosedList();			return false;		}				void Randomize ()		{		}		void ProcessIslands ()		{		}		void Save ( System::String^ file )		{		}		void Load ( System::String^ file )		{		}	private:		void AddToOpenList ( unsigned int node )		{			if ( node < 0 || node >= width*height ) return;			if ( map[node]->walkable == 0 || map[node]->walkable == 2 ) return;			if ( map[node]->list > 0 )			{				if ( map[node]->list < open )				{					unsigned int movementcost = map[current]->movementcost + GetMovementCost(current, node);					if ( movementcost < map[node]->movementcost )					{						map[node]->movementcost	= movementcost;						map[node]->totalcost	= map[node]->estimatecost + movementcost;						map[node]->parent		= current;						unsigned int i			= map[node]->list;						unsigned int j			= i / 2;						while ( true )						{							if ( map[list]->totalcost < map[list[j]]->totalcost )							{								// swap list index								map[list]->list ^= map[list[j]]->list;								map[list[j]]->list ^= map[list]->list;								map[list]->list ^= map[list[j]]->list;								// swap positions in list								list ^= list[j];								list[j] ^= list;								list ^= list[j];								// are we at the top of the list?								if ( j == 1 ) break;								i = j;								j = j / 2;							}							else break;						}					}				}				return;			}			open++;						list[open]			= node;			map[node]->list		= open;						if ( open == 1 )			{				// start node has itself as parent				map[node]->parent		= node;				map[node]->movementcost	= 0;				map[node]->estimatecost	= 0;				map[node]->totalcost	= 0;			}			else			{				map[node]->parent		= current;				map[node]->movementcost	= map[current]->movementcost + GetMovementCost(current, node);				map[node]->estimatecost	= GetEstimatedRemainingCost(node, target);				map[node]->totalcost	= map[node]->movementcost + map[node]->estimatecost;				unsigned int i			= open;				unsigned int j			= open / 2;				while ( true )				{					if ( map[list]->totalcost < map[list[j]]->totalcost )					{						// swap list index						map[list]->list ^= map[list[j]]->list;						map[list[j]]->list ^= map[list]->list;						map[list]->list ^= map[list[j]]->list;						// swap positions in list						list ^= list[j];						list[j] ^= list;						list ^= list[j];						// are we at the top of the list?						if ( j == 1 ) break;						i = j;						j = j / 2;					}					else break;				}			}		}		void RemoveFromOpenList ( unsigned int node )		{			if ( map[node]->list == 0 || map[node]->list > open ) return;			unsigned int i = map[node]->list;			unsigned int j = i;			unsigned int k;			// move the last node to the empty spot			list = list[open];			map[list]->list = i;			open--;			while ( true )			{				i = j;				k = 2*i;				if ( k+1 <= open )				{					if ( map[list]->totalcost > map[list[k]]->totalcost )	j = k;					if ( map[list[j]]->totalcost > map[list[k+1]]->totalcost )	j = k+1;				}				else if ( k <= open )				{					if ( map[list]->totalcost > map[list[k]]->totalcost )	j = k;				}				if ( i != j )				{					// swap list index					map[list]->list ^= map[list[j]]->list;					map[list[j]]->list ^= map[list]->list;					map[list]->list ^= map[list[j]]->list;					// swap positions in list					list ^= list[j];					list[j] ^= list;					list ^= list[j];				}				else break;			}		}		void AddToClosedList ( unsigned int node )		{			map[node]->list = closed;			list[closed]	= node;			closed--;		}		void CleanUpOpenList ()		{			for ( unsigned int i=0; i<=open; ++i )				map[list]->list = 0;			open	= 0;		}		void CleanUpClosedList ()		{			unsigned int size = width * height;			for ( unsigned int i=closed; i<=size; ++i )				map[list]->list = 0;			closed	= width * height;		}		unsigned int CountStepsToTarget ()		{			unsigned int steps	= 0;			unsigned int node	= target;			while ( node != start )			{ 				node = map[node]->parent;				steps++;			}			return steps;		}		unsigned int GetMovementCost ( unsigned int from, unsigned int to )		{			unsigned int d = from > to ? from-to: to-from;			if ( d == 1 || d == width ) return 10;			if ( d == width-1 || d == width+1 ) return 14;			// from-node and to-node are not adjacent			return 100;		}		unsigned int GetEstimatedRemainingCost ( unsigned int from, unsigned int to )		{			unsigned int x1 = from % width;			unsigned int y1 = (from-x1) / width;			unsigned int x2 = to % width;			unsigned int y2 = (to-x2) / width;			x1 = x1 > x2 ? x1-x2: x2-x1;			y1 = y1 > y2 ? y1-y2: y2-y1;			return (x1 < y1 ? 14 * x1 + 10 * (y1-x1): 14 * y1 + 10 * (x1-y1));		}		bool SetFinderPath ()		{			RemoveFromOpenList(current);			AddToClosedList(current);			AddToClosedList(target);			map[target]->parent = current;			current = target;			CleanUpOpenList();						unsigned int x;			unsigned int y;			unsigned int size = CountStepsToTarget();			array<Waypoint^>^ points = gcnew array<Waypoint^>(size);			for ( unsigned int i=0; i<size; ++i )			{				x = current % width;				y = (current-x) / width;				points[size-(i+1)] = gcnew Waypoint(x,y);				current = map[current]->parent;			}						finder->LoadWaypoints(points);			CleanUpClosedList();			finder = nullptr;			return true;		}		unsigned int			width;		unsigned int			height;		array<PathNode^>^		map;		unsigned int			start;		unsigned int			target;		unsigned int			current;		unsigned int			open;		unsigned int			closed;		array<int>^				list;		PathFinder^				finder;	};		bool PathFinder::FindPath ( Waypoint^ a, Waypoint^ b )	{		if ( !pathmap ) return false;		return pathmap->FindPath(this, a,b);	}} // AI#endif