1、貓抓老鼠仿真的一種實現(xiàn)方法【摘要】本文闡述了一種在固定范圍內(nèi)遵照一定規(guī)則的貓抓老鼠的仿真實現(xiàn)方法。仿真程序采用c+語言編制,在vc+軟件上運行。本文中的仿真模型，按模型的特性劃分，是屬于離散事件系統(tǒng)仿真；按仿真時鐘與實際時鐘的比例關(guān)系分類上劃分，是屬于欠實時仿真；按仿真的系統(tǒng)的結(jié)構(gòu)和實現(xiàn)手段上劃分，是屬于物理仿真。0 問題貓抓老鼠。有1個10*10的方格陣，在一些格中會有一些障礙物。貓和老鼠從方格陣內(nèi)任意位置開始，每單位時間只能走一格，且必須走一格。如果在某一刻兩者在同一格中，我們稱“貓抓到老鼠”（注意，貓和老鼠交換位置，不算被抓）。貓和老鼠的移動方式相同：平時沿直線走，下一步如果會走到障礙物

2、上去或者出界，就用1個單位時間做一個左或右轉(zhuǎn)90度。一開始他們都面向北方。仿真實現(xiàn)貓抓老鼠的過程，同時保證老鼠盡可能地不被貓抓到。1 系統(tǒng)定義1.1 仿真的邊界是在一個10*10方格陣。1.2 仿真的約束條件是貓和老鼠在規(guī)定的時間里按照一定的規(guī)則行走：（1）、貓和老鼠每單位間只能走一格，且必須走一格；（2）、貓和老鼠的移動方式相同：平時沿直線走，下一步果會走到障礙物上去或者出界，就用1個單位時間做一個左或右轉(zhuǎn)90度；（3）、老鼠盡可能不被貓抓到。1.3 仿真的的目的是，展現(xiàn)貓抓老鼠的過程。2 數(shù)學(xué)建模貓抓老鼠的仿真系統(tǒng)，是離散系統(tǒng)仿真。該系統(tǒng)的組成如下：2.1 實體：（1）、永久實體：10*1

3、0方格陣，以及里面的障礙物信息；（2）、臨時實體：貓和老鼠的坐標(biāo)信息，以及方格陣中空格的坐標(biāo)信息。2.2 事件：（1）時間是共同的主事件。因為，時間協(xié)調(diào)了實體之間的同步活動。在某種程度上，也實現(xiàn)了各實體間的信息的傳遞。（2）貓和老鼠的行進是事件。因為，貓和老鼠的行進改變了系統(tǒng)的狀態(tài)。2.3 活動：（1）實體所做的事件。在該模型中，是貓和老鼠的行進；（2）、對實體施加的事件。在該設(shè)計中，當(dāng)貓或老鼠進入一種死循環(huán)狀態(tài)時，需要一個系統(tǒng)檢測函數(shù)，改變貓或老鼠原有的行進方向。2.4 進程：貓抓老鼠的整個動態(tài)過程。3 仿真建模3.1 參數(shù)設(shè)計：（1）、10*10的方格陣用一個10*10矩陣存儲。方格陣中的

4、不同內(nèi)容在矩陣中用不同的常數(shù)表示。比如，0表示空格，1表示障礙物等等。（2）、貓和老鼠，分別用一個貓類cat和鼠類rat實現(xiàn)。在兩個類中，具有共同的成員變量有：各自的坐標(biāo)信息，上一時刻的行進方向，以及自仿真開始所走過的路徑。3.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計：鼠int ratx,raty；/坐標(biāo)int rat_dir/上一時刻的方向node rat_stack； /記錄所走過的坐標(biāo)的棧ratroute()；/下一時刻的方向選擇 仿真程序采用了c+語言。所以，具體的參數(shù)設(shè)計采用了c+類的設(shè)計方法。方格陣int table1010;time cat_count1010;time rat_count1010;in

5、itlize();/方格陣初始化checkcircle();/死鎖檢測draw();/方格陣?yán)L圖貓int catx,caty；/坐標(biāo)int cat_dir；/上一時刻的方向node cat_stack； /記錄所走過的坐標(biāo)的棧catroute()；/下一時刻的方向選擇其中，time和node是自定義數(shù)據(jù)類型。它們的具體定義如下：typedef struct timeint x;/走過的次數(shù)int timerecord10;/走過的時間記錄time;/ cat_count1010、rat_count1010不僅記錄了貓或老鼠經(jīng)過某一點的次數(shù)，同時也記錄了它們每次經(jīng)過這一點的時間。typedef

6、struct nodeint x;/走過的橫坐標(biāo)int y;/走過的縱坐標(biāo)int dir;/方向node; /用此數(shù)據(jù)類型定義的數(shù)組cat_stack其實是一個棧。3.3 處理函數(shù)設(shè)計：3.3.1 方格陣的處理函數(shù)（1）、方格陣的初始化函數(shù)initlize()。方格陣的初始化可以采用靜態(tài)初始化或動態(tài)初始化兩種方式。靜態(tài)初始化方式是直接對矩陣進行賦初值。這可以采用直接人工賦值，或調(diào)用隨機函數(shù)賦初值。動態(tài)初始化，是指當(dāng)方格陣各單元的信息已經(jīng)靜態(tài)初始化之后，還可以對里面的障礙物、貓和老鼠的坐標(biāo)進行更改，以滿足仿真所要求的狀態(tài)。該設(shè)計，就是采用了，動態(tài)初始化的方式。（2）、死鎖檢測函數(shù)checkcir

