项目介绍

我们这个项目是一个基于Python实现的推箱子小游戏，名叫Sokoban：

这个游戏的目的是让玩家，也就是大写的P，推着箱子#，填充用小写的o标记的地面上的洞

项目规则

该版本的Sokoban的规则如下：

• 游戏在矩形的二维网格上举行，其原点(0,0)位于左上方
• 网格上的每个单元格可以随时包含以下内容之一：
  • 由大写字母P表示的玩家
  • 由空格字符' '表示的地砖
  • 由哈希字符#表示的箱子
  • 由星号字符*表示的墙
  • 由小写字符o表示的洞
• 每个回合，玩家角色可以在网格上向上、向下、向左或向右移动一个单位
• 玩家角色不能移动到墙或洞中
• 每一回合，玩家角色都可以将箱子向他们试图移动的方向推一个单位，前提是玩家试图移动方向的箱子的下一个单元格是地砖或者是洞。如果不满足此条件，玩家和箱子都不会移动
• 如果玩家将箱子推入到洞中，洞和箱子都会消失，并留下一块板砖。
• 如果玩家试图离开屏幕边缘或将箱子推离屏幕边缘，如果其他规则允许，玩家或箱子应该出现在屏幕的对侧，就像屏幕的两侧是连接的一样

项目接口文档

在这个项目中你需要去实现含有以下方法的Sokoban类；

• __init__(self,board)：使用给定的board创建Sokoban实例，参数board是一个二维嵌套列表，也就是我们的游戏地图
• find_player(self)：返回玩家角色在棋盘上的位置。行和列从0开始，原点(0,0)位于网格的左上角，例如在我们项目介绍中玩家的位置为 (0,0)
• is_complete(self)：判断游戏是否结束。如果地图中没有洞，则返回真，代表游戏结束，否则返回假
• steps(self)：返回玩家角色的移动次数(也就是玩家的位置发生变化的时候)
• restart(self)：将Sokoban实例进行重置，重置为玩家开始游戏之前的状态
• undo(self)：撤销玩家的上一次移动，使游戏状态恢复到上一次移动的时候，可以重复调用以撤销多次移动。如果撤销被调用的次数超过玩家的移动次数，则棋盘应保持其初始状态
• move(self,direction)：试图将玩家移动一个位置并且推动玩家面前的箱子。方向参数是一个字符串，其值为w,a,s,d，分别表示向上，向左，向下和向右。只有当玩家的位置发生更新的时候，才会计算移动次数。如果玩家的位置没有发生改变，则游戏的状态不应以任何方式改变
• __str__(self)：返回地图的字符串表示形式。记住每行中的单元格要用空格分隔

项目实现过程

前置方法编写

我们就按文档中的接口一个个实现。先来看init方法，这个方法里面我们现在能想到的只有两件事：

• 地图初始化
• step游戏步数的初始化

    def __init__(self,board):
        self.board = board
        self.step = 0

然后我们来实现str方法，在这里使用到的就是二维列表的遍历，我们只需要要建立一个空字符串然后把列表中的元素往里面塞就行了：

    def __str__(self):
        show = ''
        num = 0
        for i in self.board:
            num += 1
            for j in i:
                show += j + ' '
            show += '\n'
        return show[:-2]

我们每遍历完一行就使用\n来控制换行。我们最后对返回的字符串进行了切片是因为：我们如果不切片的话，我们在打印最后一行的时候末尾也会有一个换行符，这个是没有必要的！我们可以把它切去：

同样使用了二维列表的遍历的还有is_complete(self)方法，这个的思路也就是单纯的遍历地图看是否还有洞口存在就行，实现较简单；

    def is_complete(self):
        for i in self.board:
            for j in i :
                if j == 'o':
                    return False
        return True

接下来我们来实现find_player(self)方法，其核心思想仍然是二维列表的遍历，这里我提供两种实现方法：

实现方法1：

    def find_player(self):
        x = -1;y = -1
        for j in self.board:
            x += 1
            for k in j:
                y += 1
                if k == 'P':
                    return (x,y)
            y = -1

实现方法2：

    def find_player(self):
        for x in range(self.board_x()):
            for y in range(self.board_x()):
                if self.board[x][y] == 'P':
                    return (x,y)

