# [出题] CatsOrganizedNeatly

# 缘由

主要目的其实是想改编成一道院赛题目。一个挺常规的 DFS 拼图,或许 OJ 上已经有一摸一样的原题了。但出于自己想折腾的念头,以及这个游戏确实玩得卡关了,就一步步看看怎么提取里面的数据。

# 大致题面

没什么特殊的,就是网格图中填充拼图块的搜索题。每个拼图还可以四个方向旋转。

# 数据准备

当然手搓数据是可以的但是那样太不优雅,而且可得费不少时间呢
直接进入游戏目录看下,大体如下:

--levels\
----level1
----level2
----...
--languages\
--data.win
--CatsOrganizedNeatly.exe
--...

其中 levels 就是关卡档案,打开看一下(节选 level1):

{
  "cats": [
    {
      "x": 896.000000,
      "id": 50.000000,
      "y": 576.000000,
      "angle": 0.000000
    },
    {
      "x": 1401.000000,
      "id": 2.000000,
      "y": 513.000000,
      "angle": 0.000000
    }
  ],
  "grid_size": 3.000000
}

很显然一个关卡用网格大小、若干猫咪就可以定义了。这里猜测网格的障碍也被纳入 Cats 类去了。cat 中的 x,y 应该是放置坐标,angle 是旋转角度。
然后试着拆包 data.win 。从 steamdb 上得知这个游戏使用 GameMaker 引擎,那么这个 data.win 包含了所有资源文件,可以使用 UndertaleModTool 进行解包。

看下 sprite,所有猫咪以 c 开头,拖拽状态的猫咪以 d 开头,障碍以 b 开头,还有其他背景相关的物体。

接着看一下脚本代码,从 level_load 入手,一步步搜到 cat_set_index 函数,这个函数里面的行为告诉我们,cat 的 id 在 0-29 表示猫咪,30 及以上表示障碍。那么现在就明白了 level 文件中 id 的含义,下面需要找到 id 对应具体猫咪的形状

顺腾摸瓜,找到 global.cats 的定义,这个列表存储的就是所有猫咪对应的 sprites 编号。发现其有序,也就是依次对应 c1-c30,比较方便。而 global.blockers 障碍列表的前 20 个是 b1-b20,第 21 个添加 151 号 sprite,查了一下是 board_tile_overpaint,一个 1x1 的空白图案障碍块。

每个 sprite 可以看到这些信息:

包括尺寸、锚点位置、碰撞掩码这些重要信息。猫咪的锚点其实用处不大。但是障碍涉及到在关卡布置中的旋转,还是需要提取出来锚点位置才能正确旋转的。
游戏在运作的时候并没有抽象的网格,而是直接使用碰撞检测,给网格障碍、各个猫咪包括网格边界加上碰撞掩码。同时,鼠标拖动的坐标位置是吸附在网格整点上的,能都放置猫咪直接通过碰撞检测就可以得到,这样实现了每次操作的合法性约束。当所有猫咪都顺利放置完了,也就过关了。
那么也就是说,为了得到一个网格化的游戏,还得自己转换一下。
不过好在游戏资源都可以扒下来,不需要手动录入数据。

下面想办法得到需要的数据。首先 UndertaleModTool 支持导出 sprites 的贴图和碰撞掩码。但是并不支持导出各项属性,包括我们需要的尺寸和锚点位置。
好在这个 UndertaleModTool 支持自定义脚本,而且代码开源。把它当下来看看怎么回事。用 VS 直接构建一下,看看 sprite 的界面,这里锚点属性 Origin 的输入框绑定给 OriginXWrapper,点进去,发现就是简单对 UndertaleSprite 对象 OriginX 的 get。

接着查看一下 ExportAllSprites.csx 脚本,发现其实并不复杂,加上导出 sprite 的属性应该不难。
直接问 GPT,很快得到这份代码。

using System.IO;
using System.Text.Json;
using System.Text.Json.Serialization;
void DumpSprite(UndertaleSprite sprite)
{
    string outputFolder = texFolder;
    if (useSubDirectories)
        outputFolder = Path.Combine(outputFolder, sprite.Name.Content);
    if (sprite.Textures.Count > 0)
        Directory.CreateDirectory(outputFolder);
        
    for (int i = 0; i < sprite.Textures.Count; i++)
    {
        if (sprite.Textures[i]?.Texture != null)
            worker.ExportAsPNG(sprite.Textures[i].Texture, Path.Combine(outputFolder, sprite.Name.Content + "_" + i + ".png"), null, padded); // Include padding to make sprites look neat!
    }
    // Export OriginX and OriginY to JSON file
    var originData = new
    {
        Width= sprite.Width,
        Height= sprite.Height,
        OriginX = sprite.OriginX,
        OriginY = sprite.OriginY
    };
    
    string jsonOutput = JsonSerializer.Serialize(originData, new JsonSerializerOptions { WriteIndented = true });
    File.WriteAllText(Path.Combine(outputFolder, sprite.Name.Content + "_prop.json"), jsonOutput);
    IncrementProgressParallel();
}

我把每个 sprite 的 Width,Height,OriginX,OriginY 导出到 json 文件。重启 UndertaleModTool,运行修改过的 ExportAllSprites 和 ExportAllMasks 脚本,所有需要的数据就都有了。

接下来就是解析这些数据,生成题目数据了

# 解析游戏数据

首先把上面得到的猫咪和障碍处理成网格图。将每个物体缩小 64 倍,就变成了网格图。另外,用 cv2 处理一下黑白掩码,得到猫咪和障碍的体块。这部分数据我导出成 meta.json,便于后面对关卡的处理。

