maze.~cpp

用C++BUILDER做的一个迷宫,可以实现深度优先,广度优先和启发式搜索算法

//---------------------------------------------------------------------------
#include <vcl.h>
#include <vector>
#include <algorithm>
#pragma hdrstop

#include <cstdlib>
#include <ctime>
#include "Maze.h"
using namespace std;
//----------------------------
bool Node::operator<(const Node & m) const
{
        return cost<m.cost;
}
//--------------------------------
Maze::Maze()
{
      num=4;
      HEIGHT_MAX=400;
      WIDTH_MAX=600;
      ReDraw=false;
}
//-------------------------------
Maze::~Maze()
{

}
//----------------------------------------------------
void Maze::Destroy()
{
   if(!open.empty())
         {
            for(ptr=open.begin();!open.end();ptr++)
               delete ptr->adr;
         }
   if(!closed.empty())
         {
            for(ptr=closed.begin();!closed.end();ptr++)
               delete ptr->adr;
         }
}
//---------------------------------------------------------------------------
void Maze::CreateMaze(int &x,int &y,TForm * f)
{
   ShpHeight=HEIGHT_MAX/x;//shape高
   ShpWidth=WIDTH_MAX/y;//shape宽
   for(int i=0;i<x;i++)
      for(int j=0;j<y;j++)
      {
      Shp[i][j]=new TShape(f);
      Shp[i][j]->Parent=f;
      Shp[i][j]->Width=ShpWidth;
      Shp[i][j]->Height=ShpHeight;
      Shp[i][j]->Top+=4+i*ShpHeight;
      Shp[i][j]->Left+=4+j*ShpWidth;
      Shp[i][j]->Shape=stRectangle;
      Shp[i][j]->Pen->Color=clWhite;
      }
}
//---------------------------------------
void Maze::MakeMaze(int &x,int &y,float &bili)
{
   srand((unsigned)time(NULL));
      //动态分配2维数组
      Maze=new int* [x];
      for(int i=0;i<x;i++)
      Maze[i]=new int[y];

      for(int i=0;i<x;i++)
         for(int j=0;j<y;j++)
         {
              Maze[i][j]=1;
         }
     for(int i=1;i<x-1;i++)
         for(int j=1;j<y-1;j++)
         {
               Shp[i][j]->Brush->Color=clWhite;
               Shp[i][j]->Shape=stRectangle;
         }
       for(int i=1;i<x-1;i++)
         for(int j=1;j<y-1;j++)
         {
             Maze[i][j]=rand()%100;
             if(Maze[i][j]<100*bili)
             Maze[i][j]=1;
             else
             Maze[i][j]=0;
         }
         Maze[1][0]=0;//
         Maze[x-2][y-1]=0;
       for(int i=0;i<x;i++)
         for(int j=0;j<y;j++)
            {
               if(Maze[i][j]==1)
               Shp[i][j]->Brush->Color=clBlue;
               Shp[i][j]->Shape=stRectangle;
            }
       for(int i=0;i<x;i++)
         for(int j=0;j<y;j++)
         {
            if(i==0||i==x-1||j==0||j==y-1)
               {
                  Shp[i][j]->Brush->Color=clBlack;
                  Shp[i][j]->Pen->Color=clBlack;
               }
         }
         //出入口颜色
         Shp[1][0]->Brush->Color=clWhite;
         Shp[1][0]->Pen->Color=clWhite;
         Shp[x-2][y-1]->Brush->Color=clWhite;
         Shp[x-2][y-1]->Pen->Color=clWhite;
         ReDraw=false;
}
//------------------------------
void Maze::SearchRoad(int &x,int &y,int gd,int sd,int ax)
{
   int k=0;//扩展结点数
   int count=0;//代价总数
   int x0=1;
   int y0=1;
   int dir0=0;
   vector <Node>::iterator ptr;//用于存放Open表中的首结点迭代器
   Node offset[4];//各个方向的步进
   offset[0].x=0;offset[0].y=1;
   offset[1].x=1;offset[1].y=0;
   offset[2].x=0;offset[2].y=-1;
   offset[3].x=-1;offset[3].y=0;
   if(ReDraw)//对数组重置
   {
   for(int i=1;i<x-1;i++)
      for(int j=1;j<y-1;j++)
      {
         if(Maze[i][j]==-1)
         {
            Shp[i][j]->Brush->Color=clWhite;
            Shp[i][j]->Shape=stRectangle;
            Maze[i][j]=0;
         }
      }
   }
 if(gd)//广度优先
 {
   Node * node=new Node();
   node->adr=node;
   open.push_back(*node);
   Node * front=node;//存放首结点
   while(true)
   {
      if(open.size()==0)
      {
         Destroy();//如无发现通路则将扩展结点删除
         ShowMessage("该迷宫无通路");
         return;
      }
      ptr=open.begin();//存放open表的首结点迭代器
      front=ptr->adr;//存放该结点的地址
      closed.push_back(*ptr);//将待扩展结点放入closed表
      open.erase(open.begin(),open.begin()+1);//将open表的首结点删除
      //判断是否找到出口
      if(front->x==x-2 && front->y==y-2)
      {
         while(front->x!=1||front->y!=1)
         {
            count+=front->cost;
            x0=front->x;
            y0=front->y;
            front=front->pre;//
            Shp[x0][y0]->Brush->Color=clLime;//走过的路径用绿色表示
            Shp[x0][y0]->Shape=stEllipse;
            if(front->x==1&&front->y==1)
            {
               count+=front->cost;
               x0=front->x;
               y0=front->y;
               Shp[x0][y0]->Brush->Color=clLime;
               Shp[x0][y0]->Shape=stEllipse;
               break;//找到初始结点后则跳出循环
            }
         }
         //删除容器中结点
         Destroy();
         open.erase(open.begin(),open.end());
         closed.erase(closed.begin(),closed.end());
         ReDraw=true;
         ShowMessage("扩展的结点数"+IntToStr(k)+",代价为"+IntToStr(count));
         return;
      }
      //判断结点是否可扩展
      x0=front->x;
      y0=front->y;
      //判断四个方向是否可扩展
      if(Maze[x0][y0+1]!=0&&Maze[x0+1][y0]!=0&&Maze[x0-1][y0]!=0&&Maze[x0][y0-1]!=0)
         continue;
      Maze[x0][y0]=-1;//标识为已扩展
      for(int i=0;i<num;i++)
      {

         x0=front->x+offset[i].x;//扩展结点坐标
         y0=front->y+offset[i].y;
         if(Maze[x0][y0]==0)
         {
            Node * node=new Node();
            node->dir=i;
            node->x=x0;
            node->y=y0;
            node->adr=node;
            node->pre=front;
            k++;
            if(front->dir==i)
               node->cost=front->cost+2;
            else
               node->cost=front->cost+3;
            open.push_back(*node);
         }
      }
      sort(open.begin(),open.end());//对open表进行排序
   }
 }//end of if(gd)
  if(sd)//深度优先
  {
   int n;//扩展结点数
   Node * node=new Node();
   node->adr=node;
   open.push_back(*node);
   Node * front=node;//存放首结点
   while(true)
   {
      if(open.size()==0)
      {
         Destroy();
         ShowMessage("该迷宫无通路");
         return;
      }
      ptr=open.begin();//存放open表的首结点迭代器
      front=ptr->adr;//存放该结点的地址
      closed.push_back(*ptr);//将待扩展结点放入closed表
      open.erase(open.begin(),open.begin()+1);//将open表的首结点删除
      if(front->x==x-2 && front->y==y-2) //判断是否找到出口
      {
         while(front->x!=1||front->y!=1)
         {
            count+=front->cost;
            x0=front->x;
            y0=front->y;
            front=front->pre;//
            Shp[x0][y0]->Brush->Color=clLime;//走过的路径用绿色表示
            Shp[x0][y0]->Shape=stEllipse;
            if(front->x==1&&front->y==1)
            {
               count+=front->cost;
               x0=front->x;
               y0=front->y;
               Shp[x0][y0]->Brush->Color=clLime;
               Shp[x0][y0]->Shape=stEllipse;
               break;//找到初始结点后则跳出循环
            }
         }
         //删除容器中结点
         Destroy();
         open.erase(open.begin(),open.end());
         closed.erase(closed.begin(),closed.end());
         ReDraw=true;
         //Application->MessageBoxA("说明","共扩展结点"+k,MB_OK);
         ShowMessage("扩展的结点数"+IntToStr(k)+",代价为"+IntToStr(count));
         return;
      }
      //判断结点是否可扩展
      x0=front->x;
      y0=front->y;
      //判断四个方向是否可扩展
      if(Maze[x0][y0+1]!=0&&Maze[x0+1][y0]!=0&&Maze[x0-1][y0]!=0&&Maze[x0][y0-1]!=0)
         continue;
      Maze[x0][y0]=-1;//标识为已扩展
      n=0;//将上次扩展结点数清0
      for(int i=0;i<num;i++)
      {
         x0=front->x+offset[i].x;//扩展结点坐标
         y0=front->y+offset[i].y;
         if(Maze[x0][y0]==0)//为0则可扩展
         {
            Node * node=new Node();
            node->dir=i;
            node->x=x0;
            node->y=y0;
            node->adr=node;
            node->pre=front;
            n++;//将结点加1
            k++;
            if(front->dir==i)
               node->g=front->g+2;
            else
               node->g=front->g+3;
               node->h=(x-2)-x0+(y-2)-y0;
               node->cost=node->g+0.2*node->h;
               open.insert(open.begin(),*node);//将扩展结点从头插入
         }
      }
      sort(open.begin(),open.begin()+n);//对刚插入的结点进行排序
   }
  }//end of if(sd)
  if(ax)//A*算法
  {
         Node * node=new Node();
   node->adr=node;
   open.push_back(*node);
   Node * front=node;//存放首结点
   while(true)
   {
      if(open.size()==0)
      {
         Destroy();
         ShowMessage("该迷宫无通路");
         return;
      }
      ptr=open.begin();//存放open表的首结点迭代器
      front=ptr->adr;//存放该结点的地址
      closed.push_back(*ptr);//将待扩展结点放入closed表
      open.erase(open.begin(),open.begin()+1);//将open表的首结点删除
      //判断是否找到出口
      if(front->x==x-2 && front->y==y-2)
      {
         while(front->x!=1||front->y!=1)
         {
            count+=front->cost;
            x0=front->x;
            y0=front->y;
            front=front->pre;//
            Shp[x0][y0]->Brush->Color=clLime;//走过的路径用绿色表示
            Shp[x0][y0]->Shape=stEllipse;
            if(front->x==1&&front->y==1)
            {
               count+=front->cost;
               x0=front->x;
               y0=front->y;
               Shp[x0][y0]->Brush->Color=clLime;
               Shp[x0][y0]->Shape=stEllipse;
               break;//找到初始结点后则跳出循环
            }
         }
         //删除容器中结点
         if(!open.empty())
         {
            for(ptr=open.begin();!open.end();ptr++)
               delete ptr->adr;
         }
         if(!closed.empty())
         {
            for(ptr=closed.begin();!closed.end();ptr++)
               delete ptr->adr;
         }
         Destroy();
         open.erase(open.begin(),open.end());
         closed.erase(closed.begin(),closed.end());
         ReDraw=true;
         //Application->MessageBoxA("说明","共扩展结点"+k,MB_OK);
         ShowMessage("扩展的结点数"+IntToStr(k)+",代价为"+IntToStr(count));
         return;
      }
      //判断结点是否可扩展
      x0=front->x;
      y0=front->y;
      //判断四个方向是否可扩展
      if(Maze[x0][y0+1]!=0&&Maze[x0+1][y0]!=0&&Maze[x0-1][y0]!=0&&Maze[x0][y0-1]!=0)
         continue;
      Maze[x0][y0]=-1;//标识为已扩展
      for(int i=0;i<num;i++)
      {
         x0=front->x+offset[i].x;//扩展结点坐标
         y0=front->y+offset[i].y;
         if(Maze[x0][y0]==0)
         {
            Node * node=new Node();
            node->dir=i;
            node->x=x0;
            node->y=y0;
            node->adr=node;
            node->pre=front;
            k++;
            if(front->dir==i)
               node->g=front->g+2;
            else
               node->g=front->g+3;
            node->h=(x-2)-x0+(y-2)-y0;//启发式函数
            node->cost=node->g+3*node->h;
            open.push_back(*node);
         }
      }
      sort(open.begin(),open.end());//对open表进行排序
   }//end of if(ax)
  }
}
//--------------------------------
void Maze::DeleteShp(int &x,int &y)
{
   for(int i=0;i<x;i++)
    {
      for(int j=0;j<y;j++)
      {
         delete Shp[i][j];
      }
    }
    for(int i=0;i<x;i++)
    {
      delete [y]Maze[i];
    }
      delete [x]Maze;
}
//-----------------------------------
#pragma package(smart_init)