http://www.zenlife.tk/level-generator.md
地图校验
生成tmx格式的地图并不难。难点是验证生成的地图是有解的。这个东西比较麻烦，开始想过一种思路是生成地图的时候直接按某种规则去生成有解的地图。但是由于卷屏，障碍物，特殊道具等，使得这个实现起来不太可行。
然后就只好用最笨的方式了，随机生成地图，事后验证地图有解。模拟点击事件进行校验，暴力搜索所有的状态。按深度优先的方式去搜索，只要找到一个解就退出。内存开销方面，只有在状态被遍历到的时候才会生成新的状态，内存使用量也就是搜索深度乘以一层的分支数。内存应该问题不大。
出现的一个问题是时间复杂度。假设只是79的格式，则一层的分支数是63，地图无解的情况下需要遍历所有可能的状态，于是会出现63^n条路径需要遍历。而且每一次状态进行验证时，也涉及到了一个mark-sweep，是一个深度或广度优先的算法。随便就到了阶乘的复杂度，时间复杂度太高了，几乎不可用。37的无解地图，足足用了10多秒才能确定它是无解的。5*7的无解的地图跑了几分钟都没出结果。
时间问题确实是目前的一个大难题，想到的一些解决思路。一方面是做限时。这个问题很明显，有解的情况只要找到一个解就可以退出，因此速度很快。而无解情况要遍历所有的情况才能确定，因此会很慢。限定一个时间，如果没有找到一个解，就退出，抛弃这张地图，假定它是无解的。反正我的需求是找有解的地图。
另一方面就是做一些启发式的搜索了，优先挑更可能的路径进行搜索，比如贪心算法，每次找最大的一块进行点击。这个更接近用户行为，这样找到的解也更好理解一些。否则出现某张地图有解，但用户试了很多遍都无法通关的情况，他们要么买道具，更可能就是删游戏了。
接下来还能做的一些优化就是并行方面考虑。
