Как мне настроить алгоритм поиска пути для моей новой программы генерации уровней? ⇐ Python

[Anonymous]

Моя проблема в том, что у меня есть такой 2D-массив:
[["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]]

игрок начинает справа (обозначается как «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))
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 [j] = getwall()
level [0][0] = " "
level [9][9] = "["


Подробнее здесь: https://stackoverflow.com/questions/792 ... eration-pr