python 迷宫生成算法：递归回溯算法

2102280160.png

步骤一：初始化地图

1.行宽和列高为奇数
2.边框设置为墙
3.所有偶数行和偶数列设置为墙

218512471.png

def __init_map(self):
        for i in range(self.height):
            row = []
            if(i % 2 == 0):
                for j in range(self.width):
                    row.append(1)
            else:
                for j in range(self.width):
                    if(j % 2 == 0):
                        row.append(1)
                    else:
                        row.append(0)
            self.__map.append(row)

步骤二：打通路线

1.选择坐标为(1,1)为起点，将起点坐标加入标记列表中
2.取标记列表中的第一个坐标，从其四周的空间中，随机取一个未被标记的空间，加入标记列表中，并打通和起点之间的墙
3.将上一个随机空间作为起点，重复第二步．（递归）直到最后一个空间四周不存在未被标记的空间．
4.将第一个起点移出标记列表，存放至已处理标记列表中．

2062210631.png 798394785.png

def __get_through(self, pos=""):
        if(pos == ""):
            pos = self.__signList[0]

        target_pos_list = self.__get_around_pos(pos)

        if(len(target_pos_list)):
            target_pos = self.__sign_pos(pos, target_pos_list)
            self.__break_wall(pos, target_pos)
            self.__get_through(target_pos)
        else:
            self.__unsignList.append(self.__signList[0])
            del self.__signList[0]

步骤三：重复打通路线

不断重复第二个步骤，直到标记列表中没有坐标为止

849776282.png

流程效果:

510248891.gif

完整代码:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import randint


class Map():
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.__map = []
        self.__signList = [(1, 1)]  # 起点
        self.__unsignList = []

    def show_data(self):
        self.__init_map()
        self.__create_map()

        return self.__map

    def show_map(self):
        self.__init_map()
        self.__create_map()

        for i in self.__map:
            for j in i:
                if(j == 1):
                    print("# ", end="")
                else:
                    print("  ", end="")
            print("")

    # 初始化地图
    def __init_map(self):
        for i in range(self.height):
            row = []
            if(i % 2 == 0):
                for j in range(self.width):
                    row.append(1)
            else:
                for j in range(self.width):
                    if(j % 2 == 0):
                        row.append(1)
                    else:
                        row.append(0)
            self.__map.append(row)

    def __create_map(self):
        while True:
            if(len(self.__signList)):
                self.__get_through()
            else:
                break

    # 从标记坐标列表中选取下标为0的元组作为起始点，
    # 一直往下打通墙，直到四周不存在未被标记的空间
    def __get_through(self, pos=""):
        #　若没有传入起始位置，取标记列表中的第一个坐标作为起始位置
        if(pos == ""):
            pos = self.__signList[0]

        # 获取起始坐标上下左右中未被标记的坐标作为目标位置列表
        target_pos_list = self.__get_around_pos(pos)

        # 如果目标位置列表不为空
        if(len(target_pos_list)):
            # 从目标位置列表中随机选取一个作为目标位置
            target_pos = self.__sign_pos(pos, target_pos_list)
            # 打通起始位置和目标位置之间的墙
            self.__break_wall(pos, target_pos)
            # 递归,将本次的目标位置作为下次的起始位置
            self.__get_through(target_pos)
        # 如果目标位置列表为空，说明路走到尽头
        # 将标记坐标列表的第一个坐标存放至已处理坐标列表
        # 结束本条路线
        else:
            self.__unsignList.append(self.__signList[0])
            del self.__signList[0]

    # 从坐标列表中随机取其中一个坐标,将该坐标存入标记列表中
    def __sign_pos(self, pos, target_pos_list):
        target_pos = target_pos_list[randint(0, len(target_pos_list) - 1)]
        self.__signList.append(target_pos)

        return target_pos

    # 将墙打通
    def __break_wall(self, pos, target_pos):
        if(target_pos[1] > pos[1]):
            x = pos[1] + 1
        elif(target_pos[1] < pos[1]):
            x = pos[1] - 1
        else:
            x = pos[1]

        if(target_pos[0] > pos[0]):
            y = pos[0] + 1
        elif(target_pos[0] < pos[0]):
            y = pos[0] - 1
        else:
            y = pos[0]

        self.__map[x][y] = 0

    # 获取指定位置四周未被标记空位
    def __get_around_pos(self, pos):
        around_pos = []
        data = []
        data.append(self.__get_top_pos(pos, 2))
        data.append(self.__get_right_pos(pos, 2))
        data.append(self.__get_below_pos(pos, 2))
        data.append(self.__get_left_pos(pos, 2))

        for item in data:
            if(item and item not in self.__signList and item not in self.__unsignList):
                around_pos.append(item)

        return around_pos

    # 获取指定坐标上方坐标
    def __get_top_pos(self, pos, step):
        if(pos[1] - step >= 0):
            return (pos[0], pos[1] - step)
        return False

    # 获取指定坐标右方坐标
    def __get_right_pos(self, pos, step):
        if(pos[0] + step < self.width):
            return (pos[0] + step, pos[1])
        return False

    # 获取指定坐标下方坐标
    def __get_below_pos(self, pos, step):
        if(pos[1] + step < self.height):
            return (pos[0], pos[1] + step)
        return False

    # 获取指定坐标左方坐标
    def __get_left_pos(self, pos, step):
        if(pos[0] - step >= 0):
            return (pos[0] - step, pos[1])
        return False


if __name__ == "__main__":
    m = Map(31, 31)
    m.show_map()