近两天准备出个拼图游戏的教程, 准备时候遇到一些问题, 收集保存分享下来, 一来自己用, 二来涨点知识, 三来有需要的小伙伴刚好也看看.
事情起因很简单, 比如下面这个拼图 (矩阵):
1 2
3 空
这样一个 2*2 矩阵, 是标准原始矩阵, 但是变一下:
3 1
2 空
这样是可还原的 (空和附近的可以换位置, 空 2, 空 3, 空 1, 空 2 即可).
但下面这个呢?
1 3
2 空
你还能还原吗?
这个不是怪你, 是真的没法还原.
当时脑子里面过了一下, 就发现不行, 然后查了查资料, 真的有前辈搞过相关的问题, 并且有了靠谱的答案.
假如两个矩阵, 从左到右, 从上到下排序, 两个矩阵的逆序数 + 空所在行 + 空所在列数的值的奇偶性相同, 则可以还原或者说等价; 若不同, 那就无法还原.
又上面说的问题, 尝试去玩了几个拼图游戏, 发现这些家伙都是鸡贼, 各个块可以直接点击与任意位置的互换, 那就不存在无解的问题了啊......
问题是, 这样游戏本身的难度就几乎没了, 游戏性简直不能看......
哦, 对了, 忘了说啥是 "逆序数", 逆序数解释如下:
比如 1234 排列是基准, 然后两个排序分别是 4321,3214.
逆序数说的是在原有排序基础上, 在新排列出现与基础排序顺序前后顺序不同则算一个逆序数.
那么分析那 4321.43,42,41 三个, 32,31 两个, 21 一个, 所以逆序数是 1 + 2 + 3 = 6 个; 而 3214,31,32 两个, 21 一个, 所以逆序数是 2 + 1 = 3 个. 1234 为基准, 即 0 个. 所以 4321 与 1234 是等价的, 可解; 3214 与 1234 不等价, 不可解.
那最上面的对比, 123 是基准, 312 逆序数为 2,132 逆序数为 1, 所以 132 不可解.
算起来很复杂, 但是通过双层循环来处理, 只要不是太多的数字都还可以接受, 毕竟是给人玩得游戏, 就算 10*10 的矩阵, 时间复杂度顶天了也就 O^2, 优化成 OlgO 也不是不行, 所以还是可以搞搞的.
具体算法代码如下:
- // 基准就是自然排序, 递增是正常的, 就是后面一定比前面的都大.
- const cal = num => {
- let arr
- if(typeof num === 'number') {
- let strs = String(num)
- arr = Array.from(strs, str => Number(str) || 0) // 安全处理, 转换错误给 0
- } else arr = num
- let length = arr.length
- let reverse = 0
- for(let i = 0; i <length - 1; i++) {
- let n = arr[i]
- for(let j = i + 1; j < length; j++) {
- let m = arr[j]
- if(n> m) reverse += 1
- }
- }
- console.log(reverse)
- }
- cal(4321) // 6
- cal(3214) // 3
- cal(312) // 2
- cal(132) // 1
- cal(54321) // 10
- cal([10, 14, 21, 7, 3, 12, 0]) // 15
这样就好了, 下次要写拼图游戏时候, 只要去专注业务逻辑就行, 游戏初始化的问题就用这个代码拓展即可.
还有一种方法就是初始化的时候按照标准序模拟合法移动 N 次, 然后在逆向工程即可. 但是这个方案拓展性几乎为 0, 所以放弃.
写业务要注意这种陷进逻辑哈, 祝你玩的开心.
喜欢文章的话, 请关注一波, 定期更新技术文章, 满满的都是干货.
来源: http://www.bubuko.com/infodetail-2806067.html