move核心方法编写

我们在思考move方法的编写的时候，乍一想会发现有很多需要注意点，有非常非常多的限制、判断，可能想着想着一下子就迷失了方向。其实我们可以思考一下，我们每执行一次move指令其实就进行了两个步骤：

• 判断能否移动
• 如果可以移动，则变动玩家(可能还有箱子)的位置

也就是说我们现在将一个指令进行了分解，让他稍微具体了一些。换句话说我们想要实现move这个方法，只需要我们完成这两个功能就可以了，这里我想了一下如果我们将这两个功能都堆叠在move方法中，会显得代码非常的乱，而且涉及if的层层嵌套，会让思维容易混乱。所以这里我们可以把判断能否移动这个功能抽象出来，令作为一个方法，我们把它命名为check。将实际的移动功能留在move方法中。

因为涉及到的四个方向，其实我们知道一个方向怎么实现之后，其他的方向实现也就是照葫芦画瓢，所以这里我只对check以及move方法中的w方向进行讲解，然后为了方便我们可以将地图的长度和宽度的获取抽象成一个方法，方便后面的使用：

    def board_x(self):
        return len(self.board)

    def board_y(self):
        return len(self.board[0])

接下来我们开工！

check()

首先我们先拿到玩家的具体位置，直接调用find_player方法即可，其位置可以通过如下坐标系来理解：

在w方向上来说，他的移动有两种情况：

• 情况一：w方向上与它相邻的位置有箱子（也就是说玩家要推着箱子走）
• 情况二：只有玩家自己移动

而情况一下面又有两种情况：

• 在w方向上，箱子的前面一个是墙
  • 这种情况下就不能移动
    
• 箱子前面没有墙
  • 这种情况下可以移动
    

这里有人会说应该还有一种情况箱子前面是洞口。这说明还没有完全弄清我们单独抽象出这个check方法的目的，我们的check方法只做一件事，那就是箱子或者箱子和人能不能移动。而箱子前面是洞口这种情况属于可以移动的情况，不需要单拿出来讨论。至于箱子与洞口的相消与地砖的填充不是我们check方法的功能，我们应该把他们放到move方法中去处理。

考虑完这些情况之后我们还不能开始写代码，因为有一点我们不能忽略，那就是项目规则中的最后一条：

• 如果玩家试图离开屏幕边缘或将箱子推离屏幕边缘，如果其他规则允许，玩家或箱子应该出现在屏幕的对侧，就像屏幕的两侧是连接的一样

这个地方如果再去加加减减的，然后弄出一大堆情况非常麻烦且容易出现角标越界等问题。我们其实可以想象一下，当我们的玩家一直在w方向上前进（假设整列没有墙不会阻碍前进），到达顶点之后，又从当前列的下方出现，这种情景有点类似于循环列表。我们可以借用取余的思想，这样就不需要进行繁杂的讨论，也可以避免角标越界等错误。

接下来我们来写代码：

    def check(self,direction):
        # 此时玩家的位置
        x = self.find_player()[0]
        y = self.find_player()[1]
        if direction not in "wasd":
            return -1
        #每个方向上的处理
        # 先考虑在你的移动方向上没有箱子的情况
        # 再考虑在你的移动方向上有箱子的情况
        # 返回正整数代表可以移动 返回1说明有箱子   返回0说明没箱子    返回负数代表不能移动
        if direction == 'w':
            # 代表方向上没有箱子
            if self.board[(x-1)%self.board_x()][y] != '#':
                if self.board[(x-1)%self.board_x()][y] not in '*o':
                    return 0
                else:
                    return -1
            # 代表方向上有箱子
            else:
                if self.board[(x-2)%self.board_x()][y] not in '*':
                    return 1
                else:
                    return -1

这里我们的返回值；

• 正整数代表可以移动
  • 0代表不需要推箱子，只有玩家移动
  • 1代表需要推箱子，玩家和箱子均需要移动
• 负数代表不能移动

其他方向同理

move

同样还是先拿到玩家的坐标，然后调用check方法，如果check返回的是一个负数那么直接return不用处理。我们重点来讨论如果返回的是正整数的时候的情况：

以w方向为例进行讨论

