//---------------------------------------------------------------------------
#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));
      //動態(tài)分配2維數(shù)組
      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;//擴展結點數(shù)
   int count=0;//代價總數(shù)
   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)//對數(shù)組重置
   {
   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)//廣度優(yōu)先
 {
   Node * node=new Node();
   node->adr=node;
   open.push_back(*node);
   Node * front=node;//存放首結點
   while(true)
   {
      if(open.size()==0)
      {
         Destroy();//如無發(fā)現(xiàn)通路則將擴展結點刪除
         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;//找到初始結點后則跳出循環(huán)
            }
         }
         //刪除容器中結點
         Destroy();
         open.erase(open.begin(),open.end());
         closed.erase(closed.begin(),closed.end());
         ReDraw=true;
         ShowMessage("擴展的結點數(shù)"+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)//深度優(yōu)先
  {
   int n;//擴展結點數(shù)
   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;//找到初始結點后則跳出循環(huán)
            }
         }
         //刪除容器中結點
         Destroy();
         open.erase(open.begin(),open.end());
         closed.erase(closed.begin(),closed.end());
         ReDraw=true;
         //Application->MessageBoxA("說明","共擴展結點"+k,MB_OK);
         ShowMessage("擴展的結點數(shù)"+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;//將上次擴展結點數(shù)清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;//找到初始結點后則跳出循環(huán)
            }
         }
         //刪除容器中結點
         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("擴展的結點數(shù)"+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;//啟發(fā)式函數(shù)
            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)