my problem is that I have a 2D array like this:
[["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]]
the player starts in the to right (represented as “X”) and the goal is to get to the door (“[“) . I’ve already made the game and player movement, but I’m trying to make a level generator so that I don’t have to manually make levels, Ive already made the level gen, I just need an algorithm to check whether or not the level is possible to play, (sometimes the door isn’t reachable)
i tried to make my own (quite janky) pathfinding algorithm and it really just didn’t work.
How do I go about making such a function, to check the levels for playability?
code for the game below:
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("33[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)
level gen:
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] = "["
New contributor
gaskutiy is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
8
Your approach is to generate a random grid, and then verify whether it is one where you can reach the exit from the entry point. I suppose if this is not possible, you will generate another random grid, and continue like that until you have found a valid one.
I would suggest to approach this differently. You can enhance the generation part to always generate a grid that has a solution. I would also suggest to avoid cycles, which also means you’d avoid trivial “spaces” that have no walls, like this:
# #
# #
You could use one of the algorithms suggested on Wikipedia – Maze generation algorithm, such as the depth-first traversal, using an explicit stack:
from random import choice, randrange
WALL = "|"
FREE = " " # A temporary value. Will not occur in a fully generated level
REACHABLE = "#"
ENTRY = "[" # The single cell where the player starts
EXIT = "]" # The target cell that the player should reach
def gen_level(size):
size |= 1 # ensure it is odd
# start with all cells surrounded by walls
level = [
[
(WALL, FREE)[(x & y) % 2]
for x in range(size)
]
for y in range(size)
]
stack = [(1, 1)]
level[1][1] = REACHABLE
while stack:
x1, y1 = stack[-1]
try:
x2, y2 = choice([
(x2, y2)
for dx, dy in ((-2, 0), (2, 0), (0, -2), (0, 2))
for x2, y2 in ((x1 + dx, y1 + dy), )
if 0 <= x2 < size and 0 <= y2 < size and level[y2][x2] == FREE
])
level[y2][x2] = level[(y1+y2)//2][(x1+x2)//2] = REACHABLE
stack.append((x2, y2))
except IndexError:
stack.pop()
level[1 + randrange(size//2) * 2][0] = ENTRY
level[1 + randrange(size//2) * 2][-1] = EXIT
return level
Here is how you would call the above function:
level = gen_level(20)
for line in level:
print(*line)
And here is one possible output that this produces:
| | | | | | | | | | | | | | | | | | | | |
| # # # # # # # | # # # # # # # # # | # |
| | | | | | | # | | | # | | | | | # | # |
| # | # # # | # # # | # # # | # # # | # |
| # | # | # | | | # | | | # | # | | | # |
| # # # | # # # | # # # | # | # # # | # |
| # | | | # | | | | | # | # | | | # | # |
| # # # | # # # # # # # | # # # | # # # ]
| | | # | | | | | | | | | # | # | | | # |
[ # | # # # # # | # # # # # | # # # | # |
| # | | | | | # | # | | | | | | | # | # |
| # # # # # | # | # # # # # # # | # | # |
| # | | | # | # | | | | | | | # | # | | |
| # # # | # # # | # # # # # | # | # # # |
| | | # | | | | | # | | | # | | | | | # |
| # | # | # # # | # # # | # # # # # # # |
| # | # | # | # | | | # | | | | | | | # |
| # | # # # | # # # | # # # | # | # # # |
| # | | | | | | | # | | | # | # | # | | |
| # # # # # # # # # # # # # | # # # # # |
| | | | | | | | | | | | | | | | | | | | |
Note that the actual height/width is odd (not 20, but 21): this is a consequence of the choice to have all (x, y) reachable that have odd x and odd y.
Unrelated, but the output is a bit more “readable” when you use block-characters for walls, and a very light character (like a dot) for the reachable cells, like using:
WALL = "█"
REACHABLE = "·"
…and then format the the output as follows:
for line in level:
print(" ".join(line).replace(WALL + " " + WALL, WALL * 3)
.replace(WALL + " " + WALL, WALL * 3))
Then you get an output like this:
█████████████████████████████████████████
█ · · · █ · · · · · · · · · · · · · █ · █
█████ · █████████ · █████████ · █ · █ · █
█ · █ · █ · · · █ · █ · · · █ · █ · · · █
█ · █ · █ · █ · █ · █████ · █ · █████████
█ · █ · · · █ · █ · · · · · █ · █ · · · █
█ · █████████ · █████████ · █ · █ · █ · █
[ · · · · · █ · █ · · · █ · █ · · · █ · █
█ · █████████ · █ · █ · █████████████ · █
█ · · · · · █ · · · █ · █ · · · · · · · █
█ · █████ · █████████ · █ · █████████████
█ · █ · · · █ · · · · · █ · █ · · · · · █
█████ · █████ · █████████ · █ · █████ · █
█ · · · █ · · · █ · · · · · █ · █ · █ · █
█ · █████ · █████ · █████████ · █ · █ · █
█ · █ · · · █ · · · · · · · · · · · █ · █
█ · █ · █████ · █████████████████ · █ · █
█ · █ · █ · · · · · · · █ · · · █ · █ · █
█ · █ · █████████████████ · █ · █████ · █
█ · · · · · · · · · · · · · █ · · · · · ]
█████████████████████████████████████████
The comments suggesting various pathfinding algorithms are correct! Since you are only looking to determine if a level is playable and you are not looking for a shortest path, I recommend using Breadth-first search.
Simply consider the start of the algorithm to be the position of the character, and consider the children of each node to be a step in each cardinal direction. Run BFS until the door is found or all nodes have been visited and this will let you know if the level is playable.