eight_code2dlg.cpp

輸入起始和目標狀態,計算出其搜索的各種属性

    roadlen=0;                                               //路径长度                                                    //用来选择启发函数的控制变量
	step_num=0;                                              //用来记录扩展的步数
	memset(open,-1,sizeof(int)*10000);                        //初始化
	memset(close,-1,sizeof(int)*10000);
	memset(nodearray,0,sizeof(int)*14*10000);
	memset(onestep,-1,sizeof(int)*1000);
	if(m_wn==0)flag=0;
	else if(m_pn==0)flag=1;
	else if(m_wf==0)flag=2;


 	nodearray[0].array[0][0]=m_begin_edit0;
	nodearray[0].array[0][1]=m_begin_edit1;
	nodearray[0].array[0][2]=m_begin_edit2;
	nodearray[0].array[1][0]=m_begin_edit3;
	nodearray[0].array[1][1]=m_begin_edit4;
	nodearray[0].array[1][2]=m_begin_edit5;
	nodearray[0].array[2][0]=m_begin_edit6;
	nodearray[0].array[2][1]=m_begin_edit7;
	nodearray[0].array[2][2]=m_begin_edit8;

	nodearray[0].pointer=-1;
	nodearray[0].g=0;
	nodearray[0].selfposition=0;
	len++;
	open[0]=0;
	openlen++;

	endnode.array[0][0]=m_end_edit0;
	endnode.array[0][1]=m_end_edit1;
	endnode.array[0][2]=m_end_edit2;
	endnode.array[1][0]=m_end_edit3;
	endnode.array[1][1]=m_end_edit4;
	endnode.array[1][2]=m_end_edit5;
	endnode.array[2][0]=m_end_edit6;
	endnode.array[2][1]=m_end_edit7;
	endnode.array[2][2]=m_end_edit8;

	nodearray[0].h=get_h(nodearray[0],endnode,flag);
	nodearray[0].f=nodearray[0].g+nodearray[0].h;
}
//--------------------------------------------------------------------------------------------
bool CEight_COde2Dlg::searchinopen(Node a,int& position_nodearray)//查找a是否在open表中，若在则将open表的值保存于position-nodearray中
{
	int temp;
	for(int i=0;i<openlen;i++){//openlen
		temp=open[i];
		if(compare(a,nodearray[temp])==true){
		    position_nodearray=temp;
			return true;
		}
	}
	return false;
}
//--------------------------------------------------------------------------------------------
bool CEight_COde2Dlg::searchinclose(Node a,int& position_nodearray,int& pos_close)//查找a是否在close表中，若在则将close表的值保存于position-nodearray中
{
	int temp;
	for(int i=0;i<closelen;i++){//closelen
		temp=close[i];
		if(compare(a,nodearray[temp])==true){
		    position_nodearray=temp;
			pos_close=i;
			return true;
		}
	}
	return false;
}
//--------------------------------------------------------------------------------------------
void CEight_COde2Dlg::handle(Node a)//处理open生成的结点a
{
    if(len>=10000)
	{
      AfxMessageBox("超过处理范围！！");
	
	}
	
	int pos_open_node=-1;
    int pos_close_node=-1;
    int pos_close=-1;
    bool open_f;
    bool close_f;
    searchinopen(a,pos_open_node);
	searchinclose(a,pos_close_node,pos_close);
	if(pos_open_node!=-1){//若在open表中
		open_f=compare_f(nodearray[pos_open_node],a);//若open中的结点f值较大则返回true
		if(open_f==true){//若open表中的f值较大，则替换
			copynode(nodearray[pos_open_node],a);
		}
	}
	else if(pos_close_node!=-1){//若在close表中
		close_f=compare_f(nodearray[pos_close_node],a);
		if(close_f==true){//若close表中的f值较大，则在nodearray中替换并在close表中删除加入open表
			copynode(nodearray[pos_close_node],a);
			close[pos_close]=-1;//删除
			open[openlen]=pos_close_node;//将结点加入open表中
			openlen++;
		}
   

	}

	else{//若既不在open中，也不在close中，加入结点到nodearray和open
		copynode(nodearray[len],a);
		nodearray[len].selfposition=len;
		open[openlen]=len;
		openlen++;
		len++;
	}
}
//--------------------------------------------------------------------------------------------

