第一次用C#寫游戲。在C#上寫算法果然是一個挑戰(zhàn)，時間復(fù)雜度太大的話造成的后果比C++明顯好多，于是總是盡量把東西做成O(n)或者O(nlogn)。這次就在上面實現(xiàn)了一個尋路算法。
這個尋路算法是這樣的：在16×16的方格上有一些終點，東西在格子上只能上下左右行動。每一個格子需要記錄到其中一個終點的最近的路的所有方向（就像三層循環(huán)的尋路算法一樣，最后給出矩陣的那個）。
于是我用了寬度優(yōu)先搜索和一個隊列來搞定這個事情。一開始算法寫錯變成O(n2)結(jié)果每一次處理都要1秒鐘。后來改正了之后結(jié)果瞬間給出。
算法如下：
1：把所有的GOAL加入隊列并標(biāo)記。
2：記錄當(dāng)前隊列的元素數(shù)量。
3：彈出一個元素，并將所有未標(biāo)記的鄰居添加一個指向自己的方向，將這些鄰居不重復(fù)地放入隊列（可以再用一個不同的標(biāo)記來檢查），標(biāo)記這個元素（非鄰居）。
4：如果彈出的元素數(shù)量沒有第2步記錄的那么多，則轉(zhuǎn)3。
5：如果隊列數(shù)量非空，轉(zhuǎn)2。
6：結(jié)束。
執(zhí)行這個算法，可以得到每一層分別是：
這個算法可以在添加障礙物的時候重新計算，僅需障礙物在一開始就被標(biāo)記就行了。
C#果然是用來做大作業(yè)的不二選擇啊，開發(fā)真是方便，而且不用顧及內(nèi)存問題（因為
一定占用非常多）。
posted on 2008-04-30 05:29
陳梓瀚(vczh) 閱讀(4485)
評論(5) 編輯 收藏 引用 所屬分類:
C++