推箱子游戏中AI的实现

2010.19AI，。，。，，，，，，。1，，1。，，，，。[1]，。，。，，2。，：（1）。（2）。1，。2，，。，[2]，A*[3]。，m_stActiveState，3。，，。，[4]，：（1）；（2），，。，4。：，。，，。，，，C++。：；；；12YESNOYESNO3782010.19。：（1）。（2），5。。，。，，。（1）。（2）。（3）。（4）。，，4。2：typedefstructNOTESTACK{STATE*state;//NOTESTACK*next;NOTESTATE();//next=NULL;boolPush(STATE*newState);//pushSTATE*Pop();boolEmpty();}STACKSTATE;CPushBoxAI，m_man()、m_box()、m_bottomMap()、m_goal()。FindRoute()：voidCPushBoxAI::FindRoute(){STATE*curState=newSTATE;//，//curState-Initial(m_man,m_box,NULL,m_bot-tomMap,m_goal,m_deadPoint);////NULLm_stAvailState-Push(curState);//STATE*newState=NULL;while(!m_stAvailState-Empty()){curState=m_stAvailState-Pop();//if(m_goal==curState-box)//{CompleteRoute(curState);//，break;}while(!curState-NoMove())//{newState=newSTATE;curState-MoveStep(newState,m_bottomMap,m_goal,m_deadPoint);//if(ReduplicateState(newState))//{deletenewState;//newState=NULL;continue;}if(!m_stAvailState-Add(newState))//m_lkAvailState{deletenewState;//newState=NULL;continue;}}m_vtRecycle.push_back(curState);////stlvector}ReleaseStateMemory();//m_lkAvailState//m_vtRecycle}3，350，10*10630s。，。，，。[1]，..2007，9.[2]，，，，..2003.[3]A*.[4]，.（ACM/ICPC）.2009.（：2010-08-01）4579