Kruskal迷宫算法的Python实现问题

Question

我决定做一个可变大小的二叉树迷宫生成器。我正在尝试使用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。

Answer 1

python turtle在定义点时不是100%准确，因此我的点有时是这样的(24.999999991,100)

你必须改变你的想法。乌龟在浮点平面上游荡。所有浮点实现都有折衷方案。学会如何处理它们：

I最终强制它们为整数...对于每个点，我测试是否有任何东西是4或9，如果是，我添加1

我建议使用round()，而不是上面和下面的int()和testing的组合。但更好的方法是使用减法或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()

​

​