new_dll_astar.cpp

用vc开发的A*寻路算法的dll,可以在其他语言调用

// new_DLL_AStar.cpp : Defines the entry point for the DLL application.
//
#include <StdAfx.h>
#include <iostream.h>
#include <stdlib.h>
#include "A_Star.h"
 

int cols;
int rows;

struct SNode 
{ 
	int parentX;
	int parentY;
	bool isOpen;//该点是否开启
	bool isClose;//该点是否关闭
	int G;//沿路径从起始点到当前点的移动耗费
	int F;//G+H
};

SNode *node;

//初始化地图数组,
char *maps;
/*
char map2[13][13+1]={	    "ooooooooooooo",
							"os      ooooo",
							"o           o",
							"o           o",
							"o           o",
							"o           o",
							"o           o",
							"o           o",
							"o           o",
							"o  oooooooooo",
							"oo          o",
							"ooo        eo",
							"ooooooooooooo",};
*/

/*  0 1 2
    3   4 
	5 6 7   方向,根据方向得到周围的一个点,如果该方向上不存在点，则返回false*/
bool GetNearNode(int dir,int fromX,int fromY,int *toX,int *toY)
{
	int changeY[8]={-1,-1,-1,0,0,1,1,1};
	int changeX[8]={-1,0,1,-1,1,-1,0,1};
	*toX=fromX+changeX[dir];
	*toY=fromY+changeY[dir];
	if(*toX<0||*toX>cols-1||*toY<0||*toY>rows-1)
		return false;
	else
		return true;
}

//判断从fx,fy是否可以走过一个dir方向,比如:左边或上边被堵死的话，是不能到达左上角的
//该判断条件是可选的
bool CanGo(int dir,int fx,int fy) 
{
	if(dir==1||dir==3||dir==4||dir==6)
		return true;
	else
	{
		int changeY[8]={-1,-1,-1, 0, 0, 1, 1, 1};
		int changeX[8]={-1, 0, 1,-1, 1,-1, 0, 1};	
		//               0  1  2  3  4  5  6  7
		int temp1=fy*cols+(fx+changeX[dir]);
		int temp2=(fy+changeY[dir])*cols+fx;
		if ( maps[temp1]=='o' ||
			  maps[temp2]=='o' )
			return false;
		else
			return true;
	}
}

void SelectParent(int PX,int PY)
{
	int disToParent[8]={14,10,14,10,10,14,10,14};//8个方向上距离与父节点的距离
	int i,x,y;
	//首先检查周围已经打开的点，看看以Px,Py作为该点的父节点G会不会更低
		//在该循环中还做了查看是否已经找到目标的判断
	for(i=0;i<8;i++)
	{
		if(GetNearNode(i,PX,PY,&x,&y))//如果这个点不是超出边界
		{
			int tempNew=y*cols+x;
			int tempP=PY*cols+PX;
			if((maps[tempNew]==' ')&&CanGo(i,PX,PY))//如果目标点不是障碍物
			{
				if(node[tempNew].isOpen)//如果这个点是开着的
				{
					int tempG;
					tempG=node[tempNew].G+disToParent[i];
					if(tempG<node[tempP].G)//如果从这条路走更近的话
					{
						node[tempP].G=tempG;
						node[tempP].parentX=x;
						node[tempP].parentY=y;
					}
				};
			}	
		}
	}
}


