#!/usr/bin/python3.7# -*- coding: utf-8 -*-import randomimport pygame#import depth_mazeimport maze#import aldous_broder_mazepygame.init()  # 初始化pygamesize = width, height = 800, 600  # 设置窗口大小screen = pygame.display.set_mode(size)  # 显示窗口# 颜色diamond_color_size = 8COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_GREY, COLOR_GOLDEN, COLOR_NO_DIAMOND = list(range(    diamond_color_size))COLOR = {    COLOR_RED: (255, 0, 0),    COLOR_BLUE: (0, 0, 255),    COLOR_GREEN: (0, 255, 0),    COLOR_YELLOW: (255, 255, 0),    COLOR_BLACK: (0, 0, 0),    COLOR_GREY: (250, 240, 230),    COLOR_GOLDEN : (255,215,0),    COLOR_NO_DIAMOND: (100, 100, 100),}# 格子大小DIAMOND_LEN = 20DIAMOND_SIZE = (DIAMOND_LEN, DIAMOND_LEN)# 蓝格子DIAMOND=pygame.surface.Surface(DIAMOND_SIZE).convert()DIAMOND.fill(COLOR[COLOR_BLUE])# 绿格子 DIAMOND_GREEN=pygame.surface.Surface(DIAMOND_SIZE).convert()DIAMOND_GREEN.fill(COLOR[COLOR_GREEN])# 红格子 DIAMOND_RED=pygame.surface.Surface(DIAMOND_SIZE).convert()DIAMOND_RED.fill(COLOR[COLOR_RED])# 黄格子 DIAMOND_YELLOW=pygame.surface.Surface(DIAMOND_SIZE).convert()DIAMOND_YELLOW.fill(COLOR[COLOR_YELLOW])# 灰的格子 DIAMOND_GREY=pygame.surface.Surface(DIAMOND_SIZE).convert()DIAMOND_GREY.fill(COLOR[COLOR_GREY])# 字体use_font = pygame.font.Font("FONT.TTF", 16)use_font12 = pygame.font.Font("FONT.TTF", 12)# 背景background=pygame.surface.Surface(size).convert()background.fill(COLOR[COLOR_BLACK])# 文字score_surface = use_font.render("找到终点", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])# 时间clock = pygame.time.Clock()###############################################   格子访问标记x,y,0，右墙x,y,1，下墙x,y,2###############################################标记 NOWALL=maze.NOWALL # 无墙WALL=maze.WALL  # 有墙WALL2=maze.WALL2  # 有墙VISIT=maze.VISIT # 到访过NOVISIT=maze.NOVISIT # 没到过VERTICAL = maze.VERTICAL # 垂直的HORIZONTAL = maze.HORIZONTAL# 水平的INFINITE = maze.INFINITE # 无穷远INFINITE = maze.INFINITE # 无穷远# def FindNext(pathList, walls, grids, rows, cols):    nextList = [] # 下一步    for node in pathList:        r, c = node        l = grids[r][c]        nl=l+1        # 可以到达的位置        if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:            # move = 'u'            nr=r-1            nc=c            if (nr,nc) not in nextList:                nextList.append((nr,nc))                grids[nr][nc] = l+1        if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:            # move = 'l'            nr=r            nc=c-1            if (nr,nc) not in nextList:                nextList.append((nr,nc))                grids[nr][nc] = l+1        if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :            # move='r'            nr=r            nc=c+1            if (nr,nc) not in nextList:                nextList.append((nr,nc))                grids[nr][nc] = l+1        if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :            # move='d'            nr=r+1            nc=c            if (nr,nc) not in nextList:                nextList.append((nr,nc))                grids[nr][nc] = l+1    return nextListdef draw_diamond(r,c, screen, POSX, POSY, diamod):    px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]    # 标记访问过的格子    screen.blit(diamod, (px, py))    return def draw_diamond_and_str(r,c, screen, POSX, POSY, diamod, use_font, string, color, color_back):    px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]    # 标记访问过的格子    screen.blit(diamod, (px, py))    distance_surface = use_font.render(string, True, color, color_back)    screen.blit(distance_surface, (px, py))    return # Sample algorithmdef multipath_maze_demo(rows, cols):    #walls = maze.aldous_broder_maze(rows, cols)    #walls = maze.depth_maze(rows, cols)    #walls = maze.kruskal_maze(rows, cols)    #walls = maze.prim_maze(rows, cols)    #walls = maze.wilson_maze(rows, cols)    walls = maze.wilson_maze(rows, cols)    POSX=40    POSY=40    # 初始化未访问    grids=[[ INFINITE for i in range(cols)]for j in range(rows)]    # 起点    # 标记迷宫    r=0    c=0    findEndPoint=False    findPath=False    # 起点    startPoint=(r,c)    # 终点    stopPoint=(rows-1,cols-1)    #     mainList=[] # 主路径    beginList=[startPoint]    endList=[stopPoint]    grids[r][c]=0 # 标记已经到过格子距离    grids[stopPoint[0]][stopPoint[1]]=0    # 没有访问过的格子    notUseGrids = []     for tr in range(rows):        for tc in range(cols):            notUseGrids.append((tr,tc))    beginMap=beginList    endMap=endList    while True:        for event in pygame.event.get():            if event.type == pygame.QUIT:                return        if notUseGrids:                    beginNextList = [] # 下一步            for node in beginList:                r, c = node                l = grids[r][c]                # 可以到达的位置                if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:                    # move = 'u'                    nr=r-1                    nc=c                    if (nr,nc) not in beginNextList:                        beginNextList.append((nr,nc))                        grids[nr][nc] = l+1                if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:                    # move = 'l'                    nr=r                    nc=c-1                    if (nr,nc) not in beginNextList:                        beginNextList.append((nr,nc))                        grids[nr][nc] = l+1                if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :                    # move='r'                    nr=r                    nc=c+1                    if (nr,nc) not in beginNextList:                        beginNextList.append((nr,nc))                        grids[nr][nc] = l+1                if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :                    # move='d'                    nr=r+1                    nc=c                    if (nr,nc) not in beginNextList:                        beginNextList.append((nr,nc))                        grids[nr][nc] = l+1            # 下一圈            beginList = beginNextList            beginMap = beginMap + beginNextList            # end            endNextList = [] # 下一步            for node in endList:                r, c = node                l = grids[r][c]                # 可以到达的位置                if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:                    # move = 'u'                    nr=r-1                    nc=c                    if (nr,nc) not in endNextList:                        endNextList.append((nr,nc))                        grids[nr][nc] = l+1                if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:                    # move = 'l'                    nr=r                    nc=c-1                    if (nr,nc) not in endNextList:                        endNextList.append((nr,nc))                        grids[nr][nc] = l+1                if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :                    # move='r'                    nr=r                    nc=c+1                    if (nr,nc) not in endNextList:                        endNextList.append((nr,nc))                        grids[nr][nc] = l+1                if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :                    # move='d'                    nr=r+1                    nc=c                    if (nr,nc) not in endNextList:                        endNextList.append((nr,nc))                        grids[nr][nc] = l+1            # 下一圈            endList = endNextList            endMap = endMap + endNextList        elif findEndPoint and not findPath:            mainList.append((r,c))            l = grids[r][c]            nl=l-1            # 最近的            if r>0 and NOWALL == walls[r][c][1] and nl == grids[r-1][c]:                # move = 'u'                nr=r-1                nc=c            if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:                # move = 'l'                nr=r                nc=c-1                beginNextList.append((nr,nc))            if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :                # move='r'                nr=r                nc=c+1            if r<rows-1 and NOWALL == walls[r+1][c][1] and nl == grids[r+1][c] :                # move='d'                nr=r+1                nc=c            # 找到起点            if 0 == nl:                mainList.append((nr,nc))                findPath = True            r,c=nr,nc        screen.blit(background, (0, 0))        # 格子        for cx in range(cols):            for ry in range(rows):                px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]                # 标记访问过的格子                if maze.INFINITE == grids[ry][cx]:                    draw_diamond(ry, cx, screen, POSX, POSY, DIAMOND)                else:                    s = "{}".format(grids[ry][cx])                    draw_diamond_and_str(ry, cx, screen, POSX,POSY, DIAMOND_GREY, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])         # 圈地        for pos in beginMap:            s = "{}".format(grids[pos[0]][pos[1]])            draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_GREEN, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])        for pos in endMap:            s = "{}".format(grids[pos[0]][pos[1]])            draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])        # 循环外圈        if beginList and not mainList:            for pos in beginList:                s = "{}".format(grids[pos[0]][pos[1]])                draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])            for pos in endList:                s = "{}".format(grids[pos[0]][pos[1]])                draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])        # 路径        if mainList:            for pos in mainList:                s = "{}".format(grids[pos[0]][pos[1]])                draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])            # r,c            px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]            screen.blit(DIAMOND_GREEN, (px, py))            s = "{}".format(grids[r][c])            distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])            screen.blit(distance_surface, (px, py))        # 画外墙        pygame.draw.rect(screen, COLOR[COLOR_RED], (POSX + 0, POSY + 0, DIAMOND_LEN*cols+1, DIAMOND_LEN*rows+1), 2)        # 画没打通的墙        for cx in range( cols):            for ry in range(rows):                px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]                color = COLOR[COLOR_BLACK]                if maze.WALL == walls[ry][cx][0]:                    pygame.draw.line(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)                if maze.WALL == walls[ry][cx][1]:                    pygame.draw.line(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)        # 打印文字提示        if findEndPoint:            screen.blit(score_surface, (POSX+50, POSY+rows*22))        # 帧率        clock.tick(25)        pygame.display.update()    return # mainif __name__ == "__main__":    '''main'''    multipath_maze_demo(20, 30)