import cv2
import json
import numpy as np
import matplotlib.pyplot as plt
meta={'cats':[],'blocks':[]}
mask_l=[]
def parse_item(path_prop,path_mask):
    fp_prop=open(path_prop,'r')
    json_prop=json.load(fp_prop)
    size,origin=[[json_prop[_] for _ in __] 
                 for __ in [['Height','Width'],['OriginY','OriginX']]]
    dsize=[_//64 for _ in size]
    dorigin=[_//64 for _ in origin]
    mask=cv2.imread(path_mask,cv2.IMREAD_GRAYSCALE)
    if mask is None:
        mask=np.ones(dsize)*255
    else:
        mask=cv2.resize(mask,list(reversed(dsize)),interpolation = cv2.INTER_AREA)
    item={['size','origin'][i]:{['x','y'][j]:d[j] for j in range(2)} for i,d in enumerate([dsize,dorigin])}
    item['verts']=[]
    for i in range(mask.shape[0]):
        for j in range(mask.shape[1]):
            mask_l.append(mask[i][j])
            if mask[i][j] > 10:
                item['verts'].append({'x':i,'y':j})
    print(item)
    return item
    
def task():
    cat_names=['c'+str(_) for _ in range(1,31)]
    block_names=['b'+str(_) for _ in range(1,21)]+['board_tile_overpaint']
    dir='./meta/'
    for name in cat_names:
        meta['cats'].append(parse_item(dir+name+'_prop.json',dir+name+'_0.png'))
    for name in block_names:
        meta['blocks'].append(parse_item(dir+name+'_prop.json',dir+name+'_0.png'))
    json.dump(meta,open('meta.json','w'))
def test():
    parse_item('./meta/b7_prop.json','./meta/b7_0.png')
if __name__=='__main__':
    task()
    # plt.hist(mask_l,bins=256)
    # plt.show()

接着将 levels 转换成网格图。这里麻烦的地方就是障碍物的旋转了,而且要考虑一下图片的坐标系和我们题目惯用的坐标系还有点区别。旋转我直接使用旋转矩阵乘法解决了。初始化的猫咪直接放弃旋转,因为猫咪方向、初始位置对游戏的顺利进行并没有任何影响。猫咪的输出格式我还是直接用 bitmap 表示了,比较简便直观。

import json
import numpy
rot={
    0:[[1,0],[0,1]],
    90:[[0,-1],[1,0]],
    180:[[-1,0],[0,-1]],
    270:[[0,1],[-1,0]]
}
rot={k:numpy.matrix(v) for k,v in rot.items()}
def test_rot():
    x,y=-2,0
    x,y=[int(_) for _ in rot[90]*[[x],[y]]]
    print(x,y)
    
meta=json.load(open('meta.json','r'))
max_cat_count=0
def parse_level(src_path, dst_path):
    level = json.load(open(src_path, 'r'))
    size=int(level['grid_size'])
    res_map=[['.' for _ in range(size)] for __ in range(size)]
    res_cats=[]
    bx=768-(size-7)*32
    by=320-(size-7)*32
    def add_block(i,j,block_id,angle):
        block=meta['blocks'][block_id]
        ox,oy=[block['origin'][_] for _ in ['x','y']]
        for p in block['verts']:
            p=[p[_] for _ in ['x','y']]
            p=[p[0]-ox,p[1]-oy]
            p=rot[angle]*[[p[0]],[p[1]]]
            p=p.reshape(1,2).tolist()[0]
            p=[p[0]+ox,p[1]+oy]
            print(block_id,i,j,p)
            res_map[i+p[0]-ox][j+p[1]-oy]='#'
    def add_cat(cat_id):
        res_cats.append(cat_id)
    for cat in level['cats']:
        x,y,id,ang=[int(cat[_]) for _ in ['x','y','id','angle']]
        i=int(y-by)//64
        j=int(x-bx)//64
        if(id>=30):
            add_block(i,j,int(id-30),ang)
        else:
            add_cat(id)
    
    
    def print_bitmap(bm,sx,sy,of=None):
        for i in range(sx):
            for j in range(sy):
                print(bm[i][j],end='',file=of)
            print(file=of)
    
    
    of=open(dst_path,'w')
    print(size,len(res_cats),file=of)
    global max_cat_count
    max_cat_count=max(max_cat_count,len(res_cats))
    print_bitmap(res_map,size,size,of)
    for index,i in enumerate(res_cats):
        cat=meta['cats'][i]
        sx,sy=[cat['size'][_] for _ in ['x','y']]
        mp=[['0' for __ in range(sy)] for _ in range(sx)]
        for p in cat['verts']:
            x,y=[int(p[_]) for _ in ['x','y']]
            mp[x][y]=1
        print(sx,sy,file=of)
        print_bitmap(mp,sx,sy,of)
    
if __name__ == '__main__':
    for i in range(1,81):
        parse_level('./levels/level'+str(i), './data/cats'+str(i)+'.in')
    # parse_level('./levels/level43','./cats.in')
    print('max_cat_count=',max_cat_count)

最后得到了 80 个关卡的数据,顺手写了份 std,发现没有什么问题。至此,这道题目就出到这里。这个游戏我也算是能通关了吧(逃)


样例输入

4 4
...#
.#.#
....
....
2 2
10
11
2 2
01
11
2 2
11
11
3 1
1
1
1

样例输出

1 1 4 # 
1 # 4 #
3 3 4 2
3 3 2 2
更新于 阅读次数