python生成处处通达的地形

Python 生成处处通达的地形（2020年8月3日）

---

制作背景

大一结束的暑假经常喜欢写各种程序，有一天，好友 Rutubet 要求我们两个人进行一场编程比赛，比赛的内容是：用自己熟悉的语言做一个游戏：生成二维随机俯视地形，能够让主角在地形中进行移动，地图由“墙体”、“空气”方块组成，就像“Minecraft”一样，只不过是二维的，像“推箱子”小游戏的那种地形。选做内容是：保存地图，读取地图，新的方块，生成处处可达的地形。比赛时间是两个小时。

生成处处可达的地形的意思就是说，比如在一个推箱子中游戏关卡中，每一个空气方块都是主角能够到达的地方，地图里没有一个“空穴”，就是没有一个封闭的、进不去的地方，处处都是连通的。（这一项本来是必须做的，但是考虑到了时间和难度，我们都同意将它改为选做了）

我们两个人在比赛内都没做这个处处可达的效果，但是我在比赛时间外经过一番思考，增添了这个功能。

主要思路

对于处处可达的地形生成，我是这样做的（没有参考任何相关资料，自己设计的，可能有不妥的地方）：

做一个能够判断地形是否是处处可达的判断函数，这个函数实现后，生成地形的时候就很轻松了。

生成地形的时候就在一个全是空气的地图里的随机位置上丢一个墙体，然后调用这个判断函数，如果丢一块墙体这个操作使得整个地图由通达状态变成了不通达状态，就“撤销”这一步操作，即把丢到的位置改为空气方块。

（后来我在做成功的时候，又想到了一种效果，那就是可以直接丢一个2x2的大墙体，或者一个更大的接近圆形的墙体块作为每次丢的内容，甚至还可以丢各种形状的大墙块，只要丢的大墙块本身自己不是闭合的，就可以，比如说丢一个空心的o形墙就不行。在撤销的时候，会直接把这个丢的内容中含有墙的方块对应的地图上的位置变成空气方块，可能丢的内容有一部分已经在墙上，有一部分不在墙上，但是这一丢导致了地图变成了非处处可达状态，于是就会把刚刚丢在空气里的和丢在墙上的墙体都变成空气，即：会出现撤销的时候会把墙直接吃掉一部分的这种效果，不过这并不影响处处可达的结果，反而我觉得这就是我想要的效果）

上述步骤执行很多很多次，每丢一个方块就判断一次处处可达，等到丢的方块非常多的时候，就生成了一个处处可达的地形了。（我知道这样很费时间，但是我认为这是非常好想到并且比较容易实现的方法了，我于是抱着看看效果的心态先就做出来）

那么接下来的重点就放在实现那个地形处处可达的判断函数了。

在想判断函数的时候我想到了一幅画面，在空气方块中滴一滴墨水，这个墨水开始向四周扩散，但是会受到墙体的阻碍，等墨水扩散完毕了之后，如果所有的空气方块都被墨水所侵染，那么整个地图就是处处通达的，否则就说明有的地方墨水无法触及，整个地图不是处处通达的。

根据上面的想法，只要遍历整个地图里的每一个方块，只要一找到空气方块，就开始执行“滴墨水”的操作，实时统计被墨水感染的方块的数量，如果被墨水感染的数量等于空气方块的数量，那么判断函数就通过了。

那么接下来的重点就放在怎么实现墨水扩展上了

我们把每一个被感染的空气方块想象成一个“哨兵”、“传播者”或者“拓荒者”。（也许是因为高中英语有一个这个单词记忆的比较深刻，所以就给变量名这么取名了），这个拓荒者是一个类对象，它有很多的属性和功能。

首先它能向周围（给上下左右四个格子，不能斜着）传递信息，让更多的拓荒者诞生，那么我们就给它一个directions属性，用来表示它接下来会向哪个方向发射信息，这时候就有问了，每个拓荒者不都是向周围四个方向上发射信息吗？不用这个属性也无妨。但是这只是第一个拓荒者，它是向四个方向传播的，第二代拓荒者就不是了，第二代拓荒者中位于最开始拓荒者右边的新的拓荒者它就没有必要再往左侧传递信息了，（因为它就是从左边传来的信息诞生出来的，所以它只需要向右，上，下三个方向传递信息。）

