遊戲名稱: 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 沒耶，這完全是手刻的；下次來試試看吧！ ......XD 感謝推！ 殘念～ 不過其實Level 25以後參數都一樣了 除了背景圖、起始玩家繼續輪之外 XD 當初在內測時還沒有接關功能，死了就回主畫面 十五關是我個人最高紀錄...... :p 抱歉勾起你的痛苦回憶...m(_ _)m Graph Coloring Problem應該算是四色問題的高階型式吧？ ※ 編輯: Alimen 來自: 219.85.209.161 (05/07 20:27) ※ 編輯: Alimen 來自: 219.84.209.188 (05/09 06:50)