推箱子的最短路徑

推箱子的最短路徑-數(shù)據(jù)結(jié)構(gòu)與C語言綜合訓(xùn)練報告信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與C語言綜合訓(xùn)練報告（2012?2013學(xué)年第二學(xué)期）報告題目：____推箱子的最短路徑_姓名：___ —專業(yè)： 軟件工程年級班級：—2012級2班指導(dǎo)教師： 完成日期：2013年7月21號數(shù)據(jù)結(jié)構(gòu)與C語言綜合訓(xùn)練實習報告一、綜合訓(xùn)練目的和要求本綜合訓(xùn)練是計算機科學(xué)與技術(shù)、信息管理與信息系統(tǒng)、軟件工程、電子商務(wù)專業(yè)重要的實踐性環(huán)節(jié)之一，是在學(xué)生學(xué)習完《程序設(shè)計語言(C)》、《數(shù)據(jù)結(jié)構(gòu)》課程后進行的一次全面的綜合練習。本課綜合訓(xùn)練的目的和任務(wù)：鞏固和加深學(xué)生對C語言、數(shù)據(jù)結(jié)構(gòu)課程的基本知識的理解和掌握掌握C語言編程和程序調(diào)試的基本技能利用C語言進行基本的軟件設(shè)計掌握書寫程序設(shè)計說明文檔的能力提高運用C語言、數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力二、綜合訓(xùn)練任務(wù)內(nèi)容題目要求：推箱子是一個很經(jīng)典的游戲.今天我們來玩一個簡單版本.在一個5X5的房間里有一個箱子和一個搬運工，搬運工的工作就是把箱子推到指定的位置，注意，搬運工只能推箱子而不能拉箱子，因此如果箱子被推到一個角上那么箱子就不能再被移動了，如果箱子被推到一面墻上，那么箱子只能沿著墻移動.同時，房間里頭還有若干障礙物(用陰影部分表示)?，F(xiàn)在給定房間的結(jié)構(gòu),箱子的位置，搬運工的位置和箱子要被推去的位置，請你計算出搬運工至少要推動箱子多少格.擴展實現(xiàn)的內(nèi)容：繪制圖形界面，通過按鈕實現(xiàn)推箱子的整個過程，整個過程中可以動態(tài)的看到箱子的移動。游戲界面如下圖：pudibox夬樂(Happy)推箱子(PushtheBox)(自動實現(xiàn)推箱子最短路徑)游戲動態(tài)移動的過程圖如下:三、總體設(shè)計所用算法主要是根據(jù)廣度優(yōu)先搜索，紀錄路徑，然后利用回溯法實現(xiàn)最短路徑的查找并紀錄保存下來。所用的數(shù)據(jù)結(jié)構(gòu)主要為順序結(jié)構(gòu)。、詳細設(shè)計說明1、 推箱子游戲具有的功能（1） 能夠顯示主菜單和界面游戲需要提供主菜單進行選擇，同時能夠把地圖文件中的信息轉(zhuǎn)換成為圖像顯示到游戲界面上。（2） 能夠?qū)崿F(xiàn)鍵盤操作功能能夠接收到空格鍵信息，按照軟件內(nèi)部實現(xiàn)的箱子移動到相應(yīng)的位置。（3） 能夠進行關(guān)卡選擇功能進入開始游戲的界面時，可以進行游戲的關(guān)卡的選擇，然后利用空格鍵進行箱子的移動。（4） 提供游戲說明功能進入游戲說明界面時，可以了解游戲的一些規(guī)則，及如何進行游戲。2、 程序結(jié)構(gòu)設(shè)計運用C++語言，以及VS2010開發(fā)環(huán)境（1） 、typedefstructPnode{introw;intcol;intweight;structPnode*back_man;}Pnode,*Position;某一點的坐標表示，當用來實現(xiàn)箱子的最短路徑的搜索時，back_man用來存儲箱子移動一個位置后，人所在的位置。（2） 、typedefstructMnode{intmrow;intmcol;charmaze[MAX_ROW][MAX_COL];}MNode,*MazeType;用來存儲地圖的信息、算法的實現(xiàn)主要有兩個類，第一個類是classShortestPath；第二個類是classManBoxStep:publicShortestPath；A、第一個類classShortestPath是用來實現(xiàn)地圖中任意兩點之間的最短路徑，成員函數(shù)及其功能如下：PositionNextPosition(Position&curpos,intdi);用來計算當前點在四個方向下的移動一格得到的下一點的坐標位置，并返回；boolCanArrive(vector<list<Position>>&vec);數(shù)據(jù)成員有start,end，此函數(shù)是判斷在地圖中能否從start到end，并利用廣度優(yōu)先搜索搜索從start到end的路徑，并把所有搜索過的位置全部記錄在順序容器vec中，vec[i]表示存儲一系列與start位置相距i個格子的被搜索的點的位置;voidRecordWay(vector<list<Position>>&vec,vector<Position>&way);此函數(shù)根據(jù)vec中所存儲的數(shù)據(jù)，利用回溯法進行往回搜索，找到從start到end的最短路徑,并把路徑存到容器way中；B、第二個類classManBoxStep是利用第一個類中的函數(shù)實現(xiàn)人和箱子一起從起點到箱子應(yīng)到的位置的最短路徑，其中的成員函數(shù)及其功能如下：PositionNextState(Positionbox,intdi);此函數(shù)的功能是紀錄當人能夠移動箱子的情況下，紀錄移動后箱子和人的位置；MazeTypeUpdateMaze(MazeTypemymaze,Positioncurpos,Positionnewpos);此函數(shù)的功能是每當在搜索下一步時，及時的更新所在的地圖(即改變?nèi)撕拖渥拥奈恢?，并每次都將地圖紀錄下來；boolBFSCanArrive(vector<list<Position>>&AllWay,vector<vector<Position>>&man_way,vector<MazeType>&maze_state);此函數(shù)的功能是，可以說是有條件的進行廣度優(yōu)先搜索，即每次搜索四個方向中的一個方向時，都要利用第一個類中的CanArrive函數(shù)判斷是否能從人的當前位置移動到推箱子的位置，并記錄最短的路徑，并保證箱子前面不是墻，AllWay是用于存儲有條件的廣度優(yōu)先搜索中所搜索到的位置，AllWay[i]是用來存儲從開始走i個格子的所有被搜索到的位置，man_way是用來存儲人走過的所有的路徑，man_way[i]存儲走過的某條路徑所經(jīng)過的點的位置；maze_state用來存儲搜索過5程中所更新的所有的地圖的狀態(tài);voidRecordBestWay(vector<list<Position>>&AllWay,vector<Position>&bestWay,vector<vector<Position>>&man_way,vector<Position>&man_bestway);此函數(shù)是根據(jù)AllWay的數(shù)據(jù)往回進行回溯法找到箱子可以移動的最短的路徑，同理，man_bestway是根據(jù)man_way來找到人整個過程中所走過的最短的路徑；、界面及圖形的繪制此軟件的界面設(shè)計主要是利用Easyx中的函數(shù)進行繪畫的，游戲的主界面以及一些按鈕時利用繪圖函數(shù)實現(xiàn)的，并且根據(jù)所畫按鈕的坐標范圍，來控制鼠標，從而來實現(xiàn)界面中按鈕的控制，游戲過程中的箱子、墻、人均是利用函數(shù)所插入的圖片，移動的時候，在不同的位置插入不同的圖片來顯示動態(tài)的過程；插入圖片的函數(shù)loadimage(&img[0],_T("F:\\VS\\test\\pushbox\\s.jpg"));loadimage(&img[1],_T("F:\\VS\\test\\pushbox\\w.jpg"));loadimage(&img[2],_T("F:\\VS\\test\\pushbox\\m.jpg"));loadimage(&img[3],_T("F:\\VS\\test\\pushbox\\b.jpg"));loadimage(&img[4],_T("F:\\VS\\test\\pushbox\\d.jpg"));loadimage(&img[5],_T("F:\\VS\\test\\pushbox\\bd.jpg"));繪制按鈕：ellipse(580,440,740,490);//畫橢圓RECTr2={580,440,740,490};drawtext(_T("游戲說明”)，&r2,DT_CENTER|DT_VCENTER|DT_SINGLELINE);鼠標的響應(yīng)：MOUSEMSGm;while(true){m=GetMouseMsg();switch(m.uMsg){case(WM_LBUTTONDOWN):地圖的獲得constcharWall='w';//表示墻constcharSpace='s';//表示通道constcharMan_Start='m';//表示人開始時的位置constcharBox_Start='b';//表示箱子初始時的位置constcharDestination='d';//箱子需要到達的目的地根據(jù)這些字符的表示含義，將不同關(guān)卡的地圖存放在不同的.txt文件中，在進行游戲時，讀取文件，在根據(jù)坐標插入相應(yīng)的圖片在界面中顯示出來，如下：ifstreaminfile;infile.open(〃F:\\VS\\test\\pushbox\\test1?txt〃)；intR_C[2];for(inti=0;i<2;i++)infile>>R_C[i];mymaze->mrow=R_C[0];mymaze->mcol=R_C[1];、結(jié)合數(shù)據(jù)與界面根據(jù)所搜索到的最短路徑的數(shù)據(jù)，利用坐標，將數(shù)據(jù)結(jié)合圖片的動態(tài)移動來表示走過的路徑。五、軟件使用說明進入開始的界面后就可以進行游戲了，然后選擇關(guān)卡，然后開始游戲，利用空格鍵使人和箱子根據(jù)計算好的路徑進行移動，如下的游戲相鄰的兩張時的界面：

