结对编程作业

021800813 林昊炜博客链接: https://www.cnblogs.com/lin-xm/p/13842318.html
021800901 陈嘉辰博客链接: https://www.cnblogs.com/021800901cjc/p/13787793.html
GitHub 仓库链接: https://github.com/l455435655/021800813-021800901
华容道游戏下载链接: https://pan.baidu.com/s/10bLf1rM1fLSIoS-iYq2WNA 提取码: cqnf
具体分工：

林昊炜陈嘉辰

AI 部分算法的实现计划、相关资料的收集

华容道游戏的实现华容道原型的设计

华容道游戏的图片收集与分类、游戏UI设计

林昊炜	陈嘉辰
AI 部分算法的实现	计划、相关资料的收集
华容道游戏的实现	华容道原型的设计
	华容道游戏的图片收集与分类、游戏UI设计

原型设计

原型开发工具：
Axure Rp 9、墨刀
原型分析：
根据题目要求，我们最终设计了相对简约的界面原型。

首先是游戏开始界面：

游玩点击开始游戏即可
点击设置可设置
点击退出游戏跳转到结束界面

点击设置后进入设置界面，设置难易度。按返回回到开始界面

点击开始后，玩家可以设置自己的昵称：

设置昵称后，选择要游玩的关卡：

点击战绩可以查看自己的往次得分
点击返回菜单回到开始界面

点击开始后进入游戏界面：

在这个界面玩家可以看到游戏时的实时步数以及用时
玩家点击提示，图中会演示如何完成
玩家点击暂停，游戏计时暂停，按播放键继续游戏。
点击返回回到关卡选择界面

战绩界面：

点击返回回到关卡选择界面

最后是结束界面：

点击退出退出游戏即可

设计说明：
我们针对要求创建了大概的界面，再考虑客户端的界面布局。主要是使界面令玩家使用舒服。按钮找的也比较有代表性，能让玩家一目了然其功能。
设计根据要求总共设计了七个界面，包括开始界面、设置界面、取名界面、选择关卡界面、游戏界面、战绩表、结束界面，可根据界面上设计的不同按钮进入或返回不同界面。
此次原型设计我们参考数字华容道游戏，一切以先行设计为主，后期根据个人水平和进展发生了一些变化。

结对过程：
两个沙北。

遇到的困难及解决方法
困难描述及解决尝试：
一开始不理解什么是原型设计，更别说工具了，然后慢慢百度查找相关资料，一开始是用的Axure Rp9，在b站学了然后试着做了一个觉得用起来有点复杂就尝试了墨刀，发现实现简单的原型用墨刀是比较方便的。一开始做的界面设计有些花哨，用的黑色背景，感觉玩起来不舒服，后来设计成现在这个，较为简洁明亮。遇到的问题基本都解决了。
收获：
第一次接触到原型设计，理解了UI设计的重要性，很新鲜很好奇，认识到了我们平常使用的应用做的是真的好。学会了简单的使用Axure Rp和墨刀，体验了和队友讨论、细化原型的过程。

图片华容道游戏的实现

没学过前端（得以后慢慢学了），所以小程序就不大可能了。

刚看到题目就想到 pygame 应该可以实现，于是后来也没考虑别的用别的了。

结果......真的一言难尽，早知道就用 QT 了。

谁然没做到像原型描绘的那样，但是也实现了 切换难度、查看排行榜、提示、重新打乱、重新开始 等几个简单的功能，还添加了一些简单的 游戏音效 。

效果具体如下。

打开游戏时的界面：

点击切换难度：

查看排行榜：

进入游戏后：

获胜的界面：

AI

代码实现思路
- 网络接口的使用
  
  使用Python的 requests库 对服务器进行 GET 和 POST 请求，返回response，并使用response对象中的json()方法调用 json库中的 JSON解码器处理 JSON数据:
```
import requests

# 获取题目
# 向服务器发出 GET请求
response = requests.get("http://47.102.118.1:8089/api/problem?stuid=031802230")
# 将返回的JSON数据转换为Python内置的数据类型
problem = response.json()


# 计算答案后得到答案 将答案以字典的形式存储
answer = {
    "uuid":"7fc1df54827345c7aa3e54c3e13a2bd1",
    "answer":{
        "operations": "wsaaadasdadadaws",
        "swap": [1,2]
    }
}
# 向服务器发出 POST请求 计算完的答案以 JSON格式 提交上去
response = requests.post(url="http://47.102.118.1:8089/api/answer", json=answer)

# 处理返回的寄送数据
result = response.json()

# 输出返回的结果
print(result)
```
- 代码组织与内部实现设计
  
  共设计了两个类：
  
  Problem类: 用于获取问题、保存问题的相关数据、计算答案和提交答案。
  
  Img类: 可以将问题数据中的经过base64编码的图片解码，并以文件的形式保存下来、将问题图片转换为一种状态用长度为9的字符串表示、get_status() 可以返回状态字符串。
