軟體實習專案3——基于A*演算法的迷宮（代碼實作）

類變數的定義以及類的初始化__init__

class MazeMap(QWidget):
    # 類變數
    # 記錄已訪問的迷宮通路單元的坐標
    checked_x = 3
    checked_y = 3

    # 迷宮地圖的行列
    row = 2 * checked_y + 1
    column = 2 * checked_x + 1

    # 玩家起始位置
    player_x = 0
    player_y = 1

    checked = []  # 已訪問串列
    maze_map = []  # 地圖串列
    route = []
    position = {1: (0, -1), 2: (0, 1), 3: (-1, 0), 4: (1, 0)}  # 1:上 2:下 3:左 4:右
    key_direction = 0  # 鍵盤方向
    victory = 0  # 玩家是否成功到達
    cat = 'head.png'  # 玩家頭像

    # 設定幾個字體
    font1 = QtGui.QFont("Calibri", 20)
    font2 = QtGui.QFont("Calibri", 15)
    font3 = QtGui.QFont("Calibri", 13)
    font4 = QtGui.QFont("幼圓", 20)
    font5 = QtGui.QFont("幼圓", 13)

    # 所有按鈕都按照這個樣式
    buttons_style = "QPushButton{background-color: rgb(255, 255, 255); border-radius:10px}" \
                    "QPushButton:hover{Background-color:qlineargradient(x1:0,y1:0,x2:0,y2:1,stop:0 #cdced1, stop:1 #f6f7fa);}" \
                    "QPushButton:pressed{Background-color:qlineargradient(x1:0,y1:0,x2:0,y2:1,stop:0 #f6f7fa, stop:1 #cdced1);}"

    # 類初始化
    def __init__(self):
        QWidget.__init__(self)
        self.setWindowTitle('Maze')  # 視窗標題
        self.setWindowIcon(QIcon('head.png'))  # 設定視窗圖示
        ctypes.windll.shell32.SetCurrentProcessExplicitAppUserModelID("myappid")  # 任務欄圖示
        self.setStyleSheet('background-color:#000000')
        self.resize(800, 800)  # 游戲視窗大小
        self.GameStart()
        self.map_init()
        self.dfsMazeCreation((0, 0))
        self.map_done = 1

一、迷宮地圖的生成

1、初始化地圖

	# 初始化地圖，將地圖設定為1與0間隔的形式
    def map_init(self):
        self.checked_x = self.checked_x + 1
        self.checked_y = self.checked_y + 1
        self.row = 2 * self.checked_y + 1
        self.column = 2 * self.checked_x + 1
        self.player_x = 0
        self.player_y = 1
        self.key_direction = 0
        self.victory = 0
        self.map_done = 0
        self.route = []
        self.checked = [[0 for _ in range(self.checked_x)] for _ in range(self.checked_y)]  # 初始化已訪問串列
        self.maze_map = [[0 for _ in range(2 * self.checked_x + 1)] for _ in range(2 * self.checked_y + 1)]  # 初始化地圖

        # 生成橫向1和0間隔的串列
        for i in range(2 * self.checked_x + 1):
            if i % 2 == 0:
                for j in range(2 * self.checked_x + 1):
                    self.maze_map[i][j] = 1

        # 生成縱向1和0間隔的串列
        for i in range(2 * self.checked_y + 1):
            if i % 2 == 0:
                for j in range(2 * self.checked_y + 1):
                    self.maze_map[j][i] = 1

        # 打通起點和終點的墻
        self.maze_map[1][0] = 0  # 打通起點的墻
        self.maze_map[self.row - 2][self.column - 1] = 0  # 打通終點的墻

2、深度優先演算法生成迷宮

	# 使用深度優先演算法生成迷宮地圖
    def dfsMazeCreation(self, current):
        c_x, c_y = current  # 設定當前通路單元坐標
        current_x = 2 * c_x + 1
        current_y = 2 * c_y + 1
        self.checked[c_y][c_x] = 1  # 將當前坐標記為已訪問
        direction_list = [1, 2, 3, 4]
        # 遍歷四個方向的鄰居通路單元
        for i in range(4):
            random.shuffle(direction_list)  # 打亂方向串列
            direction = direction_list.pop()
            # 例：start=(0,0),position[direction]=(0,1),zip=((0,0),(0,1)),next_x=0+0,next_y=0+1
            next_x, next_y = (x + y for x, y in zip(current, self.position[direction]))  # 定義下一個要訪問的鄰居通路單元
            # 若出界了，則跳過
            if next_x < 0 or next_x >= self.checked_x or next_y < 0 or next_y >= self.checked_y or self.checked[next_y][next_x] == 1:
                continue
            # 打通當前通路單元和其鄰居通路單元中間的墻，即將迷宮地圖中的1變為0
            if direction == 1:  # 上
                wall_x, wall_y = current_x, current_y - 1
            elif direction == 2:  # 下
                wall_x, wall_y = current_x, current_y + 1
            elif direction == 3:  # 左
                wall_x, wall_y = current_x - 1, current_y
            else:  # 右
                wall_x, wall_y = current_x + 1, current_y
            self.maze_map[wall_y][wall_x] = 0
            self.dfsMazeCreation((next_x, next_y))

