2016年10月20日 星期四

Scratch迷宮尋寶與簡易AI設計

當看到外國網友A Oliver寫的Pacman for Scratch,除了驚嘆作者用Scratch寫程式的功力以外,當然也要給他好好的玩一玩。






除了重溫小時候的回憶之外,當中最吸引長大後的我,已經不是玩主角過關,而是遊戲中的敵人是怎麼設計的?這也讓我進行了幾次的探索,思考如何用Scratch來實作迷宮尋寶中的AI設計。


當然,不同的迷宮有不同的走法,不同的迷宮也有不同的設定。為了簡化問題與設計,所以一開始的迷宮的設定如下:

     1、只有白色的路可以走,其他某個顏色是牆壁
     2、迷宮的路只有上下左右四個方向
     3、迷宮的路是一根腸子通到底

實作出來的第一版的迷宮尋寶AI如下:

https://scratch.mit.edu/projects/126460778/

這個原型的AI大致的演算法如下:


當然,這個AI有很多問題,比如把寶物與主角的位置對調,或是遇到有左轉及右轉的路,主角就會無法找到寶物。怎麼辦呢?

為了解決以上的問題,於是又做了第二版的迷宮尋寶AI

https://scratch.mit.edu/projects/126463199/

第二版AI的演算法大致如下:


這次的AI總算聰明一點點。當然程式也長了一些,多寫了一些偵測左右是有路的程式。
這樣如果是任意改變主角與寶物的位置,都能夠找得到。

接下來呢?目標當然是想把這個自己做的AI放到以下的迷宮囉!
(嗯!自己寫的AI放到小時候玩過的遊戲中,這個有趣)



當把AI放進去時,再做一些大小與牆壁顏色的調整,結果…真是各種慘不忍睹啊!
無法找到寶物的悲劇,與寶物擦身而過的悲劇,離寶物越來越遠的悲劇。

沒辦法,只好多思考問題的所在,自己發現有個關鍵點是---中間叉路

中間有叉路時,必需要做一些處理。當然有一種解法,
如果AI能夠記住叉路是最好,
但是一來複雜,二來Scratch對於資料結構的支援還很陽春。於是想到的方法是
幫主角增加特殊能力--可以偵測寶物的方向。這個特殊能力可以想做是生物的嗅覺。
這也是原本pacman中敵人追蹤主角的能力。利用這個能力來幫助做彎路與
叉路的轉向判斷。

於是做出來的是這個第三版迷宮尋寶

https://scratch.mit.edu/projects/126464921/

也做了一些功能,可以在一開始用滑鼠決定主角與寶物的位置。
這樣就比較像個遊戲了。

第三版AI大致的演算法如下:


當然這個AI還是在這個Pacman的迷宮中,仍然還是有少數找不到路的情形。但是能找到的情況變多了。個人也覺得很滿意了。(程式已經有點複雜了,不敢再寫下去了)

雖然自己沒有受過專業的訓練,而且用的是Scratch,但是在探索的過程中種種的問題與修正,困難與成長,不斷的充滿著驚喜與樂趣呢!(當然想不出來亦是很苦惱的)




沒有留言:

張貼留言