• 如果check返回的是0（也就是说只有玩家移动）：
  • 我们只需要将当前玩家所处的方格以地砖替代，将前一个方格使用P替代
• 如果check返回的是非零整数（也就是说玩家和箱子都要移动），这里再分为两种情况：
  • 箱子前面是洞
    • 箱子和洞口相消，玩家前移
  • 箱子前面是地砖
    • 箱子和玩家均前移一个单位

代码如下：

    def move(self,direction):
        # 此时玩家的位置
        x = self.find_player()[0]
        y = self.find_player()[1]
        ans = self.check(direction)
        if direction == 'w':
            if ans < 0:
                return
            else:
                self.board[x][y] = ' '
                if ans == 0:
                    self.board[(x-1)%self.board_x()][y] = 'P'
                else:
                    if self.board[(x-2)%self.board_x()][y] == 'o':
                        self.board[(x-2)%self.board_x()][y] = ' '
                        self.board[(x-1)%self.board_x()][y] = 'P'
                    else:
                        self.board[(x-2)%self.board_x()][y] = '#'
                        self.board[(x-1)%self.board_x()][y] = 'P'

项目收尾

截至目前我们还有下面三个方法没有实现：

• steps(self)
• restart(self)
• undo(self)

steps方法记录玩家的移动步数，而在我们当前项目中，所有的移动操作都与move的方法有关，我们可以直接在move方法中对step进行计数：

    def steps(self):
        return self.step

注意只有当我们的check方法返回非负数的时候我们才会去计数。

接下来我们看看restart(self)和undo(self)方法，这两个方法一个用来重新开始，一个用来回退。他们都有一个特点那就是状态的回溯。那么我们就可以把他们用同一种思想处理，因为他们的区别无非就是一个回溯到开头状态，一个回溯到上一步的状态。

具体的做法就是：只要玩家的位置(状态) 发生了变化，我们就将变化前的地图状态进行储存。在代码层面上来讲就是将变化前的board存储到一个专门的列表中，这里我们就把这个列表命名为history：

这里要非常注意，像下面这样存入列表是不行：

self.history.append(self.board)

你最后会发现存入history中的所有元素都一样并且与当前的board是一致的。这是因为列表在Python中是可变数据类型，即使发生变化其地址值不会发生改变。使用上面的方法我们存入history的一个个元素都有着同样的地址值，也就是说它们是同一个对象。所以这里为了避免这种问题，我们应该使用深拷贝，而普通的深拷贝对我们的多维嵌套列表是没有用的。

这里我尝试了网上最常见的几种办法都没有用：

• 列表的copy方法
• list()方法
• [:]切片方法

我们可以使用Python内置模块copy中的deepcopy方法，代码如下：

import copy

···
self.history.append(copy.deepcopy(self.board))

接下来我们只用在对应的方法中从history里取出不同的状态即可：

    def restart(self):
        self.board = self.history[0]
        self.step = 0
        self.history.clear();


    def undo(self):
        self.board = self.history[-1]
        self.step -= 1
        self.history.pop()

注意：

• 我们restart之后要将history列表清空
• 在我们回退时，除了返回history最后的元素，还要把它从列表中删除，否则在二次或者多次回退时会出错

项目完善

我们在编写代码的时候其实还忽略了几个点：

• 如果撤销被调用的次数超过玩家的移动次数，则棋盘应保持其初始状态

也就是说我们不能一直回退，按照我们的代码，一直回退下去会出现以下两种情况：

• history的列表长度问题，会衍生出角标出错
• 我们的step会变为负数

改进：

    def undo(self):
        if self.step == 0:
            return
        self.board = self.history[-1]
        self.step -= 1
        self.history.pop()

• 如果我们一开始就restart，或者说连续多次restart也会报错

其本质也是因为history列表为空导致的角标出错

改进：

    def restart(self):
        if len(self.history) == 0:
            return
        self.board = self.history[0]
        self.step = 0
        self.history.clear();

项目整体源码

'''
 推箱子
 P代表玩家 o代表洞  #代表箱子 空字符代表地砖
 项目要求：
 1）二维网格的元原点位于左上方
 2）每回合只能上下左右移动一格
 3）玩家不能移动到墙或者洞中
 4）只有当玩家推动箱子移动的下一个单位是地砖或着洞的时候才能移动成功  否则箱子不会移动
 5）箱子进入洞中之后  洞和箱子都会消失   使用地砖进行替代
 6）如果离开屏幕边缘 在规则允许的情况下（也就是第4条）  允许出现在对侧
'''


