C++程序反编译笔记(21) 扫雷的核心算法和数据结构

    大家新年好啊!

    我觉得最后再分析一下扫雷的核心算法和数据结构, 就可以结束了. 如果疑问, 可以提出来.

雷区数据结构

    通过绘制雷区的的代码可以找到表示雷区的变量.

    上面的代码将 g_compDCs[index] 里的位图数据复制到窗口中, g_compDCs是一个HDC[16]的数组, 每个元素保存了一幅图片, 比如未点击的图片, 数字1-9的图片, 旗子的图片等. 将 index 替换成 0 ~ 15 的常数, 可以看到对应的是哪幅图片.

    而g_mineTable就是存放雷区信息的数组了. 这是一个char[864]的二维数组, 864 = 32 * 27, 每行32个元素, 这就是自定义时最大的地图是24 * 30的原因. 上图中的循环是从1开始的, 说明数组中的0索引不使用, 大概是为了符合从1开始的习惯.

    数组元素占8位, 其中低5位是图片索引, 可以从 & 0x1F 看出来, 0x1F = 0001 1111. 高3位是3个标志位, 下面再说. 

扩展的算法

    所谓扩展, 就是点一个0格子后, 判断周围的格子是否要自动点开.

    通过在鼠标弹起的地方下断点, 然后单步执行这种方法找出点开格子的函数. 

    0x40 = 0100 0000, 说明雷区数组元素的位6是表示格子有没有点开过的. 继续跟踪

    cell 是雷区元素指针, *cell > 0 说明最高位为0. 代码是执行到这个if语句内部的.

其中g_array是3个全局变量合成的一个变量, 它实际是一个100个点的数组, 保存的是当前格子周围的所有0格子的坐标. 

    g_array.Reset 是这样的

    后面的代码就是打开当前格子及它周围的8个格子了.

    (cell & 0x40) != 0 说明这个格子处理过了, 直接返回. 16应该是一个特殊的值, 不代表具体的格子, 14则是 ? 的格子, 可能也有什么特殊意义.

    dword_10057A4 是已经处理过的格子数量, 与判断游戏是否结束有关, 这个没有深入分析.

    接着, 用CountMines计算当前格子周围有多少个地雷, 标志这个格子已经处理过来, 绘制点开的格子图片, 如果是0格子的话, 就加入到g_array中.

    这个函数计算周围雷数, 最外层的 if 意义不明. 最里面的 if 可以推出 雷区数组元素的最高位表示该格子是否是地雷.

后话

    对于没有深入分析扫雷的原因, 我说明一下:

    我觉得研究的是反编译的技术, 目标是构建出可以运行的项目, 并且这个项目编译出来的程序和原来的程序尽可能相等. 至于源代码, 想要百分百还原出来是不可能的, 函数名, 注释这些信息, 在编译的时候就完全被去掉了(除非是调试版的程序).

    接下来要去找工作了, 有时间的话会反编译Windows的记事本程序.

    扫雷项目的下载地址是 :  https://gitee.com/chenguc/Saolei.