void CEight_COde2Dlg::expend(Node a,Node endnode)//扩展结点a，注意指针
{
	
	
	int ii,jj,cc;
	bool equal;
	Node temp_i;
    for(ii=0;ii<3;ii++)
     for(jj=0;jj<3;jj++)
         if(a.array[ii][jj]==0)
             cc=3*ii+jj;
   switch(cc)
   {
   case 0://将结点加到ab数组中
          copynode(temp_i,a);
          temp_i.array[0][0]=temp_i.array[0][1];//空格往右移动 
          temp_i.array[0][1]=0;
		  temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.f=temp_i.g+temp_i.h;
		  temp_i.pointer=a.selfposition;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)//不等于父结点
		     handle(temp_i);	
		  
          copynode(temp_i,a);//空格向下移动***************************************deal()
          temp_i.array[0][0]=temp_i.array[1][0];
          temp_i.array[1][0]=0;
		  temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			 handle(temp_i);
		  break;//******************************************************************
   case 1:
	      
          copynode(temp_i,a);
          temp_i.array[0][1]=temp_i.array[0][2];//向右移动
          temp_i.array[0][2]=0;
		  temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);
		
		  copynode(temp_i,a);//向下移动
          temp_i.array[0][1]=temp_i.array[1][1];
          temp_i.array[1][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false) 
			  handle(temp_i);

		  copynode(temp_i,a);//向左移动
          temp_i.array[0][1]=temp_i.array[0][0];
          temp_i.array[0][0]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);
		  break;
   case 2:
	      
          copynode(temp_i,a);
          temp_i.array[0][2]=temp_i.array[0][1];//空格往左移动
          temp_i.array[0][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);//向下移动
          temp_i.array[0][2]=temp_i.array[1][2];
          temp_i.array[1][2]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);
		  break;
	      
   case 3:
	      
          copynode(temp_i,a); 
          temp_i.array[1][0]=temp_i.array[1][1];//空格往右移动 
          temp_i.array[1][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);// 向下移动
          temp_i.array[1][0]=temp_i.array[2][0];
          temp_i.array[2][0]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);

		  copynode(temp_i,a);// 向上移动
          temp_i.array[1][0]=temp_i.array[0][0];
          temp_i.array[0][0]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
          if(equal==false)
			  handle(temp_i);
		  break;
	      
    case 4:
          
          copynode(temp_i,a);
          temp_i.array[1][1]=temp_i.array[1][0];
          temp_i.array[1][0]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); //比较此结点是否为父结点
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);
          temp_i.array[1][1]=temp_i.array[0][1];
          temp_i.array[0][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i); 
           if(equal==false)
			   handle(temp_i);
          copynode(temp_i,a);
          temp_i.array[1][1]=temp_i.array[1][2];
          temp_i.array[1][2]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);
          temp_i.array[1][1]=temp_i.array[2][1];
          temp_i.array[2][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);
		  break;
	case 5:
		 
          copynode(temp_i,a); 
          temp_i.array[1][2]=temp_i.array[1][1];//空格往左移动 
          temp_i.array[1][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);// 向下移动
          temp_i.array[1][2]=temp_i.array[2][2];
          temp_i.array[2][2]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

		  copynode(temp_i,a);// 向上移动
          temp_i.array[1][2]=temp_i.array[0][2];
          temp_i.array[0][2]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);
		  break;
    case 6:
         
          copynode(temp_i,a); 
          temp_i.array[2][0]=temp_i.array[2][1];//空格往右移动 
          temp_i.array[2][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);// 向上移动
          temp_i.array[2][0]=temp_i.array[1][0];
          temp_i.array[1][0]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);
		  break;
	case 7:
		 
          copynode(temp_i,a); 
          temp_i.array[2][1]=temp_i.array[2][2];//空格往右移动 
          temp_i.array[2][2]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

          copynode(temp_i,a);// 向上移动
          temp_i.array[2][1]=temp_i.array[1][1];
          temp_i.array[1][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

		  copynode(temp_i,a);// 向左移动
          temp_i.array[2][1]=temp_i.array[2][0];
          temp_i.array[2][0]=0;
          temp_i.h=get_h(temp_i,endnode,flag);
		  temp_i.g++;
		  temp_i.pointer=a.selfposition;
		  temp_i.f=temp_i.g+temp_i.h;
          equal=compare(nodearray[a.pointer],temp_i);
          if(equal==false)
			  handle(temp_i);

		  break;
	case 8:
		
          copynode(temp_i,a); 
          temp_i.array[2][2]=temp_i.array[2][1];//空格往左移动 
          temp_i.array[2][1]=0;
          temp_i.h=get_h(temp_i,endnode,flag);