Python使用Tkinter实现机器人走迷宫

概述这本是课程的一个作业研究搜索算法，当时研究了一下Tkinter，然后写了个很简单的机器人走迷宫的界面，并且使用了各种搜索算法来进行搜索，如下图：

这本是课程的一个作业研究搜索算法，当时研究了一下Tkinter，然后写了个很简单的机器人走迷宫的界面，并且使用了各种搜索算法来进行搜索，如下图：

使用A*寻找最优路径：

由于时间关系，不分析了，我自己贴代码吧。希望对一些也要用Tkinter的人有帮助。

from Tkinter import *from random import *import timeimport numpy as npimport utilclass Directions: norTH = 'north' SOUTH = 'South' EAST = 'East' WEST = 'West'# Detect elements in the mapwindow = Tk()window.Title('CityBusPlanner')window.resizable(0,0)wIDth = 25(x,y) = (22,22)totalsteps = 0buIDings = [(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 MapcityMap()# Create Robot VIEwrobotCityMap()# Create a robotrobot = 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 Falsedef isEdge(newX,newY): global x,y if newX >= x or newY >= y or newX < 0 or newY < 0 : return True return Falsedef 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 successorsdef 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 = Falsedef 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 wroads = set()detectedBuildings = {}blockcolors = {}blockIndex = 0def 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 positionsdef 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 nodedef 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 nodedef 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 newlinkedBlockdef 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 Falsedef roadHeuristic(road): return 0def 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 sysimport inspectimport 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) == 0class 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) == 0class 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) == 0class 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深度优先算法生成迷宫Python基于分水岭算法解决走迷宫游戏示例Python使用回溯法子集树模板解决迷宫问题示例Python基于递归算法实现的走迷宫问题用Python代码来解图片迷宫的方法整理python实现的生成随机迷宫算法核心代码分享（含游戏完整代码）一道python走迷宫算法题 总结

以上是内存溢出为你收集整理的Python使用Tkinter实现机器人走迷宫全部内容，希望文章能够帮你解决Python使用Tkinter实现机器人走迷宫所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。