结对编程作业

我的博客链接
 队友杨泽远链接
 Releases
| 小组成员 |分工
| ---- | ---- | ----
| 我 | 主要UI的实现，接口使用，原型设计
| 队友 | AI算法的实现，部分UI，编写blog

2.1 - 原型设计

[2.1.1]提供此次结对作业的设计说明，要求文字准确、样式清晰、图文并茂（多贴原型图）

鼠标点击初始界面的play开始游戏
鼠标点击游戏界面的replay重置至游戏开始状态
拼图白格的移动靠wsad实现

效果展示

[2.1.2]原型模型必须采用专用的原型模型设计工具实现：如Axure Rp、Balsamiq Mockup、Prototype Composer、GUI Design Studio、Adobe设计组件等等。在博文中说明你所采用的原型开发工具。

Axure Rp

[2.1.3]描述结对的过程，提供非摆拍的两人在讨论、细化和使用专用原型模型工具时的结对照片。

结对的过程：开始各做各的，经过一段时间后互相展现目前的成果并合并代码

[2.1.4]遇到的困难及解决方法:

2.2 - AI与原型设计实现

[2.2.1]代码实现思路：

网络接口的使用

网络接口的爬虫代码通过python实现

def start(uuid):
    url = 'http://47.102.118.1:8089/api/challenge/start/' + uuid
    teamdata = {
        "teamid": 57,
        "token": "965d5fbe-4e91-4a89-9f97-fdbe611ecd5a"
    }
    r = requests.post(url, json=teamdata)
    r_json = r.json()
    print(r_json)
    chanceleft = r_json['chanceleft']
    img_str = r_json['data']['img']
    step = r_json['data']['step']
    swap = r_json['data']['swap']
    uuid = r_json['uuid']
    img_b64decode = base64.b64decode(img_str)  # base64解码
    file = open('test.jpg', 'wb')
    file.write(img_b64decode)
    file.close()
    image = io.BytesIO(img_b64decode)
    img = Image.open(image)
    return img, step, swap, uuid

def up_data(uuid, answer):
    url_up = 'http://47.102.118.1:8089/api/challenge/submit'
    updata = {
        "uuid": uuid,
        "teamid": 57,
        "token": "965d5fbe-4e91-4a89-9f97-fdbe611ecd5a",
        "answer": {
            "operations": answer,
            "swap": []
        }
    }
    r_up = requests.post(url_up, json=updata)
    r_up_json = r_up.json()
    print(r_up_json)

代码组织与内部实现设计（类图）

说明算法的关键与关键实现部分流程图

贴出你认为重要的/有价值的代码片段，并解释

A算法的实现：

A算法是一种预测算法，主要用于寻路等，根据当前状态和目标状态之间的差异，预测到达目标需要多少开销，根据这个开销来判断下一次选择以那个状态开始。这个开销在八数码问题中可以以路程为标准。

A*算法公式：

F(N)=G(N)+H(N)
F(N)表示当前状态到达目标状态所用开销
G(N)表示从起点状态到当前状态所用开销
H(N)在本问题中可以将当前状态9个数字展开成一列，位置从1到9，将当前状态数字所在位置和目标状态该数字所在位置进行相减取绝对值，依次获得8个数（0表示空位，不进行计算）的差值，相加所得即为H(N)的值。原理是每个数当前位置和其应在位置的距离是接下来到达目标大概开销。

H(N)计算示例：

当前状态012345678
目标状态123456780
其中1分别在2号位和1号位，差取绝对值为1，同理其他的数计算结果为：1、1、1、1、1、1、1。

H(N)=1+1+1+1+1+1+1+1=8

A*的时间开销相对较低，但是，不能保证解为最优值，所以在AI大比拼上吃了不少亏，时间和水平有限就没有用BFS去优化

