How to Design Petrescue

http://www.zenlife.tk/petrescue.slide
难点分析
游戏逻辑
关卡生成
关卡校验

Part1 游戏逻辑
基本块消除算法

World是一个二维数组。每个Tiled有一个唯一的ID标识它是什么。
mark-sweep算法
第一遍利用深度优先或广度优先进行标记。第二遍消除被标记的块。

下落中的下落
基本下落的实现是先把块移到目标位置，加个状态标识下落中，再插入动画，动画放完再设置状态为正常
问题：没有动态坐标，只有初始和结束坐标。
解决方式：下落中的块的点击无效。

平移
整个游戏中最难实现的点！

屏幕上移
给平移和下落的块加入引用计数，只有当没有平移和下落中的块时才允许屏幕上移

道具实现
炸弹/光波/陨石/星云/可变块/冰块/网格容器/星尘容器/2倍/钥匙/刷子
没有哪一个格外难，但是种类多了之后就引入了一些复杂度!而且bug概率随道具种类的增加是指数增长。

Part2 关卡生成
最初的版本
随机填充。对World的所有位置for循环一遍，每个格子随机上色。
发现问题:
非常难求解。有时候求解算法跑上2分钟才出结果。
机器验证有解的地图，给人解也解不出来。

难度控制
基本思想：控制生成块的大小以控制难度。生成块比较大则难度降低。
如何控制生成块的大小？
选色
方向控制
大小控制

选色
洗牌算法：对数组乱序后取前几个
抽样算法：N选M

填充算法
一个容器放待填充的位置，一个数组标记位置是否已填充
每次填充一个区域。随机选一种颜色，以一个随机坐标为起点，向上下左右四个方向生长。有个概率值是否继续生长下去。
比如给一个控制方向的概率数组[30, 30, 20, 20]，再给一个控制大小的概率数组[100, 80, 70, 50, 30, 0]
struct Pos {
    x int,
    y int,
}
将待填充的坐标点全部放在一个数组里，给数组乱序。
遍历数组，每次拿一个坐标点。
如果对应位置已标记则跳到1，否则以这个点为种子开始生成。生成以后将对应的标记表加上标记。

形状控制
生成某种形状，里面的颜色是随机的，周围块与它颜色不同以保证形状不被破坏。
mark一遍确定形状和形状边界。对形状上一种颜色，对形状边界调用填充算法。
如何排除某种颜色？选中的跟第一个交换！
问题：两个形状之间的填充是随机的，不能保证最终结果。
解决方式：只能由用户保证。加载地图人工识别。

形状控制2
多个分离的形状，随机成同一种颜色。
别人怎么做的？不保证形状周围与形状块不同颜色。

配置文件
generate -f fileName -t timeOut -c count -n threads -r configFile -s false
100 80 70 50 30 0
30
30
20
20
5

Part3 关卡校验

深度优先搜索
这个问题的本质是一个树的遍历。
树的分枝非常多，状态成指数增长，遍历所有状态不靠谱。
不需要找出所有的解，只要确定有一个解即可。

优化1 尽量生成有解的
发现的问题：机器能找到解，但人解不出来
直接生成有解的地图这种方式是行不通的。

优化2 加入超时机制
几秒内无法解得一个可行路径，即可假定这张地图是无解的。
因为我们只要找有解的地图，而不需要确定某张地图是否一定有解。
抛弃这张地图，重新生成一张。

优化3 贪心策略
每次倾向于得分更多的点击。
利用优先级队列。模拟点击以后，状态优先级等于当前状态优先级加上点击消除的得分。

优化4 充分发挥Go语言多核下的优势

优化5 避免重复状态进栈

完全走了一条弯路
刷子，变化块等特殊道具的出现使得验证关卡是否有解几乎不可行。
别人是如何做的？他们不在乎关卡是否有解!
这是个大坑!!!

总结
这是一个算法逻辑占的比重非常大的游戏。其中大量用到了深度/广度优先遍历，洗牌/抽样等概率算法，贪心等一些启发式的策略。

Generate Game Map

http://www.zenlife.tk/level-generator.md

地图校验

生成tmx格式的地图并不难。难点是验证生成的地图是有解的。这个东西比较麻烦，开始想过一种思路是生成地图的时候直接按某种规则去生成有解的地图。但是由于卷屏，障碍物，特殊道具等，使得这个实现起来不太可行。

然后就只好用最笨的方式了，随机生成地图，事后验证地图有解。模拟点击事件进行校验，暴力搜索所有的状态。按深度优先的方式去搜索，只要找到一个解就退出。内存开销方面，只有在状态被遍历到的时候才会生成新的状态，内存使用量也就是搜索深度乘以一层的分支数。内存应该问题不大。

出现的一个问题是时间复杂度。假设只是79的格式，则一层的分支数是63，地图无解的情况下需要遍历所有可能的状态，于是会出现63^n条路径需要遍历。而且每一次状态进行验证时，也涉及到了一个mark-sweep，是一个深度或广度优先的算法。随便就到了阶乘的复杂度，时间复杂度太高了，几乎不可用。37的无解地图，足足用了10多秒才能确定它是无解的。5*7的无解的地图跑了几分钟都没出结果。

时间问题确实是目前的一个大难题，想到的一些解决思路。一方面是做限时。这个问题很明显，有解的情况只要找到一个解就可以退出，因此速度很快。而无解情况要遍历所有的情况才能确定，因此会很慢。限定一个时间，如果没有找到一个解，就退出，抛弃这张地图，假定它是无解的。反正我的需求是找有解的地图。

另一方面就是做一些启发式的搜索了，优先挑更可能的路径进行搜索，比如贪心算法，每次找最大的一块进行点击。这个更接近用户行为，这样找到的解也更好理解一些。否则出现某张地图有解，但用户试了很多遍都无法通关的情况，他们要么买道具，更可能就是删游戏了。

接下来还能做的一些优化就是并行方面考虑。

How to design 15 puzzles game

X. Random generate and check whether solvable.
http://www.codeproject.com/Articles/332458/Puzzle


X. Move or change from solution.
http://gamedev.stackexchange.com/questions/42096/creating-practically-solvable-15-puzzle-inputs
KISS
Just start with finished puzzle, and then make let's say 10 random moves (1 for every second) of tiles to make sure the puzzle is both solvable and can be done in 10 moves. Make sure your moves don't negate previous, e.g. moving 3 tiles in "circle" or moving a tile back where it was before previous move.

http://www.wikihow.com/Solve-a-Fifteen-Puzzle