findpath.cpp

最经典的A星寻路算法,自己写的,感觉很好!

#include "stdafx.h"
#include "FindPath.h"

List::List()
{
	head = NULL;
}

List::~List()
{
	Node	*temp;
	while (head->next != NULL)
	{
		temp = head->next;
		head->next = head->next->next;
		delete	temp;
		temp = NULL;
	}
	delete head;
	head = NULL;
}

bool	List::Empty()
{
	return	((head == NULL || head->next == NULL) ? true : false);
}

Node *	List::GetTop(POINT *pp)
{
	if (head->next != NULL)
	{
		pp->x = head->next->pos.x;
		pp->y = head->next->pos.y;
		return head->next;
	}
	return NULL;
}

void	List::Delete(POINT pp)
{
	Node	*h/*, *temp*/;
	h = head;
	while(h->next != NULL)
	{		
		if (h->next->pos.x == pp.x && h->next->pos.y == pp.y)
		{
//			temp = h->next;
			h->next = h->next->next;
//			delete	temp;
//			temp = NULL;
		}
		if (h->next != NULL)
		{
			h=h->next;
		}
	}
}

void	List::Insert(POINT pp, Node *fnode, int assess)
{
	Node	*newnode, *h, *front;
	newnode=(Node *)malloc(sizeof(Node));

	newnode->value = assess;
	newnode->pos.x = pp.x;
	newnode->pos.y = pp.y;
	newnode->father = fnode;

	if (assess == 0)
	{
		newnode->next = head->next;
		head->next = newnode;
	}
	else
	{
		h = head;
		while(h->next != NULL)
		{
			front = h;
			h = h->next;
			if (h->value > assess)
			{
				newnode->next = h;
				front->next = newnode;
				break;
			}else if (h->next == NULL)
			{
				h->next = newnode;
				newnode->next = NULL;
				break;
			}
		}// end while
	}
}

void	List::Insert(Node	*node)
{
/*	Node	*newnode;
	newnode=(Node *)malloc(sizeof(Node));

	newnode->next = node->next;
	newnode->value = node->value;
	newnode->pos.x = node->pos.x;
	newnode->pos.y = node->pos.y;
	newnode->father.x = node->father.x;
	newnode->father.y = node->father.y;*/

	if (head->next == NULL)
	{
		head->next = node;
		node->next = NULL;
	}
	else
	{
		node->next = head->next;
		head->next = node;
	}
}

bool	List::Exsit(POINT pp)
{
	Node	*h;
	h = head;
	while (h->next != NULL)
	{
		h=h->next;
		if (h->pos.x == pp.x && h->pos.y == pp.y)
			return	true;
	}
	return	false;
}

BOOL	List::GetParent(POINT *sonpos)
{
/*	Node	*h;
	h = head;
	while (h->next != NULL)
	{
		h = h->next;
		if (h->pos.x == sonpos->x && h->pos.y == sonpos->y)
		{
			sonpos->x = h->father.x;
			sonpos->y = h->father.y;
			return	true;
		}
	}*/
	return	false;
}

int		GetAssess(POINT	temppos, POINT startpos, POINT endpos)
{
	return int(abs(temppos.x - startpos.x) + abs(temppos.y - startpos.y)
		 + abs(temppos.x - endpos.x) + abs(temppos.y - endpos.y));
}

bool	Findpath(POINT start, POINT end)
{
	return false;
}