Python3 A*寻路算法实现方式

我就废话不多说了,直接上代码吧!

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

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

# 存储搜索时的地图
test_map = []

#----------- 开放列表和关闭列表的元素类型,parent用来在成功的时候回溯路径 -----------
class Node_Elem:

 def __init__(self, parent, x, y, dist):
  self.parent = parent # 回溯父节点
  self.x = x # x坐标
  self.y = y # y坐标
  self.dist = dist # 从起点到此位置的实际距离

#----------- 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 # 起点x
  self.s_y = s_y # 起点y
  self.e_x = e_x # 终点x
  self.e_y = e_y # 终点y

  self.open = [] # open表
  self.close = [] # close表
  self.path = [] # path表

  # 创建画布
  self.root = root # 画布根节点
  self.width = w # 地图w,默认60
  self.height = h # 地图h,默认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:开始搜索或退出)")
  self.__bindEvents()
  self.new()

 # 按键响应程序
 def __bindEvents(self):

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

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

 # 更改标题
 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):
    # 生成障碍节点,半径为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",
      )
    # 显示起点
    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方法在坐标处绘制文字
       text=u'Start', # 所绘制文字的内容
       fill='black' # 所绘制文字的颜色为灰色
      )
    # 显示终点
    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方法在坐标处绘制文字
       text=u'End', # 所绘制文字的内容
       fill='black' # 所绘制文字的颜色为灰色
      )
    # 生成路径节点,半径为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", # 填充蓝色
       outline="#ffffff", # 轮廓白色
       tags="node",
      )
    # 生成搜索区域,半径为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",
      )

 # 查找路径的入口函数
 def find_path(self):
  # 构建开始节点
  p = Node_Elem(None, self.s_x, self.s_y, 0.0)
  while True:
   # 扩展节点
   self.extend_round(p)
   # 如果open表为空,则不存在路径,返回
   if not self.open:
    return
   # 取F值最小的节点
   idx, p = self.get_best()
   # 到达终点,生成路径,返回
   if self.is_target(p):
    self.make_path(p)
    return
   # 把此节点加入close表,并从open表里删除
   self.close.append(p)
   del self.open[idx]

 # 生成路径
 def make_path(self, p):
  # 从结束点回溯到开始点,开始点的parent == None
  while p:
   self.path.append((p.x, p.y))
   p = p.parent

 # 判断是否为终点
 def is_target(self, i):
  return i.x == self.e_x and i.y == self.e_y

 # 取F值最小的节点
 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 为当前路径长度,H为估计长度
  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))

 # 扩展节点
 def extend_round(self, p):
  # 八个方向移动
  xs = (-1, 0, 1, -1, 1, -1, 0, 1)
  ys = (-1, -1, -1, 0, 0, 1, 1, 1)
  # 上下左右四个方向移动
  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
   # 构造新的节点,计算距离
   node = Node_Elem(p, new_x, new_y, p.dist + self.get_cost(
      p.x, p.y, new_x, new_y))
   # 新节点在关闭列表,则忽略
   if self.node_in_close(node):
    continue
   i = self.node_in_open(node)
   # 新节点在open表
   if i != -1:
    # 当前路径距离更短
    if self.open[i].dist > node.dist:
     # 更新距离
     self.open[i].parent = p
     self.open[i].dist = node.dist
    continue
   # 否则加入open表
   self.open.append(node)

 # 移动距离,直走1.0,斜走1.4
 def get_cost(self, x1, y1, x2, y2):
  if x1 == x2 or y1 == y2:
   return 1.0
  return 1.4

 # 检查节点是否在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

 # 检查节点是否在open表,返回序号
 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] != '#'

 # 搜寻过的位置
 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

# 获取起点坐标
def get_start_XY():
 return get_symbol_XY('S')

# 获取终点坐标
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

# 标记路径位置
def mark_path(l):
 mark_symbol(l, '*')

# 标记已搜索过的位置
def mark_searched(l):
 mark_symbol(l, ' ')

# 标记函数
def mark_symbol(l, s):
 for x, y in l:
  test_map[y][x] = s

# 标记起点和终点
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'

