作者Alimen (狂人)
看板GameDesign
标题[分享] 自制HTML5小游戏 - NP Lab之着色问题
时间Tue May 7 20:45:20 2013
感谢板主的认可，那我就把拙作贴过来了～
这个游戏比较特别的地方是我为了练习，
全部用HTML5写成，
不过都是很基本的语法、也没用library，
还请各位多多指教 ^_^;
游戏名称: 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 之後，玩家先手优势取消
Omake：
Source code：
https://github.com/Alimen/ColoringProblem
Commit 次数：151次
最长Commit间隔：2013.Feb.19 ~ 2013.Mar.10
Code size：4984行、120KBytes (压缩後43.9KBytes)
图档数量：24张
这款「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)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.85.209.161
1F：推 poshboy:HTML5游戏推～ 05/08 00:33
2F：推 cuteclare:挺厉害的Q_Q/膜拜 05/08 01:32
3F：推 feng79624:厉害@@ 05/08 05:06
4F：推 s0300453:推~ 05/08 11:29
感谢各位的厚爱^_^
5F：推 gpmm:html5 的话可以直接开 gh-pages branch 用 Github Pages :P 05/09 08:55
6F：→ gpmm:直接 hosting 在 Github 推广给大家玩 05/09 08:56
好主意！ 待我来试试看......
2013.May.09 update: 原下载连结改到gh-pages上，现可开新视窗来玩
(感谢gpmm的建议！)
※ 编辑: Alimen 来自: 219.84.209.188 (05/09 14:32)
7F：推 cowbaying:看了你的文 让我也想要把游戏移植到HTML5了 05/09 14:39
^_^
8F：推 cmcer:还有人在用ie6的情况下，flash反而是比较单纯的solution... 05/09 20:55
这是一个值得讨论的议题，
但现阶段我能够想到的最佳解是在不支援的浏览器中显示：
"Your browser does not support HTML5 Canvas. Try Google Chrome (下载连结)"
9F：推 yoco315:用 opera 跟 firefox 都只能读取到 88% 就停住了 05/10 20:50
10F：→ yoco315:chrome 也是 /_\ 05/10 20:51
我东西放在Google Site，应该是连线的问题 我有一次在外面用中华电信也有碰到
(家里用So-Net没碰过)
loader那段还有很多可以改进的，不过没那麽快
在那之前就只能请你多重新整理几次了......
※ 编辑: Alimen 来自: 219.85.212.155 (05/10 21:48)
11F：推 xxxholic:题外话 问题应该是 「至少要多少颜色」...否则给「点数」 05/12 01:51
12F：→ xxxholic:种颜色必可着色 05/12 01:52
已修改，谢谢指正！
13F：推 xluds24805:为什麽我第十一关赢了只能选择restart...? 05/13 01:25
这个我没试出来过......我再看看，谢谢！
14F：推 yoco315:已经重新整理九千多次了 qq 05/15 08:10
我把档案全部移到gh-pages上了，麻烦再试试看罗^_^;
如果还是不行的话，可能要麻烦你先到github上下载，原始码里有附执行档可以玩
※ 编辑: Alimen 来自: 219.84.210.9 (05/16 15:49)
15F：推 yoco315:挖哈哈，用 fx 终於可以玩了～输了，很生气 05/28 15:31
总算可以让你正常玩了 (泪目推
※ 编辑: Alimen 来自: 219.85.248.139 (05/30 09:53)
16F：推 LFking: 07/23 14:27