实验任务（实验题目、目的）

Use VC++/Python to solve the Maze problem.

利用VC++/Python语言实现迷宫路径求解，要求图形界面，可用递归或非递归方式。

任务分析

实现思路

1. 将迷宫单元用二维列表表示，-1为墙，0为可以走的路

2. 首先初始化格子，等待输入，当点击按下后接受输入的迷宫列数，行数

3. 生成迷宫矩阵，据此画出迷宫。

4. 点击走迷宫按钮后，根据全局变量矩阵maz由三种算法计算路径。

涉及的知识点

 迷宫生成算法:dfs算法,bfs算法,Prim算法,Kruskal算法

 走迷宫算法:dfs算法,bfs算法,A*算法,(迪杰斯特拉算法,弗洛伊德算法）

 PyQt5的布局与作图

 bfs如何走迷宫并打印出迷宫路径（与dfs记录路径不一样）

出现的问题

 关于Python参数传递问题（值传递 or 址传递）

 如何动态刷新

 关于pyqt5函数的一些参数问题

使用的库

# -*- coding: utf-8 -*-

from PyQt5 import QtCore, QtGui, QtWidgets

import sys,random

from PyQt5.QtWidgets import QApplication,QMainWindow,QGraphicsItem

from PyQt5.QtCore import Qt,QRectF

import numpy as np

from queue import Queue,PriorityQueue

全局变量

WIDTH,HEIGHT=800,800 #Graphicsview的尺寸

COL_INTERVAL,ROW_INTERVAL = 3,3 #格子间的间距

COL_LEN,ROW_LEN = 20,20 #格子的长度

COL_NUM,ROW_NUM = 35,35 #格子的数量

FIND,GENERATE,SPEED=0,0,0 #生成方式，走迷宫方式，刷新速度

maz=np.ones((ROW_NUM,COL_NUM)) #迷宫矩阵

dx,dy=ROW_NUM - 2,COL_NUM - 1 #终点

record,ans,process= [],[],[] #记录答案

核心代码

深度优先生成迷宫

class DFSg ( object ):
‎ def __init__ ( self , width= 11 , height= 11 ):
‎ # 迷宫最小长宽为 5
‎ assert width >= 5 and height >= 5 , "Length of width or height must be larger than 5."
‎ # 确保迷宫的长和宽均为奇数
‎ self .width = (width // 2 ) * 2 + 1
‎ self .height = (height // 2 ) * 2 + 1
‎ self .start = [ 1 , 0 ]
‎ self .destination = [ self .height - 2 , self .width - 1 ]
‎ self .matrix = None
‎ def generate_matrix_dfs ( self ):
‎ # 地图初始化，并将出口和入口处的值设置为 0
‎ self .matrix = -np.ones(( self .height, self .width))
‎ self .matrix[ self .start[ 0 ], self .start[ 1 ]] = 0
‎ self .matrix[ self .destination[ 0 ], self .destination[ 1 ]] = 0
‎ visit_flag = [[ 0 for i in range ( self .width)] for j in range ( self .height)]
‎ def check ( row , col , row_, col_):
‎ temp_sum = 0
‎ for d in [[ 0 , 1 ], [ 0 , - 1 ], [ 1 , 0 ], [- 1 , 0 ]]:
‎ temp_sum += self.matrix[row_ + d[ 0 ]][col_ + d[ 1 ]]
‎ return temp_sum <= - 3
‎ def dfs (row, col):
‎ visit_flag[row][col] = 1
‎ self.matrix[row][col] = 0
‎ if row == self.start[ 0 ] and col == self.start[ 1 ] + 1 :
‎ return
‎ directions = [[ 0 , 2 ], [ 0 , - 2 ], [ 2 , 0 ], [- 2 , 0 ]]
‎ random.shuffle(directions)
‎ for d in directions:
‎ row_, col_ = row + d[ 0 ], col + d[ 1 ]
‎ if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and visit_flag[row_][
‎ col_] == 0 and check(row, col, row_, col_):
‎ if row == row_:
‎ visit_flag[row][ min (col, col_) + 1 ] = 1
‎ self.matrix[row][ min (col, col_) + 1 ] = 0
‎ else :
‎ visit_flag[ min (row, row_) + 1 ][col] = 1
‎ self.matrix[ min (row, row_) + 1 ][col] = 0
‎ dfs(row_, col_)
‎ dfs( self .destination[ 0 ], self .destination[ 1 ] - 1 )
‎ self .matrix[ self .start[ 0 ], self .start[ 1 ] + 1 ] = 0

P rim 算法生成迷宫

class PRIMg ( object ):
‎ def __init__ ( self , width= 11 , height= 11 ):
‎ assert width >= 5 and height >= 5 , "Length of width or height must be larger than 5."
‎ self .width = (width // 2 ) * 2 + 1
‎ self .height = (height // 2 ) * 2 + 1
‎ self .start = [ 1 , 0 ]
‎ self .destination = [ self .height - 2 , self .width - 1 ]
‎ self .matrix = None
‎ # 虽然说是 prim 算法，但是我感觉更像随机广度优先算法
‎ def generate_matrix_prim ( self ):
‎ # 地图初始化，并将出口和入口处的值设置为 0
‎ self .matrix = -np.ones(( self .height, self .width))
‎ def check (row, col):
‎ temp_sum = 0
‎ for d in [[ 0 , 1 ], [ 0 , - 1 ], [ 1 , 0 ], [- 1 , 0 ]]:
‎ temp_sum += self.matrix[row + d[ 0 ]][col + d[ 1 ]]
‎ return temp_sum < - 3
‎ queue = []
‎ row, col=(np.random.randint( 1 , self .height - 1 ) // 2 ) * 2 + 1 , (
‎ np.random.randint( 1 , self .width - 1 ) // 2 ) * 2 + 1
‎ queue.append((row, col, - 1 , - 1 ))
‎ while len (queue) != 0 :
‎ row, col, r_, c_ = queue.pop(np.random.randint( 0 , len (queue)))
‎ if check(row, col):
‎ self .matrix[row, col] = 0
‎ if r_ != - 1 and row == r_:
‎ self .matrix[row][ min (col, c_) + 1 ] = 0
‎ elif r_ != - 1 and col == c_:
‎ self .matrix[ min (row, r_) + 1 ][col] = 0
‎ for d in [[ 0 , 2 ], [ 0 , - 2 ], [ 2 , 0 ], [- 2 , 0 ]]:
‎ row_, col_ = row + d[ 0 ], col + d[ 1 ]
‎ if row_ > 0 and row_ < self .height - 1 and col_ > 0 and col_ < self .width - 1 and self .matrix[row_][
‎ col_] == - 1 :
‎ queue.append((row_, col_, row, col))
‎ self .matrix[ self .start[ 0 ], self .start[ 1 ]] = 0
‎ self .matrix[ self .destination[ 0 ], self .destination[ 1 ]] = 0

K ruskal 算法生成迷宫

class KRUSKALg ( object ):
‎ def __init__ ( self , width = 11 , height = 11 ):
‎ assert width >= 5 and height >= 5 , "Length of width or height must be larger than 5."
‎ self .width = (width // 2 ) * 2 + 1
‎ self .height = (height // 2 ) * 2 + 1
‎ self .start = [ 1 , 0 ]
‎ self .destination = [ self .height - 2 , self .width - 1 ]
‎ self .matrix = None
‎ # 最小生成树算法 -kruskal （选边法）思想生成迷宫地图，这种实现方法最复杂。
‎ def generate_matrix_kruskal ( self ):
‎ # 地图初始化，并将出口和入口处的值设置为 0
‎ self .matrix = -np.ones(( self .height, self .width))
‎ def check (row, col):
‎ ans, counter = [], 0
‎ for d in [[ 0 , 1 ], [ 0 , - 1 ], [ 1 , 0 ], [- 1 , 0 ]]:
‎ row_, col_ = row + d[ 0 ], col + d[ 1 ]
‎ if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and self.matrix[row_, col_] == - 1 :
‎ ans.append([d[ 0 ] * 2 , d[ 1 ] * 2 ])
‎ counter += 1
‎ if counter <= 1 :
‎ return []
‎ return ans
‎ nodes = set ()
‎ row = 1
‎ while row < self .height:
‎ col = 1
‎ while col < self .width:
‎ self .matrix[row, col] = 0
‎ nodes.add((row, col))
‎ col += 2
‎ row += 2
‎ unionset = UnionSet(nodes)
‎ while unionset.count > 1 :
‎ row, col = nodes.pop()
‎ directions = check(row, col)
‎ if len (directions):
‎ random.shuffle(directions)
‎ for d in directions:
‎ row_, col_ = row + d[ 0 ], col + d[ 1 ]
‎ if unionset.find((row, col)) == unionset.find((row_, col_)):
‎ continue
‎ nodes.add((row, col))
‎ unionset.count -= 1
‎ unionset.union((row, col), (row_, col_))
‎ if row == row_:
‎ self .matrix[row][ min (col, col_) + 1 ] = 0
‎ else :
‎ self .matrix[ min (row, row_) + 1 ][col] = 0
‎ break
‎ self .matrix[ self .start[ 0 ], self .start[ 1 ]] = 0
‎ self .matrix[ self .destination[ 0 ], self .destination[ 1 ]] = 0

DFS算法走迷宫

def dfs (x,y):
‎ global dx, dy,record,w
‎ # Save(record)
‎ # pp = processPaint()
‎ # pp.setPos(0, 0)
‎ # w.update(pp)
‎ if x == dx and y == dy:
‎ Keep(record)
‎ return
‎ for (kx, ky) in [[ 1 , 0 ], [- 1 , 0 ], [ 0 , 1 ], [ 0 , - 1 ]]:
‎ if (check(kx + x, ky + y)):
‎ record.append((kx + x, ky + y))
‎ dfs(kx + x, ky + y)
‎ record.pop()

BFS算法走迷宫

def bfs (t):
‎ global que,dx,dy,record
‎ lis={}
‎ visited=[( 1 , 0 )]
‎ que=Queue()
‎ que.put(t)
‎ while que:
‎ temp=que.get()
‎ if temp[ 0 ]==dx and temp[ 1 ]==dy:
‎ break
‎ for (kx, ky) in [[ 1 , 0 ], [- 1 , 0 ], [ 0 , 1 ], [ 0 , - 1 ]]:
‎ x=kx + temp[ 0 ]
‎ y=ky + temp[ 1 ]
‎ if (x > 0 and y > 0 and x < ROW_NUM and y < COL_NUM and maz[x][y] == 0 and (x,y) not in visited):
‎ que.put((x, y))
‎ visited.append((x, y))
‎ lis[(x,y)]=(temp[ 0 ],temp[ 1 ])
‎ if (x==dx and y==dy):
‎ break
‎ record.append((dx,dy))
‎ (x,y)=lis[(dx,dy)]
‎ record.append((x, y))
‎ while (x,y)!=( 1 , 0 ):
‎ (x,y)=lis[x,y]
‎ record.append((x, y))
‎ Keep(record)

A*算法走迷宫

def Astar ():
‎ start = ( 1 , 0 )
‎ final = (ROW_NUM - 2 , COL_NUM - 1 )
‎ front = PriorityQueue()
‎ front.put(start)
‎ father = {}
‎ father[start] = None
‎ sum_cost = {}
‎ sum_cost[start] = 0
‎ while front:
‎ current = front.get()
‎ if current == final:
‎ break
‎ for (dx, dy) in [[ 1 , 0 ], [- 1 , 0 ], [ 0 , 1 ], [ 0 , - 1 ]]:
‎ x = current[ 0 ] + dx
‎ y = current[ 1 ] + dy
‎ if isOK((x, y)):
‎ cost = sum_cost[current] + calcuCost(current, (x, y))
‎ if (x, y) not in sum_cost or cost < sum_cost[(x, y)]:
‎ sum_cost[(x, y)] = cost
‎ priority = cost + heuristic(start, (x, y))
‎ front.put((x, y), priority)
‎ father[(x, y)] = current
‎ if (x, y) == final:
‎ break
‎ temp=final
‎ while temp:
‎ record.append(temp)
‎ temp=father[temp]
‎ Keep(record)