pathshow.cpp

这又是一个路径探索算法

#include <vcl.h>
#include "path.cpp"

char map[100][100];
short disp[100][100];
short path[1000];
short map_h=30,map_w=45;
short m1=10,m2=6;
long OLimited=100;
long CLimited=100;
short startx,starty;
short endx,endy;
long mOpenCount;
long mCloseCount;

void popen();
void pclose();
void setting();
void setdefault();
void fpath(bool wdisp);
void draw(TImage *Image1);
/////////////////////////////////////
char mpossible(short x,short y)
{
  if (y<0||x<0||y>=map_h||x>=map_w) return 0;
  if (map[y][x]!=' ') return 0;
  return 1;
}
short judge(short x,short y)
{
  short dx=abs(x-endx);
  short dy=abs(y-endy);
  if (dx>dy) return dx*m1+dy*m2;
  return dx*m2+dy*m1;
}
class mypath:AstarPathFind
{
public:
  void set()
  {
    SetOpenLimited(OLimited);
    SetCloseLimited(CLimited);
    SetDirMask(0xff);
  }
  int myfind(bool wdisp)     // 重新写find函数以便加入些统计功能
  {                          // 大家用时不必自己写，还是用老的
        TAstarNode *root;
	int i,j,x,y,ok,dirs;
        unsigned long max=0;
	short MinJudge;
	static short incx[8]={ 0, 1, 1, 1, 0, -1, -1, -1 };
	static short incy[8]={ -1, -1, 0, 1, 1, 1, 0, -1 };

	if (!Node||!Modify) return -1;
	ClearModified();
        if (wdisp) for (j=0;j<100;j++) for (i=0;i<100;i++) disp[i][j]=0;
	root=&Node[starty][startx];
	root->ActualCost=0;
	root->EstimateCost=JudgeCost(startx,starty);
	root->Father=NULL;
	root->Modified=1;
	Modify[ModifyPoint++]=root;
	AddToOpenQueue(root);
	MinPos=tile_pos(startx,starty);
	MinJudge=JudgeCost(startx,starty);
        mOpenCount=0;
        mCloseCount=0;
	for (ok=0;ok==0;)
	{
		ok=GetFromOpenQueue();		// 取出Open队列估价值最小的节点放入Close中
		root=Close;					// 得到刚才取出的节点
		if (ok||root==NULL) { ok=-1; break; }
		x=tile_x(root->Pos);
		y=tile_y(root->Pos);
                if (wdisp) disp[y][x]++;
                if (OpenCount>mOpenCount) mOpenCount=OpenCount;
                if (CloseCount>mCloseCount) mCloseCount=CloseCount;
		if (root->EstimateCost-root->ActualCost<MinJudge)	// 找到一个估计离终点最近的点
			MinJudge=root->EstimateCost-root->ActualCost, MinPos=root->Pos;
		if (CloseCount>max) max=CloseCount;
		if (x==endx&&y==endy) MinPos=root->Pos,ok=1;	// 如果走到终点了
		else {
			for (i=0,dirs=1,j=1;i<8;i++,dirs<<=1)		// 如果没有走到终点
				if (DirMask&dirs) j&=TryTile(x+incx[i],y+incy[i],root);
			if (j) if (PopCloseStack()) { ok=-2; break; }	// 如果不是通路则从Close中取出
		}
		if (OpenCount>=OpenLimited||CloseCount>=CloseLimited) ok=2;
	}
        GetPosPath(path,500);
	if (ok<0) return -2;
	return 0;
  }
  void create() { Create(map_w,map_h,mpossible,judge); }
  void release() { Release(); }
} find;
void setting()
{
  find.set();
}
void setdefault()
{
  startx=starty=0;
  endx=endy=0;
  m1=10; m2=6;
  map_h=30;
  map_w=45;
  CLimited=map_h*map_w;
  OLimited=map_h*map_w;
  setting();
}
void popen()
{
  find.create();
  setdefault();
}
void pclose()
{
  find.release();
}

void fpath(bool wdisp)
{
  find.myfind(wdisp);
}
void draw(TImage *Image1)
{
    int x,y,c;
    TRect rect;
    for (y=0;y<map_h;rect.top+=8,rect.bottom+=8,y++)
      for (x=0,rect.left=0,rect.right=7;x<map_w;rect.left+=8,rect.right+=8,x++)
      {
        c=0xffffff;
        if (map[y][x]!=' ') c=0x1122ee;
        else if (disp[y][x]<0) c=0x11ee22;
        else if (disp[y][x]>0) c=disp[y][x],c=((c*10)&0xff)<<16;
        if (x==startx&&y==starty) c=0xff00ff;
        if (x==endx&&y==endy) c=0xff00ff;
        Image1->Canvas->Brush->Color=c;
        Image1->Canvas->FillRect(rect);
      }
}