import copy

class Sokoban:
    def __init__(self,board):
        self.board = board
        self.step = 0
        self.history = []
    def __str__(self):
        show = ''
        num = 0
        for i in self.board:
            num += 1
            for j in i:
                show += j + ' '
            show += '\n'
        return show[:-2]
    def find_player(self):
        for x in range(self.board_x()):
            for y in range(self.board_x()):
                if self.board[x][y] == 'P':
                    return (x,y)

    def is_complete(self):
        for i in self.board:
            for j in i :
                if j == 'o':
                    return False
        return True
    def steps(self):
        return self.step

    def restart(self):
        if len(self.history) == 0:
            return
        self.board = self.history[0]
        self.step = 0
        self.history.clear();


    def undo(self):
        if self.step == 0:
            return
        self.board = self.history[-1]
        self.step -= 1
        self.history.pop()

    def move(self,direction):
        # 此时玩家的位置
        x = self.find_player()[0]
        y = self.find_player()[1]
        ans = self.check(direction)
        if direction == 'w':
            if ans < 0:
                return
            else:
                self.step += 1
                self.history.append(copy.deepcopy(self.board))
                self.board[x][y] = ' '
                if ans == 0:
                    self.board[(x-1)%self.board_x()][y] = 'P'
                else:
                    if self.board[(x-2)%self.board_x()][y] == 'o':
                        self.board[(x-2)%self.board_x()][y] = ' '
                        self.board[(x-1)%self.board_x()][y] = 'P'
                    else:
                        self.board[(x-2)%self.board_x()][y] = '#'
                        self.board[(x-1)%self.board_x()][y] = 'P'
        elif direction == 'a':
            if ans < 0:
                return
            else:
                self.step += 1
                self.history.append(copy.deepcopy(self.board))

                self.board[x][y] = ' '

                if ans == 0:
                    self.board[x][(y - 1)%self.board_y()] = 'P'
                else:
                    if self.board[x][(y - 2)%self.board_y()] == 'o':
                        self.board[x][(y - 2)%self.board_y()] = ' '
                        self.board[x][(y - 1)%self.board_y()] = 'P'
                    else:
                        self.board[x][(y - 2)%self.board_y()] = '#'
                        self.board[x][(y - 1)%self.board_y()] = 'P'
        elif direction == 's':
            if ans < 0:
                return
            else:
                self.step += 1
                self.history.append(copy.deepcopy(self.board))

                self.board[x][y] = ' '
                if ans == 0:
                    self.board[(x + 1)%self.board_x()][y] = 'P'
                else:
                    if self.board[(x + 2)%self.board_x()][y] == 'o':
                        self.board[(x + 2)%self.board_x()][y] = ' '
                        self.board[(x + 1)%self.board_x()][y] = 'P'
                    else:
                        self.board[(x + 2)%self.board_x()][y] = '#'
                        self.board[(x + 1)%self.board_x()][y] = 'P'
        elif direction == 'd':
            if ans < 0:
                return
            else:
                self.step += 1
                self.history.append(copy.deepcopy(self.board))

                self.board[x][y] = ' '
                if ans == 0:
                    self.board[x][(y + 1)%self.board_y()] = 'P'
                else:
                    if self.board[x][(y + 2)%self.board_y()] == 'o':
                        self.board[x][(y + 2)%self.board_y()] = ' '
                        self.board[x][(y + 1)%self.board_y()] = 'P'
                    else:
                        self.board[x][(y + 2)%self.board_y()] = '#'
                        self.board[x][(y + 1)%self.board_y()] = 'P'

    def check(self,direction):
        # 此时玩家的位置
        x = self.find_player()[0]
        y = self.find_player()[1]
        if direction not in "wasd":
            return -1
        #每个方向上的处理
        # 先考虑在你的移动方向上没有箱子的情况
        # 再考虑在你的移动方向上有箱子的情况
        # 返回正整数代表可以移动 返回1说明有箱子   返回0说明没箱子    返回负数代表不能移动
        if direction == 'w':
            # 代表方向上没有箱子
            if self.board[(x-1)%self.board_x()][y] != '#':
                if self.board[(x-1)%self.board_x()][y] not in '*o':
                    return 0
                else:
                    return -1
            # 代表方向上有箱子
            else:
                if self.board[(x-2)%self.board_x()][y] not in '*':
                    return 1
                else:
                    return -1
        elif direction == 'a':
            # 代表方向上没有箱子
            if self.board[x][(y - 1)%self.board_y()] != '#':
                if self.board[x][(y - 1)%self.board_y()] not in '*o':
                    return 0
                else:
                    return -1
            # 代表方向上有箱子
            else:
                if self.board[x][(y - 2)%self.board_y()] not in '*':
                    return 1
                else:
                    return -1
        elif direction == 's':
            # 代表方向上没有箱子
            if self.board[(x + 1)%self.board_x()][y] != '#':
                if self.board[(x + 1)%self.board_x()][y] not in '*o':
                    return 0
                else:
                    return -1
            # 代表方向上有箱子
            else:
                if self.board[(x + 2)%self.board_x()][y] not in '*':
                    return 1
                else:
                    return -1
        elif direction == 'd':
            # 代表方向上没有箱子
            if self.board[x][(y + 1)%self.board_y()] != '#':
                if self.board[x][(y + 1)%self.board_y()] not in '*o':
                    return 0
                else:
                    return -1
            # 代表方向上有箱子
            else:
                if self.board[x][(y + 2)%self.board_y()] not in '*':
                    return 1
                else:
                    return -1

    def board_x(self):
        return len(self.board)

    def board_y(self):
        return len(self.board[0])

