[分享] 8 puzzle game
檔案連結：http://bleed1979.myweb.hinet.net/EightPuzzleV02.apk
就典型的8 puzzle game。
還在測試找看看有沒bug，就先分享給大家。
蠻無聊的，沒聲音，圖也不好看。
唯一的賣點是電腦AI，如果你玩不下去，可以點選電腦AI，會幫你接玩到結束。
程式很簡單，就不公開源碼了。
請大家儘量散佈。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.113.144
推
09/22 07:56, , 1F
09/22 07:56, 1F
我補一下遊戲做法好了。
initial state會是random產出但是這個random不是隨便產生的。
在一開始進行遊戲的時候，我會先從final state往前產生16步的所有可能。
將這些可能存放在HashMap裡。
所以initial state就是從第16步的眾多可能裡random一個出來。
這樣就確保有解。
當玩家使用電腦AI時，會從目前的盤面再產生16步的所有可能。
只要產生的圖中可以在原本的HashMap查找到，代表可以從目前的盤面找到解。
產生可能的方法是BFS（寬度優先搜尋）。
而為什麼要取16步呢？因為8 puzzle最多31步（有時間的人可以跑BFS到完成）
所以我前取16步，後取16步，就一定可以連結的上。
大致上是這樣。
※ 編輯: bleed1979 來自: 114.43.113.144 (09/22 12:00)
再補一下資料結構好了，免得沒講到code。
final class Puzzle {
long p; // 8 puzzle的值
int fatherIndex; // 上一步的索引
int zeroPos; // 空格的位置
int lastDir; // 上一步的方向
public Puzzle(long value, int lastIndex, int position, int direction) {
p = value;
fatherIndex = lastIndex;
zeroPos = position;
lastDir = direction;
}
}
上面的class代表一個盤面。
每4個bit代表一個數字，所以需要36個bit，用一個long就夠了，不開陣列。
fatherIndex是上一步的索引。
因為我寫的BFS是以queue來實作，所以要記錄索引位置。
zeroPos是空格的位置，我設定空格為0，因此命名。
會多這一個欄位是因為我不想到時候再跑一個迴圈去找0的位置。
lastDir是上一步的方向。
這是為了到時候電腦AI怎麼移動所記錄的。
我不太懂Java的容器，所以queue的部分就隨便選了ArrayList來使用。
ArrayList<Puzzle> queue ...
HashMap的部分key是盤面的值，value是索引位置。
HashMap<Long, Integer> history ...
BFS使用兩個迴圈完成。外迴圈是步數，內迴圈就是一直拿出放入queue的puzzle。
以上。
※ 編輯: bleed1979 來自: 114.43.113.144 (09/22 12:33)
→
09/22 13:40, , 2F
09/22 13:40, 2F
AndroidDev 近期熱門文章
PTT數位生活區 即時熱門文章
