成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

Python3A*尋路算法的示例分析-創(chuàng)新互聯(lián)

這篇文章主要介紹了Python3 A*尋路算法的示例分析，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供上海網(wǎng)站建設(shè)、上海做網(wǎng)站、上海網(wǎng)站設(shè)計(jì)、上海網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、上海企業(yè)網(wǎng)站模板建站服務(wù)，10多年上海做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

直接上代碼吧！

# -*- coding: utf-8 -*-
import math
import random
import copy
import time
import sys
import tkinter
import threading

# 地圖
tm = [
'############################################################',
'#S............................#............#.....#.........#',
'#..........#..................#......#.....#.....#.........#',
'#..........#..................#......#.....#.....#.........#',
'#..........#..................#......#.....#.....#.........#',
'#..........#.........................#.....#.....#.........#',
'#..........#..................#......#.....#...............#',
'#..#########..................#......#.....#.....#.........#',
'#..#..........................#......#.....#.....#.........#',
'#..#..........................#......#.....#.....#.........#',
'#..############################......#.....#.....#.........#',
'#.............................#......#.....#.....#.........#',
'#.............................#......#...........#.........#',
'#######.##################################################.#',
'#....#........#.................#.............#............#',
'#....#........#........#........#.............#............#',
'#....####.#####........#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........#.............#............#',
'#.........#............#........####.#######.##............#',
'#.........#............#........#....#.......#.............#',
'#.........#............#........#....#.......#.............#',
'#......................#........#....#.......#.............#',
'#.........#............#........##.########..#.............#',
'#.........#............#..................#..########.######',
'#.........#............#..................#...............E#',
'############################################################']

# 存儲(chǔ)搜索時(shí)的地圖
test_map = []


#----------- 開(kāi)放列表和關(guān)閉列表的元素類型，parent用來(lái)在成功的時(shí)候回溯路徑 -----------
class Node_Elem:

 def __init__(self, parent, x, y, dist):
  self.parent = parent # 回溯父節(jié)點(diǎn)
  self.x = x # x坐標(biāo)
  self.y = y # y坐標(biāo)
  self.dist = dist # 從起點(diǎn)到此位置的實(shí)際距離