# 竖着是x轴  横着是y轴
board = [
    ['*', '*', ' ', '*', '*'],
    ['*', 'o', ' ', ' ', '*'],
    ['#', ' ', 'P', '#', 'o'],
    ['*', ' ', ' ', ' ', '*'],
    ['*', '*', ' ', '*', '*'],
]


game = Sokoban(board)
move = str()
print(game)
print(game.steps(), ':', game.is_complete())
while not game.is_complete():
    move = input('move:')
    if move == 'u':
        game.undo()
    elif move == 'r':
        game.restart()
    else:
        game.move(move)
    print(game)
    print(game.steps(), ':', game.is_complete())

运行效果；

直接cv在IDE中就可以玩，地图可以自己自定义，记得箱子和洞口数量要一样多否则永远过不了关。

项目缺陷分析

• 项目中使用的数据结构较为单一，列表一用用到底。其实很多地方都可以用栈、队列、链表等数据结构进行相关的优化
• 有些地方的代码些许冗杂，可以进行语法上的优化
• 因为接口文档的束缚，其实有很多方法可以更加细化。例如move方法或者说check方法代码逻辑还是有点多。有一些逻辑两个方法可以共用，我们可以抽象出来新建一个方法。
• 既然在wasd四个方向上逻辑相似，那么我们是否可以考虑二次抽象，而不是将四种情况均放在check和move方法中。

项目收获与反思

这个推箱子的小游戏是校内老师布置的一次小作业。因为自己平时都是使用一些前端还有java后端方面的东西，python长时间不用忘得差不多了。我写的时候面向对象的方面的语法以及一些列表相关方法都是边查文档边写的。这就导致代码方面不是非常的成熟健壮。

当然收获也非常的多，一个是复习了python，然后就是取余的思想。平时可能刷算法题的时候可能会遇见，开发的时候基本没怎么用过，这个项目让我见识到了取余在实际开发中发挥的作用：在优化了代码的同时还能减少出错。一开始没想到取余的时候，一个个情况的分类讨论简直让人抓狂。

还有另外非常重要的一点，就是写代码之前打草稿的必要性

其实在平时我们进行不管是前端开发、后端开发，更多的思考的是：用什么、怎么用，那种很严格的逻辑思考其实并不是很频繁。这就导致一台电脑一个文档基本就可以解决问题。而涉及到算法或者说严格的情况分类与考虑这就需要我们打草稿整理思路再去写代码。直接一股脑地去写代码，或者说不打草稿非常的影响效率以及质量。