六、調(diào)試與測試編寫核心算法的代碼時，在一個頭文件中實現(xiàn)，并進行測試，測試一般還不是利用文件的輸入，直接鍵盤輸入，測試成功后，在分幾個文件進行管理，繼續(xù)調(diào)試以及測試，有時出現(xiàn)一些自己不能解決的問題的時候，就咨詢輔導(dǎo)老師，幫忙解決，程序執(zhí)行過程中經(jīng)常出現(xiàn)的錯誤就是內(nèi)存的錯誤，這樣邊測試變完善代碼；七、工作日志7月12號：主要開始進行程序框架的設(shè)計；7月13號：開始根據(jù)網(wǎng)上的一些資料，思索其中的核心算一一廣度優(yōu)先搜索；7月14號：開始編寫核心算法的代碼，并進行調(diào)試；7月15號：繼續(xù)調(diào)試核心算法的代碼，分幾個文件管理，并咨詢老師幫助解決一些調(diào)試中的問題；7月16號：開始進行界面的框架設(shè)計，即圖形的繪制；7月18號：在界面中添加一些文字，以及相應(yīng)一些鼠標操作；7月19號：開始在主程序中讀取文件，實現(xiàn)最短路徑的數(shù)據(jù)的存儲；7月20號：根據(jù)所得的數(shù)據(jù)進行聯(lián)系界面中圖片的插入，并調(diào)試代碼；7月21號：開始進行代碼的優(yōu)化，繼續(xù)調(diào)試，并且書寫實習報告；八、綜合訓(xùn)練心得與體會感覺通過這次綜合的實習，可以將自己所學(xué)到的東西真正的利用到了實踐當