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

[Alimen (狂人)]

遊戲名稱:       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       :你有試過 KineticJS 嗎
沒耶，這完全是手刻的；下次來試試看吧！

推 gemini2010  :Nash的獄友不是Kobe嗎?
......XD

推 sihong      :推!
感謝推！

推 FoxQ        :玩到22關  好奇總共有幾關  回首頁就...重來了= =
殘念～ 不過其實Level 25以後參數都一樣了  除了背景圖、起始玩家繼續輪之外 XD

推 horazon     :15關以後有什麼差別(AI上)嗎? 我過了呀
當初在內測時還沒有接關功能，死了就回主畫面  十五關是我個人最高紀錄...... :p

推 overhead    :既熟悉又痛苦
抱歉勾起你的痛苦回憶...m(_ _)m

推 oginome     :這不是著名的四色問題的演算？
Graph Coloring Problem應該算是四色問題的高階型式吧？

※ 編輯: Alimen          來自: 219.85.209.161       (05/07 20:27)
※ 編輯: Alimen          來自: 219.84.209.188       (05/09 06:50)