其實我們的向心法則還挺浪費時間的，不過還滿好用的就是了。
首先還是一樣，和中右法則一樣，先定義好迷宮資訊，和第一格的資訊。
講白了，我們的向心法就每一格都算一次FLOOD 演算法，這樣每格就都會有一條建議路徑提供給電腦鼠怎麼走會比較快的走到終點。因為方式都一樣，所以就不任外做了。
不過用這樣的向心法有一個缺點就是，如果FLOOD 的執行效率很低的話，是會算不出路徑的。
所以是有必要針對FLOOD 演算法做最佳化的動作。
原先我們使用掃描的方式，也就是需要每格每格的找出需要被更新的格子，這樣的運算非常浪費時間，運算起來大概約9ms @ 30MIPS。
我們使用了資料結構的方式，將需要被更新的格子記錄起來，下一次再更新被記錄的格子即可，這樣的運算時間約3ms @30MIPS。
大概只要完成了向心法則，大概電腦鼠就可以擁有滿聰明的大腦了。
至於還有一些程式技巧就需要給大家花更多的功夫研究了。
最近在研究迷宫產生器，我發現迷宫的資料結構表示是使用三維矩陣做的。它的組成元素為
回覆刪除Maze[i][j][RightWall]:說這一格到底右邊的牆在不在
Maze[i][j][ButtomWall]:說這一格到底下邊的牆在不在
上面牆則為Maze[i][j-1][ButtomWall]
左面牆則為Maze[i-1][j][ButtomWall]
之前沒有想到，原來可以如此表示。
不知版主在您的電腦鼠中是使用何種資料結構?
[版主回覆12/17/2008 16:35:12]其實是用二維來定義迷宮比較容易理解，不過我們的用法是用1維陣列來表示而已。
unsigned char maze_s[256] 牆壁資訊， 每個bit定義為 x， x ，x ， 是否走過， 東 ，南，西，北 ，初始化為0x00;
unsigned char maze_f[256] 牆壁資訊， 每個bit定義為 x， x ，x ， 是否走過， 東 ，南，西，北 ，初始化為 0xff;
另外有2個變化需要記錄方向與位置，c_n 與c_d，c_n為現在的格子，c_d為車頭方向。
左面牆應為Maze[i-1][j][RightWall]，複製後忘了改。
回覆刪除[版主回覆12/17/2008 16:39:34]用三維來記一邊的牆壁資訊好浪費喔。
這樣需要 16*16*8 = 2048 的byte，當初我老闆用matlab寫，也是類似這樣寫法，寫起來很方便，不過很浪費data memory。
那maze_s和maze_f差在那裏?
回覆刪除我本來也是想說每個座標都要記錄四邊牆。結果發現別人少用二個。因為左牆等同於左側座標的右牆。如果每個座標都記四面，測到少一面牆不就要在二組相隣座標都要做修改?
[版主回覆12/17/2008 16:54:33]嗯，所以我們有支副程式是需要同時做上下左右四面相鄰的牆壁做更新的動作，maze_s 是在search 時會用到，初始化為0x00為我們定義0為沒牆，1為有牆，而剛開始時，老鼠是不知道迷宮長什麼樣子，所以要把所有的牆試為都可以走。
但在最後走到終點要再算最短路徑時，需要認為沒有走過的都是牆璧，不然在算最短路徑的時後，很可能因為誤判而算出一條錯誤的路徑出來。其實也是可以利用maze_s 反推回maze_f。
不過好像一格只管2邊牆似乎比較單純，我記得我學弟在做borland c++ 的時後，就有用這樣的概念在做，這樣在管牆壁比較簡單，因為一格只需要管2面就好了。
這樣說，如果改成一個座標管二面，那maze_s和maze_f有機會合併了，各用4個bit。
回覆刪除[版主回覆12/17/2008 17:12:06]應該是可以，不過假設每面牆都管南邊和西邊的話，那最上面的北邊和最右邊的東邊牆是沒有牆的，就需要針對這地方去做判斷。
印象中，學弟是將外圍設成都是牆，所以好像沒有這地方的問題，實作上要怎麼消掉這地方的問題還要再研究一下。
因為程式上還是需要拿牆壁的資料來當作校正的依據，所以當牆不見時，好像又有其他的因素會存在。
我寫了產生迷宮及找解的程式。發現一件事，在搜尋時，走過的座標做標記。在找解的時候，也只找走過的標記。所以在搜尋時標記為1，在找解時再標記為0，剛好用掉。所以只用1個bit就可以做事了。
回覆刪除[版主回覆12/23/2008 11:16:31]是指已知牆面資訊，找最短路徑嗎？ 不過迷宮有4個方向，如何找最合適的路徑？有可能四邊皆走過，要如何走正確的路？ 如果走錯誤的路的話。刪掉旗標就不見了，也不能重建了。
四個方向?不是只有三個分支嗎?不會倒走回去吧。一個是來源方向，三個是下一個可走方向。整個路徑搜尋等於是最多有三分支的樹狀結構。使用有代價的路徑尋找法，結點訪問使用先廣後深法。假設貪進法是可行的，區域性最佳解可能是最後解的一部分，就可以用。可是好像會用很多記憶體做節點記錄。
回覆刪除這是我的想法啦。
[版主回覆12/23/2008 12:07:16]老鼠走到死巷子就會"馬庫"，所以會產生四個方向。