7、cle()，在該仿真系統(tǒng)中屬于系統(tǒng)級的函數(shù)。它的功能是防止貓或老鼠在方格陣中不停地繞圈，而使仿真失去意義。函數(shù)的實現(xiàn)原理是，由于該仿真系統(tǒng)有一個共同的主事件時間。所以，如果貓或老鼠走過某一點的次數(shù)過多時，并且最后幾次走過的時間間隔是相等的。那么，該檢測函數(shù)就判定貓或老鼠正在不停地繞圈。處理方案是，如果能改變貓或老鼠的方向，即不是它們此刻不是夾在一個死胡同中，則左轉(zhuǎn)或右轉(zhuǎn)90。否則，強制cat_dir調(diào)轉(zhuǎn)180。該模型的數(shù)據(jù)結(jié)構(gòu)中，方格陣對象定義了cat_count1010和rat_count1010兩個矩陣成員變量。它們的作用就是記錄貓和老鼠在方格陣中經(jīng)過每一點的次數(shù)，并記錄下每次走過的時間。

8、（3）、方格陣?yán)L圖函數(shù)。在該仿真程序的設(shè)計中，采用visualc+實現(xiàn)draw()函數(shù)的作圖功能。基本原理是，每隔一秒就根據(jù)存儲方格陣信息的矩陣table1010來重繪桌面上的窗口。這樣可以達到一種類似于動畫的動態(tài)顯示效果。具體的流程圖：checkcircle()的流程圖是：/此處僅僅是列出對貓的檢測函數(shù)，老鼠的大致類似。cat_countij大于5次i=cat_tempx; j= cat_tempy;cat_dir左轉(zhuǎn)或右轉(zhuǎn)90參數(shù)：cat_tempx，cat_tempy，cat_direndyescat_dir是否改變解釋：貓是否從tableij走過5次yesnonocat_dir調(diào)轉(zhuǎn)18

9、03.3.2 貓的處理函數(shù)貓的成員函數(shù)只有一個catroute()。該函數(shù)的功能是，每過一秒就為貓選取下一步要走的方向。這是在為貓做一個決策。在該模型的設(shè)計中，假設(shè)貓可以看到以自己的坐標(biāo)為中心，上下左右各擴展n個方格的(n+1)*(n+1)范圍內(nèi)的所有信息。那么，貓就可以對這(n+1)*(n+1)小的方格陣進行遍歷，然后做出判斷，具體決定下一步該如何走。如果從這(n+1)*(n+1)方格陣中發(fā)現(xiàn)了老鼠，就采用一種最短路徑走法來改變方向。反之，則仍然按照題目的規(guī)定來走。首先，這個(n+1)*(n+1)的小方格要從對象方格陣中提取成員變量table1010來獲取。其次，在從table1010中提取

10、(n+1)*(n+1)小方格陣時，要防止數(shù)組邊界越界。再者，須設(shè)置一個變量find_rat，當(dāng)在(n+1)*(n+1)小方格陣中遍歷到了鼠的存在時，就將find_rat這一旗幟變量賦值為正。反之，賦值為反。該仿真模型中，最短路徑走法采用了廣度優(yōu)先遍歷算法。本設(shè)計之所以選取廣度優(yōu)先遍歷算法是基于一下兩點：一、貓是在搜索老鼠，所以這可以用一個搜索類算法來實現(xiàn)；二、貓應(yīng)該是要找到一個最短的路徑去靠近老鼠。而廣度優(yōu)先遍歷便是滿足上述兩個條件的比較適合的算法。廣度優(yōu)先算法的特點是：在搜索的過程中，廣度搜索算法對于節(jié)點的搜索，是沿著層次擴展的。如果要遍歷第n+1層的節(jié)點，必須先遍歷完第n層的節(jié)點。那么，對

11、于同一層的節(jié)點來說，它們對于問題求解的價值是相同的。所以這種算法一定能保證找到最短的路徑。廣度優(yōu)先遍歷算法，有一個要求是問題具有層次性，而該模型中的層次并不是十分的明顯。具體在本程序中，可以這么來描述層次：貓或老鼠每次都只能走4個方向上、下、左、右中的一個。假設(shè)這4個方向都是可走的，則這四個方向?qū)τ趩栴}求解的價值是相同的。再擴展下去，上一層的4個方向，每一個方向又可擴展出4個方向。再在這16個方向（可能有重復(fù)）上進行擴展。這樣層次便體現(xiàn)出來了。如果在(n+1)*(n+1)小方格陣中沒有發(fā)現(xiàn)老鼠，就應(yīng)按照題目的規(guī)定來走：貓和老鼠的移動方式相同，平時沿直線走，下一步果會走到障礙物上去或者出界，就用1個單位時間做一個左或右轉(zhuǎn)90度。具體的catroute()函數(shù)流程圖：ifrat()/尋找老鼠find_rat=1最短路徑走法一般的走法進入程序endnoyes3.3.3 鼠的處理函數(shù)鼠的處理函數(shù)ratroute()同貓的處理函數(shù)大致相同。故在這里可參考貓的處理函數(shù)。程序裝載在仿真的過程中，一開始，經(jīng)過小組集體討論，確定了基本的數(shù)據(jù)結(jié)構(gòu)，以及3個對象的具體接口設(shè)計。從而將界面設(shè)計和具體的算法設(shè)計分開了。在這里，程序裝載過程，其實就是進行界面程