void FindPath(int PX,int PY,int endX,int endY)
{
	int i,j;
	int x,y;
	int disToParent[8]={14,10,14,10,10,14,10,14};//8个方向上距离与父节点的距离

	int H;//从当前点到目标点的估计距离
	int tempP=PY*cols+PX;
	//遍历周围可用的点,试图找出最优点
	for(i=0;i<8;i++)
	{
		if(GetNearNode(i,PX,PY,&x,&y))//如果这个点不是超出边界
		{
			int tempNew=y*cols+x;
			if(maps[tempNew]==' ')//如果该点不是障碍物
			{
				if((!node[tempNew].isClose)&&CanGo(i,PX,PY))//如果没有关闭，并且可以到达
				{
					if(!node[tempNew].isOpen)//如果碰到的是一个没有打开的节点
					{
						node[tempNew].isOpen=true;//添加到打开列表	
						node[tempNew].parentX=PX;
						node[tempNew].parentY=PY;
						node[tempNew].G=node[tempP].G+disToParent[i];//计算当前点到起始点的移动耗费
						SelectParent(x,y);
					}
					H=abs(x-endX)*10+abs(y-endY)*10;
					node[tempNew].F=node[tempNew].G+H;
				}
				if(x==endX&&y==endY&&CanGo(i,PX,PY))
				{
					//cout<<"\n找到最终结果"<<endl;
					node[tempNew].parentX=PX;
					node[tempNew].parentY=PY;
					node[tempNew].G=node[tempP].G+disToParent[i];
					return;//找到最终结果
				}
			}
		}
	}
	//从所有的开启点中寻找一个F最小的点
	int minF=0; 
	int minX,minY;
	for(i=0;i<rows;i++)
	{
		for(j=0;j<cols;j++)
		{
			if(node[i*cols+j].isOpen==true&&node[i*cols+j].isClose==false)
			{
				if(minF==0)
				{
					minF=node[i*cols+j].F;
					minX=j;
					minY=i;
				}
				else
				{
					if(minF>node[i*cols+j].F)
					{
						minF=node[i*cols+j].F;
						minX=j;
						minY=i;
					}
				}
			}
		}
	}
	if(minF!=0)//如果找到了一个最优的点，则继续找从该点前往目标的路
	{
		node[minY*cols+minX].isClose=true;
		FindPath(minX,minY,endX,endY);
	}
}


//初始化所有的路点
void InitNode()
{
	if(node)free(node);
	node=new SNode[cols*rows];
	for(int i=0;i<rows;i++)
	{
		for(int j=0;j<cols;j++)
		{
			node[i*cols+j].G=0;
			node[i*cols+j].F=0;
			node[i*cols+j].isClose=false;
			node[i*cols+j].isOpen=false;
		}
	}
}



int  APIENTRY  SetMap(char *inputMaps,int inputRows,int inputCols)
{
	cols=inputCols;
	rows=inputRows; 
	if(maps)free(maps);
	maps=new char[cols*rows];
	int i,j;
	for(i=0;i<rows;i++)
		for(j=0;j<cols;j++)
		{
			if(inputMaps[i*cols+j]=='o')
			{
				maps[i*cols+j]='o';
			}
			else
				maps[i*cols+j]=' ';
		}
	return 1;
}

int  APIENTRY  FindWay(int fromPoint,int toPoint, int *outWay,int *outCount)
{
	int startX,startY;
	int endX,endY;
	startX=fromPoint%cols;
	startY=fromPoint/cols;
	endX=toPoint%cols;
	endY=toPoint/cols;
	InitNode();
	FindPath(startX,startY,endX,endY);
	int tempX,tempY,tempCount=0;
	tempX=endX;
	tempY=endY;
	if(node[endY*cols+endX].G!=0)
	{
		//计算有多少个
		while(!((tempX==startX)&&(tempY==startY)))
		{
			int temp;
			temp=tempY*cols+tempX;
			tempX=node[temp].parentX;
			tempY=node[temp].parentY;
			tempCount++;
		}
		*outCount=tempCount;
		//outWay=new int[tempCount];
		//输出
		tempX=endX;
		tempY=endY;
		while(!((tempX==startX)&&(tempY==startY)))
		{
			tempCount--;
			int temp;
			temp=tempY*cols+tempX;
			tempX=node[temp].parentX;
			tempY=node[temp].parentY;
			outWay[tempCount]=temp;
		}
		return 1;
	}
	else
		return 0;
}
/*
int main()
{
	char *m_map;
	int outway[256]={0};
	int outcount=0;
	int i,j;
	m_map=new char[13*13];
	for(i=0;i<13;i++)
	{
		for(j=0;j<13;j++)
		{
			m_map[i*13+j]=map2[i][j];
		}
	}
	SetMap(m_map,13,13);
	FindWay(1*13+1,11*13+11,outway,&outcount);

	cout<<outcount<<endl;
	for(i=0;i<outcount;i++)
	{
		cout<<outway[i]%13<<","<<outway[i]/13<<endl;
	}
	system("pause");
	return 0;
}

BOOL DllMain (HINSTANCE hinstDll, DWORD fdwReason, LPVOID lpvReserved) 
{
	switch (fdwReason) 
	{
		case DLL_PROCESS_ATTACH:
			break;

	}
	return(TRUE);
}
*/


BOOL APIENTRY DllMain( HANDLE hModule, 
                       DWORD  ul_reason_for_call, 
                       LPVOID lpReserved
					 )
{
	switch(ul_reason_for_call)
	{
	case DLL_PROCESS_DETACH:
		if(node)free(node);
		if(maps)free(maps);
		break;
	}
    return TRUE;
}