Python使用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
# -------
# 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] )