# [出题] 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