15数码智能程序（广度搜索和A*算法）

#include<iostream.h> #include<string> #include<time.h> #include "SDL/SDL.h" #include "A.h" #include "Breadth.h" const int SCREEN_WIDTH = 640; const int SCREEN_HEIGHT = 480; const int SCREEN_BPP = 32; int temp[16]; int old_x,old_y,new_x,new_y,zero; bool isRun=false; bool isKey=false; int step_Num; int array[1000][16]; int src[4][4]={ {1,2,3,4}, {5,10,6,8}, {0,9,7,12}, {13,14,11,15} }; //int src[4][4]; int goal[4][4]={ {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,0} }; SDL_Surface *message[16];//信息表皮 SDL_Surface *background = NULL;//背景表皮 SDL_Surface *screen = NULL;//屏幕表皮 SDL_Thread *thread=NULL; SDL_Thread *thread1=NULL; SDL_Event gameEvent; void display(); void random16(); void simpleRandom16(); bool solution(int A[4][4],int B[4][4]); int my_thread1( void *data ); SDL_Surface *load_image( std::string filename ){ SDL_Surface* loadedImage = NULL; SDL_Surface* optimizedImage = NULL; loadedImage = SDL_LoadBMP( filename.c_str() );//装载图片 if( loadedImage != NULL ){ optimizedImage = SDL_DisplayFormat( loadedImage ); SDL_FreeSurface( loadedImage );//释放 } return optimizedImage;//返回最优化的 } void apply_surface( int x, int y, SDL_Surface* source, SDL_Surface* destination ){ SDL_Rect offset; offset.x = x; offset.y = y; SDL_BlitSurface( source, NULL, destination, &offset ); } void changeArray(int a[4][4]){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ a[i][j]=temp[i*4+j]; } } } void inChangeArray(){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ temp[i*4+j]=src[i][j]; } } } void getZero(){ for(int i=0;i<16;i++){ if(temp[i]==0){ zero=i; } } } void pressKey(){ cout<<"pressKey() function begin\n"; bool gameOver=false; while(SDL_WaitEvent(&gameEvent) >= 0){ if(gameOver==true){ break; } //SDL_PollEvent(&gameEvent); //if(&gameEvent!=0){ if(gameEvent.type == SDL_QUIT) gameOver = true; if(gameEvent.type == SDL_KEYDOWN){ if(gameEvent.key.keysym.sym == SDLK_ESCAPE){ isRun=true; gameOver = true; for(int i=0;i<16;i++){ SDL_FreeSurface( message[i]);//释放 } SDL_FreeSurface( background );//释放 } if(gameEvent.key.keysym.sym == SDLK_r){ isRun=true; isKey=false; for(int i=0;i<16;i++){ temp[i]=-1; } random16(); } if(gameEvent.key.keysym.sym == SDLK_e){ isRun=true; isKey=false; simpleRandom16(); } if(gameEvent.key.keysym.sym == SDLK_s){ isRun=true; isKey=false; changeArray(src); solution(src,goal); } if(gameEvent.key.keysym.sym == SDLK_w){ isRun=true; isKey=false; changeArray(goal); isRun=false; } if(gameEvent.key.keysym.sym == SDLK_1){ isRun=true; isKey=false; changeArray(src); /*if(!solution(src,goal)){ cout<<"The array no answer!"<<endl; }else{*/ Breadth dight(src,goal); step_Num=dight.getNum(); dight.getArray(array); //} } if(gameEvent.key.keysym.sym == SDLK_2){ isRun=true; isKey=false; changeArray(src); /*if(!solution(src,goal)){ cout<<"The array no answer!"<<endl; }else{*/ A_15Dight dight(src,goal); step_Num=dight.getNum(); dight.getArray(array); //} } if(gameEvent.key.keysym.sym == SDLK_UP){ isRun=true; isKey=false; getZero(); if(zero>3){ int tt=temp[zero]; temp[zero]=temp[zero-4]; temp[zero-4]=tt; } isRun=false; } if(gameEvent.key.keysym.sym == SDLK_DOWN){ isRun=true; isKey=false; getZero(); if(zero<12){ int tt=temp[zero]; temp[zero]=temp[zero+4]; temp[zero+4]=tt; } isRun=false; } if(gameEvent.key.keysym.sym == SDLK_RIGHT){ isRun=true; isKey=false; getZero(); if(zero%4!=3){ int tt=temp[zero]; temp[zero]=temp[zero+1]; temp[zero+1]=tt; } isRun=false; } if(gameEvent.key.keysym.sym == SDLK_LEFT){ isRun=true; isKey=false; getZero(); if(zero%4!=0){ int tt=temp[zero]; temp[zero]=temp[zero-1]; temp[zero-1]=tt; } isRun=false; } if(gameEvent.key.keysym.sym == SDLK_F1){ isRun=true; isKey=false; cout<<"*******************************************"<<endl; cout<<"Key function:"<<endl; cout<<"F1 菜单显示"<<endl; cout<<"NUM1 宽度搜索"<<endl; cout<<"NUM2 A*搜索"<<endl; cout<<"E 简单随机"<<endl; cout<<"R 全部随机"<<endl; cout<<"W 将数组存为目标数组"<<endl; cout<<"S 数组判断（未实现）"<<endl; cout<<"UP 0向上交换"<<endl; cout<<"DOWN 0向下交换"<<endl; cout<<"RIGHT 0向右交换"<<endl; cout<<"LIFT 0向左交换"<<endl; cout<<"Mouse function:"<<endl; cout<<"按住鼠标可以交换开始和结束的任意数字"<<endl; cout<<"*******************************************"<<endl; isRun=false; } if(gameEvent.key.keysym.sym == SDLK_SPACE){ isKey=true; thread1=SDL_CreateThread(my_thread1 , NULL ); } //} } if(gameEvent.type == SDL_MOUSEBUTTONDOWN){ isRun=true; old_x=(gameEvent.motion.x-180)/70; old_y=(gameEvent.motion.y-100)/70; printf("down (%d,%d)\n",old_x, old_y); } if(gameEvent.type == SDL_MOUSEBUTTONUP){ new_x=(gameEvent.motion.x-180)/70; new_y=(gameEvent.motion.y-100)/70; printf("up (%d,%d)\n",new_x, new_y); int ttt=temp[old_y*4+old_x]; temp[old_y*4+old_x]=temp[new_y*4+new_x]; temp[new_y*4+new_x]=ttt; isRun=false; } //doSomeLoopThings(); } return; } int my_thread( void *data ){ while(1){ if(isRun==false){ display(); SDL_Delay(500); } } return 0; } int my_thread1( void *data ){ while(step_Num>=0){ if(!isKey) break; for(int j=0;j<16;j++){ temp[j]=array[step_Num][j]; } isRun=false; step_Num--; SDL_Delay( 1000 ); isRun=true; } return 0; } bool solution(int A[4][4],int B[4][4]){ int a[16],b[16]; int max=16; int s1=0,s2=0,i,j; for(i=0;i<4;i++){ for(j=0;j<4;j++){ a[i*4+j]=A[i][j]; b[i*4+j]=B[i][j]; } } for(i=0;i<max-1;i++){ for(j=i+1;j<max;j++){ //if(a[i]*a[j]){ if(a[i]>a[j]) s1++; //} } } for(i=0;i<max-1;i++){ for(j=i+1;j<max;j++){ //if(b[i]*b[j]){ if(b[i]>b[j]) s2++; //} } } cout<<"s1:"<<s1<<" s2:"<<s2<<endl; if(s1%2==s2%2){ cout<<"有解"<<endl; return true; } else{ cout<<"无解"<<endl; return false; } } void random16(){ int i,j,t=0; for(i=0;i<16;i++){ srand((int)time(NULL)); loop: while(1){ t=rand()%16;//t=random(16); for(j=0;j<16;j++){ if(temp[j]==t) goto loop; } break; } temp[i]=t; } for(i=0;i<16;i++){ cout<<temp[i]<<" "; } cout<<endl; isRun=false; } void simpleRandom16(){ srand((int)time(NULL)); int t2=rand()%20; cout<<t2<<endl; for(int i=0;i<t2;i++){ int t1=rand()%4; getZero(); switch(t1){ case 0:if(zero>3){ int tt=temp[zero]; temp[zero]=temp[zero-4]; temp[zero-4]=tt; } break; case 1:if(zero<12){ int tt=temp[zero]; temp[zero]=temp[zero+4]; temp[zero+4]=tt; } break; case 2:if(zero%4!=3){ int tt=temp[zero]; temp[zero]=temp[zero+1]; temp[zero+1]=tt; } break; case 3:if(zero%4!=0){ int tt=temp[zero]; temp[zero]=temp[zero-1]; temp[zero-1]=tt; } break; } cout<<t1<<" "; } cout<<endl; isRun=false; } int main( int argc, char* args[] ){ try{ if(SDL_Init(SDL_INIT_EVERYTHING)==-1) throw SDL_GetError(); }catch(const char* s){ cerr<<s<<endl; return -1; } atexit(SDL_Quit);