拓荒者有以下属性：

• 位置（表示自己在地图中的作标位置）
• 是否是第一个拓荒者isFirst（第一个拓荒者比较特殊，因为它的传播方向有四个，其他的都是三个）
• 受到的信息massage（表示这个拓荒者是从上一个拖航这的哪个方向上传来的，这属性决定它接下来发消息的三个方向，如果是第一个拓荒者，那么它没有收到消息，就用(0, 0)来表示没有）
• 接下来的传播方向directions（一般是三个，但是如果是第一个拓荒者，那么它就有四个方向）
• 是否工作isWorking（用来在接下来迭代的过程中方便遍历每一个拓荒者用）

整个传播的过程需要三个一维列表，也用于表示拓荒者的三种状态：

1. workingPioneerArray：里面存放正在工作中的拓荒者，每次遍历的时候只遍历这个数组就可以了
2. pioneerArray：里面存放工作完成的拓荒者，最终统计数量的时候直接len这个列表就可以了
3. nextWorkingPioneer：里面存放下一步中才开始执行工作的拓荒者，也就是当前一步中刚诞生的

还需要一个二维数组，这个二维数组和地图一样大，相当于又建立了一个只表示拓荒者有无的图层：

• pioneerFlag[Y][X]：里面存放所有不同状态的拓荒者，这个用于防止拓荒者传播的时候出现两个拓荒者重复站在一个位置上

接下来

只要循环直到没有工作中的拓荒者了，就结束了，循环执行什么操作呢？

循环遍历执行每个拓荒者的传播操作，就是遍历每一个拓荒者的传播方向属性，如果这个传播方向上的对应的位置上既不是不可走上去的墙体，同时在pioneerFlag对应位置上没有拓荒者，满足这两个条件就可以让这个位置上的拓荒者诞生，并让诞生的拓荒者添加到nextWorkingPioneer。怎么让拓荒者诞生？就创建一个新的拓荒者类的实例，传入相应参数就可以了，但是注意需要根据massage属性来确定它接下来的传播方向

遍历结束后需要对三个列表进行内容上的修改：

• 每遍历结束一个拓荒者，这个拓荒者的工作就结束了，让它的isWorking属性改为False，并将它添加到pioneerArray。
• 每迭代一次，即遍历完所有工作中的拓荒者一波，就需要让nextWorkingPioneer中的拓荒者覆盖workingPioneerArray，并清空nextWorkingPioneer中的拓荒者。

详细信息可以看代码

效果截图

源代码

此源代码为整个项目的所有源代码

# -*- encoding: utf-8 -*-
"""
二维移动小游戏
实现#_@,随机地图，处处可达 选做：保存，读取地图，新方块
2020年8月3日
by littlefean
"""
from random import random
from random import randint
import numpy as np
import os
from msvcrt import getch


"""BLOCKS
该全局字典表示游戏中的方块显示字符
其中的元素为 '方块名称': '显示字符'
可以随意修改显示字符，但方块名称禁止修改
"""
BLOCKS = {
    'road': '  ',
    'wall': '▉',
    'person': '您'
}