- 说明算法的关键与关键实现部分流程图
  
  图片华容道，可以理解为八数码游戏图片形式（把每一张图片看作是一个数字，空白图片看作是0）。题目给出的图片对应为八数码中的一种状态，并用一个9位的数字字符串表示。所以，只要把判断出所给的图片对应的标准图片是哪张，并且与对应的标准图片对比，得出图片对应的状态，问题就可以转换为八数码问题了。
  
  算法：
  
  爆搜（搜就完事了）
  
  用广度优先搜索，预先计算好八数码问题中从某种状态到目标状态所需要的最优操作，并记录结果以便后续查询（打表）。
  
  获取题目后，将题目中给出的经base64编码的字符串通过base64库b64decode函数解码，并以图片的形式保存。
  
  使用pillow库将上一步保存的乱序图片和给定的标准图片都进行分割，将分割后的乱序图片与分割后的标准图片一一比对，最终确定是哪张图片和图片对应的状态。
  
  从第一步得到结果中查询状态所对应的最优操作，如果操作的步数小于等于step，则无需强制交换和自由交换，直接返回答案。如果操作的步数大于step，则进行搜索。
  
  由于题目并不完全是八数码的玩法（增加了强制交换和自由交换的规则），所以我们把需要的操作分成两部分，一部分是进行交换前的，一部分是交换后的。用广搜遍历交换前所能达到的所有状态，并用这些状态一一进行强制交换操作。从第一步计算好的结果中查询交换后状态所对应的最优操，若有解则记录该结果，若查询不到则说明此时无解，需要进行自由交换操作，进行36种自由交换操作，比较36种情况哪种还需要的操作数最少。重复上述操作直到遍历完所有状态，不断比较取最优解。

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

img.py:

对图片的切割、比较等操作用的是 pillow库

裁剪图片

    def __cut_image(self, img) -> list:
        images = []
        width = img.size[0] // 3
        height = img.size[1] // 3
        for i in range(3):
            for j in range(3):
                left = j * width
                upper = i * height
                right = (j + 1) * width
                lower = (i + 1) * height
                img_c = img.crop(box=(left, upper, right, lower))
                images.append(img_c)
        return images

将图片与标准图片比较，转换为状态字符串

    def __cmp_images(self, images: list, sample_images: list):
        blank_image = Image.open(r'.datawhite.png')
        status = ''
        for i in range(9):
            if ImageChops.difference(images[i], blank_image).getbbox() is None:
                status = status + '0'
            else:
                found = False
                for j in range(9):
                    if ImageChops.difference(images[i], sample_images[j]).getbbox() is None:
                        status = status + str(j + 1)
                        found = True
                        break
                if not found:
                    break

        if len(status) == 9:
            return status

problem.py:

