1、 專案概述

1.1 專案目標和主要內容

1.2 專案的主要功能

2、 專案設計

2.1專案總體框架

2.2 關鍵演算法分析

prim演算法：
演算法思想：
*設N=（V,E）是連通網，TE是N上最小生成樹中邊的集合，
*初始令U={U0},(U0∈V)，TE={ }，
*在所有u∈U,v∈V-U的邊（u,v）∈E中，找一條代價最小的邊（u0,v0）.
*將（u0,v0）并入集合TE,同時v0并入U0.
*重復上述操作直至U=V為止，則T=(V.TE)為N的最小生成樹，

3、設計步驟

3.1匯入模塊

import pyxel
import random

說明:
random庫是隨機生成庫
pyxel庫是一個用Python撰寫復古游戲的開發環境

3.2生成迷宮

采用 Prim 演算法生成迷宮，
演算法分析：
1、迷宮行和列必須為奇數，
2、奇數行和奇數列的交叉點為路，其余點為墻，迷宮四周全是墻，
3、選定一個為路的單元格（本例選 [1,1]），然后把它的鄰墻放入串列 wall，
4、當串列 wall 里還有墻時：
. 4.1、從串列里隨機選一面墻，如果這面墻分隔的兩個單元格只有一個單元格被訪問過
… 4.1.1、那就從串列里移除這面墻，同時把墻打通
… 4.1.2、將單元格標記為已訪問
… 4.1.3、將未訪問的單元格的的鄰墻加入串列 wall
. 4.2、如果這面墻兩面的單元格都已經被訪問過，那就從串列里移除這面墻
定義一個 Maze 類，用二維陣串列示迷宮地圖，其中 1 表示墻壁，0 表示路，然后初始化左上角為入口，右下角為出口，最后定義下方向向量，

class Maze:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        #行和列為偶數時設定為0，0表示路，1表示墻
        self.map = [[0 if x % 2 == 1 and y % 2 == 1 else 1 for x in range(width)] for y in range(height)]
        self.map[1][0] = 0  # 入口，第二行，第一列
        self.map[height - 2][width - 1] = 0  # 出口
        self.visited = []
        # right up left down
        self.dx = [1, 0, -1, 0]
        self.dy = [0, -1, 0, 1]

    def set_value(self, point, value):
        self.map[point[1]][point[0]] = value

    def get_value(self, point):
        return self.map[point[1]][point[0]]

    # 獲取坐標（x,y）的鄰居 回傳資料結構為：二維陣列
    def get_neighbor(self, x, y, value):
        res = []

        for i in range(4):
            if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and \
                    self.get_value([x + self.dx[i], y + self.dy[i]]) == value:
                res.append([x + self.dx[i], y + self.dy[i]])
        return res

    # 獲取坐標（x,y） 的鄰墻
    def get_neighbor_wall(self, point):
        return self.get_neighbor(point[0], point[1], 1)

    # 獲取坐標（x,y） 的鄰路
    def get_neighbor_road(self, point):
        return self.get_neighbor(point[0], point[1], 0)

    def deal_with_not_visited(self, point, wall_position, wall_list):
        if not [point[0], point[1]] in self.visited:    #步驟4.1
            self.set_value(wall_position, 0)    #步驟4.1.1
            self.visited.append(point)          #步驟4.1.2
            wall_list += self.get_neighbor_wall(point)#步驟4.1.3
    def generate(self):
        start = [1, 1]
        self.visited.append(start)
        wall_list = self.get_neighbor_wall(start)   #步驟3
        while wall_list:            #步驟4
            wall_position = random.choice(wall_list)    #步驟4.1
            neighbor_road = self.get_neighbor_road(wall_position)
            wall_list.remove(wall_position)
            self.deal_with_not_visited(neighbor_road[0], wall_position, wall_list)#進行4.1
            self.deal_with_not_visited(neighbor_road[1], wall_position, wall_list)

    def is_out_of_index(self, x, y):
        return x == 0 or x == self.width - 1 or y == 0 or y == self.height - 1