def isPenetrating(array):
    """
    传入一个二维数组array，判断其内部所有的0元素是否能够上下左右连接成一个整体，是则返回True，否则False
    例如：
        [[1, 0, 0]
         [1, 0, 1]
         [0, 0, 1]]
         就是可以上下左右连接成一个整体 ，像“ ∫ ”形状
    而：
        [[1, 0, 0]
         [1, 1, 1]
         [0, 0, 1]]
         是被中断的，不算练成一个整体
    但是：
        [[0, 0, 0]
         [0, 1, 1]
         [1, 0, 1]]
         在这个数组中，斜着不算连接
    注意：此函数使用到了第三方库 numpy 在函数中使用别名 np
    :param array: 二维数组（世界），内部元素只含有0和1，0表示通路，1表示墙体
    :return: 是否array中所有的0元素是否能够上下左右连接成一个整体，是则返回True，否则False
    """
    class Pioneer:
        """（拓荒者，表示一个被判定连同的方块）此类禁止外部使用、实例化"""
        def __init__(self, place, isFirst, massage=(0, 0)):
            """
            拓荒者类的构造函数
            :param place: 此拓荒者所在方块的位置
            :param isFirst: 是否是第一个拓荒者
            :param massage: 该拓荒者接受上一个拓荒者的信息
            """
            self.place = place
            self.isFirst = isFirst
            self.massage = massage
            self.directions = self.get_directions()  # 内部属性：表示该拓荒者接下来的传播方向
            self.isWorking = True  # 内部属性：表示该拓荒者是否还在工作

        def get_directions(self):
            dire = {
                'up': (0, -1),
                'down': (0, 1),
                'left': (-1, 0),
                'right': (1, 0)
            }
            # 集合被遍历方向的顺序是 顺时针方向
            if self.isFirst:
                return [dire['up'], dire['right'], dire['down'], dire['left']]
            else:
                if self.massage == dire['up']:
                    return [dire['left'], dire['up'], dire['right']]
                elif self.massage == dire['down']:
                    return [dire['right'], dire['down'], dire['left']]
                elif self.massage == dire['left']:
                    return [dire['down'], dire['left'], dire['up']]
                elif self.massage == dire['right']:
                    return [dire['up'], dire['right'], dire['down']]

        def __str__(self):
            return f"<{self.place}>"
        __repr__ = __str__

    def findStartPlace(worldArray):
        """寻找并返回一个落脚点"""
        for _i in range(len(worldArray)):
            for _j in range(len(worldArray[0])):
                if worldArray[_i][_j] == 0:
                    return _j, _i

    def add_tuple(t1, t2):
        """将两个数组相加"""
        return t1[0] + t2[0], t1[1] + t2[1]

    def in_world(p1, worldArray):
        """判断下标p1位置是否在二维数组worldArray范围之内"""
        _x, _y = p1
        if _x in range(len(worldArray[0])) and _y in range(len(worldArray)):
            return True
        else:
            return False

    pioneerFlag = np.zeros([len(array), len(array[0])])  # 二维数组存储拓荒者们在地图上站的位置
    # 寻找探路起始点并添加一个位置属性为此位置的拓荒者 到列表
    startX, startY = findStartPlace(array)
    workingPioneerArray = [Pioneer((startX, startY), True)]  # 存放正在工作的拓荒者
    pioneerArray = []  # 存放已经工作完成的拓荒者
    pioneerFlag[startY][startX] = 1
    nextWorkingPioArray = []  # 存放下一次要执行工作的拓荒者
    while len(workingPioneerArray) != 0:  # 循环，直到没有工作中的拓荒者
        # 还有工作中的拓荒者
        # 当前拓荒者列表中 遍历所有拓荒者
        for pioneer in workingPioneerArray:
            # 遍历当前拓荒者的传播方向属性
            for d in pioneer.directions:
                # 判断传播的下一个拓荒者位置在世界内
                if in_world(add_tuple(pioneer.place, d), array):
                    x, y = add_tuple(pioneer.place, d)
                    # 判断下一个拓荒者位置在地图上不是墙，并且这个位置上还没有拓荒者
                    if array[y][x] == 0 and pioneerFlag[y][x] == 0:
                        # (此处可以增加一个判断是否是可走方块的函数 来替代)
                        nextWorkingPioArray.append(Pioneer((x, y), False, massage=d))  # 下一代拓荒者列表添加成员
                        pioneerFlag[y][x] = 1
            pioneer.isWorking = False  # 此拓荒者的工作结束
            pioneerArray.append(pioneer)  # 结束工作的拓荒者添加到拓荒者列表
        workingPioneerArray = nextWorkingPioArray
        nextWorkingPioArray = []
    # 统计拓荒者是否填满了所有非墙体格
    spaceNum = 0
    pNum = len(pioneerArray)
    for i in range(len(array)):
        for j in range(len(array[0])):
            if array[i][j] == 0:  # (此处可以增加一个判断是否是可走方块的函数 来替代)
                spaceNum += 1
    if spaceNum == pNum:
        return True
    else:
        return False


