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

这本是课程的一个作业研究搜索算法,当时研究了一下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, 0), (2, 0), (3, 0), (7, 0), (8, 0), (11, 0), (12, 0), (13, 0),
 (17, 0), (18, 0), (21, 0), (21, 1), (2, 2), (5, 2), (8, 2), (9, 2), (12, 2),
 (14, 2), (15, 2), (16, 2), (17, 2), (21, 2), (2, 3), (4, 3), (5, 3), (7, 3),
 (8, 3), (11, 3), (17, 3), (18, 3), (19, 3), (2, 4), (4, 4), (5, 4), (8, 4),
 (9, 4), (14, 4), (15, 4),(17, 4), (18, 4), (19, 4), (0, 6), (2, 6), (4, 6),
 (7, 6), (8, 6), (11, 6), (12, 6), (14, 6), (15, 6),(16, 6), (18, 6), (19, 6),
 (2, 7), (5, 7), (21, 7), (0, 8), (2, 8), (11, 8), (14, 8), (15, 8), (17, 8),
 (18, 8), (21, 8), (4, 9), (5, 9), (7, 9), (9, 9), (11, 9), (14, 9), (21, 9),
 (2, 10), (7, 10), (14, 10), (17, 10), (19, 10), (0, 11), (2, 11), (4, 11),
 (5, 11), (7, 11), (8, 11), (9, 11), (11, 11), (12, 11), (14, 11), (15, 11),
 (16, 11), (17, 11), (18, 11), (19, 11), (0, 13), (2, 13), (3, 13), (5, 13),
 (7, 13), (8, 13), (9, 13), (14, 13), (17, 13), (18, 13), (21, 13), (2, 14),
 (3, 14), (5, 14), (7, 14),(9, 14), (12, 14), (14, 14), (15, 14), (17, 14),
 (18, 14), (21, 14), (2, 15), (3, 15), (5, 15), (7, 15), (9, 15), (12, 15),
 (15, 15), (19, 15), (21, 15), (0, 16), (21, 16), (0, 17), (3, 17), (5, 17),
 (7, 17),(9, 17), (11, 17), (14, 17), (15, 17), (17, 17), (18, 17), (21, 17),
 (2, 18), (3, 18), (5, 18), (7, 18),(9, 18), (11, 18), (14, 18), (17, 18),
 (18, 18), (3, 19), (5, 19), (7, 19), (9, 19), (11, 19), (12, 19), (14, 19),
 (17, 19), (18, 19), (0, 21), (1, 21), (2, 21), (5, 21), (6, 21), (9, 21),
 (10, 21), (11, 21), (12, 21), (15, 21), (16, 21), (18, 21), (19, 21), (21, 21)]

walls = [(10, 0), (0, 12), (21, 12), (14, 21)]
park = [(14, 0), (15, 0), (16, 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,width=x * width, 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, j * width, (i + 1) * width, (j + 1) * width, fill='black', outline='gray', width=1)
 for (i,j) in walls:
 view.create_rectangle(
 i * width, j * width, (i + 1) * width, (j + 1) * width, fill='blue', outline='gray', width=1)
 for (i,j) in park:
 view.create_rectangle(
 i * width, j * width, (i + 1) * width, (j + 1) * width, fill='red', outline='gray', width=1)

def robotCityMap():
 global width, x, y, buidings,walls,park,robot,robotPos
 for i in range(x):
 for j in range(y):
 robotView.create_rectangle(
 i * width, j * width, (i + 1) * width, (j + 1) * width, fill='black', width=1)
 robotView.create_rectangle(
 robotPos[0] * width, robotPos[1] * width, (robotPos[0] + 1) * width, (robotPos[1] + 1) * width, fill='white', outline='gray', 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, robotPos[1] * width + width * 2 / 10,
  robotPos[0] * width + width * 8 / 10, robotPos[1] * width + width * 8 / 10, fill="orange", width=1, tag="robot")

visited = [robotPos]

def move(dx,dy):
 global robot,x,y,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, (newX) * width + width * 2 / 10, (newY) * width + width * 2 / 10,
  (newX) * width + width * 8 / 10, (newY) * width + width * 8 / 10)
 robotPos = (newX, newY)
 if robotPos not in visited:
 visited.append(robotPos)
 visitedPanel = robotView.create_rectangle(
 robotPos[0] * width, robotPos[1] * width, (robotPos[0] + 1) * width, (robotPos[1] + 1) * width, fill='white', outline='gray', 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,x,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, fill='white', outline='gray', width=1)
 robotView.tag_lower(visitedPanel,robotSelf)