计算答案

    def __caculate_answer(self):
        status_type = 0
        for i in range(1, 10):
            if str(i) not in list(self.__img_status):
                status_type = i
                break

        operations = self.__answers_dicts[status_type].get(self.__img_status, 'w' * 100)

        if len(operations) <= self.__step:
            print("no forced swap")
            self.__answer["operations"] = operations
            self.__answer["swap"] = []
        else:
            print("forced swap")
            self.__answer["operations"], self.__answer["swap"] = 
                self.__caculate_operations(
                    stauts_type=status_type,
                    orign_status=self.__img_status,
                    force_swap=self.__swap,
                    step_to_swap=self.__step)

    def __caculate_operations(self, stauts_type: int, orign_status: str, force_swap: list, step_to_swap: int) -> tuple:
        answers = self.__answers_dicts[stauts_type]
        operation = {
            -1: 'a',
            +1: 'd',
            -3: 'w',
            +3: 's'
        }
        dindexes = {
            1: [+1, +3],
            2: [-1, +3, +1],
            3: [-1, +3],
            4: [-3, +1, +3],
            5: [-3, -1, +1, +3],
            6: [-3, -1, +3],
            7: [-3, +1],
            8: [-3, -1, +1],
            9: [-3, -1]
        }
        reverse_operation = {
            'a': 'd',
            'd': 'a',
            'w': 's',
            's': 'w'
        }

        def swap_image(status, num_1, num_2) -> str:
            status = list(status)
            status[num_1], status[num_2] = status[num_2], status[num_1]
            return ''.join(status)

        def diff(status: str, target_status: str) -> int:
            cnt = 0
            for i in range(len(status)):
                if status[i] != target_status[i]:
                    cnt += 1
            return cnt

        def h(status: str, target_status: str) -> int:
            return diff(swap_image(status, force_swap[0], force_swap[1]), target_status)

        orign_status = 's' + orign_status
        target_status = 's' + ''.join([str(i) if i != stauts_type else '0' for i in range(1, 10)])

        zero_index = 0
        for i in range(1, 10):
            if orign_status[i] == '0':
                zero_index = i
                break

        print("orign_status:", orign_status)
        print("target_status:", target_status)
        print("forced_swap:", force_swap)
        print("step_to_swap:", step_to_swap)

        vis = set()
        close_table = []

        open_table = deque()

        step = 0
        f = step
        operations = ''
        status = orign_status

        open_table.append((f, status, zero_index, step, operations))


        while open_table:
            f, status, zero_index, step, operations = open_table.popleft()

            if status in vis or step > step_to_swap:
                continue
            else:
                vis.add(status)
                close_table.append((f, status, zero_index, step, operations))

            for dindex in dindexes[zero_index]:
                next_zero_index = zero_index + dindex
                next_status = swap_image(status, next_zero_index, zero_index)
                next_operations = operations + operation[dindex]

                f = step + 1
                open_table.append((f, next_status, next_zero_index, step + 1, next_operations))

        # traverse close_table
        open_table = []
        for i in range(min(len(close_table), len(close_table))):
            f, status, zero_index, step, operations = close_table[i]
            if (step_to_swap - step) % 2 == 0:
                operations = operations + (operation[dindexes[zero_index][0]] + reverse_operation[
                    operation[dindexes[zero_index][0]]]) * ((step_to_swap - step) // 2)
                open_table.append((swap_image(status, force_swap[0], force_swap[1]), operations))

        operations_before_swap = ''
        min_operations = 'w' * 100
        free_swap = []
        # status: status aafter forced swap
        for status, operations in open_table:
            if answers.get(status[1:]):
                all_operations = operations + answers.get(status[1:])
                if len(all_operations) < len(min_operations):
                    operations_before_swap = operations
                    min_operations = all_operations
                    free_swap = []
            else:
                for i in range(1, 10):
                    for j in range(i + 1, 10):
                        all_operations = operations + answers.get(swap_image(status, i, j)[1:], 'w' * 100)
                        if len(all_operations) < len(min_operations):
                            operations_before_swap = operations
                            min_operations = all_operations
                            free_swap = [i, j]

        if min_operations == operations_before_swap:
            min_operations += ' '

        print("operations_before_swap:", operations_before_swap)
        print("all_operations:", min_operations)
        print("free_swap:", free_swap)
        return min_operations, free_swap

性能分析与改进
描述你改进的思路

主要还是网络请求、图片比较、json解析用了较多的时间。

所以我把图片的读取、算法的一些预处理都提前在了get题目之前，这样虽然总体运行时间不变，但是从获取题目到提交答案的时间减少了。

其他改进的话，我把 bfs 用的 list 改成了deque（插入删除都是O(1)），稍微更快一点。
展示性能分析图和程序中消耗最大的函数

Github 的代码签入记录
遇到的困难
- 问题描述
  
  用Pygame不知道怎么实现按钮。
- 解决尝试
  
  想了很久最后只能手动判断鼠标点击的范围，然后去调用相应的函数。
- 是否解决
  
  已解决，但是代码写得非常丑，各种乱七八糟的函数全写在一个文件里。
  
  应该把所有按钮拉出来单独写一个类的，以后还得慢慢改。
- 有何收获
  
  收获就是早知道用QT的。
对队友的评价
- 值得学习的地方
  
  人很好很不错，是个善解人意，责任心强，饱含热情的好队友。
- 需要改进的地方
  
  稍稍有些拖沓。

PSP表格和学习进度条

PSP表格:

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	60	40
Estimate	估计这个任务需要多少时间	60	40
Development	开发	1410	1850
Analysis	需求分析 (包括学习新技术)	480	600
Design Spec	生成设计文档	60	40
Design Review	设计复审	30	40
Coding Standard	代码规范 (为目前的开发制定合适的规范)	30	20
Design	具体设计	60	120
Coding	具体编码	600	800
Code Review	代码复审	30	30
Test	测试（自我测试，修改代码，提交修改）	120	200
Reporting	报告	80	120
Test Report	测试报告	30	40
Size Measurement	计算工作量	20	20
Postmortem & Process Improvement Plan	事后总结, 并提出过程改进计划	30	60
	合计	1550	2010

学习进度:

第N周	新增代码（行）	累计代码（行）	本周学习耗时(小时)	累计学习耗时(小时)	重要成长
1	0	0	8	8	学习了原型设计软件的使用方法、八数码问题的相关算法
2	300	300	14	22	学习了Git 相关的使用
3	400	700	12	34	学习了JavaScript的基础内容
4	200	900	12	46	学习了Canvas