def create_world(width, height):
    """
    随机生成一个宽度为width，高度为height的世界并返回一个二维数组表示生成的游戏地图
    对于数组里的每一个元素，整数0表示空地，整数1表示墙壁

    >>> myWorld = create_world(10, 20)

        0 1 2 3 4 5…… x
      0 ┌ ─ ─ ─ ─ ─
      1 │
      2 │   二维数组中某个元素的表示方法为：数组名[y][x]
      y
    :param width: 宽度 int
    :param height: 高度 int
    :return: 二维数组
    """

    def random_set_wall(worldArray, probability=0.5):
        """生成一个每个块都有一定概率是墙的地图"""
        for y in range(len(worldArray)):
            for x in range(len(worldArray[y])):
                if random() < probability:
                    worldArray[y][x] = 1

    def random_set_wall_unobstructed(worldArray, density=0.6):
        """生成一个每个块都有一定概率是墙的地图，但是能保证处处通达"""
        for y in range(len(worldArray)):
            for x in range(len(worldArray[y])):
                if worldArray[y][x] == 1:  # 判断含有墙
                    exit("发生错误！传入的世界中必须是一个空世界")
        tempNum = len(worldArray) * len(worldArray[0])  # 地图方块容量
        setBlockNum = int(density * tempNum * 1.5)
        for i in range(setBlockNum):
            print(f"生成世界中……{i}/{setBlockNum}")
            putX = randint(0, len(worldArray[0]) - 1)
            putY = randint(0, len(worldArray) - 1)
            worldArray[putY][putX] = 1
            if isPenetrating(worldArray):
                continue
            else:
                worldArray[putY][putX] = 0

    def random_set_walls_unobstructed(worldArray, density=0.6):
        """在上一个基础上，放置的是以大块为单位"""
        walls = np.array([
            [0, 1, 1, 0],
            [1, 1, 1, 1],
            [1, 1, 1, 1],
            [0, 1, 1, 0]
        ])
        wallNum = np.ndarray.sum(walls)  # 墙块中的方块量
        tempNum = len(worldArray) * len(worldArray[0])  # 地图方块容量
        maxPutNum = int(tempNum/wallNum)  # 大约最多放置次数
        putNum = int(density * maxPutNum)  # 待放置的次数

        def put_walls(_worldArray, wallsArray, place, isUndo=False):
            """在世界中放一大块墙"""
            wallsHeight, wallsWidth = len(wallsArray), len(wallsArray[0])
            putY, putX = place[1], place[0]
            for _y in range(wallsHeight):
                for _x in range(wallsWidth):
                    if wallsArray[_y][_x] == 1:
                        if not isUndo:
                            _worldArray[putY + _y][putX + _x] = 1
                        else:
                            _worldArray[putY + _y][putX + _x] = 0

        for i in range(putNum):
            print(f"生成世界中……{i}/{putNum}")
            x = randint(0, len(worldArray[0]) - len(walls[0]))
            y = randint(0, len(worldArray) - len(walls))
            randomLegalLocation = (x, y)
            put_walls(worldArray, walls, randomLegalLocation)
            if isPenetrating(worldArray):
                continue
            else:
                put_walls(worldArray, walls, randomLegalLocation, isUndo=True)

    createMode = [
        random_set_wall,
        random_set_wall_unobstructed,
        random_set_walls_unobstructed
    ]
    world = np.zeros([height, width], dtype=int)
    # random_set_wall_unobstructed(world, 5)
    # random_set_walls_unobstructed(world)
    # random_set_walls_unobstructed(world, density=0.5)
    # random_set_walls_unobstructed(world, density=4)
    random_set_walls_unobstructed(world, density=5)
    return world


def print_world(worldArray):
    """
    传入worldArray二维数组 并将其内容以对应字符的方式打印在控制台上
    :param worldArray: 二维数组
    :return:
    """
    print()
    for y in range(len(worldArray)):
        for x in range(len(worldArray[y])):
            if worldArray[y][x] == 0:
                print(BLOCKS['road'], end="")
            elif worldArray[y][x] == 1:
                print(BLOCKS['wall'], end="")
            elif worldArray[y][x] == -1:
                print(BLOCKS['person'], end="")
        print()