#----------- A*算法 -----------
class A_Star:
 
 def __init__(self, root, s_x, s_y, e_x, e_y, w=60, h=30):

  self.s_x = s_x # 起點(diǎn)x
  self.s_y = s_y # 起點(diǎn)y
  self.e_x = e_x # 終點(diǎn)x
  self.e_y = e_y # 終點(diǎn)y
  
  self.open = [] # open表
  self.close = [] # close表
  self.path = [] # path表

  # 創(chuàng)建畫(huà)布
  self.root = root # 畫(huà)布根節(jié)點(diǎn)
  self.width = w # 地圖w，默認(rèn)60
  self.height = h # 地圖h，默認(rèn)30
  self.__r = 3 # 半徑
  # Tkinter.Canvas
  self.canvas = tkinter.Canvas(
    root,
    width=self.width * 10 + 100,
    height=self.height * 10 + 100,
    bg="#EBEBEB", # 背景白色 
    xscrollincrement=1,
    yscrollincrement=1
   )
  self.canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH)
  self.title("A*迷宮算法(e:開(kāi)始搜索或退出)")
  self.__bindEvents()
  self.new()

 # 按鍵響應(yīng)程序
 def __bindEvents(self):

  self.root.bind("e", self.quite) # 退出程序

 # 退出程序
 def quite(self, evt):
  self.root.destroy()

 # 更改標(biāo)題
 def title(self, s):
  self.root.title(s)

 # 初始化
 def new(self):

  node = self.canvas.create_oval(100 - self.__r,
       20 - self.__r, 100 + self.__r, 20 + self.__r,
       fill="#ff0000",
       outline="#ffffff",
       tags="node",
      )
  self.canvas.create_text(130, 20,
       text=u'Wall',
       fill='black'
      )
  node = self.canvas.create_oval(200 - self.__r,
       20 - self.__r, 200 + self.__r, 20 + self.__r,
       fill="#00ff00",
       outline="#ffffff",
       tags="node",
      )
  self.canvas.create_text(230, 20,
       text=u'Path',
       fill='black'
      )
  node = self.canvas.create_oval(300 - self.__r,
       20 - self.__r, 300 + self.__r, 20 + self.__r,
       fill="#AAAAAA",
       outline="#ffffff",
       tags="node",
      )
  self.canvas.create_text(330, 20,
       text=u'Searched',
       fill='black'
      )

  for i in range(self.width):
   for j in range(self.height):
    # 生成障礙節(jié)點(diǎn)，半徑為self.__r
    if test_map[j][i] == '#':
     node = self.canvas.create_oval(i * 10 + 50 - self.__r,
       j * 10 + 50 - self.__r, i * 10 + 50 + self.__r, j * 10 + 50 + self.__r,
       fill="#ff0000", # 填充紅色
       outline="#ffffff", # 輪廓白色
       tags="node",
      )
    # 顯示起點(diǎn)
    if test_map[j][i] == 'S':
     node = self.canvas.create_oval(i * 10 + 50 - self.__r,
       j * 10 + 50 - self.__r, i * 10 + 50 + self.__r, j * 10 + 50 + self.__r,
       fill="#00ff00", # 填充綠色
       outline="#ffffff", # 輪廓白色
       tags="node",
      )
     self.canvas.create_text(i * 10 + 50, j * 10 + 50 - 20, # 使用create_text方法在坐標(biāo)處繪制文字 
       text=u'Start', # 所繪制文字的內(nèi)容 
       fill='black' # 所繪制文字的顏色為灰色
      )
    # 顯示終點(diǎn)
    if test_map[j][i] == 'E':
     node = self.canvas.create_oval(i * 10 + 50 - self.__r,
       j * 10 + 50 - self.__r, i * 10 + 50 + self.__r, j * 10 + 50 + self.__r,
       fill="#00ff00", # 填充綠色
       outline="#ffffff", # 輪廓白色
       tags="node",
      )
     self.canvas.create_text(i * 10 + 50, j * 10 + 50 + 20, # 使用create_text方法在坐標(biāo)處繪制文字 
       text=u'End', # 所繪制文字的內(nèi)容 
       fill='black' # 所繪制文字的顏色為灰色
      )
    # 生成路徑節(jié)點(diǎn)，半徑為self.__r
    if test_map[j][i] == '*':
     node = self.canvas.create_oval(i * 10 + 50 - self.__r,
       j * 10 + 50 - self.__r, i * 10 + 50 + self.__r, j * 10 + 50 + self.__r,
       fill="#0000ff", # 填充藍(lán)色
       outline="#ffffff", # 輪廓白色
       tags="node",
      )
    # 生成搜索區(qū)域，半徑為self.__r
    if test_map[j][i] == ' ':
     node = self.canvas.create_oval(i * 10 + 50 - self.__r,
       j * 10 + 50 - self.__r, i * 10 + 50 + self.__r, j * 10 + 50 + self.__r,
       fill="#AAAAAA", # 填充白色
       outline="#ffffff", # 輪廓白色
       tags="node",
      )
  
 # 查找路徑的入口函數(shù)
 def find_path(self):
  # 構(gòu)建開(kāi)始節(jié)點(diǎn)
  p = Node_Elem(None, self.s_x, self.s_y, 0.0)
  while True:
   # 擴(kuò)展節(jié)點(diǎn)
   self.extend_round(p)
   # 如果open表為空，則不存在路徑，返回
   if not self.open:
    return
   # 取F值最小的節(jié)點(diǎn)
   idx, p = self.get_best()
   # 到達(dá)終點(diǎn)，生成路徑，返回
   if self.is_target(p):
    self.make_path(p)
    return
   # 把此節(jié)點(diǎn)加入close表，并從open表里刪除
   self.close.append(p)
   del self.open[idx]

 # 生成路徑 
 def make_path(self, p):
  # 從結(jié)束點(diǎn)回溯到開(kāi)始點(diǎn)，開(kāi)始點(diǎn)的parent == None
  while p:
   self.path.append((p.x, p.y))
   p = p.parent

 # 判斷是否為終點(diǎn)
 def is_target(self, i):
  return i.x == self.e_x and i.y == self.e_y

 # 取F值最小的節(jié)點(diǎn)
 def get_best(self):
  best = None
  bv = 10000000 # MAX值
  bi = -1
  for idx, i in enumerate(self.open):
   value = self.get_dist(i)
   if value < bv:
    best = i
    bv = value
    bi = idx
  return bi, best
  
 # 求距離
 def get_dist(self, i):
  # F = G + H
  # G 為當(dāng)前路徑長(zhǎng)度，H為估計(jì)長(zhǎng)度
  return i.dist + math.sqrt((self.e_x - i.x) * (self.e_x - i.x)) + math.sqrt((self.e_y - i.y) * (self.e_y - i.y))

 # 擴(kuò)展節(jié)點(diǎn)
 def extend_round(self, p):
  # 八個(gè)方向移動(dòng)
  xs = (-1, 0, 1, -1, 1, -1, 0, 1)
  ys = (-1, -1, -1, 0, 0, 1, 1, 1)
  # 上下左右四個(gè)方向移動(dòng)
  xs = (0, -1, 1, 0)
  ys = (-1, 0, 0, 1)
  for x, y in zip(xs, ys):
   new_x, new_y = x + p.x, y + p.y
   # 檢查位置是否合法
   if not self.is_valid_coord(new_x, new_y):
    continue
   # 構(gòu)造新的節(jié)點(diǎn)，計(jì)算距離
   node = Node_Elem(p, new_x, new_y, p.dist + self.get_cost(
      p.x, p.y, new_x, new_y))
   # 新節(jié)點(diǎn)在關(guān)閉列表，則忽略
   if self.node_in_close(node):
    continue
   i = self.node_in_open(node)
   # 新節(jié)點(diǎn)在open表
   if i != -1:
    # 當(dāng)前路徑距離更短
    if self.open[i].dist > node.dist:
     # 更新距離
     self.open[i].parent = p
     self.open[i].dist = node.dist
    continue
   # 否則加入open表
   self.open.append(node)

 # 移動(dòng)距離，直走1.0，斜走1.4
 def get_cost(self, x1, y1, x2, y2):
  if x1 == x2 or y1 == y2:
   return 1.0
  return 1.4
 
 # 檢查節(jié)點(diǎn)是否在close表
 def node_in_close(self, node):
  for i in self.close:
   if node.x == i.x and node.y == i.y:
    return True
  return False
 
 # 檢查節(jié)點(diǎn)是否在open表，返回序號(hào) 
 def node_in_open(self, node):
  for i, n in enumerate(self.open):
   if node.x == n.x and node.y == n.y:
    return i
  return -1

 # 判斷位置是否合法，超出邊界或者為阻礙 
 def is_valid_coord(self, x, y):
  if x < 0 or x >= self.width or y < 0 or y >= self.height:
   return False
  return test_map[y][x] != '#'

 # 搜尋過(guò)的位置
 def get_searched(self):
  l = []
  for i in self.open:
   l.append((i.x, i.y))
  for i in self.close:
   l.append((i.x, i.y))
  return l