def solvePuzzle_A(srcLayout, destLayout):
    #先进行判断srcLayout和destLayout逆序值是否同是奇数或偶数
    src=0;dest=0
    for i in range(1,9):
        fist=0
        for j in range(0,i):
          if srcLayout[j]>srcLayout[i] and srcLayout[i]!='0':#0是false,'0'才是数字
              fist=fist+1
              # print('fist',fist)
        src=src+fist
        # print(src)
    for i in range(1,9):
        fist=0
        for j in range(0,i):
          if destLayout[j]>destLayout[i] and destLayout[i]!='0':
              fist=fist+1
        dest=dest+fist
    if (src%2)!=(dest%2):#一个奇数一个偶数，不可达
        return -1, None
    g_dict_layouts[srcLayout] = -1
    g_dict_layouts_deep[srcLayout]= 1
    g_dict_layouts_fn[srcLayout] = 1 + cal_dislocation_sum(srcLayout, destLayout)
    stack_layouts = []
    gn=0#深度值
    stack_layouts.append(srcLayout)#当前状态存入列表
    while len(stack_layouts) > 0:
        curLayout = min(g_dict_layouts_fn, key=g_dict_layouts_fn.get)
        del g_dict_layouts_fn[curLayout]
        stack_layouts.remove(curLayout)#找到最小fn，并移除
        # curLayout = stack_layouts.pop()
        if curLayout == destLayout:#判断当前状态是否为目标状态
            break
        # 寻找0 的位置。
        ind_slide = curLayout.index("0")
        lst_shifts = g_dict_shifts[ind_slide]#当前可进行交换的位置集合
        for nShift in lst_shifts:
            newLayout, fn = swap_chr(curLayout, nShift, ind_slide, g_dict_layouts_deep[curLayout] + 1, destLayout)
            if g_dict_layouts.get(newLayout) == None:#判断交换后的状态是否已经查询过
                g_dict_layouts_deep[newLayout] = g_dict_layouts_deep[curLayout] + 1#存入深度
                g_dict_layouts_fn[newLayout] = fn#存入fn
                g_dict_layouts[newLayout] = curLayout#定义前驱结点
                stack_layouts.append(newLayout)#存入集合
    lst_steps = []
    lst_steps.append(curLayout)
    while g_dict_layouts[curLayout] != -1:#存入路径
        curLayout = g_dict_layouts[curLayout]
        lst_steps.append(curLayout)
    lst_steps.reverse()
    return 0, lst_steps

性能分析与改进思路

性能分析如图所示：

开始想使用像素点拼接的方法得到原图，会比遍历找原图快很多，但是准确率不高所以还是使用切割得到的图片去对比原图。
通过群文件的图片对图片进行预处理得到“训练集”（用于对比得到图片，没有使用机器学习）

展示性能分析图和程序中消耗最大的函数!

对比找到原图：

def first_find():
    IMAGES_PATH = 'ori_split'
    IMAGES_FORMAT = ['.jpg']
    image_names = [name for name in os.listdir(IMAGES_PATH) for item in IMAGES_FORMAT if
                   os.path.splitext(name)[1] == item]
    IMAGES_PATH2 = 'text'
    image_names2 = [name for name in os.listdir(IMAGES_PATH2) for item in IMAGES_FORMAT if
                    os.path.splitext(name)[1] == item]
    # print(image_names2)
    print('图片比对中，请稍等...')
    for name in image_names:
        img = Image.open(IMAGES_PATH + '//' + name)
        img = img.convert('RGB')
        img_rgb = 0
        for i in range(300):
            for j in range(300):
                r, g, b = img.getpixel((i, j))
                img_rgb += r + b + g
        if img_rgb == 300*300*255 or img_rgb == 0:
            continue
        # print(img_rgb)
        for name2 in image_names2:
            for k in range(9):
                img_i = Image.open(IMAGES_PATH2 + '//' + name2 + '//' + str(k) + '.jpg')
                img_i = img_i.convert('RGB')
                img_rgb2 = 0
                for i in range(300):
                    for j in range(300):
                        r, g, b = img_i.getpixel((i, j))
                        img_rgb2 += r + b + g
                if img_rgb == img_rgb2:
                    print(name2)
                    return name2

** 展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路 **
如果强制交换的位置在集合内，则输出有解，如果不在则进行自由交换

####每个位置可交换的位置集合
g_dict_shifts = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5],
                 3:[0,4,6], 4:[1,3,5,7], 5:[2,4,8],
                 6:[3,7],  7:[4,6,8], 8:[5,7]}

[2.2.2]贴出Github的代码签入记录，合理记录commit信息

[2.2.3]遇到的代码模块异常或结对困难及解决方法

AI大比拼第一天几乎全是false，又急于求成浪费了许多次数，后来才找到，强制交换的是当前图片的位置，不是原图标记的位置，并且图片序号是从1-9而不是0-8，气得我啊...佛了

[2.2.4]评价你的队友（商业互吹阶段）

值得学习的地方：遇到问题从根本上去学习模块框架的使用解决问题，而我开始就想着“开源”，没找到几个“源”也学习他从头学起一行一行的码
需要改进的地方：急于求成，过于随意，心急吃不了热豆腐