def join(worldArray, place):
    """
    将玩家出生在 worldArray （二维数组）中的 place （二元整数）位置上
    该方法自动判断：如果 place 位置上是墙体，则会出生在附近的一个可以落脚的位置上
    玩家出生后会修改出生位置或附近位置上的方块对应 worldArray 中的数据为 -1 ，以表示玩家所在位置
    >>> myWord = create_world(20, 20)

    >>> join(myWord, (10, 10))
    表示世界的二维数组具体可参见 create_world 的注释
    >>> help(create_world())

    注意：该函数直接更改了 worldArray的状态
    :param worldArray: 二维数组
    :param place: 数组中的位置元组，例如(1, 5)
    :return:
    """
    print("进入世界中……")
    x, y = place
    worldWidth, worldHeight = len(worldArray[0]), len(worldArray)
    if worldArray[y][x] == 0:
        worldArray[y][x] = -1
        return
    elif worldArray[y][x] == 1:
        for i in range(max(worldWidth, worldHeight)):
            r = i + 1
            left = max(0, x - r)
            right = min(worldWidth - 1, x + r)
            top = max(0, y - r)
            bottom = min(worldHeight - 1, y + r)
            for selectY in range(top, bottom + 1):
                for selectX in range(left, right + 1):
                    print(f"正在判断({selectX}, {selectY})是否可落点")
                    if worldArray[selectY][selectX] == 0:
                        worldArray[selectY][selectX] = -1
                        return


def command(worldArray):
    """
    此方法执行后进入死循环，使玩家在 worldArray 所表示的地图上开始进行操作，修改 worldArray 的状态
    具体操作有：移动、存档、退出
        移动：用户输入 w a s d 其中一个字符使得 worldArray 中表示玩家的元素在数组中进行位置上的移动
        存档：用户输入 f 自动执行 save_world() 方法
        退出：用户输入 q 结束此方法。
    注意：
        该函数直接修改了 worldArray 的状态
        此函数要放在游戏循环体的末尾
    :param worldArray: 二维数组
    :return:
    """
    # 寻找人物的出生点
    p = (0, 0)
    for i in range(len(worldArray)):
        for j in range(len(worldArray[i])):
            if worldArray[i][j] == -1:
                p = (j, i)
    x, y = p  # x, y 表示当前的位置，实时变化
    worldWidth, worldHeight = len(worldArray[0]), len(worldArray)
    while True:
        print(f"当前世界名称：{WORD_NAME}")
        print_world(worldArray)
        print("请输入键：")
        choiceMotion = getch()
        if choiceMotion == b'w':
            if y > 0:
                if worldArray[y - 1][x] == 0:
                    worldArray[y][x] = 0
                    worldArray[y - 1][x] = -1
                    y -= 1
                else:
                    print("is wall!")
            else:
                print("world index out of range")
        elif choiceMotion == b's':
            if y < worldHeight - 1:
                if worldArray[y + 1][x] == 0:
                    worldArray[y][x] = 0
                    worldArray[y + 1][x] = -1
                    y += 1
                else:
                    print("is wall!")
            else:
                print("world index out of range")
        elif choiceMotion == b'a':
            if x > 0:
                if worldArray[y][x - 1] == 0:
                    worldArray[y][x] = 0
                    worldArray[y][x - 1] = -1
                    x -= 1
                else:
                    print("is wall!")
            else:
                print("world index out of range")
        elif choiceMotion == b'd':
            if x < worldWidth - 1:
                if worldArray[y][x + 1] == 0:
                    worldArray[y][x] = 0
                    worldArray[y][x + 1] = -1
                    x += 1
                else:
                    print("is wall!")
            else:
                print("world index out of range")
        elif choiceMotion == b'q':
            break
        elif choiceMotion == b'f':
            save_world(worldArray, WORD_NAME)
        else:
            print("无效输入")
        os.system("cls")


def open_world(fileName):
    """
    打开一个当前文件夹下的文件并返回其中的二维数组
    您的文件夹
        ├ move_game.py
        └ NewWorld.bin
    >>> myWorld = open_world("NewWorld.bin")

    >>> print_world(myWorld)

    注意：
        传入的文件必须是由本程序 save_world() 方法保存的文件（自觉保证）
        此函数使用到了第三方库 numpy 在函数中使用别名 np
    :param fileName: 文件名（加后缀名）
    :return: 二维数组
    """
    worldArray = np.load(f'{fileName}')
    return worldArray


