我决定制作一个可变大小的二叉树迷宫生成器。我正在尝试使用 Kruskal 的迷宫算法，我需要创建一个程序来查看玩家是否有办法从单元格 x 到达单元格 y。我在解决迷宫问题时遇到了麻烦。我决定在二叉树生成器中实现一个迷宫求解器，我掌握了基础知识，但它有一些我无法弄清楚的问题。
它从第一个单元格的中间开始，然后随机选择一个方向并尝试前进到墙所在或不在的位置，如果不可能移动，它会在另一个随机方向再次尝试。由于我只是简单地制作了墙壁上的空间，而是将它们绘制成白色，因此我必须创建一个列表，列出每一堵可以通过的可接受的墙壁。
我目前的问题是由于某种原因它不能垂直移动两次，但它(通常)水平移动两次没有问题。有什么想法吗？
from turtle import *
import random
def online(y,z):
first = z[0]
second = z[1]
firstx = first[0]
firsty = first[1]
secondx = second[0]
secondy = second[1]
if firstx <= y[0] <= secondx and firsty >= y[1] >= secondy:
return(True)
elif firstx <= y[0] <= secondx and firsty <= y[1] <= secondy:
return(True)
elif firstx >= y[0] >= secondx and firsty >= y[1] >= secondy:
return(True)
elif firstx <= y[0] <= secondx and firsty >= y[1] >= secondy:
return(True)
speed(0)
gridsize = 4
cellsize = 50
hideturtle()
cango = []
for i in range(4):
a = pos()
forward(gridsize*cellsize)
b = pos()
x = (a,b)
left(90)
goto(0,0)
for i in range(gridsize):
forward(cellsize)
left(90)
a = pos()
forward(gridsize*cellsize)
b = pos()
x = (a,b)
forward(-gridsize*cellsize)
seth(0)
goto(0,0)
seth(90)
for i in range(gridsize):
forward(cellsize)
right(90)
a = pos()
forward(gridsize*cellsize)
b = pos()
x = (a,b)
forward(-gridsize*cellsize)
seth(90)
color("white")
pensize(2)
seth(270)
a = pos()
forward(cellsize)
b = pos()
x = (a,b)
forward(-cellsize)
seth(0)
choices = (1,2)
for i in range(gridsize):
choices = (1,2) #Choice 1 cuts the right wall and choice 2 cuts the bottom wall
for i in range(gridsize):
a = int(pos()[0])
b = int(pos()[1])
#if the x value is all the way on the right, force the choice to cut the bottom
if a == (gridsize-1)*cellsize or a == (gridsize-1)*cellsize-1:
x = 2
#if the y value is all the way on the bottom, force the choice to cut the right
elif b == cellsize or b == cellsize-1:
x = 1
else:
#if not at x or y max choose randomly between cutting right and cutting down
x = random.choice(choices)
#cut right
if x == 1:
penup()
seth(0)
forward(cellsize)
right(90)
pendown()
a = pos()
forward(cellsize)
b = pos()
x = a,b
cango.append(x)
forward(-cellsize)
seth(0)
#cut bottom
elif x == 2:
penup()
seth(270)
forward(cellsize)
seth(0)
pendown()
a = pos()
forward(cellsize)
b = pos()
x = a,b
cango.append(x)
penup()
seth(90)
forward(cellsize)
seth(0)
penup()
seth(180)
forward(cellsize*gridsize)
seth(270)
forward(cellsize)
seth(0)
speed(3)
showturtle()
color("red")
goto(25,175)
penup()
print(cango)
pensize(4)
for i in range(1000):
if pos() == (175.0,0.0):
pensize(10)
pencolor("green")
break
direction = random.randint(1,4)
penup()
if direction == 1:
seth(0)
elif direction == 2:
seth(90)
elif direction == 3:
seth(180)
else:
seth(270)
penup()
forward(25)
nohit = True
for i in cango:
if online(pos(),i) == True:
nohit = False
x = i[0]
y = i[1]
#if x[0] == pos()[0] and x[1] == pos()[1] or y[0] == pos()[0] and y[1] == pos()[1]:
#nohit = True
if nohit == False:
backward(25)
pendown()
forward(50)
else:
backward(25)
已解决
如果有人遇到类似的问题，我的问题是因为 python turtle 在定义点时不是 100% 准确的，因此我的点有时类似于 (24.999999991,100)，我最终强制他们是整数，对于我的程序，我只处理 5 的倍数，所以我测试的每个点是 4 还是 9，如果是，我加 1。
最佳答案
python turtle isn't 100% accurate when defining points, due to this my points were sometimes things like (24.999999991,100)
你必须改变你的想法。 turtle 在浮点平面上游荡。所有浮点实现都有折衷。学会与他们打交道:
I ended up forcing them to be integers ... for every point I tested if anything was a 4 or a 9 and if so I added 1
我建议使用 round()，而不是 int() 的组合以及上面和下面的测试。但更好的方法是使用减法或 turtle.distance()，并检查差异是否小到足以称其相同。
这是我使用上述方法对您的代码进行的修改；修复问题以允许调整网格大小；样式和优化更改。看看这些修改对您是否有意义:
from turtle import *
from random import randrange, choice
GRID_SIZE = 5
CELL_SIZE = 50
RIGHT, BOTTOM = 1, 2 # Choice 1 cuts the right wall and choice 2 cuts the bottom wall
def online(position, line):
x, y = position
(firstx, firsty), (secondx, secondy) = line
if firstx <= x <= secondx and firsty >= y >= secondy:
return True
if firstx <= x <= secondx and firsty <= y <= secondy:
return True
if firstx >= x >= secondx and firsty >= y >= secondy:
return True
if firstx <= x <= secondx and firsty >= y >= secondy:
return True
return False
# Draw the grid
hideturtle()
speed('fastest')
for _ in range(GRID_SIZE):
forward(CELL_SIZE)
left(90)
forward(GRID_SIZE * CELL_SIZE)
backward(GRID_SIZE * CELL_SIZE)
right(90)
home()
setheading(90)
for _ in range(GRID_SIZE):
forward(CELL_SIZE)
right(90)
forward(GRID_SIZE * CELL_SIZE)
backward(GRID_SIZE * CELL_SIZE)
left(90)
# Undraw walls to create a maze
color('white')
setheading(270)
forward(CELL_SIZE)
backward(CELL_SIZE)
setheading(0)
cango = []
for _ in range(GRID_SIZE):
for i in range(GRID_SIZE):
a, b = position()
# if the x value is all the way on the right, force the choice to cut the bottom
if abs(((GRID_SIZE - 1) * CELL_SIZE) - a) < CELL_SIZE / 4:
wall = BOTTOM
# if the y value is all the way on the bottom, force the choice to cut the right
elif abs(CELL_SIZE - b) < CELL_SIZE / 4:
wall = RIGHT
else:
# if not at x nor y max, choose randomly between cutting right and cutting down
wall = choice([RIGHT, BOTTOM])
penup()
if wall == RIGHT: # cut right
setheading(0)
forward(CELL_SIZE)
right(90)
pendown()
start = position()
forward(CELL_SIZE)
end = position()
elif wall == BOTTOM: # cut bottom
setheading(270)
forward(CELL_SIZE)
setheading(0)
pendown()
start = position()
forward(CELL_SIZE)
end = position()
right(90)
cango.append((start, end))
penup()
backward(CELL_SIZE)
setheading(0)
penup()
backward(CELL_SIZE * GRID_SIZE)
setheading(270)
forward(CELL_SIZE)
setheading(0)
# Solve the maze
speed('slow')
shape('turtle')
color('red')
pensize(4)
goto(CELL_SIZE / 2, GRID_SIZE * CELL_SIZE - CELL_SIZE / 2)
showturtle()
change_heading = False # get the most you can out of a direction change
while pencolor() == 'red':
if distance(GRID_SIZE * CELL_SIZE - CELL_SIZE / 2, -CELL_SIZE / 2) <= CELL_SIZE / 4:
color('green')
break
penup()
if change_heading:
direction = randrange(4) * 90
setheading(direction)
change_heading = False
forward(CELL_SIZE / 2)
nohit = True
for line in cango:
if online((round(xcor()), round(ycor())), line):
nohit = False
break
backward(CELL_SIZE / 2)
if not nohit:
pendown()
forward(CELL_SIZE)
else:
change_heading = True
mainloop()
关于python - Kruskal 迷宫算法的 Python 实现问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47160561/