概述
这本是课程的一个作业研究搜索算法,当时研究了一下Tkinter,然后写了个很简单的机器人走迷宫的界面,并且使用了各种搜索算法来进行搜索,如下图:
使用A*寻找最优路径:
由于时间关系,不分析了,我自己贴代码吧。希望对一些也要用Tkinter的人有帮助。
from Tkinter import * from random import * import time import numpy as np import util class Directions: NORTH = 'North' SOUTH = 'South' EAST = 'East' WEST = 'West' # Detect elements in the map window = Tk() window.title('CityBusPlanner') window.resizable(0,0) width = 25 (x,y) = (22,22) totalsteps = 0 buidings = [(0,0),(1,(2,(3,(7,(8,(11,(12,(13,(17,(18,(21,1),2),(5,(9,(14,(15,(16,3),(4,(19,4),(0,6),7),8),9),10),11),13),14),15),16),17),18),19),21),(6,(10,21)] walls = [(10,12),21)] park = [(14,0)] robotPos = (21,12) view = Canvas(window,width=x * width,height=y * width) view.grid(row=0,column=0) searchMapButton = Button(window,text = 'search') searchMapButton.grid(row = 0,column = 1) robotView = Canvas(window,height=y * width) robotView.grid(row = 0,column = 2) def formatColor(r,g,b): return '#%02x%02x%02x' % (int(r * 255),int(g * 255),int(b * 255)) def cityMap(): global width,x,y,buidings,walls,park,robot for i in range(x): for j in range(y): view.create_rectangle( i * width,j * width,(i + 1) * width,(j + 1) * width,fill='white',outline='gray',width=1) for (i,j) in buidings: view.create_rectangle( i * width,fill='black',j) in walls: view.create_rectangle( i * width,fill='blue',j) in park: view.create_rectangle( i * width,fill='red',width=1) def robotCityMap(): global width,robot,robotPos for i in range(x): for j in range(y): robotView.create_rectangle( i * width,width=1) robotView.create_rectangle( robotPos[0] * width,robotPos[1] * width,(robotPos[0] + 1) * width,(robotPos[1] + 1) * width,width=1) # Create City Map cityMap() # Create Robot View robotCityMap() # Create a robot robot = view.create_rectangle(robotPos[0] * width + width * 2 / 10,robotPos[1] * width + width * 2 / 10,robotPos[0] * width + width * 8 / 10,robotPos[1] * width + width * 8 / 10,fill="orange",width=1,tag="robot") robotSelf = robotView.create_rectangle(robotPos[0] * width + width * 2 / 10,tag="robot") visited = [robotPos] def move(dx,dy): global robot,robotPos,robotSelf,view global totalsteps totalsteps = totalsteps + 1 newX = robotPos[0] + dx newY = robotPos[1] + dy if (not isEdge(newX,newY)) and (not isBlock(newX,newY)): #print "move %d" % totalsteps view.coords(robot,(newX) * width + width * 2 / 10,(newY) * width + width * 2 / 10,(newX) * width + width * 8 / 10,(newY) * width + width * 8 / 10) robotView.coords(robotSelf,(newY) * width + width * 8 / 10) robotPos = (newX,newY) if robotPos not in visited: visited.append(robotPos) visitedPanel = robotView.create_rectangle( robotPos[0] * width,width=1) robotView.tag_lower(visitedPanel,robotSelf) else: print "move error" def callUp(event): move(0,-1) def callDown(event): move(0,1) def callLeft(event): move(-1,0) def callRight(event): move(1,0) def isBlock(newX,newY): global buidings,y for (i,j) in buidings: if (i == newX) and (j == newY): return True return False def isEdge(newX,newY): global x,y if newX >= x or newY >= y or newX < 0 or newY < 0 : return True return False def getSuccessors(robotPos): n = Directions.NORTH w = Directions.WEST s = Directions.soUTH e = Directions.EAST successors = [] posX = robotPos[0] posY = robotPos[1] if not isBlock(posX - 1,posY) and not isEdge(posX - 1,posY): successors.append(w) if not isBlock(posX,posY + 1) and not isEdge(posX,posY + 1): successors.append(s) if not isBlock(posX + 1,posY) and not isEdge(posX + 1,posY): successors.append(e) if not isBlock(posX,posY -1) and not isEdge(posX,posY - 1): successors.append(n) return successors def getNewPostion(position,action): posX = position[0] posY = position[1] n = Directions.NORTH w = Directions.WEST s = Directions.soUTH e = Directions.EAST if action == n: return (posX,posY - 1) elif action == w: return (posX - 1,posY) elif action == s: return (posX,posY + 1) elif action == e: return (posX + 1,posY) delay = False def runAction(actions): global delay n = Directions.NORTH w = Directions.WEST s = Directions.soUTH e = Directions.EAST for i in actions: if delay: time.sleep(0.05) if i == n: #print "North" move(0,-1) elif i == w: #print "West" move(-1,0) elif i == s: #print "South" move(0,1) elif i == e: #sprint "East" move(1,0) view.update() def searchMapTest(event): global robotPos actions = [] position = robotPos for i in range(100): successors = getSuccessors(position) successor = successors[randint(0,len(successors) - 1)] actions.append(successor) position = getNewPostion(position,successor) print actions runAction(actions) def reverseSuccessor(successor): n = Directions.NORTH w = Directions.WEST s = Directions.soUTH e = Directions.EAST if successor == n: return s elif successor == w: return e elif successor == s: return n elif successor == e: return w roads = set() detectedBuildings = {} blockColors = {} blockIndex = 0 def updateBuildings(detectedBuildings): global robotView,width for block,buildings in detectedBuildings.items(): color = blockColors[block] for building in buildings: robotView.create_rectangle( building[0] * width,building[1] * width,(building[0] + 1) * width,(building[1] + 1) * width,fill=color,outline=color,width=1) def addBuilding(position): global blockIndex,detectedBuildings isAdd = False addBlock = '' for block,buildings in detectedBuildings.items(): for building in buildings: if building == position: return if util.manhattanDistance(position,building) == 1: if not isAdd: buildings.add(position) isAdd = True addBlock = block break else: #merge two block for building in detectedBuildings[block]: detectedBuildings[addBlock].add(building) detectedBuildings.pop(block) if not isAdd: newBlock = set([position]) blockIndex = blockIndex + 1 detectedBuildings['Block %d' % blockIndex] = newBlock color = formatColor(random(),random(),random()) blockColors['Block %d' % blockIndex] = color updateBuildings(detectedBuildings) def addRoad(position): global robotView,width,robotSelf visitedPanel = robotView.create_rectangle( position[0] * width,position[1] * width,(position[0] + 1) * width,(position[1] + 1) * width,robotSelf) def showPath(positionA,positionB,path): global robotView,view view.create_oval(positionA[0] * width + width * 3 / 10,positionA[1] * width + width * 3 / 10,positionA[0] * width + width * 7 / 10,positionA[1] * width + width * 7 / 10,fill='yellow',width=1) nextPosition = positionA for action in path: nextPosition = getNewPostion(nextPosition,action) view.create_oval(nextPosition[0] * width + width * 4 / 10,nextPosition[1] * width + width * 4 / 10,nextPosition[0] * width + width * 6 / 10,nextPosition[1] * width + width * 6 / 10,width=1) view.create_oval(positionB[0] * width + width * 3 / 10,positionB[1] * width + width * 3 / 10,positionB[0] * width + width * 7 / 10,positionB[1] * width + width * 7 / 10,width=1) hasDetected = set() def detectLocation(position): if position not in hasDetected: hasDetected.add(position) if isBlock(position[0],position[1]): addBuilding(position) elif not isEdge(position[0],position[1]): addRoad(position) def detect(position): posX = position[0] posY = position[1] detectLocation((posX,posY + 1)) detectLocation((posX,posY - 1)) detectLocation((posX + 1,posY)) detectLocation((posX - 1,posY)) def heuristic(positionA,positionB): return util.manhattanDistance(positionA,positionB) def AstarSearch(positionA,positionB): "Step 1: define closed: a set" closed = set() "Step 2: define fringe: a PriorityQueue " fringe = util.PriorityQueue() "Step 3: insert initial node to fringe" "Construct node to be a tuple (location,actions)" initialNode = (positionA,[]) initCost = 0 + heuristic(initialNode[0],positionB) fringe.push(initialNode,initCost) "Step 4: Loop to do search" while not fringe.isEmpty(): node = fringe.pop() if node[0] == positionB: return node[1] if node[0] not in closed: closed.add(node[0]) for successor in getSuccessors(node[0]): actions = list(node[1]) actions.append(successor) newPosition = getNewPostion(node[0],successor) childNode = (newPosition,actions) cost = len(actions) + heuristic(childNode[0],positionB) fringe.push(childNode,cost) return [] def AstarSearchBetweenbuildings(building1,building2): "Step 1: define closed: a set" closed = set() "Step 2: define fringe: a PriorityQueue " fringe = util.PriorityQueue() "Step 3: insert initial node to fringe" "Construct node to be a tuple (location,actions)" initialNode = (building1,building2) fringe.push(initialNode,initCost) "Step 4: Loop to do search" while not fringe.isEmpty(): node = fringe.pop() if util.manhattanDistance(node[0],building2) == 1: return node[1] if node[0] not in closed: closed.add(node[0]) for successor in getSuccessors(node[0]): actions = list(node[1]) actions.append(successor) newPosition = getNewPostion(node[0],building2) fringe.push(childNode,cost) return [] def calculatePositions(buildingA,path): positions = set() positions.add(buildingA) nextPosition = buildingA for action in path: nextPosition = getNewPostion(nextPosition,action) positions.add(nextPosition) return positions def showRoad(fullRoad): global view,width for road in fullRoad: view.create_oval(road[0] * width + width * 4 / 10,road[1] * width + width * 4 / 10,road[0] * width + width * 6 / 10,road[1] * width + width * 6 / 10,width=1) view.update() def search(node): successors = getSuccessors(node[0]) detect(node[0]) for successor in successors: nextPosition = getNewPostion(node[0],successor) if nextPosition not in roads: runAction([successor]) # to the next node roads.add(nextPosition) search((nextPosition,[successor],[reverseSuccessor(successor)])) runAction(node[2]) #back to top node def searchConsiderTopVisit(node,topWillVisit): successors = getSuccessors(node[0]) detect(node[0]) newTopWillVisit = set(topWillVisit) for successor in successors: nextPosition = getNewPostion(node[0],successor) newTopWillVisit.add(nextPosition) for successor in successors: nextPosition = getNewPostion(node[0],successor) if nextPosition not in roads and nextPosition not in topWillVisit: runAction([successor]) # to the next node roads.add(nextPosition) newTopWillVisit.remove(nextPosition) searchConsiderTopVisit((nextPosition,[reverseSuccessor(successor)]),newTopWillVisit) runAction(node[2]) #back to top node def searchShortestPathBetweenBlocks(block1,block2): shortestPath = [] buildingA = (0,0) buildingB = (0,0) for building1 in block1: for building2 in block2: path = AstarSearchBetweenbuildings(building1,building2) if len(shortestPath) == 0: shortestPath = path buildingA = building1 buildingB = building2 elif len(path) < len(shortestPath): shortestPath = path buildingA = building1 buildingB = building2 return (buildingA,buildingB,shortestPath) def addBuildingToBlocks(linkedBlock,buildingA): global detectedBuildings newLinkedBlock = linkedBlock.copy() for block,buildings in detectedBuildings.items(): for building in buildings: if util.manhattanDistance(buildingA,building) == 1: newLinkedBlock[block] = buildings break return newLinkedBlock def bfsSearchNextBlock(initBuilding,linkedBlock): global detectedBuildings closed = set() fringe = util.Queue() initNode = (initBuilding,[]) fringe.push(initNode) while not fringe.isEmpty(): node = fringe.pop() newLinkedBlock = addBuildingToBlocks(linkedBlock,node[0]) if len(newLinkedBlock) == len(detectedBuildings): return node[1] if len(newLinkedBlock) > len(linkedBlock): # find a new block actions = list(node[1]) ''' if len(node[1]) > 0: lastAction = node[1][len(node[1]) - 1] for successor in getSuccessors(node[0]): if successor == lastAction: nextPosition = getNewPostion(node[0],successor) actions.append(successor) return actions + bfsSearchNextBlock(nextPosition,newLinkedBlock) ''' return node[1] + bfsSearchNextBlock(node[0],newLinkedBlock) if node[0] not in closed: closed.add(node[0]) for successor in getSuccessors(node[0]): actions = list(node[1]) actions.append(successor) nextPosition = getNewPostion(node[0],successor) childNode = (nextPosition,actions) fringe.push(childNode) return [] def isGoal(node): global detectedBuildings,robotPos linkedBlock = {} positions = calculatePositions(robotPos,node[1]) for position in positions: for block,buildings in detectedBuildings.items(): for building in buildings: if util.manhattanDistance(position,building) == 1: linkedBlock[block] = buildings print len(linkedBlock) if len(linkedBlock) == 17: return True else: return False def roadHeuristic(road): return 0 def AstarSearchRoad(): global robotPos,detectedBuildings "Step 1: define closed: a set" closed = set() "Step 2: define fringe: a PriorityQueue " fringe = util.PriorityQueue() "Step 3: insert initial node to fringe" "Construct node to be a tuple (location,actions)" initRoad = (robotPos,[]) initCost = 0 + roadHeuristic(initRoad) fringe.push(initRoad,initCost) "Step 4: Loop to do search" while not fringe.isEmpty(): node = fringe.pop() if isGoal(node): print len(closed) return node[1] if node[0] not in closed: closed.add(node[0]) for successor in getSuccessors(node[0]): actions = list(node[1]) actions.append(successor) newPosition = getNewPostion(node[0],actions) cost = len(actions) + roadHeuristic(childNode) fringe.push(childNode,cost) return [] def searchRoad(building): global detectedBuildings,robotPos linkedBlock = {} initBuilding = building return bfsSearchNextBlock(initBuilding,linkedBlock) def searchShortestRoad(): shortestRoad = [] shortestPositions = set() for block,buildings in detectedBuildings.items(): for building in buildings: road = searchRoad(building) positions = calculatePositions(building,road) if len(shortestPositions) == 0 or len(positions) < len(shortestPositions): shortestRoad = road shortestPositions = positions print len(shortestPositions) showRoad(shortestPositions) def searchMap(event): print "Search Map" global robotPos,roads,detectedBuildings,delay actions = [] #roads = set()s #roads.add(robotPos) #fringe = util.Stack() initNode = (robotPos,[],[]) # (position,forwardActions,backwarsdActions) #fringe.push(initNode) roads.add(robotPos) search(initNode) #searchConsiderTopVisit(initNode,set()) print detectedBuildings print len(detectedBuildings) #path = AstarSearchBetweenbuildings((6,18)) #showPath((6,path) ''' shortestRoad = set() for block1 in detectedBuildings.values(): roads = set() for block2 in detectedBuildings.values(): if not block1 == block2: (buildingA,path) = searchShortestPathBetweenBlocks(block1,block2) #showPath(buildingA,path) positions = calculatePositions(buildingA,path) roads = roads | positions if len(shortestRoad) == 0 or len(roads) < len(shortestRoad): shortestRoad = roads print len(shortestRoad) showRoad(shortestRoad) ''' ''' block1 = detectedBuildings.values()[3] print block1 block2 = detectedBuildings.values()[5] print block2 (buildingA,block2) print buildingA,path showPath(buildingA,path) block1 = detectedBuildings.values()[10] print block1 block2 = detectedBuildings.values()[20] print block2 (buildingA,path) ''' searchShortestRoad() ''' path = searchRoad() #path = AstarSearchRoad() positions = calculatePositions(robotPos,path) print len(positions) showRoad(positions) delay = True #runAction(path) ''' window.bind("<Up>",callUp) window.bind("<Down>",callDown) window.bind("<Right>",callRight) window.bind("<Left>",callLeft) window.bind("s",searchMap) searchMapButton.bind("<Button-1>",searchMap) window.mainloop()
下面的util.py使用的是加州伯克利的代码:
# util.py # ------- # Licensing Information: You are free to use or extend these projects for # educational purposes provided that (1) you do not distribute or publish # solutions,(2) you retain this notice,and (3) you provide clear # attribution to UC Berkeley,including a link to http://ai.berkeley.edu. # # Attribution Information: The Pacman AI projects were developed at UC Berkeley. # The core projects and autograders were primarily created by John DeNero # (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu). # Student side autograding was added by Brad Miller,Nick Hay,and # Pieter Abbeel (pabbeel@cs.berkeley.edu). import sys import inspect import heapq,random """ Data structures useful for implementing SearchAgents """ class Stack: "A container with a last-in-first-out (LIFO) queuing policy." def __init__(self): self.list = [] def push(self,item): "Push 'item' onto the stack" self.list.append(item) def pop(self): "Pop the most recently pushed item from the stack" return self.list.pop() def isEmpty(self): "Returns true if the stack is empty" return len(self.list) == 0 class Queue: "A container with a first-in-first-out (FIFO) queuing policy." def __init__(self): self.list = [] def push(self,item): "Enqueue the 'item' into the queue" self.list.insert(0,item) def pop(self): """ Dequeue the earliest enqueued item still in the queue. This operation removes the item from the queue. """ return self.list.pop() def isEmpty(self): "Returns true if the queue is empty" return len(self.list) == 0 class PriorityQueue: """ Implements a priority queue data structure. Each inserted item has a priority associated with it and the client is usually interested in quick retrieval of the lowest-priority item in the queue. This data structure allows O(1) access to the lowest-priority item. Note that this PriorityQueue does not allow you to change the priority of an item. However,you may insert the same item multiple times with different priorities. """ def __init__(self): self.heap = [] self.count = 0 def push(self,item,priority): # FIXME: restored old behavIoUr to check against old results better # FIXED: restored to stable behavIoUr entry = (priority,self.count,item) # entry = (priority,item) heapq.heappush(self.heap,entry) self.count += 1 def pop(self): (_,_,item) = heapq.heappop(self.heap) # (_,item) = heapq.heappop(self.heap) return item def isEmpty(self): return len(self.heap) == 0 class PriorityQueueWithFunction(PriorityQueue): """ Implements a priority queue with the same push/pop signature of the Queue and the Stack classes. This is designed for drop-in replacement for those two classes. The caller has to provide a priority function,which extracts each item's priority. """ def __init__(self,priorityFunction): "priorityFunction (item) -> priority" self.priorityFunction = priorityFunction # store the priority function PriorityQueue.__init__(self) # super-class initializer def push(self,item): "Adds an item to the queue with priority from the priority function" PriorityQueue.push(self,self.priorityFunction(item)) def manhattanDistance( xy1,xy2 ): "Returns the Manhattan distance between points xy1 and xy2" return abs( xy1[0] - xy2[0] ) + abs( xy1[1] - xy2[1] )
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。
总结
以上是编程之家为你收集整理的Python使用Tkinter实现机器人走迷宫全部内容,希望文章能够帮你解决Python使用Tkinter实现机器人走迷宫所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