astarfind.cpp

vc写的源程序,是关于游戏类的程序。调用了系统的很多API

#include "AstarFind.h"

CAstarFind::CAstarFind(int *m, int w, int h)
{
	open = NULL;
	close = NULL;
	stack = NULL;
	map = m;
	width = w;
	height = h;
	tilecount = w * h;
	findok = FALSE;
	path.path = new POINT [tilecount + 1];
}

CAstarFind::~CAstarFind()
{
	FreeNodes();
	FreeStack();
	delete path.path;
}

void CAstarFind::FindPath(int sx, int sy, int dx, int dy)
{
	NODE *node, *bestnode;
	int destnum = GetTileNum(sx, sy);
	node = new NODE;
	node->g = 0;
	node->h = (dx - sx) * (dx - sx) + (dy - sy) * (dy - sy);
	node->f = node->g + node->h;
	node->x = dx;
	node->y = dy;
	node->number = GetTileNum(dx, dy);
	node->parent = NULL;
	node->next = NULL;
	for (int i = 0; i < 8; i++)
		node->child[i] = NULL;
	open = node;
	while(TRUE)
	{
		bestnode = ReturnBestNode();
		if (bestnode == NULL)
		{
			findok = FALSE;
			break;
		}
		else if (bestnode->number == destnum)
		{
			findok = TRUE;
			NODE *temp = bestnode;
			for (int i = 0; temp != NULL; i++, temp = temp->parent)
			{
 				path.path[i].x = temp->x;
				path.path[i].y = temp->y;
			}
			path.count = i;
			break;
		}
		CreateChild(bestnode, sx, sy);
	}
}

int CAstarFind::GetTileNum(int x, int y)
{
	return y * width + x;
}

int CAstarFind::GetTileType(int x, int y)
{
	return *(map + y * width + x);
}

NODE* CAstarFind::ReturnBestNode()
{
	NODE *temp;

	if (open == NULL)
		return NULL;
	temp = open;
	open = open->next;
	temp->next = close;
	close = temp;
	return temp;
}

void CAstarFind::CreateChild(NODE * b, int dx, int dy)
{
	int x, y;

	for (int i = 0; i < 8; i++)
		b->child[i] = NULL;
	// up - left
	if (GetTileType(x = b->x - 1, y = b->y - 1) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// up
	if (GetTileType(x = b->x, y = b->y - 1) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// up - right
	if (GetTileType(x = b->x + 1, y = b->y - 1) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// right
	if (GetTileType(x = b->x + 1, y = b->y) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// down - right
	if (GetTileType(x = b->x + 1, y = b->y + 1) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// down
	if (GetTileType(x = b->x, y = b->y + 1) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// down - left
	if (GetTileType(x = b->x - 1, y = b->y + 1) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
	// left
	if (GetTileType(x = b->x - 1, y = b->y) <= 0)
		if (x >= 0 && x < width && y >= 0 && y < height)
			_CreateChild(b, x, y, dx, dy);
}

void CAstarFind::_CreateChild(NODE * b, int x, int y, int dx, int dy)
{
	int i, snum = GetTileNum(x, y),
		g = b->g + 1;
	NODE *old;
	if ((old = CheckOPEN(snum)) != NULL)
	{
		for (i = 0; i < 8; i++)
			if (b->child[i] == NULL)
				break;
		b->child[i] = old;
		if (g < old->g)
		{
			old->parent = b;
			old->g = g;
			old->f = g + old->h;
		}
	}
	else if ((old = CheckOPEN(snum)) != NULL)
	{
		for (i = 0; i < 8; i++) 
			if (b->child[i] == NULL)
				break;	
		b->child[i] = old;
		if (g < old->g)
		{
			old->g = g;
	   	    old->f = g + old->h;
	   	    PropagateDown(old);
		}
	}
	else
	{
		NODE *succ = new NODE;
		succ->parent = b;
		succ->g = g;
		succ->h = (x - dx) * (x - dx) + (y - dy) * (y - dy);
		succ->f = g + succ->h;
		succ->x = x;
		succ->y = y;
		succ->number = snum;
		for (i = 0; i < 8; i++)
			succ->child[i] = NULL;
		Insert(succ);
		for (i = 0; i < 8; i++)
			if (b->child[i] == NULL)
				break;
		b->child[i] = succ;
	}
}

NODE* CAstarFind::CheckOPEN(int num)
{
	NODE *temp;
	temp = open;
	while(temp != NULL)
	{
		if (temp->number == num)
			return temp;
		temp = temp->next;
	}
	return temp;
}

NODE* CAstarFind::CheckCLOSE(int num)
{
	NODE *temp;
	temp = close;
	while(temp != NULL)
	{
		if (temp->number == num)
			return temp;
		temp = temp->next;
	}
	return temp;
}

void CAstarFind::Push(NODE * node)
{
	STACK *temp = new STACK;
	temp->node = node;
	temp->next = stack;
	stack = temp;
}

NODE* CAstarFind::Pop()
{
	STACK *tempS;
	NODE *tempN;
	tempS = stack;
	tempN = stack->node;
	stack = stack->next;
	free(tempS);
	return tempN;
}

void CAstarFind::PropagateDown(NODE * old)
{
   int c, g;
   NODE *child, *father;

   g = old->g;
   for (c = 0; c < 8; c++)
   {
	   if ((child = old->child[c]) == NULL)
		   break;
	   if (g + 1 < child->g)
	   {
		   child->g = g + 1;
		   child->f = child->g + child->h;
		   child->parent = old;
	       Push(child);
		}
   }

   while(stack->next != NULL)
   {
		father = Pop();
		for (c = 0; c < 8; c++)
		{
			if ((child = father->child[c]) == NULL)
				break;
			if (father->g + 1 < child->g)
			{
				child->g = father->g + 1;
				child->f = child->g + child->h;
				child->parent = father;
				Push(child);
			}
	   }
   }
}

void CAstarFind::Insert(NODE * succ)
{
   NODE *tmp1, *tmp2;
   int f;

   if (open == NULL)
   {
	   open = succ;
	   succ->next = NULL;
	   return;
   }

   f = succ->f;
   tmp1 = open;
   tmp2 = open->next;

   while((tmp2 != NULL) && (tmp2->f < f))
   {
	   tmp1 = tmp2;
       tmp2 = tmp2->next;
   }

   succ->next = tmp2;
   tmp1->next = succ;
}

void CAstarFind::FreeNodes()
{
	NODE *Node, *OldNode;

	if (open != NULL)
	{
		Node = open;
		while(Node != NULL)
		{
			OldNode = Node;
			Node = Node->next;
			free(OldNode);
		}
	}

	if (close != NULL)
	{
		Node = close;
		while(Node != NULL)
		{
			OldNode = Node;
			Node = Node->next;
			free(OldNode);
		}
	}

	open = close = NULL;
}

void CAstarFind::FreeStack()
{
	STACK *Temp;

	Temp = stack;
	while(Temp != NULL)
	{
		free(Temp->node);
		Temp = Temp->next;
	}
	stack = NULL;
}

BOOL CAstarFind::NewPath(int sx, int sy, int dx, int dy)
{
	if (GetTileNum(sx, sy) == GetTileNum(dx, dy))
	{
		findok = FALSE;
		return FALSE;
	}
	if (*(map + sy * width + sx) <= 0 && *(map + dy * width + dx) <= 0)
	{
		FreeNodes();
		FreeStack();
		FindPath(sx, sy, dx, dy);
		if (findok)
			return TRUE;
		return FALSE;
	}
	else
	{
		findok = FALSE;
		return FALSE;
	}
}