精华内容
下载资源
问答
  • 分享一下A星算法及A星优化算法源码,提供大家学习使用!
  • 动态衡量式A星算法及拐角优化的matlab文件,内部包含两个matlab文件,A_ROAD_3 为完整的动态衡量式A星算法文件,A_ROAD_4是进行拐角优化后的文件,详情请见博文----详细介绍用MATLAB实现基于A*算法的路径规划(附...
  • 本源代码借助标准C++ STL中的vector,list和heap等已封装的数据结构,优化A星算法搜索地图、检索开始列表过程,减小了程序的时间和空间花费。经检验,检索20000*20000的随机障碍物地图时,程序在规划路径部分的平均...
  • 在地图中选好起始点,然后调用A星算法规划出最优路线,此Demo对A*算法中一些细节进行了相应的优化大大提升了检索的效率
  • python 实现A星算法

    千次阅读 2019-12-23 19:09:34
    python A星算法效果图 效果图 (程序在cmd中打印所有有点闪屏!!!)

    效果图

    (程序在cmd中打印所以有点闪屏!!!)
    A星算法效果

    上代码

    # -*- coding: utf-8 -*-
    # @Date    : 2019-12-23 20:53:33
    # @Author  : Flying Hu (1152598046@qq.com)
    # @Link    : http://www.flyinghu.cn
    # @name    : A星算法实现
    # @Version : 0.1
    
    
    import os
    import math
    from random import randint
    import time
    
    
    # 定义全局变量
    gz_char = '█'  # 定义默认格子字符
    fruit_char = '★'  # 定义果实显示字符
    self_char = '●'  # 定义自身显示字符
    wall_char = '◆'  # 定义墙壁显示字符
    
    # 全程使用上往下方向为x正方向  (二维列表行索引增加方向)
    # 全程使用左往右方向为y正方向  (二维列表列索引增加方向)
    
    
    class Map2D(object):
        '''2D地图类'''
    
        def __init__(self, width=20, height=20):
            '''初始化
            Args:
                width   地图宽
                height   地图高
            '''
            self.width = width
            self.height = height
            self.char = gz_char  # 地图默认字符
            # 生成地图
            self.map = [[self.char for col in range(
                self.width)] for row in range(self.height)]
            # 生成地图周围墙
            self.wall = [[i, j] for j in [-1, self.width] for i in range(self.height)] + [
                [j, i] for j in [-1, self.height] for i in range(-1, self.width + 1)]
    
        def __getitem__(self, item):
            '''以键方式取值'''
            return self.map[item]
    
        def __setitem__(self, key, value):
            '''以键方式存值'''
            self.map[key] = value
    
        def show(self):
            '''在控制台打印当前地图'''
            for row in self.map:
                for c in row:
                    # 使用控制台颜色控制, 区分
                    if c == self_char:
                        print('\033[1;35;44m' + c + '\033[0m', end='')
                    elif c == wall_char:
                        print('\033[0;36;41m' + c + '\033[0m', end='')
                    elif c == fruit_char:
                        print('\033[1;33;40m' + c + '\033[0m', end='')
                    else:
                        print('\033[0;37;41m' + c + '\033[0m', end='')
                print()
            # 重置地图, 重置后就不会留下运动轨迹
            # self.reload()
    
        def reload(self):
            '''重置地图'''
            self.map = [[self.char for col in range(
                self.width)] for row in range(self.height)]
    
    
    class AStar(object):
        '''实现A星算法'''
    
        class Node(object):
            '''节点类'''
    
            def __init__(self, x, y, parent_node=None):
                self.x = x
                self.y = y
                self.parent = parent_node  # 父节点
                # F = G + H
                # G = 从起点 A 移动到指定方格的移动代价
                # H = 从指定的方格移动到终点 B 的估算成本。试探法。 这里使用 Manhattan 方法估算H
                self.G = 0
                self.H = 0
    
        def __init__(self, map2D):
            '''初始化'''
            self.map = map2D
    
        def MinF(self):
            '''从open_list中取出F最小的节点
            Returns:
                minF    返回open_list中F值最小的节点
            '''
            # 先假设第一个为最小, 然后循环挑选出F最小的节点
            minF = self.open_list[0]
            for node in self.open_list:
                if (node.G + node.H) <= (minF.G + minF.H):
                    minF = node
            return minF
    
        def in_close_list(self, x, y):
            '''判断坐标是否在close_list中
            Args:
                x   x坐标
                y   y坐标
            Return:
                node    如果坐标在close_list中, 返回该节点, 反之返回False
            '''
            for node in self.close_list:
                if node.x == x and node.y == y:
                    return node
            return False
    
        def in_open_list(self, x, y):
            '''判断坐标是否在open_list中
            Args:
                x   x坐标
                y   y坐标
            Return:
                node    如果坐标在open_list中, 返回该节点, 反之返回False
            '''
            for node in self.close_list:
                if node.x == x and node.y == y:
                    return node
            return False
    
        def search(self, node):
            '''搜索周围路径
            Args:
                node 搜索节点
            '''
            # 判断改节点是否为障碍物(障碍物或者墙壁)
            if [node.x, node.y] in self.obstacles:
                # 如果为障碍物则忽略该路径
                return
            # 判断是否在close_list中
            if self.in_close_list(node.x, node.y):
                # 如果已经在close_list中则忽略该节点
                return
            # 计算G和H
            node.G = node.parent.G + 10
            node.H = abs(self.target_node.x - node.x) + \
                abs(self.target_node.y - node.y) * 10
            # 判断是否在open_list中
            tmp = self.in_close_list(node.x, node.y)
            if tmp:
                # 在open_list中
                # 比较当前F和open_list中F
                if (node.G + node.H) < (tmp.G + tmp.H):
                    # 如果判断该路径F值是否比open_list中存在的相同坐标的F值更小
                    tmp = node
            else:
                # 不在open_list中, 向open_list中添加
                self.open_list.append(node)
    
        def start(self, current_position, target_positiion, obstacles):
            '''计算A星最优路径
            Args:
                current_position    当前位置坐标
                target_positiion    目标位置坐标
                obstacles           障碍物坐标列表
            Returns:
                path_list           如果存在最优路径返回A星最优路径, 反正返回None
            '''
            # 目标节点
            self.target_node = AStar.Node(*target_positiion)
            # 当前节点
            self.current_node = AStar.Node(*current_position)
            # 开启表, 添加当前节点到open_list中
            self.open_list = [self.current_node]
            # 关闭表
            self.close_list = []
            # 障碍物坐标集  (真实障碍物 + 墙壁)
            self.obstacles = obstacles + self.map.wall
            # 开启A星计算循环
            while True:
                # 判断是否到达终点, 判断目标节点坐标是否在close_list中
                tmp = self.in_close_list(self.target_node.x, self.target_node.y)
                if tmp:
                    # 返回路线
                    path_list = [[tmp.x, tmp.y]]
                    # 逆推路线
                    while tmp.parent:
                        tmp = tmp.parent
                        path_list.append([tmp.x, tmp.y])
                    # 反转列表
                    path_list.reverse()
                    return path_list
                if not self.open_list:
                    # 如果open_list为空, 表示无路可走
                    return None
                # 从open_list中选出F最小路径节点
                minF = self.MinF()
                # 将当前选出节点添加到close_list中, 并从open_list中移除
                self.close_list.append(minF)
                self.open_list.remove(minF)
                # 搜索路径并将当前节点作为父节点  根据固定顺序搜索  (固定就行, 顺序任意)
                self.search(AStar.Node(minF.x - 1, minF.y, minF))
                self.search(AStar.Node(minF.x, minF.y - 1, minF))
                self.search(AStar.Node(minF.x + 1, minF.y, minF))
                self.search(AStar.Node(minF.x, minF.y + 1, minF))
                # 存在计算时长比较久的清空, 打印提示信息
                print('\r叼毛, 正在规划路径...', end='')
    
        def sub_start(self, current_position, target_positiion, obstacles, num=20):
            '''限定次数判断是否有路可走'''
            # 目标节点
            self.target_node = AStar.Node(*target_positiion)
            # 当前节点
            self.current_node = AStar.Node(*current_position)
            # 开启表, 添加当前节点到open_list中
            self.open_list = [self.current_node]
            # 关闭表
            self.close_list = []
            # 障碍物坐标集  (真实障碍物 + 墙壁)
            self.obstacles = obstacles + self.map.wall
            # 开启A星计算循环
            for i in range(num):
                # 判断是否到达终点, 判断目标节点坐标是否在close_list中
                tmp = self.in_close_list(self.target_node.x, self.target_node.y)
                if tmp:
                    # 返回路线
                    path_list = [[tmp.x, tmp.y]]
                    # 逆推路线
                    while tmp.parent:
                        tmp = tmp.parent
                        path_list.append([tmp.x, tmp.y])
                    # 反转列表
                    path_list.reverse()
                    return True
                if not self.open_list:
                    # 如果open_list为空, 表示无路可走
                    return False
                # 从open_list中选出F最小路径节点
                minF = self.MinF()
                # 将当前选出节点添加到close_list中, 并从open_list中移除
                self.close_list.append(minF)
                self.open_list.remove(minF)
                # 搜索路径并将当前节点作为父节点  根据固定顺序搜索  (固定就行, 顺序任意)
                self.search(AStar.Node(minF.x - 1, minF.y, minF))
                self.search(AStar.Node(minF.x, minF.y - 1, minF))
                self.search(AStar.Node(minF.x + 1, minF.y, minF))
                self.search(AStar.Node(minF.x, minF.y + 1, minF))
            else:
                return True
    
    
    class Game(object):
        '''游戏类'''
    
        def __init__(self, map2D, obs_num=None):
            '''初始化
            Args:
                map2D   2D地图
                obs_num 初始化障碍物数量
            '''
            self.map = map2D
            self.height = self.map.height
            self.width = self.map.width
            # 随机一个初始化运动方向
            self.direction = randint(0, 3)
            # 根据地图大小计算障碍物数量
            # self.obs_num = int(math.sqrt(self.height * self.width))
            self.obs_num = obs_num if obs_num else int(
                math.sqrt(self.height * self.width))
            # 初始化起点
            self.current = [
                randint(int(1/4 * (self.height - 1)),
                        int(3/4 * (self.height - 1))),
                randint(int(1/4 * (self.width - 1)),
                        int(3/4 * (self.width - 1)))
            ]
            # 生成果实目标
            self.gen_fruit()
            # 生成障碍物
            self.gen_obs()
    
        def gen_fruit(self):
            '''生成果实'''
            while True:
                # 随机生成果实坐标
                self.fruit = [randint(0, self.height - 1),
                              randint(0, self.width - 1)]
                # 避免果实和起点坐标重合
                if self.fruit != self.current:
                    break
    
        def gen_obs(self):
            '''生成障碍物'''
            self.obs_list = []
            for i in range(self.obs_num):
                while True:
                    tmp = [randint(0, self.height - 1), randint(0, self.width - 1)]
                    # 避免障碍物和起点或者果实重合
                    if tmp != self.current and tmp != self.fruit:
                        self.obs_list.append(tmp)
                        break
    
        def move(self):
            '''根据移动方向移动
            0, 1, 2, 3分别对应上, 左, 下, 右
            '''
            if self.direction == 0:
                self.current = [self.current[0] - 1, self.current[1]]
            elif self.direction == 1:
                self.current = [self.current[0], self.current[1] - 1]
            elif self.direction == 2:
                self.current = [self.current[0] + 1, self.current[1]]
            else:
                self.current = [self.current[0], self.current[1] + 1]
    
        def cls(self):
            '''清空控制台输出'''
            os.system('cls')
    
        def load(self):
            '''加载果实和障碍物'''
            # 加载障碍物
            for row, col in self.obs_list:
                self.map[row][col] = wall_char
            # 加载果实和当前点
            row, col = self.current
            self.map[row][col] = self_char
            row, col = self.fruit
            self.map[row][col] = fruit_char
    
        def start(self):
            '''开始游戏循环'''
            # 开启A星
            g = self.a_star()
            # 进入循环
            while True:
                # 清空控制台输出
                self.cls()
                # 加载
                self.load()
                # 打印显示
                self.map.show()
                # 判断是否吃到果实
                if self.current == self.fruit:
                    # 吃到果实
                    # 重置地图
                    self.map.reload()
                    # 重新生成果实, 重新生成障碍物
                    self.gen_fruit()
                    self.gen_obs()
                    self.map.reload()
                if next(g) is False:
                    # 表示无路可走
                    # 重置地图
                    self.map.reload()
                    continue
                # 移动
                self.move()
                # 控制移动速度
                time.sleep(0.3)
    
        def a_star(self):
            '''接入A*算法寻路
            使用python生成器方式实现在游戏循环中一次一次改变方向
            '''
            # 创建对象
            a = AStar(self.map)
            while True:
                # 提前加载显示地图, 提前显示可以人工判断是否真的无路可走
                # 清空控制台输出
                self.cls()
                # 加载
                self.load()
                # 打印显示
                self.map.show()
                # 先反向判断, 在限定次数中是否得出无路可走, 添加改策略一定程度减少计算时间很长的正向计算
                if a.sub_start(self.fruit, self.current, self.obs_list, 30) is False:
                    # 表示无路可走
                    input('无路可走, 回车刷新地图')
                    self.map.reload()
                    self.gen_fruit()
                    self.gen_obs()
                    # 返回无路可走信号
                    yield False
                    continue
                path_list = a.start(self.current, self.fruit, self.obs_list)
                if not path_list:
                    # 表示无路可走
                    # 提前加载显示地图, 提前显示可以人工判断是否真的无路可走
                    # 清空控制台输出
                    # self.cls()
                    # # 加载
                    # self.load()
                    # # 打印显示
                    # self.map.show()
                    input('无路可走, 回车刷新地图')
                    self.map.reload()
                    self.gen_fruit()
                    self.gen_obs()
                    # 返回无路可走信号
                    yield False
                    continue
                # 遍历启动后路径, 对比得出行走方向
                for path in path_list[1:]:
                    if path[0] > self.current[0]:
                        self.direction = 2
                    elif path[0] < self.current[0]:
                        self.direction = 0
                    elif path[1] > self.current[1]:
                        self.direction = 3
                    else:
                        self.direction = 1
                    yield
    
    
    if __name__ == "__main__":
        # 初始化控制台大小
        os.system("mode con cols=80 lines=80")
        # 创建地图
        map2D = Map2D(width=20, height=20)
        # 新建游戏, 指定障碍物
        game = Game(map2D, 150)
        # 开启游戏
        game.start()
    

    源码下载地址

    点击下载源码–>https://download.csdn.net/download/flyinghu123/12047767

    程序下载地址

    A星.exe–>https://download.csdn.net/download/flyinghu123/12047636

    展开全文
  • A星寻路算法

    2012-03-11 23:57:20
    最常见的A星寻路算法,包括常见处理<部分数据算法任然可以优化处理>
  • python3.6实现的A星算法

    万次阅读 多人点赞 2018-06-20 22:28:40
    A星算法原理: 原理我就不再赘述,可以参考这篇博客https://blog.csdn.net/hitwhylz/article/details/23089415 最近用js写了一遍,用的同样的算法,需要js代码的看这里:...

    A星算法原理:

        原理我就不再赘述,可以参考这篇博客https://blog.csdn.net/hitwhylz/article/details/23089415

        最近用js写了一遍,用的同样的算法,需要js代码的看这里:https://blog.csdn.net/qq_39687901/article/details/85697127

    代码实现:

        首先添加两个通用类Array2D和Point:

    class Array2D:
        """
            说明:
                1.构造方法需要两个参数,即二维数组的宽和高
                2.成员变量w和h是二维数组的宽和高
                3.使用:‘对象[x][y]’可以直接取到相应的值
                4.数组的默认值都是0
        """
        def __init__(self,w,h):
            self.w=w
            self.h=h
            self.data=[]
            self.data=[[0 for y in range(h)] for x in range(w)]
    
    
        def showArray2D(self):
            for y in range(self.h):
                for x in range(self.w):
                    print(self.data[x][y],end=' ')
                print("")
    
        def __getitem__(self, item):
            return self.data[item]

     

    class Point:
        """
        表示一个点
        """
        def __init__(self,x,y):
            self.x=x;self.y=y
    
        def __eq__(self, other):
            if self.x==other.x and self.y==other.y:
                return True
            return False
        def __str__(self):
            return "x:"+str(self.x)+",y:"+str(self.y)

     

        Array2D是为了简化二维数组的创建,Point是为了表示一个点,并且重载等号运算符,可以判断两个Point坐标是否相等.

     

        AStar类:

        

    
    class AStar:
        """
        AStar算法的Python3.x实现
        """
    
        class Node:  # 描述AStar算法中的节点数据
            def __init__(self, point, endPoint, g=0):
                self.point = point  # 自己的坐标
                self.father = None  # 父节点
                self.g = g  # g值,g值在用到的时候会重新算
                self.h = (abs(endPoint.x - point.x) + abs(endPoint.y - point.y)) * 10  # 计算h值
    
        def __init__(self, map2d, startPoint, endPoint, passTag=0):
            """
            构造AStar算法的启动条件
            :param map2d: Array2D类型的寻路数组
            :param startPoint: Point或二元组类型的寻路起点
            :param endPoint: Point或二元组类型的寻路终点
            :param passTag: int类型的可行走标记(若地图数据!=passTag即为障碍)
            """
            # 开启表
            self.openList = []
            # 关闭表
            self.closeList = []
            # 寻路地图
            self.map2d = map2d
            # 起点终点
            if isinstance(startPoint, Point) and isinstance(endPoint, Point):
                self.startPoint = startPoint
                self.endPoint = endPoint
            else:
                self.startPoint = Point(*startPoint)
                self.endPoint = Point(*endPoint)
    
            # 可行走标记
            self.passTag = passTag
    
        def getMinNode(self):
            """
            获得openlist中F值最小的节点
            :return: Node
            """
            currentNode = self.openList[0]
            for node in self.openList:
                if node.g + node.h < currentNode.g + currentNode.h:
                    currentNode = node
            return currentNode
    
        def pointInCloseList(self, point):
            for node in self.closeList:
                if node.point == point:
                    return True
            return False
    
        def pointInOpenList(self, point):
            for node in self.openList:
                if node.point == point:
                    return node
            return None
    
        def endPointInCloseList(self):
            for node in self.openList:
                if node.point == self.endPoint:
                    return node
            return None
    
        def searchNear(self, minF, offsetX, offsetY):
            """
            搜索节点周围的点
            :param minF:F值最小的节点
            :param offsetX:坐标偏移量
            :param offsetY:
            :return:
            """
            # 越界检测
            if minF.point.x + offsetX < 0 or minF.point.x + offsetX > self.map2d.w - 1 or minF.point.y + offsetY < 0 or minF.point.y + offsetY > self.map2d.h - 1:
                return
            # 如果是障碍,就忽略
            if self.map2d[minF.point.x + offsetX][minF.point.y + offsetY] != self.passTag:
                return
            # 如果在关闭表中,就忽略
            currentPoint = Point(minF.point.x + offsetX, minF.point.y + offsetY)
            if self.pointInCloseList(currentPoint):
                return
            # 设置单位花费
            if offsetX == 0 or offsetY == 0:
                step = 10
            else:
                step = 14
            # 如果不再openList中,就把它加入openlist
            currentNode = self.pointInOpenList(currentPoint)
            if not currentNode:
                currentNode = AStar.Node(currentPoint, self.endPoint, g=minF.g + step)
                currentNode.father = minF
                self.openList.append(currentNode)
                return
            # 如果在openList中,判断minF到当前点的G是否更小
            if minF.g + step < currentNode.g:  # 如果更小,就重新计算g值,并且改变father
                currentNode.g = minF.g + step
                currentNode.father = minF
    
        def start(self):
            """
            开始寻路
            :return: None或Point列表(路径)
            """
            # 判断寻路终点是否是障碍
            if self.map2d[self.endPoint.x][self.endPoint.y] != self.passTag:
                return None
    
            # 1.将起点放入开启列表
            startNode = AStar.Node(self.startPoint, self.endPoint)
            self.openList.append(startNode)
            # 2.主循环逻辑
            while True:
                # 找到F值最小的点
                minF = self.getMinNode()
                # 把这个点加入closeList中,并且在openList中删除它
                self.closeList.append(minF)
                self.openList.remove(minF)
                # 判断这个节点的上下左右节点
                self.searchNear(minF, 0, -1)
                self.searchNear(minF, 0, 1)
                self.searchNear(minF, -1, 0)
                self.searchNear(minF, 1, 0)
                # 判断是否终止
                point = self.endPointInCloseList()
                if point:  # 如果终点在关闭表中,就返回结果
                    # print("关闭表中")
                    cPoint = point
                    pathList = []
                    while True:
                        if cPoint.father:
                            pathList.append(cPoint.point)
                            cPoint = cPoint.father
                        else:
                            # print(pathList)
                            # print(list(reversed(pathList)))
                            # print(pathList.reverse())
                            return list(reversed(pathList))
                if len(self.openList) == 0:
                    return None
    

     

        最后,进行代码测试:

        

     

    if __name__ == '__main__':
        #创建一个10*10的地图
        map2d=Array2D(10,10)
        #设置障碍
        map2d[4][0]= 1
        map2d[4][1] = 1
        map2d[4][2] = 1
        map2d[4][3] = 1
        map2d[4][4] = 1
        map2d[4][5] = 1
        map2d[4][6] = 1
        #显示地图当前样子
        map2d.showArray2D()
        #创建AStar对象,并设置起点为0,0终点为9,0
        aStar=AStar(map2d,Point(0,0),Point(9,0))
        #开始寻路
        pathList=aStar.start()
        #遍历路径点,在map2d上以'8'显示
        for point in pathList:
            map2d[point.x][point.y]=8
            # print(point)
        print("----------------------")
        #再次显示地图
        map2d.showArray2D()

     

    运行效果:

    最近用这个A星算法在游戏里实际应用上了:

    https://blog.csdn.net/qq_39687901/article/details/88554716

     

     

        

    展开全文
  •   本篇实现的A星算法是基于贪婪优先算法实现的,由于贪婪优先算法得到的是次优路径,因此我们增加一个当前节点到起始节点的一个路径开销分量来提升路径的质量,筛选最优路径。具体实现如下: 节点类的编写   ...

      本篇实现的A星算法是基于贪婪优先算法实现的,由于贪婪优先算法得到的是次优路径,因此我们增加一个当前节点到起始节点的一个路径开销分量来提升路径的质量,筛选最优路径。具体实现如下:

    节点类的编写

      节点主要用来存储当前节点在地图中的位置信息,如:行号,列号、父节点、到起始节点的路径开销量g,到目标节点的路径开销量h,总的开销量;并包含计算g和h的方法;具体实现代码如下:

    /// <summary>
    /// 节点类
    /// </summary>
    public class ANode : System.IComparable
    {
        /// <summary>
        /// 行
        /// </summary>
        public int Row { get; set; }
        /// <summary>
        /// 列
        /// </summary>
        public int Col { get; set; }
    
        /// <summary>
        /// 父节点
        /// </summary>
        public ANode parent = null;
        /// <summary>
        /// 相邻节点
        /// </summary>
        public List<ANode> adjacent = new List<ANode>();
        /// <summary>
        /// 曼哈顿距离
        /// </summary>
        public int h = 0;
    
        public int g = 0;
    
        public int f = 0;
    
        public void H(ANode endNode)
        {
            h = Mathf.Abs(endNode.Row - Row) + Mathf.Abs(endNode.Col - Col);
    
            f = g + h;
        }
    
        /// <summary>
        /// 清除
        /// </summary>
        public void Clear()
        {
            parent = null;
            h = 0;
            g = 0;
            f = 0;
        }
    
        public int CompareTo(object obj)
        {
            ANode node = obj as ANode;
    
            if (f - node.f < 0)
                return -1;
            else if (f - node.f == 0)
                return 0;
            else
                return 1;
        }
    }
    

    地图存储

      地图存储与贪婪算法中的思路一样,代码逻辑一样,只是把节点变量换一下即可,这里不在描述,代码大家自行实现。

    寻路算法实现

      寻路算法与贪婪优先算法的实现相比只是增加了一个与起点的开销分量计算,然后根据f值来判断最优路径,具体实现代码如下:

    public class AStarAlgorithm
    {
        private ANode startNode;
        private ANode destNode;
    
        private List<ANode> openSet = new List<ANode>();
        private List<ANode> closedSet = new List<ANode>();
    
        private AMap map;
    
        /// <summary>
        /// 初始化地图
        /// </summary>
        /// <param name="map"></param>
        public AStarAlgorithm(AMap map)
        {
            this.map = map;
        }
    
        /// <summary>
        /// 查找开放式集合中H值最小的节点
        /// </summary>
        /// <returns></returns>
        private ANode FindLowest()
        {
            openSet.Sort();
            return openSet[0];
        }
    
        /// <summary>
        /// 将节点的相邻节点添加到开放集合中
        /// </summary>
        /// <param name="node"></param>
        private void AddAdjacent(ANode node)
        {
            for (int i = 0; i < node.adjacent.Count; i++)
            {
                if (closedSet.Contains(node.adjacent[i]))
                    continue;
                int newG = node.g + Mathf.Abs(node.Row - node.adjacent[i].Row) + Mathf.Abs(node.Col - node.adjacent[i].Col);
                    
                if(newG < node.adjacent[i].g || !openSet.Contains(node.adjacent[i]))
                {
                    node.adjacent[i].parent = node;
                    node.adjacent[i].g = newG;
                    node.adjacent[i].H(destNode);
                    if (!openSet.Contains(node.adjacent[i]))
                        openSet.Add(node.adjacent[i]);
                }
            }
        }
    
        /// <summary>
        /// 更新地图
        /// </summary>
        /// <param name="map"></param>
        public void UpdateMap(AMap map)
        {
            this.map = map;
        }
    
        public void Start(ANode startNode, ANode endNode)
        {
            openSet.Clear();
            closedSet.Clear();
    
            openSet.Add(startNode);
            destNode = endNode;
            this.startNode = startNode;
    
            for (int i = 0; i < map.aNodes.Length; i++)
            {
                map.aNodes[i].Clear();
            }
        }
    
        public Stack<ANode> Find()
        {
            Stack<ANode> path = new Stack<ANode>();
    
            ANode currNode = openSet[0];
    
            while (currNode != destNode)
            {              
                if (openSet.Count == 0)
                    break;
    
                currNode = FindLowest();
                openSet.Remove(currNode);
                closedSet.Add(currNode);
    
                AddAdjacent(currNode);
            }
    
            if (currNode == destNode)
            {
                ANode node = destNode;
                while (node != null)
                {
                    path.Push(node);
                    node = node.parent;
                }
            }
            else
                return null;
    
            return path;
        }
    }
    

    对于节点类的优化可以继承贪婪优先算法的节点类,这样便于维护修改。

    Unity实现效果如下

    [https://github.com/FredLyu/FredLyu.github.io/tree/master/基于Unity的A星算法实现-md/A星算法效果.png]

    完整工程仓库地址:A星算法
    个人博客地址:基于Unity的A星算法实现


    参考

    《游戏编程算法与技巧》

    展开全文
  • A星算法的实现(JAVA)

    2012-10-19 20:35:22
    A星寻路算法基本实现,但有进一步优化的空间。
  • 最近有个项目需要用到A星算法,在论坛翻了一下,没啥好用的源码,16年开源的Astart.dll也有点问题 就自己研究了几天这个这个算法,发现实现的原理并不难,借鉴了论坛几位前辈的源码后自己写了一个A星算法,速度也还...
  • 如果角色可以360度走,要怎么使路径平滑呢???? ???????????????????????????????????
  • C++ A星寻路算法

    热门讨论 2011-03-26 18:05:43
    使用C++实现了A星算法,加二叉堆优化,菜鸟新做,高手飘过,仅供新手学习
  • (关于A星算法网上有一个经典的寻路例子的中文翻译,有兴趣可以先原英文翻译和中文翻译现有积木若干,积木可以放在桌子上,也可以放在另一块积木上面。状态表示如下:clear(x):积木x上面没有任何积木。 on(x,y)...

    来自人工智能的实验题实现(block,简单积木机器人问题,给出若干积木状态以及目标状态,为机器人给出动作序列)
    (关于A星算法网上有一个经典的寻路例子的中文翻译,有兴趣可以先原英文翻译中文翻译


    现有积木若干,积木可以放在桌子上,也可以放在另一块积木上面。
    
    状态表示如下:
    
    clear(x):积木x上面没有任何积木。
    onx,y):积木x在积木y上面。
    ontable(x):积木x在桌子上。
    操作表示如下:
    
    move(x,y):把积木x放到积木y上面。前提是积木x和积木y上面都没有其他积木。
    moveToTable(x):把积木x放到桌子上,前提是积木x上面无其他积木,且积木x不在桌子上(即x在其他积木上面)。
    举例如下:
    
    初始状态序列:cleara), ona,b), onb,c), ontablec), cleard), ontabled),
    目标状态序列:cleara), ona,c), ontablec), clearb), ond,b), ontableb),
    操作方案序列:moveToTable(a), moveToTable(b), move(a,c), move(d,b)。
    请使用A*算法来规划此问题。INPUT为初始状态序列和目标状态序列,OUTPUT为操作方案序列。

    对于A星算法,其实就是比我们一般的BFS,DFS通过评价函数来约束,使得我们的搜索更快的接近最优解
    其核心思想就是通过定义评价函数f=g+h(其中g其实可以当作是到达当前状态已经走过的步数或者说是消耗代价,h则是我们定义的一个由当前状态到达目标状态的估值函数,一般该值小于真实值,所以f其实就是整个过程的估值)

    其次就是我们要维护的两个表:openlist和closelist
    openlist其实就是我们从开始状态搜索后续状态是衍生的后继状态加入到其中,然后每次从中取出评价函数值最小的状态进行后续搜索,我比较倾向于用存有状态的优先队列来作为我们的openlist,因为我们可以定义优先队列按评价函数值大小来排序,这样一来每次取得的状态点其实就是评价函数值最小的点。至于closelist为了后面查重需要所以可以用vector或者list


    直接附上我的代码,一口气写下来的,没有考虑空间时间的问题,考虑空间问题其实可以用一维数组存的。
    比如clear(a),on(a,d),on(d,b),ontable(b),ontable(c)就可以用
    [ 3,-1,-1,1]
    [a][b][c][d]
    按a,b,c,d索引为0,1,2,3来设计,a下面是d,指向d的索引3,b下面没有,指向-1,c下面也没有,指向-1,d下面是b,指向b的索引1

    我这里就用二维数组存,a下面有d,则mat[0][3]=1;d下面有b,则mat[3][1]=1;b在桌面上,则mat[1][1]=1;c在桌面上,则mat[2][2]=1;其他为0
    所以如果一个木块a不在桌面上并且其上是clear的,则mat[0~n][0]=0


    #include <iostream>
    #include <cmath>
    #include <string>
    #include <queue>
    #include <list> 
    #include <cstring>
    using namespace std;
    const int num =20; //预定义下规模 
    int mat_begin[num][num]; //初始状态矩阵 
    int mat_end[num][num];  //目标状态矩阵 
    int index1,index2; //状态的语句数,如on(a,b),ontable(b),ontable(c) 为3个  
    int row = -1;//可能积木个数没有num那么多,可以对矩阵操作时候节省时间 ,row=col 
    
    struct operator_string
    {
        string str_operator; //moveToTable 或者 move 
        string str_A; //第一个操作对象 
        string str_B; //第二个操作对象 
    };
    
    struct status
    {
        int g; //==搜索了第几步 
        int h;//估值,与目标的估计距离 
        int mat[num][num];//每一个状态下的矩阵 
        list<operator_string> array_operator;//用来存储操作序列 
        //可移动的对象 
        string not_ontable; //不在桌面上并且上面没有其他积木的木块 
        string ontable; //在桌面上的木块并且上面没有其他积木的木块 
        string sum;
        friend bool operator< (status n1, status n2){
            return n1.g+n1.h > n2.g+n2.h;   //">"为从小到大排列 f=g+h 
        }   
    };
    
    list<status> li;
    string deal_space(string s)  //预处理一下客户输入的字符串,因为可能出现多余空格的问题 
    {
        string temp = s;
        int size = temp.size();
        for( int i = 0; i < size; i ++ ){
            if( temp[i] ==' '){
                for ( int j = i; j < size; j ++ ) temp[j] = temp[j+1];
                i--;
                size--;
            }
            if( temp[i] == ',' && temp[i-1] == ')'){        //将‘)’后面的逗号处理掉 
                for ( int j = i; j < size; j ++ ) temp[j] = temp[j+1];
                i--;
                size--;
            }
         } 
         return temp;
    }
    
    void show_mat(int mat[num][num])//显示矩阵 
    {
        for(int i=0;i<row;i++){
            for(int j=0;j<row;j++){
                cout<<mat[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    bool same_mat(int a[num][num],int b[num][num])//矩阵是否相同 
    {
        int ans = 0;
        for(int i=0;i<row;i++){
            for(int j=0;j<row;j++){
                if(a[i][j]!=b[i][j]){
                    ans = 1;
                    break;
                }
            }
        }
        if(ans == 0) return true;
        else
        return false;
    }
    
    void copy_mat(int a[num][num],int b[num][num])//拷贝矩阵 
    {
        for( int i = 0 ; i < num ; i++ )
            for ( int j = 0; j < num; j ++ ) a[i][j]=b[i][j];
    }
    
    void string_to_mat(string s,int & index,int & row,int  mat[num][num])//将字符串转为状态矩阵 
    {
        int size = s.size();
        int flag1=0,flag2=0;//flag1对应着左括号,flag2对应逗号 
        string temp1="",temp2="",temp3="";  //temp代表on/ontable/clear, temp2代表第一个操作对象,temp3代表第二个对象 
        for( int i = 0; i < size; i++ ){
            if( flag1 == 0 && s[i] != '(' ) temp1 += s[i];
            else if( flag1 == 0 && s[i] == '(' ) flag1 = 1;
            else if( flag2 == 0 && s[i] != ',' && s[i] != ')' ) temp2 += s[i];
            else if( s[i] == ',' ) flag2 = 1;
            else if( flag2 == 1 && s[i] != ')' ) temp3 += s[i];
            else if( s[i] == ')' ){     //一旦遇到有括号,就开始操作 
                flag1 = 0,flag2 = 0;
                if( temp1 == "on" ){
                    row = max(row,temp2[0]-'a');
                    row = max(row,temp3[0]-'a');//row 就是为了找总共有a、b、c、d、e...多少个 
                    mat[ temp2[0] - 'a' ][ temp3[0] - 'a' ] = 1;//设为1 
                }
                else if( temp1 == "ontable" ){
                    row = max(row,temp2[0]-'a');
                    mat[ temp2[0] -'a' ][ temp2[0] - 'a' ] = 1;//设为1 
                }
                else{
                    row = max(row,temp2[0]-'a');//clear,不用操作 
                }
                temp1 = "",temp2 = "",temp3 = "";
                index++;    
            }
            else 
            continue;
        }
        row++;
    }
    
    int count_h(int a[num][num],int b[num][num]) //计算h的估值 方法是从底部网上找相同,相同加一 
    {
        int visit[num][num];
        memset(visit,0,sizeof(visit));
        int ans  = 0;
        for(int i = 0; i < row; i++ ){
            if(a[i][i]==b[i][i]&&a[i][i]==1&&visit[i][i]==0){
                visit[i][i]=1;
                ans++;
                int k = i;
                int flag=1;
                while(flag){//如果flag=0,证明该木块往上已经找不到木块了,终止循环 
                    flag=0;
                    int temp;
                    for(int j=0;j<row;j++){
                        if(a[j][k]==b[j][k]&&a[j][k]==1&&visit[j][k]==0){//该列 
                            flag=1;
                            visit[j][k]=1;
                            ans++;
                            temp = j;
                        }
                    }
                    k=temp;  
                } 
             } 
        }
        return row - ans;
    }
    void strategy(status & current)//计算可以做的下一步操作,将对象加到not_ontable 和ontable两个字符串中,以便后面取得下一步操作策略 
    {
        for( int j = 0 ; j < row ; j ++ ){
            int ans1=0,ans2=0;
            for( int i = 0 ; i < row ; i ++ ){
                if( current.mat[i][j] == 1 ){
                    if( i != j) ans2++;
                    ans1++;
                }   
            }
            if( ans1 == 0 ) current.not_ontable += ( j + 'a');
            else
                if( ans2 == 0) current.ontable += ( j + 'a');
        }
        current.sum = current.not_ontable + current.ontable;
    }
    
    void copy_and_change(status & to,status from,int index)//从上个状态中继承可以继承的数据 
    {
        to.g=from.g+1;
        copy_mat(to.mat,from.mat); 
        list<operator_string>::iterator iter;
        for(iter = from.array_operator.begin();iter!=from.array_operator.end();iter++){
            operator_string temp;
            temp.str_operator=(*iter).str_operator;
            temp.str_A=(*iter).str_A;
            temp.str_B=(*iter).str_B;
            to.array_operator.push_back(temp);
        }
        for (int j = 0 ; j < num ; j++ )  { //将对应的行置0
            if( from.mat[index][j] == 1 ){
                to.mat[index][j] = 0;
            }
        }
    }
    
    void add_move_operator(status & to,int index1,int index2)
    {
        operator_string temp_string;
        temp_string.str_operator="move";
        temp_string.str_A+=( index1 + 'a' );
        temp_string.str_B+=( index2 + 'a' );
        to.array_operator.push_back(temp_string);
        to.mat[index1][index2] = 1;
    }
    status not_ontable_to_table( status current, int index )//将不在桌面的移到桌面 
    {
        status temp;
        int char_index = current.not_ontable[index] - 'a'; 
        copy_and_change(temp,current,char_index);
        temp.mat[char_index][char_index] = 1;
        operator_string temp_string;
        temp_string.str_operator="moveToTable";
        temp_string.str_A+=( char_index + 'a' );
        temp.array_operator.push_back(temp_string);
        temp.h = count_h(temp.mat,mat_end);
        strategy(temp);
    
        return temp;
    }
    status move_between(status current,int index1,int index2)
    {
        status temp;
        int char_index1 = current.sum[index1] - 'a';
        int char_index2 = current.sum[index2] - 'a';
        copy_and_change(temp,current,char_index1);
        add_move_operator(temp,char_index1,char_index2);
        temp.h = count_h(temp.mat,mat_end);
        strategy(temp);
        return temp;
    } 
    
    bool have_same(status a)//在li链表中是否相同的状态矩阵,有的话就是搜索过的 
    {
        list<status>::iterator iter;
        int ans = 0;
        for(iter = li.begin();iter!=li.end();iter++){
            if(same_mat((*iter).mat,a.mat)){
                ans=1;break;
            }
        }
        if(ans == 1) return true;
        else 
        return false;
    }
    
    int main()
    {
        string s1,s2;
        cout<<"请输入初始串:"<<endl;
        getline(cin,s1);
        cout<<"请输入目标串:"<<endl;
        getline(cin,s2);
        cout<<"=============================================block begin==============================================="<<endl; 
        string begin = deal_space(s1);
        string end = deal_space(s2); 
        string_to_mat(begin,index1,row,mat_begin);
        row=0;
        string_to_mat(end,index2,row,mat_end); 
        cout<<"原始状态矩阵:"<<endl;
        show_mat(mat_begin);
        cout<<"目标状态矩阵"<<endl;
        show_mat(mat_end); 
        priority_queue <status> que;    //优先队列存储结点 
        status start;
        start.g=0;
        start.h=count_h(mat_begin,mat_end);
        copy_mat(start.mat,mat_begin);
        strategy(start);
        que.push(start);
        li.push_back(start);
        status p; 
        status pp; //用来记录最后的结果 
        int ans = 0;
        int count=0;//记录访问过多少个走步 
        while( que.size() )
        {
            if(ans == 1)
            break;
            p=que.top();
            que.pop();
            int size1 = p.not_ontable.size();
            for(int i=0;i<size1;i++)//从不再桌面的移到桌面上 
            {
                count++;
                status temp;
                temp=not_ontable_to_table(p,i);
                if ( same_mat(temp.mat,mat_end) ) {
                    pp=temp;
                    ans=1;
                    break;
                }
                if(!have_same(temp)){
                    li.push_back(temp);
                    que.push(temp);
                }
            }
            int size3=p.sum.size();//不再桌面的和在桌面上的总序列 
            for(int i=0;i<size3;i ++ )//之间相互移动 
            {
                if(ans == 1)
                break;
                for(int j = 0;j<size3;j++){
                    count++;
                    if(i!=j){
                        status temp;
                        temp=move_between(p,i,j);
                        if ( same_mat(temp.mat,mat_end) ) {
                            pp=temp;
                            ans=1;
                            break;
                        }
                        if(!have_same(temp)){
                            li.push_back(temp);
                            que.push(temp);
                        }
                    }
                }
            }
        }
        cout<<"count="<<count<<endl;
        cout<<"求得的结果步数 = "<<pp.g<<endl;
        list<operator_string>::iterator iter;
        for(iter = pp.array_operator.begin();iter!=pp.array_operator.end();iter++)
        {
            if((*iter).str_B!="")
            cout<<(*iter).str_operator<<"("<<(*iter).str_A<<","<<(*iter).str_B<<")  ";
            else
            cout<<(*iter).str_operator<<"("<<(*iter).str_A<<")  "; 
        }
        return 0;
     } 

    附上相关的测试样例:

    /*样例输出下:
    ===========================================================================================================================3
    clear(a),on(a,b),ontable(b),ontable(c)
    clear(b),on(b,c),ontable(c),ontable(a)
    原始状态矩阵:
    0 1 0
    0 1 0
    0 0 1
    目标状态矩阵
    1 0 0
    0 0 1
    0 0 1
    count=11
    求得的结果步数 = 2
    moveToTable(a)  move(b,c)
    ===========================================================================================================================4
    clear(a),on(a,b),on(b,c),ontable(c),clear(d),ontable(d)
    clear(a),on(a,c),ontable(c),clear(d),on(d,b),ontable(b)
    原始状态矩阵:
    0 1 0 0
    0 0 1 0
    0 0 1 0
    0 0 0 1
    目标状态矩阵
    0 0 1 0
    0 1 0 0
    0 0 1 0
    0 1 0 0
    count=54
    求得的结果步数 = 4
    moveToTable(a)  moveToTable(b)  move(d,b)  move(a,c)
    ===========================================================================================================================5
    clear(a),on(a,b),on(b,c),ontable(c),clear(d),on(d,e),ontable(e)
    clear(a),on(a,d),on(d,b),ontable(b),clear(e),on(e,c),ontable(c) 
    原始状态矩阵:
    0 1 0 0 0
    0 0 1 0 0
    0 0 1 0 0
    0 0 0 0 1
    0 0 0 0 1
    目标状态矩阵
    0 0 0 1 0
    0 1 0 0 0
    0 0 1 0 0
    0 1 0 0 0
    0 0 1 0 0
    count=91
    求得的结果步数 = 5
    moveToTable(a)  moveToTable(b)  move(d,b)  move(a,d)  move(e,c)
    ===========================================================================================================================6
    clear(a),on(a,b),on(b,c),clear(d),on(d,e),on(e,f),ontable(c),ontable(f)
    clear(f),on(f,a),on(a,c),clear(d),on(d,b),on(b,e),ontable(c),ontable(e) 
    原始状态矩阵:
    0 1 0 0 0 0
    0 0 1 0 0 0
    0 0 1 0 0 0
    0 0 0 0 1 0
    0 0 0 0 0 1
    0 0 0 0 0 1
    目标状态矩阵
    0 0 1 0 0 0
    0 0 0 0 1 0
    0 0 1 0 0 0
    0 1 0 0 0 0
    0 0 0 0 1 0
    1 0 0 0 0 0
    count=382
    求得的结果步数 = 7
    moveToTable(d)  moveToTable(e)  move(a,f)  move(b,e)  move(a,c)  move(d,b)  move(f,a)
    
    ===========================================================================================================================7
    clear(a),on(a,b),on(b,c),clear(d),on(d,e),on(e,f),on(c,g),ontable(f),ontable(g)
    clear(f),on(f,a),on(a,c),clear(d),ontable(g),on(d,b),on(b,e),ontable(c),ontable(e)
    原始状态矩阵:
    0 1 0 0 0 0 0
    0 0 1 0 0 0 0
    0 0 0 0 0 0 1
    0 0 0 0 1 0 0
    0 0 0 0 0 1 0
    0 0 0 0 0 1 0
    0 0 0 0 0 0 1
    目标状态矩阵
    0 0 1 0 0 0 0
    0 0 0 0 1 0 0
    0 0 1 0 0 0 0
    0 1 0 0 0 0 0
    0 0 0 0 1 0 0
    1 0 0 0 0 0 0
    0 0 0 0 0 0 1
    count=597
    求得的结果步数 = 8
    moveToTable(d)  moveToTable(e)  move(a,f)  move(b,e)  moveToTable(c)  move(a,c)  move(f,a)  move(d,b)
    
    ===========================================================================================================================8
    clear(a),on(a,b),on(b,h),on(h,e),ontable(e),clear(g),on(g,f),ontable(f),clear(c),on(c,d),ontable(d)
    clear(d),on(d,e),on(e,g),ontable(g),clear(c),on(c,h),on(h,a),ontable(a),clear(f),on(f,b),ontable(b)
    原始状态矩阵:
    0 1 0 0 0 0 0 0
    0 0 0 0 0 0 0 1
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 0 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 0 0 0 1 0 0
    0 0 0 0 1 0 0 0
    目标状态矩阵
    1 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0
    0 0 0 0 0 0 0 1
    0 0 0 0 1 0 0 0
    0 0 0 0 0 0 1 0
    0 1 0 0 0 0 0 0
    0 0 0 0 0 0 1 0
    1 0 0 0 0 0 0 0
    count=420
    求得的结果步数 = 8
    moveToTable(a)  moveToTable(b)  moveToTable(g)  move(h,a)  move(f,b)  move(e,g)  move(c,h)  move(d,e)
    
    ===========================================================================================================================9
    clear(c),on(c,d),on(d,f),on(f,g),ontable(g),clear(e),on(e,h),on(h,a),ontable(a),clear(i),on(i,b),ontable(b)
    clear(h),on(h,a),on(a,g),on(g,c),ontable(c),clear(b),on(b,d),ontable(d),clear(f),on(f,e),on(e,i),ontable(i) 
    原始状态矩阵:
    1 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0
    0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0
    1 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0
    目标状态矩阵
    0 0 0 0 0 0 1 0 0
    0 0 0 1 0 0 0 0 0
    0 0 1 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0
    0 0 0 0 0 0 0 0 1
    0 0 0 0 1 0 0 0 0
    0 0 1 0 0 0 0 0 0
    1 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 1
    count=1964
    求得的结果步数 = 10
    moveToTable(c)  moveToTable(d)  moveToTable(i)  move(e,i)  move(f,e)  move(g,c)  move(h,d)  move(a,g)  move(h,a)  move(b,d)
    
    ===========================================================================================================================10
    clear(c),on(c,d),on(d,f),on(f,g),ontable(g),clear(e),on(e,h),on(h,a),ontable(a),clear(i),on(i,b),ontable(b),ontable(j)
    clear(a),on(a,h),on(h,j),on(j,g),on(g,c),ontable(c),clear(b),on(b,d),ontable(d),clear(f),on(f,e),on(e,i),ontable(i) 
    原始状态矩阵:
    1 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 1 0 0 0
    1 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 1
    目标状态矩阵
    0 0 0 0 0 0 0 1 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 1 0
    0 0 0 0 1 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 1
    0 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 1 0 0 0
    count=651
    求得的结果步数 = 10
    moveToTable(c)  moveToTable(d)  moveToTable(i)  move(e,i)  move(b,d)  move(f,e)  move(g,c)  move(j,g)  move(h,j)  move(a,h)
    ===========================================================================================================================10
    clear(c),on(c,d),on(d,f),on(f,g),ontable(g),clear(e),on(e,h),on(h,a),ontable(a),clear(j),on(j,i),on(i,b),ontable(b)
    clear(a),on(a,h),on(h,j),on(j,g),on(g,c),ontable(c),clear(b),on(b,d),ontable(d),clear(f),on(f,e),on(e,i),ontable(i)
    原始状态矩阵:
    1 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 1 0 0 0
    1 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 1 0
    目标状态矩阵
    0 0 0 0 0 0 0 1 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 1 0
    0 0 0 0 1 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 1
    0 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 1 0 0 0 
    count=1429
    求得的结果步数 = 11
    moveToTable(c)  moveToTable(d)  moveToTable(j)  moveToTable(i)  move(e,i)  move(f,e)  move(b,d)  move(g,c)  move(j,g)  move(h,j)  move(a,h)
    ===========================================================================================================================11
    clear(k),on(k,c),on(c,d),on(d,f),on(f,g),ontable(g),clear(e),on(e,h),on(h,a),ontable(a),clear(j),on(j,i),on(i,b),ontable(b)
    clear(a),on(a,h),on(h,k),on(k,j),on(j,g),on(g,c),ontable(c),clear(d),on(d,b),ontable(b),clear(f),on(f,e),on(e,i),ontable(i)
    原始状态矩阵:
    1 0 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0 0
    0 0 0 0 0 1 0 0 0 0 0
    0 0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 1 0 0 0 0
    1 0 0 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 1 0 0
    0 0 1 0 0 0 0 0 0 0 0
    目标状态矩阵
    0 0 0 0 0 0 0 1 0 0 0
    0 1 0 0 0 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 1 0 0
    0 0 0 0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 1
    0 0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 0 0
    0 0 0 0 0 0 0 0 0 1 0
    count=3355
    求得的结果步数 = 12
    moveToTable(k)  moveToTable(c)  move(j,k)  moveToTable(i)  move(d,b)  move(e,i)  move(f,e)  move(g,c)  move(j,g)  move(k,j)  move(h,k)  move(a,h)
    */
    展开全文
  • python的搜索算法,例如深度优先算法,A星算法,其中的h函数可以优化,原文件只采用了欧氏距离。
  • A星算法(基于matlab)

    千次阅读 2019-04-10 17:30:29
    A星算法属于图这种数据结构的搜索算法,对比于树的遍历搜索,需要考虑到的问题是:同一个节点的重复访问,所以需要对于已经访问过的节点进行标记。 曼哈顿距离: 在几何度量空间中,用以标明两个点在标准坐标系上...
  • A*算法(A星算法)DFS BFS

    千次阅读 2012-02-11 15:19:55
    BFS算法过程: 1.取出队列首元素作为当前节点,检查是否为目的地。 2.对当前点进行展开,检查是否与队列重复,依次进入队列。 3.当队首指针与队尾指针重合时,表示所有路径已经探索完毕。 优点:获得最短路径...
  • A星算法-自动寻路-c++

    万次阅读 2010-06-26 17:46:00
    A星算法小DEMO
  • A星寻路算法的Lua实现

    千次阅读 2016-03-06 19:48:05
    A*搜寻算法俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。这里有一篇文章,很适合新手学习 莫水千流:A星寻路算法介绍 。对A星算法的理解还是要从公式 F = G + H开始:在节点化的...
  • A* A星 算法 C语言 实现代码

    千次阅读 2016-12-12 17:25:44
    关于A*算法,很早就想写点什么,可是貌似天天在忙活着什么,可事实又没有做什么,真是浮躁啊!所以今晚还是来写一下总结吧!  A*算法是很经典的只能启发式搜索算法,关于只能搜索算法和一般的搜索算法(例如DFS,...
  • A star算法优化

    千次阅读 2018-03-18 22:36:39
    本文目的是对A*寻路算法所生成的路径进行一些人性化的调整,使其看起来不至于太机械化。关于A*算法的原理与实现,读者可以阅读其他资料,这里不再详细阐述。如何写估价函数 A*寻路算法本质上是一个有方向性的广度...
  • 纯lua版A*算法优化测试

    千次阅读 2015-06-11 14:44:15
    纯lua版A*算法优化测试写了个A*算法的lua版本,也参考了不少网上资料还有开源的代码,关于写这个的原因,只是在做一个rts的寻路,写了个lua版本也是图省事,想尽快看效果。出于程序员的好奇和执着,修改了好几个版本...
  • AStar算法优化

    2020-01-12 15:06:12
    A星算法也有很多弊端,就比如如果目的地不能到达 他还是会遍历寻路(可以寻路的时候判断 也可以算的上优化) 其次,如果地图过大,计算起来会很消耗时间,所以可以在计算上进行优化 下面说一下优化的一些可行的方法 一....
  • A*走路 自动寻路A*算法 易语言源码优化A*走路 自动寻路A*算法 易语言源码优化A*走路 自动寻路A*算法 易语言源码优化
  • 路径规划: a star, A星算法详解

    千次阅读 2018-02-26 18:09:01
    如此好贴,不能不转!...如果侵害到您的权益,请联系我,我将删除...Amit's A star Page中译文 译序这篇文章很适合A*算法的初学者,可惜网上没找到翻译版的。本着好东西不敢独享的想法,也为了锻炼一下英文,本人译了...
  • A星和B寻路算法

    热门讨论 2013-03-29 14:17:14
    用XNA4.0平台上写得A*和B*算法,其中B*算法有BUG的!由于时间关系没修复,但解决一般简单的路径是没问题的。只提供参考了解B*算法用。具体思路解释看代码注释。(ctrl + a进行A星算法,ctrl + b进行B星算法)
  • A*寻路算法优化方法

    2019-11-25 13:31:37
    角色或者怪物寻路,并不需要找最短的那条路径,在性能允许的情况下,找一条次优或者其它的路径也可以,这样可能更适合游戏,所以,我们需要根据游戏的特点,去优化寻路算法优化A*的寻路,我能想到的...
  • cocos2dx之A星算法

    千次阅读 2014-01-13 23:30:14
    研究了几个小时,看了网上的一些资料,感觉都写得不好,可能是我太笨了,我现在来讲解一下在cocos2dx如何利用A*算法自动寻找目标。 我是根据上下左右来进行搜索的,通过不停地去比较F值来取得取得最小代价得到路径:...
  • 简介 基于【漫画算法-小灰的...没有做太多的性能优化,算是深化对A星寻路算法的理解。 界面预览: 初始化: 寻路: 后退: 提示: 完成: 刷新地图: 下载地址: 项目地址: https://github.com/milovetingting/Maze ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,093
精华内容 6,037
关键字:

a星算法优化