def showPath(positionA,positionB,path):
 global robotView,width,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, fill='yellow', 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, fill='yellow', 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,[])
 initCost = 0 + heuristic(initialNode[0],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], successor)
 childNode = (newPosition,actions)
 cost = len(actions) + heuristic(childNode[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, fill='yellow', 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,[successor],[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], successor)
 childNode = (newPosition,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,21), (2, 18))
 #showPath((6,21),(2,18), path)
 '''
 shortestRoad = set()
 for block1 in detectedBuildings.values():
 roads = set()
 for block2 in detectedBuildings.values():
 if not block1 == block2:
 (buildingA,buildingB,path) = searchShortestPathBetweenBlocks(block1, block2)
 #showPath(buildingA,buildingB,path)
 positions = calculatePositions(buildingA,buildingB,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,buildingB,path) = searchShortestPathBetweenBlocks(block1, block2)
 print buildingA,buildingB,path
 showPath(buildingA,buildingB,path)

 block1 = detectedBuildings.values()[10]
 print block1
 block2 = detectedBuildings.values()[20]
 print block2
 (buildingA,buildingB,path) = searchShortestPathBetweenBlocks(block1, block2)
 print buildingA,buildingB,path
 showPath(buildingA,buildingB,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, item, 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走迷宫算法题
(0)

相关推荐

  • 一道python走迷宫算法题

    前几天逛博客时看到了这样一道问题,感觉比较有趣,就自己思考了下方案顺便用python实现了一下.题目如下: 用一个二维数组表示一个简单的迷宫,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠走迷宫,找到从入口到出口的一条路径. 如图所示: 先说下我的思路吧: 1.首先用一个列表source存储迷宫图,一个列表route_stack存储路线图,一个列表route_history存储走过的点,起点(0,0),终点(4,4). 2.老鼠在每个点都有上下左右

  • 用Python代码来解图片迷宫的方法整理

    译注:原文是StackOverflow上一个如何用程序读取迷宫图片并求解的问题,几位参与者热烈地讨论并给出了自己的代码,涉及到用Python对图片的处理以及广度优先(BFS)算法等. 问题by Whymarrh: 当给定上面那样一张JPEG图片,如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫? 我的第一直觉是将这张图按像素逐个读入,并存储在一个包含布尔类型元素的列表或数组中,其中True代表白色像素,False代表非白色像素(或彩色可以被处理成二值图像).但是这种做法存在一个问题,那

  • Python深度优先算法生成迷宫

    本文实例为大家分享了Python深度优先算法生成迷宫,供大家参考,具体内容如下 import random #warning: x and y confusing sx = 10 sy = 10 dfs = [[0 for col in range(sx)] for row in range(sy)] maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] #1:up 2:down 3:left 4:right opera

  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

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

    这本是课程的一个作业研究搜索算法,当时研究了一下Tkinter,然后写了个很简单的机器人走迷宫的界面,并且使用了各种搜索算法来进行搜索,如下图: 使用A*寻找最优路径: 由于时间关系,不分析了,我自己贴代码吧.希望对一些也要用Tkinter的人有帮助. from Tkinter import * from random import * import time import numpy as np import util class Directions: NORTH = 'North' SOU

  • 教你用Python创建微信聊天机器人

    最近研究微信API,发现个非常好用的python库:wxpy.wxpy基于itchat,使用了 Web 微信的通讯协议,实现了微信登录.收发消息.搜索好友.数据统计等功能. 这里我们就来介绍一下这个库,并在最后实现一个聊天机器人. 有没有很兴奋?有没有很期待? 好了,接下来,开始我们的正题. 准备工作 安装非常简单,从官方源下载安装 pip install -U wxpy 或者从豆瓣源安装 pip install -U wxpy -i "https://pypi.doubanio.com/sim

  • 用Q-learning算法实现自动走迷宫机器人的方法示例

    项目描述: 在该项目中,你将使用强化学习算法,实现一个自动走迷宫机器人. 如上图所示,智能机器人显示在右上角.在我们的迷宫中,有陷阱(红色×××)及终点(蓝色的目标点)两种情景.机器人要尽量避开陷阱.尽快到达目的地. 小车可执行的动作包括:向上走 u.向右走 r.向下走 d.向左走l. 执行不同的动作后,根据不同的情况会获得不同的奖励,具体而言,有以下几种情况. 撞到墙壁:-10 走到终点:50 走到陷阱:-30 其余情况:-0.1 我们需要通过修改 robot.py 中的代码,来实现一个 Q

  • Python解决走迷宫问题算法示例

    本文实例讲述了Python解决走迷宫问题算法.分享给大家供大家参考,具体如下: 问题: 输入n * m 的二维数组 表示一个迷宫 数字0表示障碍 1表示能通行 移动到相邻单元格用1步 思路: 深度优先遍历,到达每一个点,记录从起点到达每一个点的最短步数 初始化案例: 1   1   0   1   1 1   0   1   1   1 1   0   1   0   0 1   0   1   1   1 1   1   1   0   1 1   1   1   1   1 1 把图周围加上

  • python基于tkinter点击按钮实现图片的切换

    tkinter是python的标准Tk GUI工具包的接口,在windows下如果你安装的python3,那在安装python的时候,就已经自动安装了tkinter了 如果是在linux系统中,则不会自动安装tkinter,需要通过 sudo apt-get install python-tk 手动安装 首先先介绍一下,tkinter本身只支持gif等少数几个图片格式,如果图片并不复杂,建议直接右击图片,进入编辑,在画图界面将图片另存为gif格式就可以使用了(连png和jpeg都不支持...真的

  • Python基于Tkinter的HelloWorld入门实例

    本文实例讲述了Python基于Tkinter的HelloWorld入门实例.分享给大家供大家参考.具体分析如下: 初学Python,打算做几个Tkinter的应用来提高. 刚学的HelloWorld,秀一下.我用Python3.2的,Windows版本的. 源代码如下: #导入sys和tkinter模块 import sys, tkinter #创建主窗口 root = tkinter.Tk() root.title("HelloWorld") root.minsize(200, 10

  • Python基于tkinter模块实现的改名小工具示例

    本文实例讲述了Python基于tkinter模块实现的改名小工具.分享给大家供大家参考,具体如下: #!/usr/bin/env python #coding=utf-8 # # 版权所有 2014 yao_yu # 本代码以MIT许可协议发布 # 文件名批量加.xls后缀 # 2014-04-21 创建 # import os import tkinter as tk from tkinter import ttk version = '2014-04-21' app_title = '文件名

  • python的tkinter布局之简单的聊天窗口实现方法

    本文实例展示了一个python的tkinter布局的简单聊天窗口.分享给大家供大家参考之用.具体方法如下: 该实例展示的是一个简单的聊天窗口,可以实现下方输入聊天内容,点击发送,可以增加到上方聊天记录列表中.现在只是"单机"版. 右侧预留了空位可以放点儿其它东西.感兴趣的读者可以进一步做成socket双方互聊. 以下是功能代码部分: from Tkinter import * import datetime import time root = Tk() root.title(unic

随机推荐