▲ T. R. Jensen, B. Toft, "Graph Coloring Problems", Wiley-Interscience, 1994
遊戲名稱：NP Lab : Coloring Problem / NP Lab之著色問題遊戲類型：自製 / 益智 / 對奕 / 搶三十
全破所需時間：???
(推薦使用Google Chrome 或 Mozilla Firefox 瀏覽器觀看本頁)
給螢幕不夠寬的朋友：在新視窗開啟
2013.May.01 update: 在Quit對話框中增加Restart level功能 (感謝bastardxx的建議！)
2013.May.09 update: 原下載連結改到gh-pages上，現可開新視窗來玩 (感謝gpmm的建議！)
2013.May.16 update: 將圖檔由Google Site搬至gh-pages，以期改善下載到一半時卡住的情形
在計算複雜度理論的領域中，圖著色問題(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！
▲ 遊戲截圖
Omake：Source code：GitHub
Commit 次數：149次
最長Commit間隔：2013.Feb.19 ~ 2013.Mar.10
Code size：4984行、120KBytes (壓縮後43.9KBytes)
圖檔數量：24張
這款「NP Lab之著色問題」的點子浮上我心頭，是在我剛上研究所沒多久的時候。那時候沒事就窩到咖啡館喝咖啡吃paper，某天，閒著發慌在公用的留言本裡塗鴉，底下墊著的論文給了我靈感，在紙上畫了幾條切割線就和akilo玩了起來。
那時的規則就和現在的差不多了，主要只有end game條件不同吧。
那時本來想做成flash小遊戲的，不過actionscript實在是本人的弱項之一，後來整個點子就被無限期擱置了。直到去年接觸到HTML5 canvas，想找個題材練習的情況下，才又回憶起當年有想過這個遊戲。
HTML5的優點不少，包括強大的單一舞台(single stage)讓我不用再跟奇奇怪怪的Flash MovieClip object打交道，點陣圖的取用也相對直覺，API的模式也和OpenGL有異曲同工之妙；但是它也有很大的缺點，例如要自己做double buffering、低效的pixel access、缺乏向量動畫的支援等。尤其是向量動畫這一塊，現階段似乎可以引入svg來解，不過這就是之後的功課了。
接下來，同一個主題應該還會出 Knapsack Problem 與 Cake Theory 湊成一個系列吧？不過我要先去和unity玩耍、休息一下囉！下次見！
特別感謝
T_C
美術顧問
Akilo
Quality Control
我媽
Testing & Feedback
▲ 和T_C討論時的一些手稿(笑)
0 意見:
張貼留言