我应该如何为我的新关卡生成程序配置寻路算法

Question

我的问题是我有一个像这样的二维数组：

    [["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
     ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]]

玩家从右边开始（表示为“X”），目标是到达门口（“[”）。我已经制作了游戏和玩家移动，但我正在尝试制作一个关卡生成器，这样我就不必手动制作关卡，我已经制作了关卡生成器，我只需要一个算法来检查是否该关卡可以玩，（有时门无法到达）

我尝试制作自己的（相当简陋的）寻路算法，但它真的不起作用。

我该如何制作这样一个功能来检查可玩性级别？

以下游戏代码：

import sys
import tty
import termios
import os
import random
#instalize base variables for the game
levelnum = 1
op = 1
atk = 1
hp = 20
ehp = 5
XX = 0
XY = 0
keytf = False
level = [["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "["],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "["],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"]]
#key getting function
def get_key():  # get the key pressed
    fd = sys.stdin.fileno()
    old_settings = termios.tcgetattr(fd)
    try:
        tty.setraw(fd)
        ch = sys.stdin.read(1)
    finally:
        termios.tcsetattr(fd, termios.TCSADRAIN, old_settings)
    return ch
#print level function
def printlevel():  # Print the current level
    level[XY][XX] = "X"
    print("\033[H", end="")  # Clear the terminal
    for i in range(10):
        print(" ".join(level[i]))
    print("Stats:")
    print("HP: " + str(hp))
    print("ATK: " + str(atk))
    print("Enemy HP: " + str(ehp))
#level storage
def newlevel(levelnum):
    global level
    if levelnum == 1:
        level = [["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "#", "#", "#", "#", "#", "["],
                 ["#", "#", "#", "#", "#", "#", "#", "#", "#", "["],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"]]
    elif levelnum == 2:
        level = [["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "|", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "#", "e", "#", "#", "#", "["],
                 ["#", "#", "#", "#", "|", "|", "#", "#", "#", "["],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"]]
    elif levelnum == 3:
        level = [["#", "|", "#", "e", "#", "|", "#", "e", "#", "#"],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "#"],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "#"],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "#"],
                 ["H", "|", "H", "|", "H", "|", "H", "|", "#", "["],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "["],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "#"],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "#"],
                 ["#", "|", "#", "|", "#", "|", "#", "|", "#", "#"],
                 ["#", "e", "#", "|", "#", "e", "#", "|", "#", "#"]]
    elif levelnum == 4:
        level = [["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "#", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "|", "|", "#", "#", "#", "#"],
                 ["#", "#", "#", "#", "#", "D", "#", "#", "#", "["],
                 ["#", "|", "|", "|", "|", "|", "#", "#", "#", "["],
                 ["#", "#", "#", "|", "|", "#", "#", "#", "#", "#"],
                 ["|", "|", "#", "|", "|", "#", "#", "#", "#", "#"],
                 ["|", "K", "#", "|", "|", "#", "#", "#", "#", "#"],
                 ["|", "|", "|", "|", "|", "#", "#", "#", "#", "#"]]
#check your next move
def movechecker(move, op):
    global XY, XX, levelnum, ehp, atk, hp, keytf
    level[XY][XX] = "#"
    
    if move == "[":
        XX = 0
        XY = 0
        levelnum += 1
        newlevel(levelnum)
    elif move == "e" and ehp >= 1:
        ehp -= atk
        hp -= 1
    elif move == "H":
        hp += 10
        moveit(op)
    elif move == "K":
        keytf = True
        moveit(op)
    elif move == "D" and keytf == True:
        moveit(op)
    elif ehp < 1:
        moveit(op)
        ehp = 5
    else:
        moveit(op)

    printlevel()
#move the player   
def moveit(op):
    global XY, XX
    
    if op == 1:  # Move right
        XX += 1
    elif op == 2:  # Move left
        XX -= 1
    elif op == 3:  # Move up
        XY -= 1
    elif op == 4:  # Move down
        XY += 1
    level[XY][XX] = "X"
    printlevel()

printlevel()
#main game loop
while True:  # Main game loop
    key = get_key()
    if key == "d" and XX < 9 and level[XY][XX+1] != "|":
        move = level[XY][XX+1]
        op = 1
        movechecker(move, op)
    elif key == "a" and XX > 0 and level[XY][XX-1] != "|":
        move = level[XY][XX-1]
        op = 2
        movechecker(move, op)
    elif key == "w" and XY > 0 and level[XY-1][XX] != "|":
        move = level[XY-1][XX]
        op = 3
        movechecker(move, op)
    elif key == "s" and XY < 9 and level[XY+1][XX] != "|":
        move = level[XY+1][XX]
        op = 4
        movechecker(move, op)

关卡生成：

    import random

level = [["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
         ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]]
def getwall():
    if random.randint(1, 100) < 35:
        return "|"
    return "#"
def genlevel():
    for i in range (10):
        for j in range (10):
            level [i][j] = getwall()
    level [0][0] = " "
    level [9][9] = "["

Answer 1

建议各种寻路算法的评论是正确的！由于您只想确定是否某个关卡可玩，而不是寻找最短路径，因此我建议使用广度优先搜索。

简单地将算法的开始视为角色的位置，并将每个节点的子节点视为每个基本方向上的一步。运行 BFS 直到找到门或访问所有节点，这会让您知道该关卡是否可以玩。