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 避免重复状态进栈
完全走了一条弯路
刷子，变化块等特殊道具的出现使得验证关卡是否有解几乎不可行。
别人是如何做的？他们不在乎关卡是否有解!
这是个大坑!!!
总结
这是一个算法逻辑占的比重非常大的游戏。其中大量用到了深度/广度优先遍历，洗牌/抽样等概率算法，贪心等一些启发式的策略。
难点分析
游戏逻辑
关卡生成
关卡校验
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 避免重复状态进栈
完全走了一条弯路
刷子，变化块等特殊道具的出现使得验证关卡是否有解几乎不可行。
别人是如何做的？他们不在乎关卡是否有解!
这是个大坑!!!
总结
这是一个算法逻辑占的比重非常大的游戏。其中大量用到了深度/广度优先遍历，洗牌/抽样等概率算法，贪心等一些启发式的策略。
