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