gpt4 book ai didi

Python:解决 "n-to-n"迷宫

转载 作者:行者123 更新时间:2023-11-28 18:40:42 29 4
gpt4 key购买 nike

我正在尝试用 python 编写脚本来解决一种具有多个起点和多个终点的迷宫。正确的路径是从起点沿着直线前进。

例如一个有 4 条路径的迷宫:

Colored maze with 4 paths

起初我想使用左手/右手规则,但由于迷宫的特点,它没有太大意义。我已经尝试制作一种算法来遵循 4 个方向(上、下、左、右)的直线。

我现在拥有的:

from PIL import Image

UP='up'
DOWN='down'
LEFT='left'
RIGHT='right'

directionOld=RIGHT


def checkAdjacents(im,x,y):

matrix=[]
for Y in range(y-1,y+2):
r=[]
for X in range(x-1,x+2):
if im.getpixel((X,Y))==255:
r.append(True)
else:
r.append(False)
matrix.append(r)

return matrix




def testDirection(adj,direction):
if direction==UP and adj[0][1]:
return False
if direction==LEFT and adj[1][0]:
return False
if direction==RIGHT and adj[1][2]:
return False
if direction==DOWN and adj[2][1]:
return False

return True



def changeDirection(adj,direction):
if direction==UP or direction==DOWN:
if adj[1][2]:
direction=RIGHT
else:
direction=LEFT
else:
if adj[2][1]:
direction=DOWN
else:
direction=UP
return direction



def move(im,im2,x,y,directionOld,color):
im2.putpixel((x,y),color)
adj=checkAdjacents(im,x,y)
change=testDirection(adj,directionOld)
directionNew=directionOld
if change:
directionNew=changeDirection(adj,directionOld)
print "New direction ->",directionNew

if directionNew==UP:
y-=1
elif directionNew==DOWN:
y+=1
elif directionNew==RIGHT:
x+=1
else:
x-=1
return (x,y,directionNew)




image_file = Image.open("maze.png") # open colour image
im = image_file.convert('1') # convert image to black and white
im.save("2.png")
im2=im.copy() #duplicate to store results
im2=im2.convert("RGB") #results in color


paths=[(114,110,(255,0,255)),#Path1
(114,178,(255,0,0)),#Path2
(114,250,(0,255,0)),#Path3
(114,321,(0,0,255)),#Path4
]

for path in paths:
print "------------------------------------"
print "----------------Path"+str(paths.index(path))+"---------------"
print "------------------------------------"
x,y,color=path
for i in range(0,750):#number of steps
x,y,directionOld=move(im,im2,x,y,directionOld,color)

im2.save("maze_solved.png")

输入图像是像这样的黑白图像:

Initial maze

产生:

Maze solution

我想过使用类似的东西,但添加 4 个方向更符合对角线方向。

还有什么其他想法可以取得好的结果吗?

最佳答案

这是我想出的解决方案。我认为它不会太难破解,但它适用于测试集。此外,我将 pygame 与 PIL 一起使用,以观察算法运行时的输出路径渲染。 (Tkinter 对我不起作用,所以我只使用了 pygame。)

import sys

import math
from PIL import Image
#from pygame import *
import pygame, pygame.gfxdraw

# Float range utility - grabbed off Stackoverflow
def xfrange(start, stop, step):
while start < stop:
yield start
start += step

# Test a pixel for validity - fully white is valid if coordinate is within the image bounds
def testLocation(im, x, y) :
# Make sure the X position is valid
if (x < 0) or (x >= im.size[0]):
return False

# Make sure the Y position is valid
if (y < 0) or (y >= im.size[1]):
return False

if im.getpixel((x, y)) == (255, 255, 255) :
return True;

return False;

# Get the next point in the path - this is brute force. It looks for the longest
# path possible by extending a line from the current point in all directions
# (except the angle it came from - so it doesn't retrace its route) and then
# follows the longest straight line.
def getNextPoint(im, x, y, angle) :
strengthMap = []

# Sweep across the whole circle
# Note: the original step of '1' did not provide enough angular resolution
# for solving this problem. Change this back to one and solve for the violet
# path and it will end up following the blue path. For thinner or longer paths,
# this resolution might have to be even finer.
# Also, -120:120 is not a general case range - it is a slight optimization to
# solve this maze. A more general solution would be +/- 175'ish - the point is
# to prevent the "best solution" to be the last position (i.e. back tracking).
# This should happen when the angle = angle + 180
for i in xfrange(angle - 120.0, angle + 120.0, 0.25) :
# Choosing a better starting value for this would be a great optimization
distance = 2

# Find the longest possible line at this angle
while True :
nextX = int(x + distance * math.cos(math.radians(i)))
nextY = int(y + distance * math.sin(math.radians(i)))

if testLocation(im, nextX, nextY) :
distance = distance + 1
else :
# This distance failed so the previous distance was the valid one
distance = distance - 1
break

# append the angle and distance to the strengthMap
strengthMap.append((i, distance))

# Sort the strengthMap based on the distances in descending order
sortedMap = sorted(strengthMap, key=lambda entry: entry[1], reverse=True)

# Choose the first point in the sorted map
nextX = int(x + sortedMap[0][1] * math.cos(math.radians(sortedMap[0][0])))
nextY = int(y + sortedMap[0][1] * math.sin(math.radians(sortedMap[0][0])))

return int(nextX), int(nextY), sortedMap[0][0]

## Init Environment
path = 'c:\\maze problem\\';
maze_input = "maze_1.png";

paths=[(114,110,(255,0,255)),#Path1
(114,178,(255,0,0)),#Path2
(114,250,(0,255,0)),#Path3
(114,321,(0,0,255)),#Path4
]

defaultAngle = 0

pathToSolve = 3

pygame.init()

image_file = Image.open(path + maze_input) # open color image
im = image_file.convert('L');
im = im.point(lambda x : 0 if x < 1 else 255, '1') # the image wasn't cleanly black and white, so do a simple threshold
im = im.convert('RGB');

# Working Globals
posX = paths[pathToSolve][0]
posY = paths[pathToSolve][1]
color = (255, 255, 255)
angle = defaultAngle

#create the screen
window = pygame.display.set_mode((640, 480))

# Load the image for rendering to the screen - this is NOT the one used for processing
maze = pygame.image.load(path + maze_input)
imagerect = maze.get_rect()

window.blit(maze, imagerect)

# Iteration counter in case the solution doesn't work
count = 0

processing = True
while processing:
# Process events to look for exit
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit(0)

# Get the next point in the path
nextPosX, nextPosY, angle = getNextPoint(im, posX, posY, angle)

pygame.gfxdraw.line(window, posX, posY, nextPosX, nextPosY, color)
posX = nextPosX
posY = nextPosY

#draw it to the screen
pygame.display.flip()

count = count + 1
if count > 20 or posX > 550:
processing = False

这是一个示例解决方案: Blue Maze Solved

关于Python:解决 "n-to-n"迷宫,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26498708/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com