Skip to main content
 首页 » 编程设计

python之Kruskal 迷宫算法的 Python 实现问题

2025年01月19日11EasonJim

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