二、玩家走迷宮

1、鍵盤事件

	# 按下鍵盤前進
    def keyPressEvent(self, event):
        QWidget.keyPressEvent(self, event)
        key = event.key()
        # 1、按了↑
        if key == Qt.Key_Up or key == Qt.Key_W:
            self.key_direction = 1
        # 2、按了↓
        elif key == Qt.Key_Down or key == Qt.Key_S:
            self.key_direction = 2
        # 3、按了←
        elif key == Qt.Key_Left or key == Qt.Key_A:
            self.key_direction = 3
        # 4、按了→
        elif key == Qt.Key_Right or key == Qt.Key_D:
            self.key_direction = 4
        self.remove_footprint()

        # 5、按空格
        if key == Qt.Key_Space:
            self.checked_x = self.checked_x - 1
            self.checked_y = self.checked_y - 1
            self.map_init()
            self.dfsMazeCreation((0, 0))
            self.map_done = 1
            self.route = []

        # 6、按R尋路
        if key == Qt.Key_R:
            self.key_direction = 0
            self.show_route()

        self.player()

2、玩家移動

	# 玩家移動
    def player(self):
        if self.key_direction == 1 and self.maze_map[self.player_y - 1][self.player_x] == 0:
            self.player_y -= 1  # 縱坐標-1
        elif self.key_direction == 2 and self.maze_map[self.player_y + 1][self.player_x] == 0:
            self.player_y += 1  # 縱坐標+1
        elif self.key_direction == 3 and self.maze_map[self.player_y][self.player_x - 1] == 0 and self.player_x - 1 >= 0:
            self.player_x -= 1  # 橫坐標-1
        elif self.key_direction == 4 and self.maze_map[self.player_y][self.player_x + 1] == 0 and self.player_x + 1 <= self.column - 1:
            self.player_x += 1  # 橫坐標+1
        if self.player_x == self.column - 1 and self.player_y == self.row - 2:
            self.victory = 1
            self.update()
            self.GameOver()
        self.update()

三、A*演算法迷宮尋路

1、A*尋路

# A*演算法尋路
def AStar(maze_map, row, column, player_x, player_y):
    open_list = []  # 待訪問串列
    close_list = []  # 已訪問串列
    open_list.append(NODE(player_x, player_y, row, column))  # 把起點作為節點類的物件，加入open_list
    end = NODE(column - 2, row - 2, row, column)  # 創建終點的節點類物件
    # 遍歷open_list，直到當前節點為終點
    while len(open_list):
        current_node = open_list[0]
        for node in open_list:
            if node.f < current_node.f:
                current_node = node  # 將F值最小的節點作為當前節點
        open_list.remove(current_node)  # 從open_list中移除當前節點
        close_list.append(current_node)  # 在close_list中放入當前節點

        # 若當前節點為終點，回傳終點
        if current_node.x == end.x and current_node.y == end.y:
            path = []
            while current_node is not None:
                path.append((current_node.x, current_node.y))
                current_node = current_node.parent
            path.reverse()
            return path

        # 找到所有鄰居節點，并放入鄰居節點串列
        neighbors = [NODE(current_node.x, current_node.y - 1, row, column),
                     NODE(current_node.x, current_node.y + 1, row, column),
                     NODE(current_node.x - 1, current_node.y, row, column),
                     NODE(current_node.x + 1, current_node.y, row, column)]

        # 遍歷鄰居節點
        for node in neighbors:
            # 若非墻結點未超界、不在close_list中
            if 0 <= node.x < column and 0 <= node.y < row and maze_map[node.y][node.x] != 1 \
                    and not whether_in_list(node, close_list):
                if not whether_in_list(node, open_list):
                    node.note_node(current_node, end)  # 標記current_node作為該鄰居節點的父節點，通過end來計算并標記F值
                    open_list.append(node)  # 將滿足條件的鄰居節點放入open_list
                else:
                    for i in open_list:
                        if node.x == i.x and node.y == i.y:
                            if node.g < i.g:
                                i.note_node(node, end)
                            break


def whether_in_list(node, list):
    for i in list:
        if node.x == i.x and node.y == i.y:
            return True
    return False


# 節點類
class NODE:
    def __init__(self, x, y, row, column):
        self.x = x
        self.y = y
        self.g = 0
        self.h = abs(column - 2 - self.x) + abs(row - 2 - self.y)
        self.f = self.g + self.h
        self.parent = None

    # 標記節點的父節點以及F值
    def note_node(self, parent, end):
        self.parent = parent
        if parent is not None:
            self.g = parent.g + 1
        self.h = abs(end.x - self.x) + abs(end.y - self.y)
        self.f = self.g + self.h