def save_world(worldArray, fileName):
    """
    将世界world以二进制文件形式(.bin)保存到当前模块所在的文件夹下
    >>> myWorld = create_world(10, 20)

    >>> join(myWorld, (0, 0))

    >>> save_world(myWorld, "NewWorld")
    您的文件夹
        ├ move_game.py
        └ NewWorld.bin
    注意：
        此函数使用到了第三方库 numpy 在此函数中使用别名 np
        自觉保证文件前缀名的合法性 譬如不能含有特殊字符比如/.*
    :param worldArray: 二维数组
    :param fileName: 文件名（不加后缀名）
    :return:
    """
    np.save(f'{fileName}', worldArray)


if __name__ == '__main__':
    WORD_WIDTH = 80
    WORD_HEIGHT = 40
    WORD_NAME = "NewWord"
    BIRTH_PLACE = int(WORD_WIDTH / 2), int(WORD_HEIGHT / 2)

    while True:
        print("1. 新建游戏")
        print("2. 载入游戏")
        print("3. 地图设置")
        print("4. 帮助提示")
        print("5. 退出程序")
        choice = input("请输入操作")

        if choice == '1':
            WORD_NAME = input("请为地图起个名字，例如(NewWord)：")
            if WORD_NAME == '':
                WORD_NAME = 'NewWord'
            newWord = create_world(WORD_WIDTH, WORD_HEIGHT)
            print_world(newWord)
            join(newWord, BIRTH_PLACE)
            print_world(newWord)
            command(newWord)

        elif choice == '2':
            print("地图列表为：")
            fileList = os.listdir('.')
            npyList = []
            number = 1
            for file in fileList:
                if file.split('.')[1] == 'npy':
                    npyList.append(file)
                    print(f"{number}: {file}")
                    number += 1
            try:
                choiceMapNum = int(input("请输入地图列表的序号："))-1
                world = open_world(npyList[choiceMapNum])
                command(world)
            except IndexError:
                print("您输入的序号不存在")
            except ValueError:
                print("您输入的格式不正确")

        elif choice == '3':
            while True:
                print("1. 设置地图大小")
                print("2. 设置出生点")
                print("3. 设置方块显示方式")
                print("4. 设置地图模式(待做)")
                print("5. 返回")
                settingsChoice = input("请输入操作")
                if settingsChoice == '1':
                    print(f"当前的世界宽度为{WORD_WIDTH}，高度为{WORD_HEIGHT}")
                    try:
                        WORD_WIDTH = int(input("请输入地图宽度"))
                        WORD_HEIGHT = int(input("请输入地图高度"))
                    except ValueError:
                        print("您输入的格式不正确")
                elif settingsChoice == '2':
                    try:
                        b = tuple(input("请输入出生点，先x后y，中间空格隔开").split())
                        BIRTH_PLACE = (int(b[0]), int(b[1]))
                    except ValueError:
                        print("您输入的格式不正确")
                elif settingsChoice == '3':
                    for block in BLOCKS:
                        print(f"{block}:/t/"{BLOCKS[f'{block}']}/"")
                    print("提示：在控制台里，中文汉字一般为两个空格的宽度，英文字符和空格宽度相同，而▉则是和汉字差不多宽")
                    blockName = input("请输入您要修改的方块的名称：")
                    if blockName in BLOCKS:
                        display = input(f"请输入您要设置{blockName}方块显示的字符：")
                        BLOCKS[f'{blockName}'] = display
                    else:
                        print("未找到该方块，请检查输入是否正确")
                elif settingsChoice == '4':
                    pass
                elif settingsChoice == '5':
                    break

        elif choice == '4':
            print("wasd 键控制移动")
            print("f 键存档")
            print("q 键退出游戏")
            print(f"{BLOCKS['road']}为道路")
            print(f"{BLOCKS['wall']}为墙体")
            print(f"{BLOCKS['person']}为您")

        elif choice == '5':
            exit()

        else:
            print("输入异常，请重新输入")

总结与反思

我的这种算法时间复杂度太大，空间复杂度也不小，因此还需要改进。

我还需要学习一些相关算法知识，纯自己做出来的感觉有些地方可能有点冗余。