# 獲取起點(diǎn)坐標(biāo)
def get_start_XY():
 return get_symbol_XY('S')


# 獲取終點(diǎn)坐標(biāo)
def get_end_XY():
 return get_symbol_XY('E')


# 查找特定元素
def get_symbol_XY(s):
 for y, line in enumerate(test_map):
  try:
   x = line.index(s)
  except:
   continue
  else:
   break
 return x, y

  
# 標(biāo)記路徑位置 
def mark_path(l):
 mark_symbol(l, '*')


# 標(biāo)記已搜索過(guò)的位置 
def mark_searched(l):
 mark_symbol(l, ' ')


# 標(biāo)記函數(shù)
def mark_symbol(l, s):
 for x, y in l:
  test_map[y][x] = s

  
# 標(biāo)記起點(diǎn)和終點(diǎn)
def mark_start_end(s_x, s_y, e_x, e_y):
 test_map[s_y][s_x] = 'S'
 test_map[e_y][e_x] = 'E'


# 將地圖字符串轉(zhuǎn)化為表
def tm_to_test_map():
 for line in tm:
  test_map.append(list(line))

  
# 尋找路徑  
def find_path():
 s_x, s_y = get_start_XY()
 e_x, e_y = get_end_XY()
 # A*算法
 a_star = A_Star(tkinter.Tk(), s_x, s_y, e_x, e_y)
 a_star.root.mainloop()
 a_star.find_path()
 searched = a_star.get_searched()
 path = a_star.path
 # 標(biāo)記已搜索過(guò)的位置
 mark_searched(searched)
 # 標(biāo)記路徑位置 
 mark_path(path)
 # 標(biāo)記起點(diǎn)和終點(diǎn)
 mark_start_end(s_x, s_y, e_x, e_y)
 print(u"路徑長(zhǎng)度:%d" % (len(path)))
 print(u"搜索過(guò)的區(qū)域:%d" % (len(searched)))
 a_star = A_Star(tkinter.Tk(), s_x, s_y, e_x, e_y)
 a_star.root.mainloop()
 
#----------- 程序的入口處 -----------

    
if __name__ == '__main__':

 print (u""" 
--------------------------------------------------------
 程序：A*迷宮問(wèn)題程序 
 作者：Gm
 日期：2019-7-08
 語(yǔ)言：Python 3.7 
-------------------------------------------------------- 
 """)
 # 載入地圖
 tm_to_test_map()
 # 尋找路徑
 find_path()

Python3 A*尋路算法的示例分析

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Python3 A*尋路算法的示例分析”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!

本文題目：Python3A*尋路算法的示例分析-創(chuàng)新互聯(lián)
分享地址：http://jinyejixie.com/article48/dedpep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、虛擬主機(jī)、響應(yīng)式網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)
大关县| 彩票| 秦安县| 朔州市| 绥江县| 略阳县| 霸州市| 兴仁县| 璧山县| 滨州市| 平原县| 越西县| 江陵县| 日土县| 延津县| 东兰县| 德化县| 汉寿县| 阜平县| 明水县| 溆浦县| 舞钢市| 南木林县| 怀宁县| 昭平县| 紫阳县| 拉孜县| 长白| 疏勒县| 普格县| 佛山市| 广宁县| 和平县| 靖江市| 珲春市| 珲春市| 永济市| 合山市| 潞城市| 江油市| 冀州市|