findpath.cpp

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

#include "FindPath.h"

int offset_x[] = {-1, 1, -1, 1, 0, -1, 1, 0};
int offset_y[] = {-1, -1, 1, 1, -1, 0, 0, 1};

CFindPath::CFindPath(int *m, int w, int h, int range1, int range2)
{
	// 为各变量赋初值
	Width = w;
	Height = h;
	Root = NULL;
	Stack1 = Stack2 = NULL;
	TileCount = w * h;
	FindOk = FALSE;
	DestNode = NULL;
	Step = 0;
	Path = NULL;
	Nodes = NULL;

	// 设置地图
	SetMap(m, range1, range2);
}

CFindPath::~CFindPath()
{
	if (Map)
		delete Map;
	if (MapBak)
		delete MapBak;
	FreeAll();
}

BOOL CFindPath::FindPath(int sx, int sy, int dx, int dy)
{
	memcpy(Map, MapBak, sizeof(int) * TileCount);
	FreeAll();
	if (GetTileType(sx, sy) != 0 && GetTileType(dx, dy) != 0)
		return FALSE;
	SrcPoint = GetTileNum(sx, sy);
	DestPoint = GetTileNum(dx, dy);
	Step = 2;
	// 建立根节点
	Root = new NODE;
	if (Root == NULL)
		return FALSE;
	Root->x = sx;
	Root->y = sy;
	Root->number = GetTileNum(sx, sy);
	for (int i = 0; i < 8; i++)
		Root->child[i] = NULL;
	LPSTACK s = new STACK;
	if (s == NULL)
	{
		delete Root;
		Root = NULL;
		return FALSE;
	}
	s->node = Root;
	s->next = NULL;
	Stack1 = s;
	while(Stack1)
	{
		if (CreateNode())
			return TRUE;
		// 交换堆栈
		LPSTACK s = Stack1;
		Stack1 = Stack2;
		Stack2 = s;
		Step++;
	}
	FindOk = FALSE;
	DestNode = NULL;
	return FALSE;
}

BOOL CFindPath::CreateNode()
{
	// 进行新一轮的扩展
	while(Stack1)
	{
		LPNODE n = Pop();
		if (CreateNode8(n))
		{
			GetPath();
			return TRUE;
		}
	}
	return FALSE;
}

void CFindPath::Push(LPNODE n)
{
	// 压入一个节点到Stack2
	LPSTACK s = new STACK;
	if (s == NULL)
		return;
	s->next = Stack2;
	s->node = n;
	Stack2 = s;
}

LPNODE CFindPath::Pop()
{
	// 从Stack1弹出一个节点
	LPSTACK s = Stack1;
	Stack1 = Stack1->next;
	LPNODE n = s->node;
	delete s;
	return n;
}

BOOL CFindPath::CreateNode8(LPNODE n)
{
	int x, y;
	int ii = 0;
	BOOL ok = FALSE;
	for (int i = 0; i < 8; i++)
	{
		x = n->x + offset_x[i];
		y = n->y + offset_y[i];
		if (x >= 0 && y >= 0 && x < Width && y < Height && GetTileType(x, y) == 0)
		{
			// 如果没有越界并且没有扩展过则建立节点
			LPNODE temp = new NODE;
			if (temp == NULL)
				return FALSE;
			temp->x = x;
			temp->y = y;
			temp->number = GetTileNum(x, y);
			temp->child[ii++] = temp;
			temp->parent = n;
			// 将该节点压入堆栈
			Push(temp);
			// 将该节点压入节点列表
			LPSTACK tempstack = new STACK;
			tempstack->node = temp;
			tempstack->next = Nodes;
			Nodes = tempstack;
			if (GetTileNum(x, y) == DestPoint)
			{
				FindOk = TRUE;
				DestNode = temp;
				return TRUE;
			}
			else
				// 标志扩展过的节点
				*GetTilePtr(x, y) = 1;
			ok = TRUE;
		}
	}
	/*
	if (!ok)
	{
	// 如果无路可走了,则走到最近的位置
	}
	*/
	return FALSE;
}

BOOL CFindPath::GetPath()
{
	if (FindOk)
	{
		// 如果上一次搜索成功,则获取路径
		LPNODE e = DestNode;
		for (int i = 0; i < Step; i++)
		{
			LPSTACK s = new STACK;
			s->node = e;
			s->next = Path;
			Path = s;
			e = e->parent;
		}
		return TRUE;
	}
	return FALSE;
}

void CFindPath::FreeAll()
{
	// 释放堆栈Stack1, Stack2, Path
	LPSTACK t;
	while(Stack1)
	{
		t = Stack1;
		Stack1 = Stack1->next;
		delete t;
	}
	Stack1 = NULL;
	while(Stack2)
	{
		t = Stack2;
		Stack2 = Stack2->next;
		delete t;
	}
	Stack2 = NULL;
	while(Path)
	{
		t = Path;
		Path = Path->next;
		delete t;
	}
	Path = NULL;
	FindOk = FALSE;
	// 释放宽度优先树
	while(Nodes)
	{
		LPSTACK s = Nodes;
		delete s->node;
		Nodes = Nodes->next;
		delete s;
	}
	Nodes = NULL;
}

BOOL CFindPath::PopPath(int & x, int & y)
{
	if (FindOk && Path != NULL)
	{
		// 如果条件符合,则从路径堆栈中弹出下一步
		x = Path->node->x;
		y = Path->node->y;
		LPSTACK temp = Path;
		Path = Path->next;
		delete temp;
		return TRUE;
	}
	return FALSE;
}

BOOL CFindPath::SetMap(int *m, int range1, int range2)
{
	// 设置地图
	Map = new int [TileCount];
	if (Map == NULL)
		return FALSE;
	MapBak = new int [TileCount];
	if (MapBak == NULL)
		return FALSE;
	int *p = Map, *p1 = m;
	for (int i = 0; i < TileCount; i++)
	{
		if (*p1 >= range1 && *p1 <= range2)
			*p++ = -3;
		else
			*p++ = 0;
		p1++;
	}
	memcpy(MapBak, Map, sizeof(int) * TileCount);
	return TRUE;
}