2、顯示路徑、移除腳印

    def show_route(self):
        self.route = AStar.AStar(self.maze_map, self.row, self.column, self.player_x, self.player_y)
        for (x, y) in self.route:
            if self.player_x == x and self.player_y == y:
                index = self.route.index((x, y))
                self.route = self.route[index + 1:]
                break

    def remove_footprint(self):
        for (x, y) in self.route:
            if self.player_x == x and self.player_y == y:
                index = self.route.index((x, y))
                self.route = self.route[index + 1:]
                break

四、繪制游戲界面

	# 繪制迷宮游戲
    def paintEvent(self, event):
        QWidget.paintEvent(self, event)
        painter = QPainter(self)
        row_space = self.height() / self.row  # 行間距
        column_space = self.width() / self.column  # 列間距
        # 背景圖片
        painter.drawImage(QRectF(0, 0, self.width(), self.height()), QImage('bg.jpg'))
        # 繪制老鼠
        if self.victory == 0:
            painter.drawImage(
                QRectF((self.column - 1) * column_space, (self.column - 2) * row_space, column_space, row_space),
                QImage('mouse.png'))

        # 繪制迷宮地圖
        for row in range(self.row):
            for column in range(self.column):
                element = self.maze_map[row][column]
                # 該位置的元素為1，表明它是墻
                if element == 1:
                    painter.drawImage(QRectF(column * column_space, row * row_space, column_space, row_space),
                                      QImage('light.png'))

        # 繪制迷宮路徑
        for (x, y) in self.route:
            painter.drawImage(QRectF(x * column_space, y * row_space, column_space, row_space),
                              QImage('path.png'))

        # 繪制玩家
        painter.drawImage(QRectF(self.player_x * column_space, self.player_y * row_space, column_space, row_space),
                          QImage(self.cat))

五、游戲開始與結束界面

	# 開始游戲
    def GameStart(self):
        # 訊息框的大小和樣式
        message_box = QMessageBox()
        message_box.setStyleSheet('width: 450; height: 70')
        message_box.setWindowTitle('WELCOME')
        message_box.setFont(self.font4)
        message_box.setText("喵咪探險迷宮🐱")
        message_box.setWindowIcon(QIcon('head.png'))  # 設定訊息框圖示
        message_box.setStyleSheet('background-color:#deebf7')

        # click to start按鈕
        message_box.setStandardButtons(QMessageBox.Yes)
        yes = message_box.button(QMessageBox.Yes)
        yes.setText("Click to Start")
        yes.setFont(self.font2)
        yes.setStyleSheet(self.buttons_style)

        # 下拉框貓咪選項
        items = ['喵喵:', '銀漸層', '英短藍白', '橘貓', '奶牛貓', '三花貓']
        cb = QComboBox(message_box)
        cb.addItems(items)  # 添加下拉框選項
        cb.setGeometry(340, 27, 125, 45)
        cb.setFont(self.font5)
        cb.setStyleSheet('background-color: rgb(255, 255, 255); border-radius:10px')
        cb.currentIndexChanged.connect(self.catChoosing)  # 下拉框選項改變即觸發
        self.catChoosing(cb.currentIndex())  # 將下拉框此時的選項索引傳遞給speedChanging函式

        # 退出游戲開始訊息框，進入游戲主界面
        message_box.exec()
        self.show()

    # GameStart方法中貓咪下拉框選項改變時呼叫的槽函式，用來選擇自己喜歡的貓咪
    def catChoosing(self, index):
        if index == 1:
            self.cat = 'head.png'
        elif index == 2:
            self.cat = 'head1.png'
        elif index == 3:
            self.cat = 'head2.png'
        elif index == 4:
            self.cat = 'head3.png'
        elif index == 5:
            self.cat = 'head4.png'

    # 結束游戲
    def GameOver(self):
        message_box = QMessageBox()
        message_box.setStyleSheet('width: 200; height: 70')
        message_box.setWindowTitle('END')
        message_box.setFont(self.font1)
        message_box.setWindowIcon(QIcon('head.png'))  # 設定訊息框圖示
        message_box.setWindowOpacity(0.75)  # 透明度
        message_box.setText("You Win!")
        # 設定游戲結束訊息框的兩個按鈕
        message_box.setStandardButtons(QMessageBox.Retry | QMessageBox.Abort)
        retry = message_box.button(QMessageBox.Retry)
        retry.setText("Next Level →")
        retry.setFont(self.font2)
        retry.setStyleSheet(self.buttons_style)
        abort = message_box.button(QMessageBox.Abort)
        abort.setText("Exit")
        abort.setFont(self.font2)
        abort.setStyleSheet(self.buttons_style)
        abort.clicked.connect(QCoreApplication.instance().quit)  # 點擊此按鈕則退出程式
        message_box.exec()
        self.map_init()
        self.dfsMazeCreation((0, 0))
        self.map_done = 1

——2020/12/27（殷越）