# 将地图字符串转化为表
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
 # 标记已搜索过的位置
 mark_searched(searched)
 # 标记路径位置
 mark_path(path)
 # 标记起点和终点
 mark_start_end(s_x, s_y, e_x, e_y)
 print(u"路径长度:%d" % (len(path)))
 print(u"搜索过的区域:%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*迷宫问题程序
 作者:Gm
 日期:2019-7-08
 语言:Python 3.7
--------------------------------------------------------
 """)
 # 载入地图
 tm_to_test_map()
 # 寻找路径
 find_path()

以上这篇Python3 A*寻路算法实现方式就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 手把手教你python实现SVM算法

    什么是机器学习 (Machine Learning) 机器学习是研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能.它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域. 机器学习的大致分类: 1)分类(模式识别):要求系统依据已知的分类知识对输入的未知模式(该模式的描述)作分析,以确定输入模式的类属,例如手写识别(识别是不是这个数). 2)问题求解:要求对于给定的目标状态,寻找一个将当前状态转换为目标状态的动作序

  • 详解用python实现简单的遗传算法

    今天整理之前写的代码,发现在做数模期间写的用python实现的遗传算法,感觉还是挺有意思的,就拿出来分享一下. 首先遗传算法是一种优化算法,通过模拟基因的优胜劣汰,进行计算(具体的算法思路什么的就不赘述了).大致过程分为初始化编码.个体评价.选择,交叉,变异. 遗传算法介绍 遗传算法是通过模拟大自然中生物进化的历程,来解决问题的.大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的.把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的.当然,只

  • Python3 A*寻路算法实现方式

    我就废话不多说了,直接上代码吧! # -*- coding: utf-8 -*- import math import random import copy import time import sys import tkinter import threading # 地图 tm = [ '############################################################', '#S............................#........

  • python实现A*寻路算法

    A* 算法简介 A* 算法需要维护两个数据结构:OPEN 集和 CLOSED 集.OPEN 集包含所有已搜索到的待检测节点.初始状态,OPEN集仅包含一个元素:开始节点.CLOSED集包含已检测的节点.初始状态,CLOSED集为空.每个节点还包含一个指向父节点的指针,以确定追踪关系. A* 算法会给每个搜索到的节点计算一个G+H 的和值F: F = G + H G:是从开始节点到当前节点的移动量.假设开始节点到相邻节点的移动量为1,该值会随着离开始点越来越远而增大. H:是从当前节点到目标节点的

  • 赫赫大名的A*寻路算法(vb.net版本)

    在网上看到一篇A*寻路算法的译文 http://data.gameres.com/message.asp?TopicID=25439 按此原理写了以下程序 另外补充:1.此算法不是最短路径算法.        2.在实际应用中肯定还需要优化,以适合具体游戏.        3.(vb.net2005测试通过) /Files/bearhunter/6f1e1005-a5a3-4fc9-9bfe-99a615e113ed.rar 本地下载 //

  • Python3通过Luhn算法快速验证信用卡卡号的方法

    本文实例讲述了Python3通过Luhn算法快速验证信用卡卡号的方法.分享给大家供大家参考.具体分析如下: Python3通过Luhn算法快速验证信用卡卡号,python用起来就是爽,很简单的三行代码就可以验证信用卡卡号是否有效 def luhn_check(num): ''' Number - List of reversed digits ''' digits = [int(x) for x in reversed(str(num))] check_sum = sum(digits[::2]

  • js版本A*寻路算法

    说到做游戏,必不可少的需要用到寻路算法,一般游戏里的寻路算法大多数都以A*算法为主,这里也就实现了js里采用a*寻路的程序,在51js和蓝色都开了帖. 程序是以前写的,后来也没有修正或者精简,有冗余之处大家还见谅一下. 当然,这个寻路算法也不是最优化的,像幻宇开发的"交点寻径法"也是个中精品,两者可谓各有千秋,只是如果地图很大的情况下,我们会惊讶于"交点寻径法"的迅速. use A* to find path... /* written by 百晓生 email:j

  • Python2和Python3之间的str处理方式导致乱码的讲解

    Python字符串问题 在arcpy中版本为 python2.x 在QGIS中版本为 python2.x 或者 python3.x python2 和python3 之间的str处理方式经常会导致乱码,故出此文 python3版本 # 将str或字节并始终返回str def to_str(bytes_or_str): if isinstance(bytes_or_str, bytes): value = bytes_or_str.decode('utf-8') else: value = byt

  • 深入理解js A*寻路算法原理与具体实现过程

    本文实例讲述了js A*寻路算法原理与具体实现过程.分享给大家供大家参考,具体如下: 这两天研究了下 A* 寻路算法, 主要学习了这篇文章, 但这篇翻译得不是很好, 我花了很久才看明白文章中的各种指代. 特写此篇博客用来总结, 并写了寻路算法的代码, 觉得有用的同学可以看看. 另外因为图片制作起来比较麻烦, 所以我用的是原文里的图片. 当然寻路算法不止 A* 这一种, 还有递归, 非递归, 广度优先, 深度优先, 使用堆栈等等, 有兴趣的可以研究研究~~ 简易地图 如图所示简易地图, 其中绿色方

  • Python3爬楼梯算法示例

    本文实例讲述了Python3爬楼梯算法.分享给大家供大家参考,具体如下: 假设你正在爬楼梯.需要 n 步你才能到达楼顶. 每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数. 方案一:每一步都是前两步和前一步的和 class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ pre, cur =

  • JS实现的A*寻路算法详解

    本文实例讲述了JS实现的A*寻路算法.分享给大家供大家参考,具体如下: 这两天在做百度前端技术学院的题目,其中有涉及到寻路相关的,于是就找来相关博客进行阅读. 看了Create Chen写的理解A*寻路算法具体过程之后,我很快就理解A*算法的原理.不得不说作者写的很好,通熟易懂,图片也做的很好,可见作者在这上面是花了心思的.如果让我写,我是写不来这么好的. 唯一的不足就是,因为我学的是js,因此最后给我的源码我是用不了的......因此才有自己写一篇的打算,方面学习js人的学习.然而前面的描述我

  • JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例

    本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法.分享给大家供大家参考,具体如下: 原理可参考:https://www.jb51.net/article/152744.htm 完整实例代码如下: <!DOCTYPE html> <html lang="en"> <head> <meta name="viewport" content="width=device-width, initial-s

随机推荐