3.3定義走迷宮函式

    def dfs(self, x, y, path, visited=[]):
        # 越界
        if self.is_out_of_index(x, y):
            return False

        # 訪問過 or 撞墻
        if [x, y] in visited or self.get_value([x, y]) == 1:
            return False

        visited.append([x, y])
        path.append([x, y])

        # over
        if x == self.width - 2 and y == self.height - 2:
            return True

        # 遞回程序
        for i in range(4):
            if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and \
                    self.get_value([x + self.dx[i], y + self.dy[i]]) == 0:
                if self.dfs(x + self.dx[i], y + self.dy[i], path, visited):
                    return True
                elif not self.is_out_of_index(x, y) and path[-1] != [x, y]:
                    path.append([x, y])

    # dfs
    def dfs_route(self):
        path = []
        self.dfs(1, 1, path)

        ans = [[0, 1]]
        for i in range(len(path)):
            ans.append(path[i])
            if 0 < i < len(path) - 1 and path[i - 1] == path[i + 1]:
                ans.append(path[i])
        ans.append([width - 1, height - 2])
        return ans

    # bfs
    def bfs_route(self):
        start = {'x': 0, 'y': 1, 'prev': None}
        now = start
        q = [start]
        visited = [[start['x'], start['y']]]
        # 1、從起點出發，獲取起點周圍所有連通的路
        # 2、如果該路沒有走過，則加入佇列 Q，否則跳過 同時記錄其前驅節點
        while q:
            now = q.pop(0)
            # 結束
            if now['x'] == self.width - 2 and now['y'] == self.height - 2:
                break
            roads = my_maze.get_neighbor_road([now['x'], now['y']])
            for road in roads:
                if not road in visited:
                    visited.append(road)
                    q.append({'x': road[0], 'y': road[1], 'prev': now})

        ans = []
        while now:
            ans.insert(0, [now['x'], now['y']])
            now = now['prev']
        ans.append([width - 1, height - 2])
        return ans

3.4可視化

呼叫python的pyxel庫進行可視化

class App:
    def __init__(self):
        #pyxel.init(width * pixel, height * pixel, caption='maze', border_width=10, border_color=0xFFFFFF)
        pyxel.init(width * pixel, height * pixel)
        self.death = True
        self.index = 0
        self.route = []
        self.step = 5  # 步長，數值越小速度越快，1：每次一格； 10：每次 1/10 格
        self.color = start_point_color
        self.bfs_route = my_maze.bfs_route()
        self.dfs_route = my_maze.dfs_route()
        self.dfs_model = True
        pyxel.run(self.update, self.draw)

    def update(self):
        if pyxel.btn(pyxel.KEY_Q):
            pyxel.quit()

        if pyxel.btn(pyxel.KEY_S):
            self.death = False

        if not self.death:
            self.check_death()
            self.update_route()

    def draw(self):
        # draw maze
        for x in range(height):
            for y in range(width):
                color = road_color if my_maze.map[x][y] is 0 else wall_color
                pyxel.rect(y * pixel, x * pixel, pixel, pixel, color)
        pyxel.rect(0, pixel, pixel, pixel, start_point_color)
        pyxel.rect((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)

        if self.index > 0:
            # draw route
            offset = pixel / 2
            for i in range(len(self.route) - 1):
                curr = self.route[i]
                next = self.route[i + 1]
                self.color = backtrack_color if curr in self.route[:i] and next in self.route[:i] else route_color
                pyxel.line(curr[0] + offset, (curr[1] + offset), next[0] + offset, next[1] + offset, self.color)
            pyxel.circ(self.route[-1][0] + 2, self.route[-1][1] + 2, 1, head_color)

    def check_death(self):
        if self.dfs_model and len(self.route) == len(self.dfs_route) - 1:
            self.death = True
        elif not self.dfs_model and len(self.route) == len(self.bfs_route) - 1:
            self.death = True

    def update_route(self):
        index = int(self.index / self.step)
        self.index += 1
        if index == len(self.route):  # move
            if self.dfs_model:
                self.route.append([pixel * self.dfs_route[index][0], pixel * self.dfs_route[index][1]])
            else:
                self.route.append([pixel * self.bfs_route[index][0], pixel * self.bfs_route[index][1]])


App()

運行游戲，按s開始游戲

4、 結果