[分享] 自製益智遊戲-NP Lab之著色問題

看板Little-Games (小遊戲)作者Alimen (狂人)時間13年前 (2013/05/01 16:33)推噓7(7推 0噓 0→)

留言7則, 7人參與討論串1/1

遊戲名稱: NP Lab : Coloring Problem / NP Lab之著色問題遊戲簡稱: 著色問題遊戲類型: 自製 / 益智 / 對奕 / 搶三十遊戲截圖: http://ppt.cc/7Ee- 遊戲載點: http://alimencave.blogspot.tw/2013/05/np-lab.html (推薦使用Google Chrome或Mozilla Firefox瀏覽器， ie或pcman可能沒辦法執行) 遊戲介紹: 　　在計算複雜度理論的領域中，圖著色問題(Graph Coloring Problem)是一個著名的NP-Complete問題，並可簡述如下：給定一無向圖，其中相連的點必須被塗上不同顏色，試問需要多少種顏色，才能把圖上所有的點都上色？　　有點頭暈了嗎？麻煩撐住一下，或是實際玩玩看吧？　　「NP Lab之著色問題」是一個由圖著色問題發想的雙人對奕小遊戲，規則如下：　　　1. 輪到你時，你必須選擇一個區域(region)來著色　　　2. 相鄰(adjacent)的區域不能是相同的顏色　　　3. 當一個區域沒有可塗的顏色時，會自動變成黑色　　　4. 如果輪到你時，沒有區域可以上色，你就輸了　　幾個小提示：　　　1. 第一次玩的玩家：保持「我塗完後還剩下偶數個區域」的步調，就有一定　　　　的勝率　　　2. 單人模式中，困難度「簡單」從Level 1開始打，「普通」從Level 5，而　　　　「困難」從Level 9 開始 3. AI的核心是簡單的貪婪演算法，最多預測兩步；在Level 13之前，AI有一定的機率放水，優先選擇能讓玩家獲勝的區域/顏色 4. Level 11 之後，玩家先手優勢取消　　Have Fun！遊戲心得: 　　這款「NP Lab之著色問題」的點子浮上我心頭，是在我剛上研究所沒多久的時候。那時候沒事就窩到咖啡館喝咖啡吃paper，某天，閒著發慌在公用的留言本裡塗鴉，底下墊著的論文給了我靈感，在紙上畫了幾條切割線就和朋友玩了起來。　　那時的規則就和現在的差不多了，主要只有end game條件不同吧。　　那時本來想做成flash小遊戲的，不過actionscript實在是本人的弱項之一，後來整個點子就被無限期擱置了。直到去年接觸到HTML5 canvas，想找個題材練習的情況下，才又回憶起當年有想過這個遊戲。　　HTML5的優點不少，包括強大的單一舞台(single stage)讓我不用再跟奇奇怪怪的 Flash MovieClip object打交道，點陣圖的取用也相對直覺，API的模式也和OpenGL有異曲同工之妙；但是它也有很大的缺點，例如要自己做double buffering、低效的 pixel access、缺乏向量動畫的支援等。尤其是向量動畫這一塊，現階段似乎可以引入svg來解，不過這就是之後的功課了。　　希望大家會喜歡～　　(謎之聲：究竟有沒有人能夠突破Level 15呢？ XD) -- 「你知道嗎？」納許的囚徒這樣對著他的獄友說：「據說柏拉圖的囚徒，都在看電影」「是阿是阿，」對方不耐煩地回答：「所以你下次到底要選合作還是背叛？」 ──《林人狂的小書櫃》 http://alimencave.blogspot.tw -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 27.105.15.187

推

CRPKT

05/01 16:47, , 1^F

05/01 16:47, 1^F

沒耶，這完全是手刻的；下次來試試看吧！

推

gemini2010

05/01 16:49, , 2^F

05/01 16:49, 2^F

......XD

推

sihong